Bounded rationality and correlated equilibria

We study an interactive framework that explicitly allows for nonrational behavior. We do not place any restrictions on how players’ behavior deviates from rationality, but rather, on players’ higher-order beliefs about the frequency of such deviations. We assume that there exists a probability p such that all players believe, with at least probability p, that their opponents play rationally. This, together with the assumption of a common prior, leads to what we call the set of p-rational outcomes, which we define and characterize for arbitrary probability p. We then show that this set varies continuously in p and converges to the set of correlated equilibria as p approaches 1, thus establishing robustness of the correlated equilibrium concept to relaxing rationality and common knowledge of rationality. The p-rational outcomes are easy to compute, also for games of incomplete information. Importantly, they can be applied to observed frequencies of play for arbitrary normal-form games to derive a measure of rationality \(\overline{p}\) that bounds from below the probability with which any given player chooses actions consistent with payoff maximization and common knowledge of payoff maximization.     

On the geometry of Nash equilibria and correlated equilibria

It is well known that the set of correlated equilibrium distributions of an n-player noncooperative game is a convex polytope that includes all the Nash equilibrium distributions. We demonstrate an elementary yet surprising result: the Nash equilibria all lie on the boundary of the polytope.We are grateful to Francoise Forges, Dan Arce, the editors, and several anonymous referees for helpful comments. This research was supported by the National Science Foundation under grant 98–09225 and by the Fuqua School of Business.The use of correlated mixed strategies in 2-player games was discussed by Raiffa (1951), who noted: it is a useful concept since it serves to convexify certain regions [of expected payoffs] in the Euclidean plane. (p. 8)Received: April 2002 / Revised: November 2003     

On weakly correlated and correlated equilibria in discontinuous games

This paper treats of non-zero-sum discontinuous games with compact Hausdorff strategy spaces. It is assumed that the payoff function of each player in the game is bounded, Borel measurable and is upper semicontinuous on his strategy space, for all fixed actions of the remaining players. It is shown that for each ε>0, such games possess weakly correlated ε-epuilibria introduced by Moulin and Vial as extension of correlated equilibria in the sense of Aumann. An upper semicontinuous came having weakly correlated equilibria and no correlated equilibria is discussed in details.     

General procedures leading to correlated equilibria

Hart and Mas-Colell [2000] show that if all players play regret-matching strategies, i.e., they play with probabilities proportional to the regrets, then the empirical distribution of play converges to the set of correlated equilibria, and the regrets of every player converge to zero. Here we show that if only one player, say player i, plays with these probabilities, while the other players are not too sophisticated, then the result that player is regrets converge to zero continues to hold. The condition of not too sophisticated essentially says that the effect of one change of action of player i on the future actions of the other players decreases to zero as the horizon goes to infinity. Furthermore, we generalize all these results to a whole class of regret-based strategies introduced in Hart and Mas-Colell [2001]. In particular, these simplify the conditional smooth fictitious play of Fudenberg and Levine [1999].Received: May 2004This is a revision of the authors M.Sc. thesis, May 2000.The author thanks Professor Sergiu Hart for his help and guidance, and the Associate Editor and an anonymous referee for their comments. I am grateful to my parents and wife for everything.     

Characterization of correlated equilibria in stochastic games

A general communication device is a device that at every stage of the game receives a private message from each player, and in return sends a private signal to each player; the signals the device sends depend on past play, past signals it sent, and past messages it received.  An autonomous correlation device is a general communication device where signals depend only on past signals the device sent, but not on past play or past messages it received.  We show that the set of all equilibrium payoffs in extended games that include a general communication device coincides with the set of all equilibrium payoffs in extended games that include an autonomous correlation device. A stronger result is obtained when the punishment level is independent of the history. Final version July 2001     

Coarse correlated equilibria in linear duopoly games

For duopoly models, we analyse the concept of coarse correlated equilibrium using simple symmetric devices that the players choose to commit to in equilibrium. In a linear duopoly game, we prove that Nash-centric devices, involving a sunspot structure, are simple symmetric coarse correlated equilibria. Any small unilateral perturbation from such a structure fails to be an equilibrium.     

Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity

We provide motivations for the correlated equilibrium solution concept from the game-theoretic and optimization perspectives. We then propose an algorithm that computes ${\varepsilon}$ -correlated equilibria with global-optimal (i.e., maximum) expected social welfare for normal form polynomial games. We derive an infinite dimensional formulation of ${\varepsilon}$ -correlated equilibria using Kantorovich polynomials, and re-express it as a polynomial positivity constraint. We exploit polynomial sparsity to achieve a leaner problem formulation involving sum-of-squares constraints. By solving a sequence of semidefinite programming relaxations of the problem, our algorithm converges to a global-optimal ${\varepsilon}$ -correlated equilibrium. The paper ends with two numerical examples involving a two-player polynomial game, and a wireless game with two mutually-interfering communication links.     

Structure of extreme correlated equilibria: a zero-sum example and its implications

We exhibit the rich structure of the set of correlated equilibria by analyzing the simplest of polynomial games: the mixed extension of matching pennies. We show that while the correlated equilibrium set is convex and compact, the structure of its extreme points can be quite complicated. In finite games the ratio of extreme correlated to extreme Nash equilibria can be greater than exponential in the size of the strategy spaces. In polynomial games there can exist extreme correlated equilibria which are not finitely supported; we construct a large family of examples using techniques from ergodic theory. We show that in general the set of correlated equilibrium distributions of a polynomial game cannot be described by conditions on finitely many moments (means, covariances, etc.), in marked contrast to the set of Nash equilibria which is always expressible in terms of finitely many moments.     

Generating Acceptable Shift-Working Schedules

When a factory operates a shift system of working, the work patterns are usually laid down at the start and adhered to for long periods. In this case study, small out-stations with frequent changes in manning require the frequent generation of new schedules. Producing and agreeing such schedules with the workforce can be a fraught and time-consuming task. Hence a computer routine was devised which takes over the generation. An interesting feature is that several feasible routines are generated, allowing the final decision to be taken by the workforce itself.     

Evaluation of Acceptable Risk

Fundamental to the use of risk analysis is the concept of ‘acceptable risk’. This paper examines the different methods of determining a value for acceptable risk. It concludes that the comparison of risk versus change in life expectancy is the only method that has consistent units and satisfies the Pareto criterion.     

Acceptable Numerations of Morphisms and Myhill-Shepherdson Property

Myhill-Shepherdson property in recursive function theory states that extensional effective program transformations determine continuous operations on partial functions. Case showed that this property fails to characterize acceptability of numberings of partial recursive functions. In this note we present a higher type analogue to Myhill-Shepherdson property. Our purpose is to show that higher type Myhill-Shepherdson property characterizes weak acceptability under a natural condition.     

The Handling of Acceptable Risks

This paper examines some of the problems associated with the handling of risk and, in particular, the arguments that may be deployed in favour of reducing particular forms of risk. The paper suggests that, whilst risk can always be reduced, the costs involved vary enormously in terms of benefits achieved. Governments should be concerned to maximize overall risk reduction for any given level of expenditure. To treat each risk separately and independently can lead to a non-optimal allocation of resources.     

Stationary points and equilibria

Almost all existence results in mathematical economics and game theory rely on some type of fixed point theorem. However, in many cases it is much easier to apply an equivalent stationary point theorem. In this survey paper we show for various general equilibrium and game-theoretical models the usefulness of the stationary point approach to prove existence of equilibrium. We also consider path following methods to find a stationary point and illustrate such methods by an example. Finally, we discuss some refinements of stationary points and their application to solve the problem of equilibrium selection.     

Inequalities and Nash equilibria

This paper concentrates on the problem of the existence of equilibrium points for non-cooperative generalized N-person games, N-person games of normal form and their related inequalities. We utilize the K-K-M lemma to obtain a theorem and then use it to obtain a new Fan-type inequality and minimax theorems. Various new equilibrium point theorems are derived, with the necessary and sufficient conditions and with strategy spaces with no fixed point property. Examples are given to demonstrate that these existence theorems cover areas where other existence theorems break down.     

Pareto optimality and Walrasian equilibria

The paper concerns the study of a class of convex, constrained multiobjective optimization problems from the viewpoint of the existence issues. The main feature of the presented approach is that the classical qualification condition requiring the existence of interior points in the effective domains of functions under consideration does not hold. A variant of duality theory for multiobjective optimization problems based on the Fenchel theorem is formulated. Next, by using very recent results on the Walrasian general equilibrium model of economy obtained in Naniewicz [Z. Naniewicz, Pseudo-monotonicity and economic equilibrium problem in reflexive Banach space, Math. Oper. Res. 32 (2007) 436-466] the conditions ensuring the existence of Pareto optimal solutions for the class of multiobjective optimization problems are established. The concept of the proper efficiency is used as the solution notion. Finally, a new version of the second fundamental theorem of welfare economics is presented.     

Conflict individual-Pareto equilibria

We suggest a rather universal notion of equilibrium that has the properties of a conflict equilibrium and the Pareto optimality and contains, as special cases, numerous known notions of efficiency and equilibrium. Its various strengthenings are also considered.     

Acceptable optimality in linear fractional programming with fuzzy coefficients

Based on the specified grades of satisfaction, we propose two new concepts of (α, β)-acceptable optimal solution and (α, β)-acceptable optimal value of a fuzzy linear fractional programming problem with fuzzy coefficients, and develop a method to compute them. An example is provided to demonstrate the method.     

Exchange price equilibria and variational inequalities

The aim of this paper is to show the relevance of the concept and the theory of variational inequalities in the study of economic equilibria.Supported by the National Science Foundation grant DMS-8601778.     

Uncoupled automata and pure Nash equilibria

We study the problem of reaching a pure Nash equilibrium in multi-person games that are repeatedly played, under the assumption of uncoupledness: EVERY player knows only his own payoff function. We consider strategies that can be implemented by finite-state automata, and characterize the minimal number of states needed in order to guarantee that a pure Nash equilibrium is reached in every game where such an equilibrium exists.