Cumbersome coordination in repeated games

This paper examines the role communication between players might serve in enabling them to reach an agreement on the future play of a repeated game. The property of the communication process that we focus on is the amount of time it takes to complete. We characterize the effects of such communication processes indirectly by determining the set of agreements they may yield. A weak and a strong criterion are introduced to describe sets of agreements that are “stable” in the sense that players would follow the current agreement and not seek to reach a new agreement. We show that as players become extremely patient, strongly stable sets converge to Pareto efficient singletons. We apply the stability criteria to Prisoner’s Dilemmas and show how the unique strongly stable set reflects asymmetries in the players’ stage-game payoffs. Finally, we model the communication process as a Rubinstein alternating-offer bargaining game and demonstrate that the resulting agreements help characterize the strongly stable set for a general class of communication mechanisms. Received January 1998/final version June 1999     

Fictitious play in coordination games

We study the Fictitious Play process with bounded and unbounded recall in pure coordination games for which failing to coordinate yields a payoff of zero for both players. It is shown that every Fictitious Play player with bounded recall may fail to coordinate against his own type. On the other hand, players with unbounded recall are shown to coordinate (almost surely) against their own type as well as against players with bounded recall. In particular, this implies that a FP player's realized average utility is (almost surely) at least as large as his minmax payoff in 2×2 coordination games. Received: December 1997/Final version: November 1998     

On coordination games with quantum correlations

A necessary condition is derived that helps to determine whether an entangled quantum system can improve coordination in a game with incomplete information. The author would like to express his gratitude to Diana Bloom for her help with editing this paper.     

Nash equilibria of Cauchy-random zero-sum and coordination matrix games

We consider zero-sum games (A,  − A) and coordination games (A,A), where A is an m-by-n matrix with entries chosen independently with respect to the Cauchy distribution. In each case, we give an exact formula for the expected number of Nash equilibria with a given support size and payoffs in a given range, and also asymptotic simplications for matrices of a fixed shape and increasing size. We carefully compare our results with recent results of McLennan and Berg on Gaussian random bimatrix games (A,B), and describe how the three situations together shed light on random bimatrix games in general.     

Advertising coordination games of a manufacturer and a retailer while introducing a new product

Two kinds of vertical cooperative advertising program are considered in a distribution channel constituted by a manufacturer and a retailer, where the manufacturer pays part of the retailer’s advertising costs. In the first participation scheme, the manufacturer chooses his/her advertising participation rate in the retailer’s advertising effort and then each player determines the advertising effort that maximizes his/her profit. In the second scheme, the retailer chooses the manufacturer’s participation rate and then the manufacturer determines the advertising efforts of both players with the objective of maximizing the manufacturer’s profit. Each participation scheme corresponds to a special Stackelberg game: the manufacturer is the leader of the first, while the retailer is the leader of the second. The Stackelberg equilibrium advertising efforts and participation rate in both games are provided. Then the equilibrium strategies of the two players in the analyzed scenarios are compared with the Nash equilibrium in the competitive framework. Finally, the conditions which suggest a special kind of agreement to a player are analyzed. This work was supported by the Italian Ministry of University and Research and the University of Padua.     

Lead-time hedging and coordination between manufacturing and sales departments using Nash and Stackelberg games

In a firm, potential conflict exists between manufacturing and sales departments. Salespersons prefer to order from manufacturing departments in advance so that they can secure products in the amount they need to satisfy customers in time. This time in advance strategy is defined as “lead-time hedging.” While this hedging strategy is good for the sales department to guarantee the right quantity at the right time for customers, it adds additional costs and pressure to the manufacturing department. One scheme to resolve this conflict is to introduce a fair “internal price,” charged by the manufacturing department to the sales department. In this paper, two models involving a fair internal price are introduced. In one model, a Nash game is played to reach an optimal strategy for both parties. In the other model, a Stackelberg game is played in which the manufacturing department serves as the leader. We show that these two models can successfully reduce lead-time hedging determined by the salesperson and can increase the firm’s overall profit, as compared to the traditional model without considering the internal price. More insights have also been analyzed that include the comparisons of the manufacturer’s and the salesperson’s profits among the traditional model, the Nash game model, the Stackelberg game model, and the centralized global optimization model.     

Strong equilibria in claim games corresponding to convex games

This paper deals with a specific aspect of the problem of coalition formation in a situation described by a TU-game. First, we define a very simple normal form game which models the process of coalition formation. To define the payoff functions of the players we use an allocation rule for TU-games. The main objective of this paper is ascertain what conditions of the allocation rule lead to the grand coalition being a strong equilibrium of the normal form game, when the original TU-game is convex. Received January 1996/Revised version December 1996/Final version May 1997     

Cycle games and cycle cut games

Two players play a game on a connected graphG. Each player in his turn occupies an edge ofG. The player who occupies a set of edges that contains a cycle, before the other does it, wins. This game may end in a draw. We call this game the normal cycle game. We define furthermore three similar games, which are called the misère cycle game, the normal cycle cut game and the misère cycle cut game. We characterize the above four games.     

Totally monotonic games and flow games

Equivalences between totally balanced games and flow games, and between monotonic games and pseudoflow games are well-known. This paper shows that for every totally monotonic game there exists an equivalent flow game and that for every monotonic game, there exists an equivalent flow-based secondary market game.     

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.     

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.     

Partizan octal games: Partizan subtraction games

A subtraction gameS=(s ₁, ...,s _k)is a two-player game played with a pile of tokens where each player at his turn removes a number ofm of tokens providedmεS. The player first unable to move loses, his opponent wins. This impartial game becomes partizan if, instead of one setS, two finite setsS _L andS _R are given: Left removes tokens as specified byS _L, right according toS _R. We say thatS _L dominatesS _R if for all sufficiently large piles Left wins both as first and as second player. We exhibit a curious property of dominance and provide two subclasses of games in which a dominance relation prevails. We further prove that all partizan subtraction games areperiodic, and investigatepure periodicity.     

Perturbation theory for games in normal form and stochastic games

In this paper, the effect on values and optimal strategies of perturbations of game parameters (payoff function, transition probability function, and discount factor) is studied for the class of zero-sum games in normal form and for the class of stationary, discounted, two-person, zero-sum stochastic games.A main result is that, under certain conditions, the value depends on these parameters in a pointwise Lipschitz continuous way and that the sets of -optimal strategies for both players are upper semicontinuous multifunctions of the game parameters.Extensions to general-sum games and nonstationary stochastic games are also indicated.     

Randomized stopping games and Markov market games

We study nonzero-sum stopping games with randomized stopping strategies. The existence of Nash equilibrium and ɛ-equilibrium strategies are discussed under various assumptions on players random payoffs and utility functions dependent on the observed discrete time Markov process. Then we will present a model of a market game in which randomized stopping times are involved. The model is a mixture of a stochastic game and stopping game. Research supported by grant PBZ-KBN-016/P03/99.     

Non-cooperative monopolistic games and monopolistic market games

A class of non-cooperative games is discussed in which one player (“the monopolist”) by choosing his strategy restricts the other players to subsets of their strategy sets. Examples of such games in various fields are given. In particular it is shown that some very important economic situations fall within this class of games. A solution concept is defined and sufficient conditions for its existence are derived. The question of the advantages a player derives from being a monopolist is raised and conditions are derived for him to benefit from being a monopolist.     

Reduction of Silverman-like games to games on bounded sets

A two person zero sum game is regarded as Silverman-like if the strategy sets are sets of real numbers bounded below, the payoff function is bounded, the maximum payoff is achieved whenever the second player's numbery exceeds the first player's numberx by “too much”, and the minimum is achieved wheneverx exceedsy by “too much”. Explicit upper bounds are obtained for pure strategies to be included in an optimal mixed strategy in such games. In particular, if the strategy sets are discrete, the games may be reduced to games on specified finite sets.     

Totality in arena games

We tackle the problem of preservation of totality by composition in arena games. We first explain how this problem reduces to a finiteness theorem on what we call pointer structures, similar to the parity pointer functions of Harmer, Hyland & Melliès and the interaction sequences of Coquand. We discuss how this theorem relates to normalization of linear head reduction in simply-typed λ-calculus, leading us to a semantic realizability proof à la Kleene of our theorem. We then present another proof of a more combinatorial nature. Finally, we discuss the exact class of strategies to which our theorems apply.     

Bargaining in cooperative games

This paper introduces a new solution concept for cooperative games without sidepayments, called the aspiration bargaining set, and proves that this set is nonempty for a wide, and economically interesting, class of games.