Consistent extensions and subsolutions of the core for the multichoice transferable-utility games

Abstract

We extend the reduced games introduced by Davis and Maschler (Naval Res. Log. Q. 12:223–259, 1965) and Moulin (J. Econ. Theory. 36:120–148, 1985) to multichoice transferable-utility games. First, we provide an example to illustrate that the core proposed by van den Nouweland et al. (Math Methods Oper. Res. 41:289–311, 1995) violates related consistency properties. Further, we propose the minimal consistent extensions of the core and the maximal consistent subsolutions of the core. We also provide an axiomatization based on related consistency properties and its converse.     

The multichoice consistent value

We consider multichoice NTU games, i.e., cooperative NTU games in which players can participate in the game with several levels of activity. For these games, we define and characterize axiomatically the multichoice consistent value, which is a generalization of the consistent NTU value for NTU games and of the multichoice value for multichoice TU games. Moreover, we show that this value coincides with the consistent NTU value of a replicated NTU game and we provide a probabilistic interpretation. Received: May 1998/Final version: January 2000     

A new approach to the core and Weber set of multichoice games

Multichoice games have been introduced by Hsiao and Raghavan as a generalization of classical cooperative games. An important notion in cooperative game theory is the core of the game, as it contains the rational imputations for players. We propose two definitions for the core of a multichoice game, the first one is called the precore and is a direct generalization of the classical definition. We show that the precore coincides with the definition proposed by Faigle, and that the set of imputations may be unbounded, which makes its application questionable. A second definition is proposed, imposing normalization at each level, causing the core to be a convex compact set. We study its properties, introducing balancedness and marginal worth vectors, and defining the Weber set and the pre-Weber set. We show that the classical properties of inclusion of the (pre)core into the (pre)-Weber set as well as their coincidence in the convex case remain valid. A last section makes a comparison with the core defined by Van den Nouweland et al. A preliminary and short version of this paper has been presented at 4th Logic, Game Theory and Social Choice meeting, Caen, France, June 2005 (Xie and Grabisch 2005).     

Multilinear extensions and values for multichoice games

We define multilinear extensions for multichoice games and relate them to probabilistic values and semivalues. We apply multilinear extensions to show that the Banzhaf value for a compound multichoice game is not the product of the Banzhaf values of the component games, in contrast to the behavior in simple games. Following Owen (Manag Sci 18:64–79, 1972), we integrate the multilinear extension over a simplex to construct a version of the Shapley value for multichoice games. We compare this new Shapley value to other extensions of the Shapley value to multichoice games. We also show how the probabilistic value (resp. semivalue, Banzhaf value, Shapley value) of a multichoice game is equal to the probabilistic value (resp. semivalue, Banzhaf value, Shapley value) of an appropriately defined TU decomposition game. Finally, we explain how semivalues, probabilistic values, the Banzhaf value, and this Shapley value may be viewed as the probability that a player makes a difference to the outcome of a simple multichoice game.     

A generalization of correlated equilibrium: A new protocol

A new correlation scheme (leading to a special equilibrium called “soft” correlated equilibrium) is introduced for finite games. After randomization over the outcome space, players have the choice either to follow the recommendation of an umpire blindly or freely choose some other action except the one suggested. This scheme can lead to Pareto-better outcomes than the simple extension introduced by [Moulin, H., Vial, J.-P., 1978. Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7, 201–221]. The informational and interpretational aspects of soft correlated equilibria are also discussed in detail. The power of the generalization is illustrated in the prisoners’s dilemma and a congestion game.     

Potential approach and characterizations of a Shapley value in multi-choice games

The main focus of this paper is on the restricted Shapley value for multi-choice games introduced by Derks and Peters [Derks, J., Peters, H., 1993. A Shapley value for games with restricted coalitions. International Journal of Game Theory 21, 351–360] and studied by Klijn et al. [Klijn, F., Slikker, M., Zazuelo, J., 1999. Characterizations of a multi-choice value. International Journal of Game Theory 28, 521–532]. We adopt several characterizations from TU game theory and reinterpret them in the framework of multi-choice games. We generalize the potential approach and show that this solution can be formulated as the vector of marginal contributions of a potential function. Also, we characterize the family of all solutions for multi-choice games that admit a potential. Further, a consistency result is reported.     

The multichoice coalition value

In this paper we define a solution for multichoice games which is a generalization of the Owen coalition value (Lecture Notes in Economics and Mathematical Systems: Essays in Honor of Oskar Morgenstern, Springer, New York, pp. 76–88, 1977) for transferable utility cooperative games and the Egalitarian solution (Peters and Zanks, Ann. Oper. Res. 137, 399–409, 2005) for multichoice games. We also prove that this solution can be seen as a generalization of the configuration value and the dual configuration value (Albizuri et al., Games Econ. Behav. 57, 1–17, 2006) for transferable utility cooperative games.     

Dominance solvable games and trees

We study social choice functions represented by Moulin's dominance solvable games. We first show that dominance solvability of games is independent of the order in which dominated strategies are deleted. This implies that the perfect equilibrium of a game with perfect information generally coincides with its solution according to dominance solvability. Then we show that a large class of d-solvable games yields the same social choice functions as those represented by games of perfect information. We show that for three alternatives and all n relatively prime to 6 there exists a method of social choice fractional elimination, which can be represented by a kingmaker tree. This covers some cases not previously covered by Moulin. We also find numerous examples.     

Discounted and finitely repeated minority games with public signals

We consider a repeated game where at each stage players simultaneously choose one of the two rooms. The players who choose the less crowded room are rewarded with one euro. The players in the same room do not recognize each other, and between the stages only the current majority room is publicly announced, hence the game has imperfect public monitoring. An undiscounted version of this game was considered by Renault et al. [Renault, J., Scarlatti, S., Scarsini, M., 2005. A folk theorem for minority games. Games Econom. Behav. 53 (2), 208–230], who proved a folk theorem. Here we consider a discounted version and a finitely repeated version of the game, and we strengthen our previous result by showing that the set of equilibrium payoffs Hausdorff-converges to the feasible set as either the discount factor goes to one or the number of repetition goes to infinity. We show that the set of public equilibria for this game is strictly smaller than the set of private equilibria.     

Consistent and covariant solutions for TU games

One of the important properties characterizing cooperative game solutions is consistency. This notion establishes connections between the solution vectors of a cooperative game and those of its reduced game. The last one is obtained from the initial game by removing one or more players and by giving them the payoffs according to a specific principle (e.g. a proposed payoff vector). Consistency of a solution means that the restriction of a solution payoff vector of the initial game to any coalition belongs to the solution set of the corresponding reduced game. There are several definitions of the reduced games (cf., e.g., the survey of T. Driessen [2]) based on some intuitively acceptable characteristics. In the paper some natural properties of reduced games are formulated, and general forms of the reduced games possessing some of them are given. The efficient, anonymous, covariant TU cooperative game solutions satisfying the consistency property with respect to any reduced game are described.The research was supported by the NWO grant 047-008-010 which is gratefully acknowledgedReceived: October 2001     

Computing power indices: Multilinear extensions and new characterizations

Johnston [Johnston, R.J., 1978. On the measurement of power: some reactions to Laver. Environment and Planning A 10, 907–914], Deegan and Packel [Deegan, J., Packel, E.W., 1979. A new index of power for simple n-person games. International Journal of Game Theory 7, 113–123], and Holler [Holler, M.J., 1982. Forming coalitions and measuring voting power. Political Studies 30, 262–271] proposed three power indices for simple games: Johnston index, Deegan–Packel index, and the Public Good Index. In this paper, methods to compute these indices by means of the multilinear extension of the game are presented. Furthermore, a new characterization of the Public Good Index is given. Our methods are applied to two real-world examples taken from the political field.     

A nonsmooth Levenberg–Marquardt method for solving semi-infinite programming problems

In this paper, we first transform the semi-infinite programming problem into the KKT system by the techniques in [D.H. Li, L. Qi, J. Tam, S.Y. Wu, A smoothing Newton method for semi-infinite programming, J. Global. Optim. 30 (2004) 169–194; L. Qi, S.Y. Wu, G.L. Zhou, Semismooth Newton methods for solving semi-infinite programming problems, J. Global. Optim. 27 (2003) 215–232]. Then a nonsmooth and inexact Levenberg–Marquardt method is proposed for solving this KKT system based on [H. Dan, N. Yamashita, M. Fukushima, Convergence properties of the inexact Levenberg–Marquardt method under local error bound conditions, Optimim. Methods Softw., 11 (2002) 605–626]. This method is globally and superlinearly (even quadratically) convergent. Finally, some numerical results are given.     

Characterizations of a multi-choice value

A multi-choice game is a generalization of a cooperative game in which each player has several activity levels. We study the extended Shapley value as proposed by Derks and Peters (1993). Van den Nouweland (1993) provided a characterization that is an extension of Young's (1985) characterization of the Shapley value. Here we provide several other characterizations, one of which is the analogue of Shapley's (1953) original characterization. The three other characterizations are inspired by Myerson's (1980) characterization of the Shapley value using balanced contributions. Received: November 1997/final version: February 1999     

Core,value and equilibria for market games: On a problem of Aumann and Shapley

In this note a partial solution of Open Problem 41C of Aumann and Shapley [1974, pp. 250–251] is presented. A sufficient condition for the Aumann-Shapley value of a market game to exist, to be contained in its core, and to be the competitive payoff distribution of a transferable utility competitive equilibrium is given. In this context, balancedness and σ-balancedness criteria for large classes of cooperative games are proven.     

Seat reservation allowing seat changes

We consider a variant of the Seat Reservation Problem [J. Boyar, K.S. Larsen, Algorithmica 25 (1999) 403–417] in which seat changes are allowed. We analyze the model using the competitive ratio, the competitive ratio on accommodating sequences [J. Boyar, K.S. Larsen, Algorithmica 25 (1999) 403–417], and the accommodating function [J. Boyar et al., Acta Informatica 40 (2003) 3–35; J. Boyar et al., SIAM J. Comput. 31 (1) (2001) 233–258]. A very promising family of algorithms considered in this paper is Min-Change, which will ask passengers to change seats, only if they would otherwise have been rejected. Min-Change belongs to a large class of conservative algorithms, which all have very high performance guarantees. For instance, if the optimal off-line algorithm can seat all of the passengers, 2/3 of the passengers can be seated on-line using any conservative algorithm allowing only one seat change and 3/4 will be seated if two seat changes are allowed. This should be compared to the asymptotic hardness result of 1/2 for the best algorithm when no seat changes are allowed [E. Bach et al., J. Sched. 6 (2003) 131–147]. Another interesting algorithm, Modified-Kierstead–Trotter, is proposed and shown to seat all passengers if the optimal off-line algorithm could have accommodated them with only half as many seats. On this type of sequence, Modified-Kierstead–Trotter is strictly better than Min-Change-First-Fit which is strictly better than the Checkerboard algorithm.     

The pseudo-average rule: bankruptcy,cost allocation and bargaining

A division rule for claims problems, also known as bankruptcy or rationing problems, based on the pseudo-average solution is studied (for 2-person problems). This solution was introduced in Moulin (Jpn Econ Rev 46:303–332, 1995) for discrete cost allocation problems. Using the asymptotic approach, we obtain a division rule for claims problems. We characterize the division rule axiomatically and show that it coincides with the rule associated to the equal area bargaining solution (this is not true for n = 3). Moreover, following Moulin and Shenker (J Econ Theor 64:178–201, 1994), we show that its associated solution for continuous homogeneous goods is precisely the continuous pseudo-average solution.     

Balancedness of multiple machine sequencing games revisited

We study m-sequencing games, which were introduced by [Hamers, H., Klijn, F., Suijs, J., (1999). On the balancedness of multiple machine sequencing games. European Journal of Operational Research 119, 678–691]. We answer the open question whether all these games are balanced in the negative. We do so, by an example of a 3-sequencing situation with 5 jobs, whose associated 3-sequencing game has an empty core. The counterexample finds its basis in an inconsistency in [Hamers et al., ibid], which was probably overlooked by the authors. This observation demands for a detailed reconsideration of their proofs.¹     

A double obstacle problem arising in differential game theory

A Hamilton–Jacobi equation involving a double obstacle problem is investigated. The link between this equation and the notion of dual solutions—introduced in [S. As Soulaimani, Infinite horizon differential games with asymmetric information, PhD thesis; P. Cardaliaguet, Differential games with asymmetric information, SIAM J. Control Optim. 46 (3) (2007) 816–838; P. Cardaliaguet, C. Rainer, Stochastic differential games with asymmetric information, Appl. Math. Optim. 59 (1) (2009) 1–36] in the framework of differential games with lack of information—is established. As an application we characterize the convex hull of a function in the simplex as the unique solution of some nonlinear obstacle problem.     

Nonsymmetric values under Hart-Mass-Colell consistency

Let f be a single valued solution for cooperative TU games that satisfies inessential game property, efficiency, Hart Mas-Colell consistency and for two person games is strictly monotonic and individually unbounded. Then there exists a family of strictly increasing functions associated with players that completely determines f. For two person games, both players have equal differences between their functions at the solution point and at the values of characteristic function of their singletons. This solution for two person games is uniquely extended to n person games due to consistency and efficiency. The extension uses the potential with respect to the family of functions and generalizes potentials introduced by Hart and Mas Colell [6]. The weighted Shapley values, the proportional value described by Ortmann [11], and new values generated by power functions are among these solutions. The author is grateful to anonymous referee and Associate Editor for their comments and suggestions.     

On stable position control in differential games : PMM vol. 42, no. 6, 1978, pp 963–968

A procedure for control with a guide (1–3], yielding a solution, stable with respect to small data disturbances, of game problems of dynamics is proposed for a class, more general in comparison with [1–3], of conflict-controlled systems, i.e., systems requiring uniqueness of the program motions and their uniform boundedness. The terminology and notation follow [2].