A note on the core of an income redistribution game

We consider a redistribution of income by an n-person game in which each member is levied a proportional income tax under some fixed rule. It is shown that the redistribution that will be achieved by a specific negative income tax is in the core of the game, which means that the redistribution can not be upset by any coalition of members acting strategically to evade the full taxation.     

The Nash bargaining solution in general n-person cooperative games

We present a noncooperative foundation for the Nash bargaining solution for an n-person cooperative game in strategic form. The Nash bargaining solution should be immune to any coalitional deviations. Our noncooperative approach yields a new core concept, called the Nash core, for a cooperative game based on a consistency principle. We prove that the Nash bargaining solution can be supported (in every subgame) by a stationary subgame perfect equilibrium of the bargaining game if and only if the Nash bargaining solution belongs to the Nash core.     

The supercore for normal-form games

This paper analyzes the supercore of a system derived from a normal-form game. For the case of a finite game with pure strategies, we define a sequence of games and show that the supercore coincides with the set of Nash equilibria of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a normal-form game, we show that the set of Nash equilibrium profiles coincides with the supercore for games with a finite number of Nash equilibria.     

An admissible set occurring in various bargaining situations

Given a set of alternatives S and a binary relation M on S the admissible set of the pair (S, M) is defined to be the set of maximal elements with respect to the transitive closure of M. It is shown that existing solutions in game theory and mathematical economics are special cases of this concept (they are admissible sets of a natural S and M). These include the core of an n-person cooperative game, Nash equilibria of a noncooperative game, and the max-min solution of a two-person zero sum game. The competitive equilibrium prices of a finite exchange economy are always contained in its admissible set. Special general properties of the admissible set are discussed. These include existence, stability, and a stochastic dynamic process which leads to outcomes in the admissible set with high probability.     

Monotone Games with Positive Spillovers

A monotone game comprises the infinitely repeated play of an n-person stage game, subject to the constraint that players' actions be monotonically nondecreasing over time. These games represent a variety of strategic situations in which players are able to make (partial) commitments. If the stage games have positive spillovers and satisfy certain other conditions, then the limit points of the subgame perfect equilibria are precisely the approachable action profiles. This characterization is applied to voluntary contribution games, market games, and coordination games. Journal of Economic Literature Classification Number: C7.     

A Note on the Probability of k Pure Nash Equilibria in Matrix Games

A formula is derived for the probability that a "randomly selected" n-person matrix game has exactly k pure strategy equilibria. It is shown that for all n ≥ 2, this probability converges to e⁻¹/k! as the sizes of the strategy sets of at least two players increase without bound. Thus the number of pure strategy equilibria in large random n-person matrix games is approximately Poisson distributed with mean one. The latter is a known result obtained by a new proof in this note. Journal of Economic Literature Classification Number: C72.     

Better-reply dynamics and global convergence to Nash equilibrium in aggregative games

We consider n-person games with quasi-concave payoffs that depend on a player's own action and the sum of all players' actions. We show that a discrete-time, stochastic process in which players move towards better replies—the better-reply dynamics—converges globally to a Nash equilibrium if actions are either strategic substitutes or strategic complements for all players around each Nash equilibrium that is asymptotically stable under a deterministic, adjusted best-reply dynamics. We present an example of a 2-person game with a unique equilibrium where the derivatives of the best-reply functions have different signs and the better-reply dynamics does not converge.     

Risk sensitivity in bargaining with more than two participants

In two-person bargaining over riskless outcomes where the outcome is chosen according to the Nash solution or the Kalai-Smorodinsky solution, an increase in a player's risk aversion is to the advantage of the opponent. It is shown in this note that for the n-person Nash solution, an increase in risk aversion is to the player's own disadvantage but needs not be advantageous to all the opponents. For the n-person Kalai-Smorodinsky solution, the increase is to the player's own disadvantage and to the advantage of all the opponents.     

Undecidability of the existence of pure Nash equilibria

Summary. The purpose of this paper is to show that for any positive integer n, there exists no algorithm which decides for each non-cooperative n-person game in strategic form with partially computable payoff functions whether it has a pure Nash equilibrium or not.Received: 20 March 2002, Revised: 23 April 2003, JEL Classification Numbers: C72.The author thanks the Referee and the Associate Editor for offering critical comments on this paper, which is dedicated to his brother Konstantinos Efstathiou Sofronidis.     

Two characterizations of the Raiffa solution

It is shown when and how the two-person bargaining solution proposed by Raiffa can be generalized to the n-person case. Two characterizations are proposed involving the familiar axioms of Pareto-optimality, Symmetry, and Invariance, as well as two new Monotonicity axioms.     

Characterization of the private alternatives domains admitting arrow social welfare functions

An n-person social choice problem is considered in which the alternatives are n dimensional vectors with the ith component of such a vector being the part of the alternative effecting individual i alone. Assuming that individuals are selfish (i is indifferent between any two alternatives that have the same ith component) we characterize all the families of permissible individual preferences that admit nondictatorial Arrow-type social welfare functions. We also show that the existence of such a function for a given family of preferences is independent of n provided that is greater than one.     

The multilinear extension and the coalition structure value

The multilinear extension has been shown to be an effective tool for computing the Shapley value of an n-person game. We modify here the method for the multilinear extension to calculate the modified coalition structure value (CS-value) for such games.     

Homotopy methods to compute equilibria in game theory

This paper presents a survey of the use of homotopy methods in game theory. Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by various selection theories. We present the relevant techniques underlying homotopy algorithms. We give detailed expositions of the Lemke–Howson algorithm and the van den Elzen–Talman algorithm to compute Nash equilibria in 2-person games, and the Herings–van den Elzen, Herings–Peeters, and McKelvey–Palfrey algorithms to compute Nash equilibria in general n-person games. We explain how the main ideas can be extended to compute equilibria in extensive form and dynamic games, and how homotopies can be used to compute all Nash equilibria.     

Passing the Buck On the acceptance of responsibility

In the Passing the Buck game, the n members of a group decide in a given order whether or not to incur costs so that they can fix a certain problem for the benefit of the group. Passing the Buck means that one relies on the service of a successor. The decision is influenced by social preferences and by strategic considerations. We derive three main conclusions from experiments with n=3 and n=4. (i) The unique perfect Baysian equilibrium of the Passing the Buck game with incomplete information about the preferences of other players generally fits the data, however with two interesting exceptions. (ii) Backward induction breaks down if it requires more than two steps, i.e., for the first player in the game with n=4. (iii) Making one of the members of the group an “expert” who alone is competent to fix the problem is connected with a change of social preferences.     

Competitive outcomes and the inner core of NTU market games

We consider the inner core as a solution concept for cooperative games with non-transferable utility (NTU) and its relationship to payoffs of competitive equilibria of markets that are induced by NTU games. An NTU game is an NTU market game if there exists a market such that the set of utility allocations a coalition can achieve in the market coincides with the set of utility allocations the coalition can achieve in the game. In this paper, we introduce a new construction of a market based on a closed subset of the inner core which satisfies a strict positive separability. We show that the constructed market represents the NTU game and, further, has the given closed set as the set of payoff vectors of competitive equilibria. It turns out that this market is not uniquely determined, and thus, we obtain a class of markets. Our results generalize those relating to competitive outcomes of NTU market games in the literature.     

Iterated Weak Dominance in Strictly Competitive Games of Perfect Information

We prove that any strictly competitive perfect-information two-person game with n outcomes is solvable in n−1 steps of elimination of weakly dominated strategies— regardless of the length of the game tree. The given bound is shown to be tight using a variant of Rosenthal's centipede game. Journal of Economic Literature Classification Numbers: C70, C72.     

Anonymous monotonic social welfare functions

This paper presents two results about preference domain conditions that deepen our understanding of anonymous and monotonic Arrovian social welfare functions (ASWFs). We characterize the class of anonymous and monotonic ASWFs on domains without Condorcet triples. This extends and generalizes an earlier characterization (as Generalized Majority Rules) by Moulin (Axioms of Cooperative Decision Making, Cambridge University Press, New York, 1988) for single-peaked domains. We also describe a domain where anonymous and monotonic ASWFs exist only when there are an odd number of agents. This is a counter-example to a claim by Muller (Int. Econ. Rev. 23 (1982) 609), who asserted that the existence of 3-person anonymous and monotonic ASWFs guaranteed the existence of n-person anonymous and monotonic ASWFs for any n>3. Both results build upon the integer programming approach to the study of ASWFs introduced in Sethuraman et al. (Math. Oper. Res. 28 (2003) 309).     

Dynamic group formation in the repeated prisoner?s dilemma

We consider dynamic group formation in repeated n-person prisoner?s dilemma. Agreements in coalitional bargaining are self-binding in that they are supported as subgame perfect equilibria of repeated games. Individuals are allowed to renegotiate the cooperating group agreement through a process of voluntary participation. We prove that a cooperating group forms as an absorbing state of a Markov perfect equilibrium after a finite number of renegotiations if and only if the group is Pareto efficient, provided that individuals are patient. The cooperating group can only expand.     

The Nash-threats folk theorem with communication and approximate common knowledge in two player games

We show that the use of communications to coordinate equilibria generates a Nash-threats folk theorem in two-player games with “almost public” information. The results generalize to the n-person case. However, the two-person case is more difficult because it is not possible to sustain equilibria by comparing the reports of different players, and using these “third parties” to effectively enforce contracts.     

Subjective evaluations of n-person games

Using an axiomatization of subjective expected utility due to Fishburn, we characterize a class of utility functions over a set of n-person games in characteristic-function form. A probabilistic value is defined as the expectation of some player's marginal contribution with respect to some probability measure on the set of coalitions of other players. We decribe conditions under which a utility function on the set of n-person games is a probabilistic value; we prove as well an analogous result for simple games. We present additional axioms that characterize the semivalues and, in turn, the Shapley and Banzhaf values.