Back to International Conference

Contributed Talks



Zafer Akin

Penn State University

The role of time-inconsistent preferences in intertemporal decisions and bargaining  [PDF]

Previous papers about procrastination in intertemporal decision problems take the payoff of the agents as given. In this paper, we make the payoff structure endogenous by introducing a bargaining stage after the investment game and show that this changes the results significantly. Examining Rubinstein's alternating offer bargaining games played by (naive and sophisticated) time-inconsistent agents gives different results than the games with time-consistent agents. Sophisticated agent does worse than naive agent in terms of bargaining share. Naive agent overestimates his payoff, possibly, leading to a regret motive. In a complete information framework, the minimal incentive scheme to prevent inefficient procrastination is derived. We show that for naive players, minimal incentive scheme involves an increasing reward structure and it requires -for any given project- higher rewards for players with higher time-inconsistency problems.

Leif Albers

IMW, Bielefeld University

Feasible Beliefs in Noncooperative Games  [PDF]

This paper refines the "equilibrium under uncertainty" introduced in Eichberger and Kelsey (2000) and modified in Albers (2000). We assume that a player s uncertainty prevents him from choosing certain beliefs. In particular, frightened players cannot choose (most) additive beliefs. Therefore, for each player we use a feasible set that specifies all beliefs that are consistent with his uncertainty. It is possible to impose such a restriction in a very general way and still guarantee the existence of an equilibrium in feasible beliefs.

Leandro Arozamena

Universidad Torcuato Di Tella

The Effect of Corruption on Bidding Behavior in First-Price Auctions  [PDF]

- joint work with Federico Weinschelbaum (Universidad de San Andres)

Most of the literature on auctions assumes that the auctioneer owns the object on sale. However, most auctions are organized and run by an agent of the owner. This separation generates the possibility of corruption. We analyze the effect of a particular form of corruption on bidding behavior in a single-object, private-value auction with risk-neutral bidders. Bidders believe that, with a certain probability, the auctioneer has reached an agreement with one of the bidders by which, after receiving all bids, (i) she will reveal to that bidder all of her rivals' bids, and (ii) she will allow that bidder to change her original bid upwards or downwards. We study how an honest bidder would adjust her bidding behavior when facing this type of collusion between a dishonest rival and the auctioneer. In a first price auction, an honest bidder can become more or less aggressive than she would be without corruption, or her behavior can remain unchanged. We identify sufficient conditions for each of the three possibilities. We also examine the extent to which the most commonly used distributions satisfy each of the three conditions and the consequences of this form of corruption on the seller's revenue.

Siddhartha Bandyopadhyay

University of Birmingham

Economic reforms, conflict resolution and leadership quality: A model of political failure  [PDF]

- joint work with Mandar P. Oak

We analyze an agency model of politics where the e±cient policy depends on the leader quality as well as the state of the the economy, both of which are private information to the incumbent politician. Even though the polity gains from having an able leader, reelection concerns cause the incumbent's preferences to diverge from those of the population. Specifically, two types of distortions could arise - one, a low ability leader may try to mimic the high ability one; and two - the high ability leader may want to choose a suboptimal policy under the given state of the world. We look at voting strategies which cause low quality leaders to separate out from high quality ones. We compare this with strategies which cause pooling of types and find that when the rents from o±ce are su±ciently high, the pooling equilibrium welfare dominates the separating one. However, pooling equilibrium has a credibility problem as the high quality leader may take actions which would reveal the type to the voters thereby making it optimal for voters to renege on their strategy. Specific applications discussed include economic reforms, conflict negotiation, and the role of the UN as a credible commitment agency. The results in the model give possible explanations of the cycle of violence in the Middle East as well as the `hawkish' drift in politics especially in the war on `terror'.

Larissa Batrancea

Babes-Bolyai University

Homo Oeconomicus Ludens  [PDF]

In the XVIIIth century Adam Smith, the author of the Theory of Moral Sentiments and Wealth of Nations, gave birth to the fundamental concept of his whole theoretical thinking system: Homo Oeconomicus. Since then the concept of Homo Oeconomicus – with its specific features: perfectly rational, perfectly egocentric, perfectly free, perfectly competitional and perfectly social - has represented the prototype of the classical and neoclassical economic agent. Since the appearance of Game Theory the outcome of each economic agent is no longer only a result of its own (strategies) property rights, money and the competitive market’s features as in terms of classical and neoclassical economics, but also a result of the strategies chosen by the other economic agents. As a consequence, the old Homo Oeconomicus cannot represent any more the prototype of the economic agent. Therefore in the new game theoretical conditions it is more adequate to call and to define the economic agent as a Homo Oeconomicus Ludens. Which are its features, which are the similarities and the differences between this new concept and the old one, these are the main aspects analyzed in extenso in this article.

Eyal Beigman

Hebrew University of Jerusalem

Aggregation with Many Effective Voters  [PDF]

McGarveys’s theorem shows that majority aggregation of a profile of linear orders generates any complete binary relation. Kalai proved that the same is true for any neutral monotone SWF defined by a strong simple game where the power of every voter is sufficiently small, which implies that there are many effective voters. In this paper we study neutral monotone SWFs with many effective voters with no restriction on voter
power. We give bounds on the minimal number of relations generated by such SWFs.

Juan Miguel Benito

Public University of Navarre

Schelling's dynamic models of segregation: A cellular automata approach  [PDF]

- joint work with Penélope Hernández

Schelling presented one-dimensional landscapes populated with agents of two distinct "types" in which micro-level agent preferences involve macro-level effects. Schelling's model exhibits the sectorial dynamics of individual preferences. A crucial feature in Schelling's model is the dynamic given the asynchronous movements of each agent. Given an order, each player chooses to move or to stay depending on his neighborhood configuration. Each agent looks for a position where he becomes happy because in it his neighborhood configuration is admissible. A happy society verifies that all agents are happy therefore we obtain a "stable society". We study a variant of the one-dimensional Schelling's model, capturing the myopic behavior of players in a geometric environment. We propose a cellular automata
approach acquiring the dynamics micro-level preferences. A cellular automaton consists of a lattice of cells, or sites over a finite alphabet, and a rule. At each time, the type of agent at site "i" is updated according to the fixed value and the corresponding of its immediate neighbors. Under our approach, we characterize the set of stable society and the set of environment in which converges to a stable situation.

Yutian Chen

Stony Brook University

Partial Outsourcing in Cournot Competition  [PDF]

Firms with a strictly concave production cost for a product which is not in their core competency have incentive to fully outsource this kind of product to an outsider provider. However, in reality we observe a lot of partial outsourcing in stead of 100% outsourcing. This paper finds that based on its cost advantage in the non-core product, the outside provider has the potential to enter and become a direct competitor in their core product with these outsourcing firms. To deter entrance of the outside provider, firms choose partial outsourcing and the optimal level of outsourcing is determined in a SPNE.

Johann Choi


Computation of Ordinal-Invariant Trajectory Solutions to Multiperson Bargaining Problems  [PDF]

A solution to the bargaining problem among 3 or more players is explicitly computed and discussed from the point of view of its invariance under continuously differentiable order-preserving transformations of the individual bargainers' utility scales. It is of the trajectory type, reflecting that the problem narrows down as negotiations among the bargainers proceed. Assuming the continuous differentiability of the individuals' utility scales gives us an opportunity to use differential equations in explicitly constructing the trajectory leading to this solution and in theoretically justifying its existence. For the 3 person case, this trajectory solution is graphically illustrated and the singularities of the Pareto surface are discussed. Numerical calculation of this trajectory solution for the 4 person case is also included.

Amrita Dhillon

University of Warwick

Scoring Rule Voting Games and Dominance Solvability  [PDF]

- joint work with Lucia Buenrostro

This paper studies the dominance solvability (by iterated elimination of weakly dominated strategies) of scoring rule voting games. The scoring rules we study include Plurality Rule, Approval Voting, Negative Plurality Rule Borda Rule and Relative Utilitarianism. We provide a classification of scoring rule voting games according to whether the sufficient condituons for dominance solvability require sufficient agreement on the best or the worst alternative. We also characterise the solutions when the sufficient conditions for dominance sovability are satisfied.

Irinel Dragan

University of Texas

On the Semivalues and the Least Square Values, Average per capita formulas and relationships  

In an earlier paper (I.Dragan,1992), we have shown that the Shapley value of a cooperative T.U. game (N,v), n=/N/, may be expressed in terms of n*2 average worth, precisely vs=average worth of the coalitions of size s, and vsi=average worth of coalitions of size s which do not contain player i, by a formula we have called the Average per capita formula. This formula may also be found in another paper (I.Dragan, T.Driessen, Y.Funaki,1996), where it has been used to compute the Shapley value for a class of games. The Semivalue associated with a weight vector satisfying a normalization condition was axiomatically introduced and its formula has also been given in the case of T.U. games
(P.Dubey, A.Neyman, R.J. Weber, 1981). This is a family of values which for specified weights contains the Shapley value and many other values. This fact suggests that a Semivalue may also be expressed in terms of the same average
worth as the Shapley value. We prove the Average per capita formula for Semivalues. Moreover, the Power Game relative to the Semivalues of the game and its subgames may be expressed only in terms of the averages vs. We prove the corresponding formula for the Power Game, to be further used. The Least Square Value associated with a weight vector satisfying a normalization condition was shown earlier as a solution of a quadratic optimization problem (M.Keane,
1969), then recently axiomatized (L.Ruiz, F.Valenciano, J.M.Zarzuelo, 1998). They proved also the LS-value formula. This is a family of values which contains for specified weights the Shapley value. This fact suggests that the LS-value may be expressed in terms of the same average worth as the Shapley value. We prove the Average per capita
formula for LS-values. Moreover, from this formula it follows the interesting result that a LS-value is the Shapley value of a game obtained by rescaling from the given game, with some simple functions of the weights as rescaling factors. Note that the existence of the similar average per capita formulas for the Shapley value, the Semivalues
and the LS-values offer much help in solving the inverse problem for the last two values, taking into account the solution given earlier for the Shapley value and the Weighted Shapley value (Dragan, 1991). The inverse problem for a value V can be stated as follows: given the n-vector Y, find out the set of games (N,v) such that V(N,v)=Y. Recently, in the paper providing an axiomatization of the LS-values, the authors show axiomatically that the efficient normalization of a Semivalue is a LS-value, where the result shows also the connection between the weight vectors. In the present paper, we use the average per capita formula for Semivalues and the expression of the Power Game in terms of the averages, in order to reach the average per capita formula for the LS-values. In other words, we give an algebraic proof for the Ruiz/Valenciano/Zarzuelo theorem mentioned above. Obviously, taking into account what was said
above about the LS-values and the Shapley value, it follows that the Semivalue of a game is the Shapley value of a game obtained by a linear transformation from the given game.

Peter Engseld

Lund University

Choosing Opponents in Prisoners Dilemma  

- joint work with Andreas Bergh

We consider a class of symmetric 2 × 2 games that includes the class of Prisoners dilemma games. It is assumed that the game is played in an evolutionary environment with a population of agents that are able to make (more or less) noisy observations of every participating agent’s propensity to play hard (defect) or nice (cooperate). This observation is called the reputation of the opponent. The agents form strategies where actions are conditioned on the reputation of their opponent. Moreover, we allow agents to choose opponents based on reputation. We analyze a matching scheme where each agent in each period is matched against one (or several) agent(s) of their choosing that agree to participate in the game.
It can be shown that the strategy “always choose to play nice (cooperate) and choose to play with agents that always plays nice (cooperate)” is a unique evolutionary stable strategy (ESS), given that cooperation (C,C) is socially optimal and the noise in the observation of reputation is small enough. If instead the case (C,D) should be socially optimal, then it can be shown that if the there exists a unique mixed strategy that is ESS, given the noise is small enough, where the agents plays cooperate with at least 50% probability.

Andrey Garnaev

Saint Petersburg State University

Competition for Staff between Two Departments  [PDF]

- joint work with V.J.Baston (University of Southampton)

The following scenario is analyzed from a game-theoretical point of view. Two departments in a large organization are each seeking to make an appointment within the same area of expertise, for instance, a computer science specialist. To avoid duplication it has been decided that the heads of the two departments should together interview the applicants in turn and make their decisions on one applicant before interviewing any others. If a candidate is rejected by both departmental heads, the candidate cannot be considered for either post at a later date. If both heads decide to make an offer two cases are considered: (a) the departments are equally attractive so that an applicant has no preference between them (b) one department can offer better prospects to applicants who will always choose that department. The departmental heads know that there are precisely n applicants and that each applicant has an expertise which is random over a known range. If no appointment is made to a department from these n applicants, then the department will suffer from a shortfall of expertise. It will be shown that that the games (a) and (b) have very different characteristics. The game (b) has just one NE but game (a) has many NE. It will be shown that it is reasonable to have several NE solutions as different dynamics within the firm can result in different outcomes. Thus, if one departmental head is aggressive and one passive, we might expect a different outcome to one in which both are of a similar temperament. In the former case we would not necessarily expect a symmetric outcome even though the scenario does not give one player an advantage over the other. Thus, although it may be natural to expect a solution of (a) to be symmetric, we will also investigate non-symmetric solutions. These non-symmetric equilibria have the advantage that the players have pure actions whereas, in our symmetric solution, the players are called upon to employ actions with complicated probabilities.

Ori Haimanko

Ben-Gurion University

Uniform Continuity of the Value of Zero-Sum Games with Differential Information  [PDF]

- joint work with Ezra Einy, Diego Moreno, and Binyamin Shitovitz

We establish uniform continuity of the value for zero-sum games with differential information, when the distance between changing information fields of each player is measured by the Boylan (1971) pseudo-metric. We also show that the optimal strategy correspondence is upper semi-continuous when the information fields of players change, even with the weak topology on players' strategy sets.

David Housman

Goshen College

Solutions for Partially Defined Cooperative Games  [PDF]

A partially defined cooperative game is a coalition function form game in which some of the coalition worths are not known. An application would be cost allocation of a joint project among so many players that the determination of all coalition worths is prohibitive. Although some coalition worths are not known precisely, we assume that there are some a priori bounds. For example, it may be known that the fully defined game must be zero monotonic, superadditive, or convex.
Three approaches are taken to obtain solutions for partially defined games. In an formulaic approach, we generalize the concept of the Shapley value for cooperative games to the class of partially defined cooperative games. In an axiomatic approach, several allocation method characterization theorems are given utilizing linearity, symmetry, formulation independence, subsidy freedom, and monotonicity properties. A third approach is to compute the solution of a "central" fully defined game among all possible fully defined games consistent with the given partially defined game. Relationships among these different approaches are explored.
This presentation reviews and builds upon the results reported in my paper "Linear and symmetric allocation of methods for partially defined cooperative games," International Journal of Game Theory (2001) 30:377-404. This is the paper that is uploaded with this abstract.

George Hwang

Shih Hsin University

The War and Peace between the Snipe and the Clam  [PDF]

Will the possibility of a stalemate and the consequent predation by a common enemy (fisherman) bring about peace between the two rivals (snipe and clam) at war? According to a simple game-theoretic model of contest, the answer is no. If the equilibrium without a fisherman is a war, then a possible attack by a fisherman will not bring about peace in equilibrium. The fisherman effect on the war effort can be positive if war effort reduces the probability of stalemate. Furthermore, the fisherman can destroy a previously equilibrium state of peace. If the initial equilibrium is not peace, at least one contestant will fight harder in response to an increase in the probability of the fisherman’s arrival or the strength of the fisherman.

Wei-Torng Juang

Academia Sinica

A Folk Theorem on Equilibrium Selection  [PDF]

- joint work with Hamid Sabourian

We studies behaviors of evolutionary systems in the long run. In a system where players are randomly matched to play an NN game in each period and players are allowed to revise their rules, we obtain a general result on equilibrium selection. For any arbitrarily prescribed stage game equilibrium, we can always add one rule in each population of the system such that the newly added rule combination is universally dominant and can support the given equilibrium. Therefore, a folk theorem results and any Nash equilibrium of the stage game can be selected in the long run.

Sham Kakade

University of Pennsylvania

The Economics of Social Network  [PDF]

- joint work with Michael Kearns, Luis Ortiz, Robin Pemantle, and Siddharth Suri

In an attempt to explain a number of apparently universal statistical properties of natural social and economic networks, many authors have recently proposed a rich family of probabilistic generative models for social network formation. We have recently introduced a graph-theoretic representation for classical mathematical economic models. This paper studies the marriage of these two lines of inquiry: we examine the network effects that social network models (such as preferential attachment) introduce into classical economic settings. Our findings are a mixture of theoretical results and large-scale simulations that have been made possible only by algorithmic advances of the last two years.

Adam Kalai

University of Chicago

On Program Equilibrium and Metagames  

- joint work with Ehud Kalai

Tennenholtz (2004) introduces the notion of program equilibrium to study games in which each of n-players submits a computer program to play a simultaneous move game G on his behalf. He proves a semi folk theorem: every individually rational payoff that can be supported by independent mixed strategies of G is obtained at some (pure strategy) equilibrium of the program submission game.
Somewhat surprisingly, with (independent) mixed strategies a full folk theorem holds: every individually rational payoff that can be supported by a correlated mixed strategy of G is obtained at some mixed strategy equilibrium of the program submission game. Moreover, this is true despite the fact that the realized selected programs are informed of the identity of the opponents’ realized programs before deciding how to play.
To illustrate the above, we introduce a notion of a metagame and relate it to other areas of economics and game theory.

Vladislav Kargin

Cornerstone Research

Theory of Quantum Games  [PDF]

Modern technological developments allow manipulating individual quantum states. The quantum environment requires changing the ways in which the theories of statistics, communication, or decision-making are applied to reality. This paper explains how the methods of game theory can help in this task. It reviews the range of applicability of classical game-theoretical results, such as the minimax theorem and the equilibrium existence, in the quantum context. It also poses some foundational questions about the role of quantum entanglement in coordination games with remote players.

Hyunho Kim

Stony Brook University

A Location Model with Preference for Variety  [PDF]

- joint work with Konstantinos Serfes

We propose a new location model where consumers are allowed to make multiple purchases (i.e., one unit from each firm). This model fits many markets (e.g. newspapers, credit cards, scholarly journals, subscriptions to TV channels, etc.) better than existing models. A common feature of these markets is that some consumers are loyal to one brand, while others consume more than one product. Our model yields predictions consistent with this observation. Moreover, it restores Hotelling's Principle of Minimum Differentiation, by generating an equilibrium in pure strategies and with a linear transportation cost, where firms are located at the center and charge prices above marginal cost.

Jeff Kline

Bond University

Modeling a Player's Perspective II: Inductive Derivation of an Individual View  [PDF]

- joint work with Mamoru Kaneko

This is a sequel to our investigation of a player's perspective. We consider the inductive derivation of a player's individual view from his accumulated memory. Formally, an individual view is a pair of a subjective game description (information protocol) and a memory function. We first give an inductive derivation of this view based strictly on his accumulated memories. However, this derived view may fail to satisfy certain basic axioms. We give conditions on the memory function to guarantee that the derived view satisfies these basic axioms. Next, we proceed in another direction by allowing a player to add new elements in the construction of his view. We show that this general procedure results in an individual view that satisfies the basic axioms and respects his accumulated memories. There is no guarantee, however, that the constructed view will match the truth, even if the player's memory is perfect. We comment on the behavioral use of an inductively derived protocol and also on the famous examples of Plato's "Analogy of the Cave" and Piccione-Rubinstein's "Absentminded Driver".

Pierfrancesco La Mura

Leipzig Graduate School of Management

Computation of Strategic Equilibria in Game Networks  [PDF]

Recently, the subject of structured representations (La Mura 2000, Koller and Milch 2001, Kearns et al, 2001) for multi-agent decision problems has attracted considerable interest at the intersection of game theory and artificial intelligence. In my talk, I will discuss a recently introduced class of graphical representations for multi-agent decision problems, Game networks (G nets). Compared to standard game-theoretic representations, such as strategic and extensive forms, G nets are more structured and often significantly more compact, as both probabilities and utilities enjoy a modular representation. More fundamentally, G nets provide a computationally advantageous framework for strategic inference, as one can exploit conditional probability and utility independencies to reduce the complexity of the inference process.
An important aspect of multi-agent reasoning is the identification of some or all of the strategic equilibria in a game. For all but the simplest classes of games this is a computationally demanding task, which can in principle be alleviated by making more efficient use of the information contained in the game structure. I will present polynomial homotopy continuation methods for the computation of strategic equilibria which can exploit strategic separabilities in the G net representation in order to simplify computations. Specifically, I will describe a path-tracking method which identifies a unique sample equilibrium, and one which identifies all equilibria.
Time permitting, I will also present an extension of G nets to the case of non-linear risk preferences.

Jaehee Lee

Penn State University

Standard setting, compatibility externalities and R&D  [PDF]

This paper considers a R&D contest between two firms who canchoose to concentrate their research in one of two avenues or approaches. In the R&D contest, firms compete in two stages. In the first stage, firms choose which approach they will investigate, after which they endogenously select optimal effort level given firms’ choice of approach in the second stage. There are “compatibility externalities” if they choose the same approach. However, there is also greater probability of simultaneous discovery which may cause harmful results to both firms. We examine 3 situations with different payoff structures by considering the Bertrand R&D game, the equal sharing R&D game and the research alliance game. The equilibrium avenue choice in each game depends on the size of compatibility externality and it may exhibit too much differentiation or too much duplication. The equilibrium effort choice conditional on duplication is inefficient except in the Bertrand R&D game, while the equilibrium effort choice is efficient when firms choose different research avenues. The result of the excess differentiation and the efficient investment choice in the Bertrand R&D game suggest that the lump-sum investment subsidy may need to be implemented in the US wireless mobile phone industry to reduce inefficiency involved in excess differentiation without distorting efficient investment choice.

Justin Lenzo

Boston University

Correlated Equilibrium in Evolutionary Models with Subpopulations  [PDF]

- joint work with Todd Sarver

We study a version of the multipopulation replicator dynamics, where each population is comprised of multiple subpopulations. We establish that correlated equilibrium is a natural solution concept in this setting. Specifically, we show that every correlated equilibrium is equivalent to a stationary state in the replicator dynamics of some subpopulation model. We also show that every interior stationary state in a subpopulation model is equivalent to a correlated equilibrium. We find that any state that is Lyapunov stable or the limit of an interior solution is equivalent to a correlated equilibrium. We also provide an example with a Lyapunov stable limit state that is equivalent to a correlated equilibrium outside the convex hull of the set of Nash equilibria. Finally, we prove that any subpopulation setting in which the matching distribution is a product measure leads to equivalence with Nash equilibrium.

Kevin Leyton-Brown

University of British Columbia

Action-Graph Games, and an Algorithm for Computing their Equilibria  [PDF]

- joint work with Navin Bhat

General-purpose algorithms for computing Nash equilibria are only practical for relatively small numbers of agents; however, many games of interest have very regular structure which is untapped by the general algorithms. We present action-graph games (AGGs), a fully expressive, structured game representation which can compactly express both strict and context-specific independence between agents' utility functions, yielding more efficient computation of equilibria. Actions are represented as nodes in a graph G, and the payoff to an agent who chose the action s depends only on the numbers of other agents who chose actions connected to s. We present algorithms for computing both symmetric and arbitrary equilibria of AGGs using a continuation method. By exploiting game structure, we achieve exponential speedup in the worst-case for the bottleneck step of computing the Jacobian of the payoff function. When the in-degree of G is bounded by a constant and the game is symmetric, the Jacobian can be computed in polynomial time.

Duozhe Li

Boston University

Bargaining with History Dependent Preferences  [PDF]

We study perfect information bilateral bargaining game with an infinite alternating-offers procedure, in which we add an assumption of history dependent preference. A player will devalue a share which gives her strictly lower discounted utility than what she was offered in earlier stages of the bargaining. Under the strong version of the assumption, we characterize the essentially unique subgame perfect equilibrium path, which involves considerable delay and efficiency loss. We give different interpretations of the assumption. The assumption can also be weakened under the interpretation of loss aversion. We provide a sufficient condition under which the feature of the equilibrium from strong assumption remains.

Zhen Liu

Stony Brook University

An extended No-Bet theorem  [PDF]

Given two players holding a common prior and distinct information partitions, the No Bet theorem says that when at a state it is common knowledge that one’s conditional expectation is no less than a certain number but the other one’s is not greater than it, their conditional expectations must be the same. The extended theorem generalizes the result by taking away the separating number which is sometimes not available in practice. We also generalize the extended theorem to the case where priors are heterogeneous, and find it can not be generalized with nonpartitional information structures. As the applications, we show if the ranking of each player’s expectation, or just the identity of the highest(lowest) one is common knowledge, players must agree in the logic of the extended theorem, but may not agree under the original No Bet theorem.

Xiao Luo

McGill University

Towering over Babel: Worlds Apart but Acting Together  [PDF]

- joint work with Yossi Greenberg and Sudheer Gupta

We offer a formal framework that enables the analysis of the fascinating phenomenon whereby individuals who “live in different worlds” agree to a shared course of action. We define the notion of a course of action which, unlike a (behavioral) strategy profile, does not require a complete specification of actions in every contingency. We introduce a new solution concept: a mutually acceptable course of action (MACA). Loosely speaking, an MACA consists of actions that “make sense” in every player’s (perception of the) game, and every player takes into account that all players are rational. In particular, an MACA can be viewed as an (incomplete) contract or a social norm that free rational individuals would be willing to follow for their own diverse reasons. We show that by varying the degree of completeness of the underlying course of action, the concept of an MACA can be related to many of the commonly used solution concepts, such as perfect equilibrium, perfect Bayesian equilibrium, (rationalizable) self-confirming equilibrium, and rationalizable outcomes. Thus, our framework also serves to unify “game-theoretic” and “incomplete contracts” viewpoints.

Jinpeng Ma

Rutgers University - Camden

Jobless Recovering and Equilibrium Involuntary Unemployment with Simple Efficiency Wage Model  [PDF]

The U.S. economy had experienced the "jobless recovering" after the 1990-1991 and 2001 recessions, which has been constantly puzzling the economists, market analysts, and policymakers. This paper uses a simple hiring game in an effciency wage model framework to resolve that puzzle. Our effciency wage model emphasizes the importance of the local unemployment rate, which is endogenously determined by firms' hiring decision at a symmetric Nash equilibrium. Our model has a new feature such that nonzero steady involuntary unemployment at equilibrium may coexist with an effciency wage that stays below the market-clearing wage. Moreover, we show how it is possible to use our model to study income inequality as a result of skill-biased technical change, inter-industry wage differentials, and skill wage premiums. We also demonstrate how it is possible to derive the wage curve (Blanch ower and Oswald (1994)) as an equilibrium locus of our model.

Virginie Masson

University of Pittsburgh

Neighbors versus Strangers in a Spatial Interaction Model  [PDF]

In this paper, we study an evolutionary model of spatial interaction among individuals with different information. Time is discrete and in each period, individuals from a finite population are randomly paired to play a 2×2 symmetric coordination game. Each individual knows the structure of the game.
The first innovation of this paper is the spatial structure that differs from the ones presented by Ellison (1993) and Blume (1993). The notion of neighborhood which we use is much wider: individual j is a neighbor of individual i if individual i has access to all past plays and payoffs of individual j, for a finite number of periods. The matching can give rise to three situations: (i) both individuals are neighbors, (ii) both individuals are strangers, (iii) one considers the other as a neighbor whereas the latter considers the former as a stranger.
Another innovation of this paper is that the decision rule used by the individuals is contingent to the opponent. When an individual faces one of his neighbors, he draws a sample from his opponent’s past action, and plays his best reply to the sample, as in Young (1993, 1998). In the case he faces a stranger, he draws a strategy-payoff pairs sample from individuals that belong to his neighborhood and plays the strategy that paid the highest payoff, as in Josephson and Matros (2001). The intuition behind this decision rule is the following: when an individual i faces someone from his neighborhood, he may want to try to anticipate his opponent action, since he can access his opponent’s past decisions and performances; but when individual i faces a stranger, he has no information about his opponent and may want to ask around in order to imitate his most successful neighbor.
In any 2×2 symmetric coordination game that contains both, risk dominant and Pareto efficient equilibria, we prove that the Pareto efficient equilibrium is always selected. This contrasts with the result obtained by Ellison (1993), Young (1993) and Kandori, Mailath and Rob (1993), but is consistent with Matros (2004). By simulating different population structures, we also show that the speed of convergence is positively correlated with the numbers of imitators.

Alexander Matros

University of Pittsburgh

Evolutionary Learning with Multiple Decision Rules  

In this paper, a general evolutionary model is considered. My evolutionary framework with perpetual random shocks similar to Young (1998), but allows considering agents of different types: agents of the same type always use the same decision rule.
I show that the short-run prediction of the model is not optimal in general (if all decision rules are present in all populations). However, if an evolution process is driven by weakly rational decision rules - rules, which select rational decisions if all agents in the sample have also selected rational decisions, then such an evolutionary process in fact selects optimal outcomes. In other words, given mistake-free play, (short-run) outcomes are identical whether agents are constrained to employ the best-reply rule only; or they can use weakly rational rules. Corollaries of this result are the main results of Young (1998), Saez-Marti and Weibull (JET, 1999), and Matros (JET, 2003).
This paper also shows that: Given the possibility of mistakes, (long-run) outcomes are determined by “imitate the highest payoff” rule.

Bryan McCannon

Elmira College

Party Formation and Platform Selection with Binary Issues: Can the Minority Win?  [PDF]

This paper considers the formation of political parties and their choice of platform. In a representative democracy, individuals vote for the party that represents their preferred position on the issue and the party with the most votes wins the election. The question raised here is whether parties align themselves so that the winner has chosen a platform that is preferred by only a minority of the population. I show in a model with binary issues that the minority platform can win the election. There exist equilibria where a third party enters with the platform preferred by the majority of the population splitting the votes. This allows the party with the minority platform to win. Furthermore, under certain environments, it is the only outcome that exists. As a consequence, restricting entry to the political process is beneficial when it stops entrants from causing the minority position to win.

Soiliou Namoro

University of Pittsburgh

Economic Incentives of the Olympic Games  [PDF]

- joint work with Alexander Matros

We provide a game-theoretic analysis of countries’ strategic allocations of resources to different sports and athletes performance at Olympic Games. Individuals are assumed to face opportunity costs of spending efforts to become elite athletes and countries are assumed to be medal number maximizers. We test the predictions of the model using Olympics data covering eleven Olympic Games (1960-2000).

Ricardo Nieva

Concordia University

ANC Analytical Payoff Functions for Networks with Endogenous Bilateral Long Cheap Talk  [PDF]

For any three-agent cooperative game, we extend the Aumann-Myerson (1988) Shapley (1953) solution by allowing non-myopic pairs of agents to propose simultaneously both payoffs and future bilateral coordination schemes . For a link to form double proposals have to coincide and the sum of indidual payoff proposals has to be equal to the sum of both agents's Myerson values in the prospective graph implied by the added link. For equilibrium selection, we derive a "two-agent" bargaining game from a strategic form game with also double proposals but with induced credible expected payoffs. Bargaining is solved implicitly with a smoothed Nash (1950) demand game. Loosely speaking, one agent reminds to play according to earlier bilateral discussions, say no further linking, the other one obeys and thus, there is credibly bilateral coordination as long it is over subgame perfect equilibrium outcomes of the multistage game with just payoff proposals. We proof existence and uniqueness and refer to a companion paper for the analytical formulas. The outcome is always efficient. For strictly superadditive games, we only predict two link graphs. If a one link or coalition of two agents forms then the colluded can achieve what the grand coalition can.

Noa Nitzan

Hebrew University

Non-Genericity of Strict Correlated equilibrium  [PDF]

There have been only few attempts to refine the solution concept of correlated equilibria. In 1997, Mayerson came up with the concept of elementary games: A game is elementary if it has some correlated equilibrium for which all the incentive constraints are satisfied as strict inequalities. The current paper examines the related but distinct concept of strict games. A game is strict if it has some correlated equilibrium, for which all the incentive constraints regarding strategies with positive probability hold as strict inequalities. It proves that strictness is not generic.

Eugene Nudelman

Stanford University

Understanding Game-Theoretic Algorithms: The Game Matters  [PDF]

- joint work with Yoav Shoham, Jennifer Wortman, and Kevin Leyton-Brown

We present GAMUT, a new suite of game generators designed for testing game-theoretic algorithms. We highlight the importance of using comprehensive test data by benchmarking existing algorithms. We show surprisingly large variation in algorithm performance across different sets of games for two widely-studied problems in game theory.

Mandar P. Oak

Williams College

Approval Voting with Endogenous Candidates  [PDF]

- joint work with Arnuad Dellis

We present a formal model of political competition under approval voting which allows for endogenous candidate entry. Our analysis yields a number of novel insights. First, we develop a notion of sincere voting behavior under approval voting, called relative sincerity. We then show that the relatively sincere voting behavior is consistent with the strategic calculus of voting. Second, we show that in a one-dimensional model with distance preferences, equilibria in relatively sincere strategies and without spoiler candidates always generate outcomes close to the median voter. Moreover, approval voting satisfies Duverger’s Law in the sense that there are at most two winning positions! Finally, we extend our analysis to arbitrary policy spaces. In the general setting, approval voting is shown to be susceptible to the same kinds of problems as the plurality rule, such as the possibility of non-majoritarian outcomes, failure to elect the Condorcet winner and existence of spoiler candidates.

Sergio O. Parreiras

University of North Carolina

All-play auctions with endogenous asymmetries  [PDF]

We study N-bidders, asymmetric all-pay auctions under incomplete information. First, we solve for the equilibrium of a parametric model. Each bidder's valuation is independently drawn from a uniform [0,alpha_{i}] where the parameter alpha_{i} may vary across bidders. In this game, asymmetries are exogenously given. Next, a two-stage game where asymmetries are endogenously generated is studied. At the first stage, each bidder chooses the level of an observable, costly, value-enhancing action. The second stage is the bidding sub-game, whose equilibrium is simply the equilibrium of the, previously analyzed, game with exogenous asymmetries. Finally, natural applications of the all pay-auction in the context of political lobbying are considered: the effects of excluding bidders, as well as, the impact of caps on bids.
All-pay auctions under perfect information are well understood, see for instance, Baye et. al. (1993, 1996) and Che and Gale (1998). The main features of the equilibrium are: Only high valuation bidders, those bidders who have the highest or the second-highest valuation, participate. Low valuation bidders do not participate; in equilibrium, they bid zero. The equilibrium is unique provided there are only two high valuation bidders. Otherwise, there is a continuum of equilibria, which are not revenue equivalent. Also, two important result results of the perfect information model are: 1) The Exclusion Principle, which states that the seller revenue may increase if bidders with highest valuations are excluded from the auction; 2) Caps on bids may increase the seller revenue.
Amann and Leininger (1996) prove existence and uniqueness of the equilibrium for two-bidders, all-pay auctions under incomplete, independent information. Since their model restricts attention to the two-bidder case, it does not allow one to address the revenue effects of excluding bidders. One cannot address the question whether the Exclusion Principle holds true under incomplete information.
All-pay auctions under incomplete information, with many bidders having symmetric, affiliated information were studied by Krishna and Morgan (1997). The all-pay auction revenue dominates the first-price auction, but it is revenue dominated by the War of Attrition. Because their model does not allow for asymmetries among bidders, one cannot address the question whether the Exclusion Principle holds true under incomplete information.
The novelty of this paper is that it presents a model of incomplete information, N-bidders, asymmetric all-pay auction. Although, the model is parametric, valuations are uniformly distributed, the first section presents a general model; useful to compute the equilibrium for other parameterizations.

Marcin Peski

Northwestern University

Hierarchies of Belief and Interim Rationalizabilty  [PDF]

- joint work with Jeffrey Ely

For the purposes of determining what is rationalizable for a player in a game of incomplete information, conventional hierarchies of belief are incomplete as descriptions of the players' information. We show this by example and then investigate what is essential about a player's information to identify rationalizable sets in any game. We do this by constructing the universal type space for rationalizability and characterizing the types in terms of their beliefs. Infinite hierarchies of beliefs over conditional beliefs, what we call Δ-hierarchies, are what turn out to matter. We show that any two types in any two type spaces have the same rationalizable sets in all games if and only if they have the same Δ-hierarchies.

Ryan W. Porter

Stanford University

Simple Search Methods for Finding a Nash Equilibrium  [PDF]

- joint work with Eugene Nudelman and Yoav Shoham

We present two simple search methods for computing a sample Nash equilibrium in a normal-form game: one for 2-player games and one for n-player games. We test these algorithms on many classes of games, and show that they perform well against the state of the art-- the Lemke-Howson algorithm for 2-player games, and Simplicial Subdivision and Govindan-Wilson for n-player games.

Marco Scarsini

Universita di Torino

A Folk Theorem for Minority Games  [PDF]

- joint work with Jerome Renault and Sergio Scarlatti

We study a particular case of repeated games with public signals. In the stage game an odd number of players have to choose simultaneously one of two rooms. The players who choose the less crowded room receive a reward of one euro (whence the name “minority game”). Between the stages, only the current majority room is publicly announced. We show that in the infinitely repeated game any feasible payoff can be achieved as a uniform equilibrium payoff, and as an almost sure equilibrium payoff. In particular we construct an inefficient equilibrium where, with probability one, all players choose the same room at almost all stages. This equilibrium is sustained by punishment phases which use, in a unusual way, the pure actions that were played before the start of the punishment.

Paul Schweinzer

University of Bonn

Dissolving a common value partnership in a repeated "queto" game with incomplete information on both sides  [PDF]

We analyse a common value, alternating ascending bid, first price auction as a repeated game of asymmetric incomplete information on both sides where the bidders own the object auctioned in equal shares. The object is indivisible and of common value. Consequently an owner can accept her partner’s offer (by quitting the repeated game) or can veto a proposed settlement by submitting an own offer. We characterise the equilibrium map of this game and discuss its properties.

Abhijit Sengupta

Stony Brook University

Inducing Efficiency in an Oligopolistic Industry with Increasing Returns to Scale  [PDF]

- joint work with Yair Tauman

We consider a Cournot Oligopoly market of firms possessing increasing returns to scale technologies (which may not be identical). It is shown that an external regulating agency can increase total social welfare without running a deficit by offering to subsidize one firm an amount which depends on the output level of that firm and the market price. The firms bid for this contract, the regulator collects the highest bid upfront and subsidizes the highest bidding firm. It is shown that there exists a subsidy schedule such that (i) The regulator breaks even (ii) The subsidized firm obtains zero net profit and charges a price equal to its average cost (iii) Every other firm willingly exit the market and (iv) Market price decreases, consumers are better off and total welfare improves.

Jeff Shamma


Feedback control for learning in games  [PDF]

- joint work with Gurdal Arslan

This talk presents an overview of recent results that adopt a “feedback control” perspective in repeated matrix games. In particular, it is shown how the introduction of feedback control principles can result in convergence to a mixed strategy Nash equilibrium even for previously nonconvergent examples, such as the Shapley and Jordan games.
The particular notion used from feedback control models is “derivative action”. Derivative action is a very commonplace tool in the design of feedback controllers. A typical feedback controller responds to observations of an “error signal”, i.e., a discrepancy between desired behavior and actual measured (feedback) behavior. The implementation to learning in games requires that a player uses available observations and their derivatives in adaptively updating player strategies.
We consider the usual set-up in repeated matrix games in which multiple decision making players adjust their strategies according to observations of each other's actions. The game is noncooperative in that each player may have its own objective/utility function, and these objectives are not shared among players.
We will discuss how the introduction of derivative action can enable convergence to mixed strategy Nash equilibrium in both continuous-time and discrete-time settings. We will also discuss the “utility measurement” scenario, in which player actions are not observable, but only individual stage-by-stage rewards are available.

Marilda Sotomayor

Universidade de São Paulo

The competitive multiple-partners assignment game  [PDF]

Multiple-partners assignment game is the name used by Sotomayor (1992, 1999) to describe the cooperative approach to the many-to-many matching market with separable and additive utilities. The competitive approach explores a new way of studying this game. The question is to know whether competitive equilibria always exist, and if so, how they can be obtained. One confirms their existence and proves that the minimum competitive equilibrium price, as well as the two optimal stable outcomes, can be obtained through dynamic mechanisms that generalize the auction of Demange, Gale and Sotomayor (1986). Several properties of interest to the cooperative and competitive markets are derived.

Raphael Soubeyran


Political Alternation: A Suggested Interpretation  [PDF]

- joint work with Pascal Gautier

This paper proposes an explanation for the instability of parties in power in democratic regimes. We consider a dynamic political game with two opportunistic parties/candidates, different in the sets of programs they can propose. Citizens have political preferences defined over couples of durables public goods. We show that political alternation is more likely to happen when (i) political competition is polarized, (ii) median voter is moderate, (iii)and public goods have a low depreciation rate. We then suggest several specifications for parties motivations and study how they affect alternation. Finally, we discuss simulated political histories.

Amparo Urbano

Universidad de Valencia

Markets with Complementarities and Mixed-Bundling Pricing  [PDF]

- joint work with Ivan Arribas

We show the existence of subgame perfect Nash equilibrium prices in two market structures with some specific geometry-based complementarities. Namely, markets of compatible systems and spatial markets with interval-based complementarities.
Arribas and Urbano (2003) analyze a model with price competition among n multiproduct firms and one representative buyer, characterized by her willingness to pay -in monetary terms- for every subset of products. They show that a mixed bundling subgame perfect equilibrium outcome always exists and it is efficient in the sense of maximizing the social surplus. The set of subgame-perfect Nash equilibrium outcomes is equivalent to integer-valued solutions of the linear relaxation of a package assignment problem. However, the existence of equilibrium outcomes for an m-buyers' model under general value functions is hardly guaranteed (see also Bikhchandani and Ostroy, 2002, for the Walrasian Equilibrium set up).
We offer results in models with complementaries, which hinges upon market structures as well as on the buyers' value functions. A market of compatible systems is defined as a set of consumers and a set of firms, where each firm produces two complementary components of a system, which are substitutes of the two products produced by its rival firms. Each consumer is characterized by a value function over any system, representing her total willingness to pay for any system. Each firm i set prices for its two products however, it can offer both of them as a bundle for a special price. In spatial markets with interval-based complementarities, there is a total ordering among products, and consumers’ preferences are only positively defined for consecutive products. As above a consumption’s set is pure if all products in the interval belongs to only one firm and it is mixed otherwise.
The two market structures can be modeled as an integer package assignment problem, where the set of restrictions defines a polyhedron belonging to the class of polymatroids. This guarantees an efficient integer partition of the goods. Moreover, if the buyers' value functions satisfy a “compatibility assumption”, then the existence of the dual of an associated linear programming problem providing the equilibrium (mixed-bundling) prices is also assured. The equilibrium assignment is efficient since it maximizes the social surplus and may consist of both pure and mixed consumption sets.

Jose Vila

Universidad de Valensia

Communication through Noisy Channels  [PDF]

- joint work with Penelope Hernandez, Amparo Urbano

We study two-player coordination games in which one player is better informed than the other and where the costs of miscoordination are different in distinct states of nature. There are two players and several states of the world and a game is associated to each state. Nature chooses a state, and hence a game to be played, using a commonly known probability distribution and informs only to player 1 of its choice. Then, the informed player transmits his private information to the uninformed one, trough a noisy channel, and actions are chosen and payoffs realized.
We assume that there is a unique optimal play in each game, and that players communicating through a discrete memoryless noisy channel, can use it repeatedly n times. A discrete channel is a system consisting of an input alphabet X and output alphabet Y, and a probability transition matrix p(y|x), that expresses the probability of observing the output symbol y, given that the symbol x was sent. Our aim is to analyze and characterize the set of achievable equilibrium outcomes for a given channel and a given finite number of ''uses'' (repetitions) of the channel. We bound the efficiency loss of noisy communication in terms of the properties of the noisy channels such as the transition probability p(y|x) and the channel capacity.
We design a noisy communication protocol which consists of a codification of the states of nature into a channel input sequences, a noisy channel, and a decodification rule mapping channel outputs into the uninformed player's actions. The noisy channel transforms the input sequence into an output sequence that is random but has a distribution that depends on the input sequence. From the received output sequence, the uninformed player attempts to recover the transmitted message. Each of the possible input sequences induces a probability distribution on the output sequences. Since two different input sequences may give rise to the same output sequence, the inputs are confusable. The informed player wants to choose a ''non-confusable'' subset of input sequences so that with high probability, there is only one highly likely input that could have caused that particular output. The number of possible decodification functions is exponential with respect to n, since it is given by the number of partitions of the k subsets associated to each element of the state space, over the set of output sequences of length n. To cope with this problem, we use the Typical Set methodology, which enables to partition the set of sequences into two sets, the ''typical set'', where the sample entropy is close to the true entropy and the non-typical set, which contains the other sequences. The codification mapping consists of a random choice of a sequence of signals, for each state of nature, in the typical set. Then, we will decode a channel output as a particular state if the input sequence is ''jointly typical'' with the received output sequence, or in other words, if both sequences are highly probabilistically related.
Although the jointly typical decoding is suboptimal for a finite number of repetitions, it is a less complex way (polynomial with respect to n) to design noisy communication protocols than that of checking all feasible codifications to find the optimal one. However, being suboptimal, it still allows transmitting enough information to achieve coordination outcomes. Moreover, the Typical Set approach generates a deterministic decodification rule and thus, given a channel and a number of repetitions, we can design a communication protocol and characterize the equilibrium outcomes.

George Waters

Illinois State University

An Evolutionary Game Theory Approach to Rational Expectations  [PDF]

- joint work with William R. Parke

Multiple martingale, or bubble, solutions exist when expectations about future values of endogenous variables enter a model under rational expectations. Such solutions reproduce bubble behavior, as seen in asset markets for example, and have implications about the nature of rational expectations in many contexts. Economists often select a unique rational expectations solution from the class of martingale solutions using a principle such as minimum state variables. In contrast, we allow agents to choose from different forecasts based on bubble solutions. Evolutionary game theory selection dynamics describe agents’ choices of forecasts using squared forecast errors as payoffs, and we study whether agents’ expectations converge to a unique, fundamental solution. Under the commonly studied replicator dynamic, agents come to agree on a fundamental forecast. However, under convex monotonic selection dynamics, when agents switch more rapidly to forecasts with lower errors, bubble solutions can play an important role in the evolution of the model. These results show how bubbles can arise and raise doubts about focusing on a unique rational expectations solution.

Quan Wen

Vanderbilt University

Wage Bargaining under the National Labor Relations Act  [PDF]

- joint work with Jesse A. Schwartz

Sections 8(a)(3) and 8(a)(5) of the National Labor Relations Act prevent a firm from unilaterally increasing the wage it pays the union during the negotiation of a new wage contract. To understand this regulation, we study a counterfactual negotiation model where the firm can temporarily increase compensation to its employees during wage negotiations. Comparing this to the case where the firm does not have this option, we show that the firm may strategically increase the union's temporary wage to upset the union's incentive to strike, decreasing the union's bargaining power, and shrinking the set of permanent wage contracts that may arise in a perfect equilibrium. As the union becomes more patient, the best possible equilibrium contract to the union gets worse. In the limit, the uniqueness and hence the full efficiency of the perfect equilibrium are restored. We also demonstrate that allowing the union to refuse the firm's temporary compensation does not affect the set of perfect equilibrium outcomes.

Andreas Westermark

Uppsala University

Worker Substitutability and Bargaining Delays  [PDF]

We analyze a bargaining model with imperfect information where a firm bargains with more than one worker. We find that equilibrium delay decreases in the substitutability of workers. The reason is that a decrease in substitutability increases both wages and wage differentials between high and low productive firms. Then, to ensure separation, low productive firms must delay agreement longer to deter the high productive firm from mimicking. We also analyze how delay depend on the number of workers.

Chun-Hsien Yeh

Academia Sinica

An alternative characterization of the nucleolus in airport problems  [PDF]

We consider the problem of sharing the cost of a public facility among agents who have di®erent needs for it. We show that the nucleolus is the only rule satisfying e±ciency, equal treatment of equals, last-agent cost additivity, and last-agent consistency. Our result reveals the importance of the last agent in characterizing the rule and generalizes that of Potters and Sudholter (1999).

Andriy Zapechelnyuk

Stony Brook University

Regret-Based Adaptive Dynamics with Finite Memory  [PDF]

We investigate a simple adaptive procedure of playing a repeated game proposed by Hart and Mas-Colell (2000), under the assumption that players have limited memory. We show that if a game has ``block'' structure, the adaptive play becomes absorbed in one of the blocks, and if a game is ``weakly acyclic'' in its strictly better-reply graph, the adaptive play converges almost surely to a Nash equilibrium in pure strategies. Besides, we show that, regardless of game structure, the adaptive play converges to the set of epsilon-correlated equilibria, where epsilon converges to zero as memory length goes to infinity.

Back to International Conference