Simple coalitional strategy profiles in repeated games

In this paper we introduce simple coalitional strategy profiles to avoid group deviations in repeated games. In the repeated Cournot supergame we prove that it is possible to sustain the symmetric monopoly outcome by means of a variety of strategies which satisfy the requirement that no coalition (other than the grand one) will deviate in any subgame.     

Adaptive allocation rules for hypergraph games

Cooperative games with hypergraph structure, or hypergraph games, assume that all players in a hyperlink or conference have to be present before communication. Contrary to this situation, assuming that whenever players leave a conference the remaining players can still communicate with each other, adaptive allocation rules for hypergraph games, being alternative extensions of the Myerson value and the position value respectively, are introduced in this paper. Axiomatic characterizations are also provided by considering players' absence.     

Asymptotic vulnerability of positional voting rules to coalitional manipulation

Voting rule performances are sometimes evaluated according to their respective resistances to allow profitable misrepresentation of individual preferences. This seems to be a hard task when scoring systems with possibly non integer weights are involved. In this paper, it is shown how one can still obtain asymptotic results in these settings. Our analysis for three-candidate elections provides a characterization of unstable voting situations at which a positional voting rule is manipulable by some coalition not larger than an arbitrary proportion of the electorate. This allows us to address a conjecture by Pritchard and Wilson (2007). That is, under the Impartial Anonymous Culture (IAC), the plurality rule asymptotically minimizes the vulnerability to coalitional manipulation when the size of the manipulating coalition is unrestricted. This later result is no longer valid when only manipulation by small coalitions is considered: now, the Borda rule tends to outperform other rules. Furthermore, the vulnerability of a positional voting rule to coalitional manipulation is not affected by increasing the size of the manipulating coalition from 0.5 to 1.     

Allocation rules for hypergraph communication situations

This paper considers hypergraph communication situations, where for a group of agents the economic possibilities are described by a coalitional game and the communication possibilities are described by a hypergraph in which the nodes are the agents and the edges are the subgroups of agents who can effect communication. Axiomatic characterizations are provided for two allocation rules, the Myerson value and the position value.     

A coalitional procedure leading to a family of bankruptcy rules

We provide a general coalitional procedure that characterizes a family of rules for bankruptcy problems inspired by the Talmud.     

Evolutionary games and matching rules

This study considers evolutionary games with non-uniformly random matching when interaction occurs in groups of \(n\ge 2\) individuals using pure strategies from a finite strategy set. In such models, groups with different compositions of individuals generally co-exist and the reproductive success (fitness) of a specific strategy varies with the frequencies of different group types. These frequencies crucially depend on the matching process. For arbitrary matching processes (called matching rules), we study Nash equilibrium and ESS in the associated population game and show that several results that are known to hold for population games under uniform random matching carry through to our setting. In our most novel contribution, we derive results on the efficiency of the Nash equilibria of population games and show that for any (fixed) payoff structure, there always exists some matching rule leading to average fitness maximization. Finally, we provide a series of applications to commonly studied normal-form games.     

Weighted allocation rules for standard fixed tree games

In this paper we consider standard fixed tree games, for which each vertex unequal to the root is inhabited by exactly one player. We present two weighted allocation rules, the weighted down-home allocation and the weighted neighbour-home allocation, both inspired by the painting story in Maschler et al. (1995) . We show, in a constructive way, that the core equals both the set of weighted down-home allocations and the set of weighted neighbour allocations. Since every weighted down-home allocation specifies a weighted Shapley value (Kalai and Samet (1988)) in a natural way, and vice versa, our results provide an alternative proof of the fact that the core of a standard fixed tree game equals the set of weighted Shapley values. The class of weighted neighbour allocations is a generalization of the nucleolus, in the sense that the latter is in this class as the special member where players have all equal weights.     

Allocation processes in cooperative games

This paper deals with a temporal aspect of cooperative games. A solution of the game is reached through an allocation process. At each stage of the allocation process of a cooperative game a budget of fixed size is distributed among the players. In the first part of this paper we study a type of process that, at any stage, endows the budget to a player whose contribution to the total welfare, according to some measurements, is maximal. It is shown that the empirical distribution of the budget induced by each process of the family converges to a least square value of the game, one such value being the Shapley value. Other allocation processes presented here converge to the core or to the least core. Received: January 2001/Revised: July 2002 I am grateful to the Associate Editor and to the two anonymous referees of International Journal of Game Theory. This research was partially supported by the Israel Science Foundation, grant no. 178/99     

Stability property of matchings is a natural solution concept in coalitional market games

Stability of matchings was proved to be a new cooperative equilibrium concept in Sotomayor (Dynamics and equilibrium: essays in honor to D. Gale, 1992). That paper introduces the innovation of treating as multi-dimensional the payoff of a player with a quota greater than one. This is done for the many-to-many matching model with additively separable utilities, for which the stability concept is defined. It is then proved, via linear programming, that the set of stable outcomes is nonempty and it may be strictly bigger than the set of dual solutions and strictly smaller than the core. The present paper defines a general concept of stability and shows that this concept is a natural solution concept, stronger than the core concept, for a much more general coalitional game than a matching game. Instead of mutual agreements inside partnerships, the players are allowed to make collective agreements inside coalitions of any size and to distribute his labor among them. A collective agreement determines the level of labor at which the coalition operates and the division, among its members, of the income generated by the coalition. An allocation specifies a set of collective agreements for each player.     

Monotonic games are spanning network games

Spanning network games, which are a generalization of minimum cost spanning tree games, were introduced by Granot and Maschler (1991), who showed that these games are always monotonic. In this paper a subclass of spanning network games is introduced, namely simplex games, and it is shown that every monotonic game is a simplex game. Hence, the class of spanning network games coincides with the class of monotonic games.     

Spanning network games

We study fundamental properties of monotone network enterprises which contain public vertices and have positive and negative costs on edges and vertices. Among the properties studied are the nonemptiness of the core, characterization of nonredundant core constraints, ease of computation of the core and the nucleolus, and cases of decomposition of the core and the nucleolus. Received December 1994/Final version March 1998     

The intermediate set and limiting superdifferential for coalitional games: between the core and the Weber set

We introduce the intermediate set as an interpolating solution concept between the core and the Weber set of a coalitional game. The new solution is defined as the limiting superdifferential of the Lovász extension and thus it completes the hierarchy of variational objects used to represent the core (Fréchet superdifferential) and the Weber set (Clarke superdifferential). It is shown that the intermediate set is a non-convex solution containing the Pareto optimal payoff vectors that depend on some chain of coalitions and marginal coalitional contributions with respect to the chain. A detailed comparison between the intermediate set and other set-valued solutions is provided. We compute the exact form of intermediate set for all games and provide its simplified characterization for the simple games and the glove game.     

Weakly unimodal domains,anti-exchange properties,and coalitional strategy-proofness of aggregation rules

It is shown that simple and coalitional strategy-proofness of an aggregation rule on any rich weakly unimodal domain of an idempotent interval space are equivalent properties if that space satisfies interval anti-exchange, a basic property also shared by a large class of convex geometries including–but not reducing to–trees and Euclidean convex spaces. Therefore, strategy-proof location problems in a vast class of networks fall under the scope of that proposition.It is also established that a much weaker minimalanti-exchangeproperty is necessary to ensure equivalence of simple and coalitional strategy-proofness in that setting. An immediate corollary to that result is that such equivalence fails to hold both in certain median interval spaces including those induced by bounded distributive lattices that are not chains, and in certain non-median interval spaces including those induced by partial cubes that are not trees.Thus, it turns out that anti-exchange properties of the relevant interval space provide a powerful general common principle that explains the varying relationship between simple and coalitional strategy-proofness of aggregation rules for rich weakly unimodal domains across different interval spaces, both median and non-median.     

Representation of finite games as network congestion games

Weighted network congestion games are a natural model for interactions involving finitely many non-identical users of network resources, such as road segments or communication links. However, in spite of their special form, these games are not fundamentally special: every finite game can be represented as a weighted network congestion game. The same is true for the class of (unweighted) network congestion games with player-specific costs, in which the players differ in their cost functions rather than their weights. The intersection of the two classes consists of the unweighted network congestion games. These games are special: a finite game can be represented in this form if and only if it is an exact potential game.     

Decomposition of network communication games

Using network control structures, this paper introduces a general class of network communication games and studies their decomposition into unanimity games. We obtain a relation between the dividends in any network communication game and its underlying transferable utility game, which depends on the structure of the communication network. Moreover, we introduce a new class of network control values which contains both the Myerson value and the position value. The decomposition results are used to explicitly express these values in terms of dividends.     

Evidence based rules and learning in symmetric normal-form games

We put forth a general theory of boundedly rational behavior and learning for symmetric normal-form games with unique symmetric Nash equilibria. A class of evidence-based behavioral rules is specified, which includes best-responding to a prior and Nash play. A player begins with initial propsenities towards the rules, and given experience over time adjusts his/her propensities in proportion to the past performance of the rules. We focus on scenarios in which the past distribution of play is revealed to all players. Confronting this theory with experimental data, we find significant support for rule learning and heterogeneity among participants. Received June 1996/Final version April 1997