A large class of sequential decision making problems under uncertainty with multiple competing decision makers/agents can be modeled as stochastic games. Stochastic games having Markov properties are called Markov games or competitive Markov decision processes. This dissertation presents an approach to solve non cooperative stochastic games, in which each decision maker makes her/his own decision independently and each has an individual payoff function. In stochastic games, the environment is nonstationary and each agent's payoff is affected by joint decisions of all agents, which results in the conflict of interest among the decision makers. In this research, the theory of Markov decision processes (MDPs) is combined with the game theory to analyze the structure of Nash equilibrium for stochastic games. In particular, the Laurent series expansion technique is used to extend the results of discounted reward stochastic games to average reward stochastic games. As a result, auxiliary matrix games are developed that have equivalent equilibrium points and values to a class of stochastic games that are irreducible and have average reward performance metric. R-learning is a well known machine learning algorithm that deals with average reward MDPs. The R-learning algorithm is extended to develop a Nash-R reinforcement learning algorithm for obtaining the equivalent auxiliary matrices. A convergence analysis of the Nash-R algorithm is developed from the study of the asymptotic behavior of its two time scale stochastic approximation scheme, and the stability of the associated ordinary differential equations (ODEs). The Nash-R learning algorithm is tested and then benchmarked with MDP based learning methods using a well known grid game. Subsequently, a real life application of stochastic games in deregulated power market is explored. According to the current literature, Cournot, Bertrand, and Supply Function Equilibrium (SFEs) are the three primary equilibrium models that are used to evaluate the power market designs. SFE is more realistic for pool type power markets. However, for a complicated power system, the convex assumption for optimization problems is violated in most cases, which makes the problems more difficult to solve. The SFE concept in adopted in this research, and the generators' behaviors are modeled as a stochastic game instead of one shot game. The power market is considered to have features such as multi-settlement (bilateral, day-ahead market, spot markets and transmission congestion contracts), and demand elasticity. Such a market consisting of multiple competing suppliers (generators) is modeled as a competitive Markov decision processes and is studied using the Nash-R algorithm.

A simple stochastic game (SSG) is a game defined on a directed multigraph and played between players MAX and MIN. Both players have control over disjoint subsets of vertices: player MAX controls a subset VMAX and player MIN controls a subset VMIN of vertices. The remaining vertices fall into either VAVE, a subset of vertices that support stochastic transitions, or SINK, a subset of vertices that have zero outdegree and are associated with a payoff in the range [0, 1]. The game starts by placing a token on a designated start vertex. The token is moved from its current vertex position to a neighboring one according to certain rules. A fixed strategy σ of player MAX determines where to place the token when the token is at a vertex of VMAX. Likewise, a strategy τ of player MIN determines where to place the token when the token is at a vertex of VMIN. When the token is at a vertex of VAVE, the token is moved to a uniformly at random chosen neighbor. The game stops when the token arrives on a SINK vertex; at this point, player MAX gets the payoff associated with the SINK vertex. A fundamental question related to SSGs is the SSG value problem: Given a SSG G, is there a strategy of player MAX that gives him an expected payoff at least 1/2 regardless of the strategy of player MIN? This problem is among the rare natural combinatorial problems that belong to the class NP ∩ coNP but for which there is no known polynomial-time algorithm. In this thesis, we survey known algorithms for the SSG value problem and characterize them into four groups of algorithms: iterative approximation, strategy improvement, mathematical programming, and randomized algorithms. We obtain two new algorithmic results: Our first result is an improved worst-case, upper bound on the number of iterations required by the Homan-Karp strategy improvement algorithm. Our second result is a randomized Las Vegas strategy improvement algorithm whose expected running time is O(20:78n).

Doctor of Philosophy (PhD) / This thesis examines the growing debate around the concept of social capital. The concept has been heralded by many as a means of uniting the social sciences, particularly economics and sociology, and of overcoming ideological divisions between left and right. However, critics argue that the concept is poorly theorised and provides little insight. More radical critics have claimed the concept may be a neo-liberal ‘Trojan horse’, a mechanism by which the atomistic thinking of neoclassical economics colonises social theory. I examine these more radical claims by exploring the origins of the concept of social capital within rational choice economics. I argue that we should differentiate between two types of potential colonisation. The first is a form of methodological colonisation, whereby overly abstract, reductionist and rationalist approaches (which I term modernist) are extended into social theory. The second is a form of ideological colonisation, whereby a normative commitment to individualism and the market is extended into social theory. I argue that the concept of social capital has been the product of a trend within rational choice economics away from the extremes of modernism. In this sense the concept represents an attempt to bring economics and social theory closer together, and a willingness on the part of rational choice theorists to take more seriously the techniques and insights of the other social sciences. However, I argue that this trend away from modernism has often been associated with a reaffirmation of rational choice theorists’ normative commitment to individualism and the market. In particular, I argue the concept of social capital has been strongly influenced by elements of the Austrian economic tradition, and forms part of a spontaneous order explanation of economic and social systems. I then apply these insights to the Australian social capital debate. I argue that initially the Australian social capital debate continued an earlier debate over economic rationalism and the merits of market-orientated economic reform. I argue that participants from both sides of the economic rationalism debate used the concept of social capital to move away from modernism, but continued to disagree over the role of individualism. Finally, I argue that confusion between moving away from modernism, and moving away from market ideology, has led some Third Way theorists to misconstrue the concept as a means to overcome ideology.

The rapid growth in demand due to the emergence of mobile communication services with variable rates, coupled with the resource scarcity of mobile air interface, has encouraged researchers to find technological solutions to increase spectral efficiency in order to support different levels of Quality of Service (QoS). Radio resource management (RRM) plays a major role in QoS provisioning and congestion control for wireless networks. The main problem with the congestion control mechanisms provided by current RRM schemes is that they are mostly reactive, triggered only when congestion occurs. The common, traditional solution to congestion has been for system planners to over-engineer a network by assigning more resources than are necessary. This approach is very costly because busy periods are usually brief, causing the network to be often under-utilised outside of these periods. Current static, usage-based pricing models also fail to assist in traffic shaping to even out loads. Economic modelling offers a new perspective into current RRM schemes and enables efficient utilisation of scarce resources and congestion prevention based on concepts such as utility, price, Pareto optimality and game theory. Dynamic pricing has been proposed as a mechanism to encourage users to adapt their resource consumption level according to network conditions. A good pricing model can provide the necessary positive incentives to increase users’ arrival rate when the network load is relatively low and negative incentives for users to defer their usage when the load is relatively high. In this dissertation, we propose an economic framework for pricing and RRM for 3G and beyond systems. Our aim is two-fold: to calculate an optimal integrated dynamic pricing and RRM policy; and to allocate scarce network resources in a fair and Pareto-optimal manner. The optimal integrated dynamic pricing and RRM policy is computed based on the stochastic distribution of users’ budget, arrivals, handoffs and departures. Our results show that the integrated policy is superior in terms of average reward improvement and congestion prevention to current schemes that use static pricing models. In interferencebased networks such as WCDMA, we suggest users be charged according to their noise rise factor, i.e. an estimate of the amount of interference generated by the call. This interference-based pricing model improves on the conventional load-based model in by delivering higher revenue and lower call blocking and handoff probabilities. Using the axiomatic bargaining concepts from cooperative game theory, we derive a class of fair and Pareto-optimal bargaining solutions that allocate wireless resources based on users’ minimum and maximum rate requirements. We propose two models: symmetric and asymmetric. In the latter, resource is allocated according to the price paid by the users. An important significance of the asymmetric bargaining model is that this solution is still Pareto-optimal and fair according to the users’ bargaining power. Our approach is also a departure from current works using noncooperative game theory that can only achieve an inefficient outcome, i.e. the Nash equilibrium; or cooperative game theory that focus on only one solution on the Pareto-optimal boundary. By analysing a range of bargaining solutions instead of specific ones, operators can proceed to select the best outcome out of these Pareto-optimal solutions based on criteria like revenue. / Thesis (Ph.D) -- University of Adelaide, School of Electrical and Electronic Engineering, 2007

<p>Whist is one of the most played card games of the world. Though there have been many studies made in the field of game theory, whist is still somewhat of an unchartered territory. In this thesis some methods to obtain an optimal strategy for whist are discussed. </p><p>Whist belongs to a group of games called logical games. For this group there exists algorithms which result in an optimal strategy. Two algorithms where examined. The minmax algorithm and the alphbeta algorithm. these algorithms could be adapted to whist </p><p>It is possible that there are methods that use the properties of the cards better the the former algorithms to get an optimal result. A few such methods will also be discussed. </p><p>The practical result of the theoretical investigation was a game where the adapted algorithms were implemented. </p>

<p>According to the Leniency programme that was implemented in Sweden in 2002, a company participating in a cartel can escape administrative fines if it exposes the cartel to the Swedish Competition Authority and cooperates with the Authority during its investigation. Whether cartels should be criminalized, or not, has been debated in the Swedish Parliament in recent years. If cartels are turned into a felony, the leaders of the companies involved risk being held personally responsible.</p><p>This essay discusses how the incitements for unveiling cartels take form, drawing on game-theoretical models. The essay, in addition, analyses how the incitement-structure would change if cartels would become a felony, compared to the current legislation, in the form of the Leniency programme.</p><p>The conclusions that the author arrives at are that the incitements to expose cartels would increase if fines were to increase. The incitements would furthermore increase if the company feared that someone within the organization could expose the cartel to the Competition Authority. Turning cartels into a felony would on the contrary decrease the incitements for unveiling the cartel. The key task for the Competition Authority, as regards to cartels, should hence be to create uncertainty for firms participating in cartels and increase the security of employees if and when exposing their employer as a participant in a cartel.</p> / <p>År 2002 skrevs Leniencyprogrammen in i svensk konkurrenslagstiftning. Ett företag som ingår i ett kartellsamarbete kan i enlighet med programmen undslippa konkurrensskadeavgift ifall företaget avslöjar kartellen och samarbetar med konkurrensverket. Under senare år har en debatt kring huruvida karteller bör kriminaliseras eller inte förts i Riksdagen. En kriminalisering skulle innebära personligt straffansvar för bland annat företagsledare.</p><p>Uppsatsens syfte är att med spelteoretiska modeller och resonemang kartlägga och analysera hur incitamentsstrukturen för avslöjandet av karteller kan tänkas se ut. Vidare syftar uppsatsen till att föra en diskussion kring hur incitamentsstrukturen kan tänkas förändras om nuvarande lagstiftning ändras till att medföra en kriminalisering av karteller.</p><p>Slutsatser som kan dras av uppsatsens analys är att incitamenten för avslöjande med nuvarande lagstiftning skulle öka om konkurrensskadeavgifterna höjs. En kriminalisering skulle minska incitamenten för avslöjande, jämfört med nuvarande lagstiftning. Incitamenten för företagen att avslöja karteller ökar om företagen befarar att någon inom organisationen har för avsikt att avslöja kartellen till konkurrensverket. Konkurrensverkets viktigaste uppgift vad gäller kartellbekämpning torde därmed bli att skapa osäkerheter för företagen på flera områden för att öka misstron mellan aktörerna samt att arbeta för att öka anställdas incitament att avslöja sin arbetsgivares inblandning i kartellsamarbeten.</p>

Future wireless communications expect to experience a spectrum shortage problem. One practical solution is spectrum sharing. This thesis studies precoding strategies to allocate communication resources for spectrum sharing in multi-user wireless systems from a game-theoretic perspective. The approaches for the precoding games are developed under different constraints. It is shown that the precoding game with spectral mask constraints can be formulated as a convex optimization problem and a dual decomposition based algorithm can be exploited to solve it. However, the problem is non-convex if users also have total power constraints. This study shows that an efficient sub-optimal solution can be derived by allocating the bottleneck resource in the system. The sub-optimal solution is proved to be efficient and can even achieve an identical performance to that of the optimal solution in certain cases, but with significantly reduced complexity. / Communications

This paper studies the problem of multi-period pricing for perishable products in a competitive (oligopolistic) market. We study non cooperative Nash equilibrium policies for sellers. At the beginning of the time horizon, the total inventories are given and additional production is not an available option. The analysis for periodic production-review models, where production decisions can be made at the end of each period at some production cost after incurring holding or backorder costs, does not extend to this model. Using results from game theory and variational inequalities we study the existence and uniqueness of equilibrium policies. We also study convergence results for an algorithm that computes the equilibrium policies. The model in this paper can be used in a number of application areas including the airline, service and retail industries. We illustrate our results through some numerical examples. / Singapore-MIT Alliance (SMA)

Thesis (Ph. D.)--Ohio State University, 2006. / Title from first page of PDF file. Includes bibliographical references (p. 135-140).

Thesis (M.A.)--Ohio University, June, 2005. / Title from PDF t.p. Includes bibliographical references (p. 132-140)