14th International Conference on Game Theory at Stony Brook


Please note: Many papers contain preliminary and possibly incomplete results. Please contact the author(s) if you find any errors, and do not cite without their permission. The full author list is found in each paper.

Missing numbers are withdrawn papers where the presenter cannot attend the conference.

Jump to abstract:  1  2  3  4  5  6  7  8  9   10  11  13  14  15  16  17  19   20  21  22  23  24  25  26  27  29   30  31  32  36  40  41  43  44  45  46  49   50  53  54  55  59   60  61  62  63  64  65  67  69   72  73  75  76  77  78  79   80  82  83  84  85  86  87  88  89   90  91  92  93  94  95  96  97  98  99   100  102  103  104  105  106  107  

1   Josune Albizuri:  Coalitional Configurations and Value

In this work we suppose players in a cooperative game with transferable utility are joined in coalitions and form any collection of coalitions. In this framework we define and characterize a value, which will be called configuration value. When players form a partition of the set of players this value coincides with the Owen value (1977), so it is a generalization of the Owen value.

Talk time: Thursday 24 July, 3:00-3:25     Paper with full author list: Stony03.pdf (8 kB)

2   Jose Apesteguia:  Blowing the Whistle

Leniency clauses, offering cartelists legal immunity if they blow the whistle on each other, is a recent anti-trust innovation. The authorities wish to thwart cartels and promote competition. This effect is not evident, however; whistle-blowing may enforce trust and collusion by providing a tool for cartelists to punish each other. We examine the impact of leniency law, and other rules, theoretically and experimentally.

Talk time: Monday 21 July, 3:35-4:00     Paper with full author list: BlowingWhistle.pdf (210 kB, revised June 4)

3   Jabier Arin:  Egalitarian Distributions for Coalitional Models: The Lorenz Criterion

The paper presents a framework where the most important single-valued solutions in the literature of TU-games are jointly analyzed. It also suggests that similar frameworks can be used in other coalitional models.

Talk time: Thursday 24 July, 3:35-4:00     Paper with full author list: arin.pdf (251 kB)

4   Goksel Asan:  On the Stability and Optimality of Coalitions Voluntarily Providing Impure Public Goods

We analyze the coalition formation in a society where every coalition produces an excludable but possibly impure public good by the voluntary contributions of its members. Agents are allowed to make individual moves only while entry to and exit from a coalition is free. In such a world and under the absence of crowding effects, the set of stable and efficient coalition structures coincide with the grand coalition. On the other hand, this positive result about the stability-efficiency equivalence collapses when the public good is impure. In fact, there may be economies where the set of stable and efficient coalition structures are disjoint. However, tightening the membership property rights by requiring the consent of all agents affected by an individual move ensures that every efficient coalition structure is stable, though the converse need not be true.

Talk time: Friday 25 July, 10:15-10:40     Paper with full author list: AsanSanversbgt.pdf (106 kB)

5   Siddhartha Bandyopadhyay:  Party Formation and Coalitional Bargaining in a Model of Proportional Representation

We study a game theoretic model of a parliamentary democracy under proportional representation. In our model, 'citizen candidates' form parties prior to the election, voting takes place and then governments are formed. If no single party has an absolute majority, coalition governments may emerge and we study the underlying coalition building process. The type of government that is formed in equilibrium depends on the parties' seat shares, the size of the rents that ruling parties can extract from holding office and their ideologies. We show that, depending on the relative magnitudes of these factors, a variety of coalition governments may result. Coalitions may be minimal; each member of the coalition is necessary to retain the majority or may contain some redundant parties. Moreover, coalitions may be comprised of parties that are not adjacent in terms of their ideology, that is, there may be a coalition government made up of leftists and rightists from which centrists are excluded. We then look at how the outcomes of the coalition formation game affect the incentives for voter groups to strategically form parties. We compare the results of party formation under proportional representation with that under the plurality rule. We show, in particular, that Duverger's hypothesis that proportional representation leads to more political competition than does the plurality rule may not hold. Our model explains the diversity of electoral outcomes observed empirically under proportional representation.

Talk time: Thursday 24 July, 10:50-11:15     Paper with full author list: revisingdraftpr.pdf (301 kB)

6   Bradley Belsky:  Optimization Using Weighted Fictitious Play

Fictitious play is a model traditionally used to describe learning. Players in a game assume that their opponents have a fixed, but unknown mixed strategy. At each stage, each player plays their best strategy assuming that every other player uses as their mixed strategy the empirical distribution of their past plays. A recent development of fictitious play is its use as an optimization heuristic. The belief distributions from the fictitious play heuristic converge to the set of Nash Equilibrium, which we view as a local optimum.
In this paper we investigate a modification to the fictitious play optimization heuristic. When calculating the empirical distribution of each player using standard fictitious play, each stage is weighted equally. Players in a game have no initial knowledge of their opponents mixed strategies and are more likely to make strategic mistakes in earlier stages. As the game progresses, the player begins to learn their opponents mixed strategies as they converge to the set of Nash Equilibrium. This intuition leads us to believe that weighting later stages more than earlier stages when calculating the empirical mixed strategy of all players may lead to faster convergence.
This paper investigates truncating weighting schemes. In a truncating weighting scheme weights are assigned to each stages, however, at some point, the amount of weight assigned to each play will be fixed. Numerous truncating weighting schemes are investigated using randomly generated games of various sizes. We compare results of the different weighting schemes against standard fictitious play.

Talk time: Wednesday 23 July, 3:35-4:00     Paper with full author list: belsk-abs.txt (3 kB)

7   Gustavo Bergantińos:  The Consistent Coalitional Value

We introduce a value for NTU games with coalition structure. This value coincides with the consistent value for trivial coalition structures, and with the Owen value for TU games with coalition structure. Furthermore, we present two characterizations: the first one using a consistency property and the second one using balanced contributions' properties.

Talk time: Monday 21 July, 3:00-3:25     Paper with full author list: ntuccv.pdf (333 kB)

8   Ulrich Berger:  A General Model of Best Response Adaptation

I develop a general model of best response adaptation in large populations for symmetric and asymmetric conflicts with role-switching. For special cases, including the classical best response dynamics and Cressman's symmetrized best response dynamics, I show that the set of Nash equilibria is attracting for zero-sum games. For any finite two-player base game, if the populations are equally large, convergence to a Nash equilibrium in the base game implies convergence to a Nash equilibrium on the Wright manifold in the role game.

Talk time: Monday 21 July, 10:50-11:15     Paper with full author list: BergerUBRadapt.pdf (266 kB)

9   Ulrich Berger:  Fictitious Play in 2xn Games

It is known that every continuous time fictitious play process approaches equilibrium in every nondegenerate 2×2 and 2×3 game, and it has been conjectured that convergence to equilibrium holds generally for 2×n games. We give a simple geometric proof of this. As a corollary, we obtain the same result for the discrete fictitious play process.

Talk time: Tuesday 22 July, 3:35-4:00     Paper with full author list: fp2xnub.pdf (165 kB)

10   Steven Brams:  Voter Sovereignty and Election Outcomes

Voters are sovereign to the degree that they can express their approval for any set of candidates. While voter sovereignty is maximized under approval voting (AV), AV can lead to
- a plethora of outcomes, depending on where voters draw the line between acceptable and unacceptable candidates; and
- Condorcet losers and other lesser candidates, even in equilibrium.
But we argue that voters' judgments about candidate acceptability should take precedence over standard social-choice criteria, such as electing a Condorcet or Borda winner. Among other things, we show that
- sincere outcomes under all voting systems considered are AV outcomes, but not vice versa;
- a Condorcet winner's election under AV is always a strong Nash-equilibrium outcome but not under other systems; and
- outcomes that other systems cannot prevent can be prevented under AV.

Talk time: Tuesday 22 July, 3:00-3:25     Paper with full author list: Sovereignty.pdf (149 kB)

11   Yves Breitmoser:  Long-Term Equilibria of Repeated Consistently Competitive Games

The class of consistently competitive games canonically unifies Prisoner's Dilemmas, contests, auctions, and Bertrand competitions. If those games are repeated infinitely, the players have to negotiate about the strategies that are to be repeated infinitely. These negotiations, however, are perturbed by the possibility that players make defective proposals (defective proposals are sensibly not maintained in the long term). The opponents' defections have to be detected and retaliated. In this study, these aspects (negotiations and defections) are analyzed jointly, and (thus) a refinement concept for Folk theorem equilibria is introduced.

Talk time: Wednesday 23 July, 10:50-11:15     Paper with full author list: compgame.pdf (169 kB, revised June 20)

13   Eliane Catilina:  Absent-Minded Driver's Paradox: An Experiment

This paper searches for experimental evidence to the absent-minded driver's paradox posed by Piccione and Rubinstein (GEB, 1997a, P&R hereafter). Absent-mindedness is defined as a form of imperfect recall where a player is not able to recall if he/she has visited a decision node before and thus, is not able "distinguish between two histories on the same path" (P&R, p. 5).

Talk time: Monday 21 July, 3:00-3:25     Paper with full author list: absentminded.pdf (7 kB)

14   Archishman Chakraborty:  Seller Cheap Talk in Common Value Auctions

Sellers benefit on average from revealing information about their goods to buyers, but the incentive to exaggerate undermines the credibility of seller statements. When multiple goods are being auctioned, we show that revealing a complete or partial ordering of the different goods by value can be credible. Ordinal cheap talk of this form is not susceptible to exaggeration because it simultaneously reveals favorable information about some goods and unfavorable information about other goods. Any informative ordering increases revenues in accordance with the linkage principle, and the complete ordering is asymptotically revenue-equivalent to full revelation as the number of goods becomes large. These results provide a new explanation in addition to bundling, complementarities, and versioning for how a seller benefits from the sale of multiple goods.

Talk time: Monday 21 July, 3:35-4:00     Paper with full author list: sellercheaptalk.pdf (303 kB, revised July 9)

15   Alfredo Di Tillio:  Subjective Expected Utility in Games

A model of subjective expected utility in games is constructed in the spirit of Savage. First, the problem of establishing what is a state of the world for a player is solved: The result is a "universal space of acts", constructed hierarchically, where preference relations, and their axioms, are naturally induced from simpler objects. Second, a representation theorem is given: Here the hierarchical structure provides the appropriate cardinality, especially important for uniqueness of the representation. Third, game-theoretic results - e.g. the relationship with existing solution concepts - will then be discussed: This part is, however, still at a very preliminary stage.

Talk time: Thursday 24 July, 3:00-3:25     Paper with full author list: subjectiveSB.pdf (50 kB)

16   Irinel Dragan:  The Least Square Values and the Shapley Value

The Least Square Values of cooperative TU games (briefly LS-values), were found as solutions of an optimization problem on the preimputation set (M.Keane, 1969). L.Ruiz, F.Valenciano and J.Zarzuelo have axiomatized the LS-values and discussed many properties (GEB, 1998). In earlier papers, we have shown that the Banzhaf value (Dragan, 1996) and all Semivalues (Dragan, 1999) are Shapley values of games easily derived from a given game. In the present paper, we prove that an LS-value of a given game is also a Shapley value of a game easily derived from the given one. To do this we derive an Average per capita formula for LS-values, very similar to that obtained earlier for the Shapley value (Dragan, 1991). A computational algorithm for Semivalues follows and, a theoretical result, the relationship with the Shapley value is obtained. Further, a potential basis for the space of TU games is shown and from this, like in the case of the Shapley value, we solve the inverse problem: given an n- vector, find out the set of games for which the LS-value equals the given vector. The inverse problem was earlier solved for the Shapley value and the Weighted Shapley value (Dragan, 1991).

Talk time: Wednesday 23 July, 3:00-3:25     Paper with full author list: dragan.txt (3 kB)

17   David Dreisigmeyer:  Discretizing Evolutionary Games

Here we examine the process of discretizing an evolutionary game. First, we change the replicator equation of game theory into a Lotka-Volterra population equation. Then we use the technique developed by Bettelheim, Agam and Shnerb to turn the continuous Lotka-Volterra equation into a discrete version. This involves treating the Lotka-Volterra equation as a mean field equation and using techniques from quantum field theory and statistical mechanics.

Talk time: Wednesday 23 July, 3:00-3:25     Paper with full author list: gameconfpaper.pdf (1082 kB)

19   Ori Haimanko:  On Continuity of the Equilibrium and Core Correspondences in Economies with Differential Information

We study upper semi-continuity of correspondences of several solution concepts for economies with differential information, with Boylan (1971) topology on agents' information fields. Radner (1958, 1982) introduced the notion of competitive equilibrium for economies with differential information by requiring agents' trades to be measurable with respect to their respective information fields. We show that in economies for which the (contingent) commodity space is in a class of certain classical Banach spaces, the Radner equilibrium correspondence is upper semi-continuous. For a related ex ante core concept, the private core (Yannelis 1991, Allen 1993), it is shown that the core correspondence may not be upper semi-continuous. An interim core concept, the coarse core (Wilson 1978), also does not lead to an upper semi-continuous core correspondence.

Talk time: Thursday 24 July, 10:15-10:40     Paper with full author list: abs-einy.pdf (51 kB)

20   Peter Engseld:  Coordination Through Status

This paper suggests a mechanism for coordination by which positional concerns might evolve endogenously. A generalized 2x2 Hawk-Dove game, which comprises Battle of the sexes, is analyzed in an evolutionary environment where a continuum of agents is randomly matched against each other. Status is here defined by the agents' performance in previous games. The agents' are assumed to have the ability to make an imperfect observation on how their own status relates to that of their opponent. These observations are then utilized as an instrument for coordinating the strategies in the game by the conditioning of the pure strategies on whether the opponent has a higher status or a lower status. Since this model implies that a conditioned strategy does not necessarily correspond to a homogenous payo¤, a modified version of ESS is introduced by which evolutionary stability is determined. From this criterion it is shown that, as the agent's observational skills come close to being perfect, there exist three evolutionary stable strategies, two conditioned and one unconditioned. It is then assumed that these stable strategies can evolve and grow separately in di¤erent isolated populations and that the each population grows in proportion to its average payoff. Eventually, as they grow larger, two populations are assumed to encounter each other and merge into one. At this point it is assumed that the adjustment process of the distribution is much quicker than the growth process that in turn is much faster than the mutations. As the criterion defined above is yet again utilized to determine which strategy is evolutionarily stable. It is shown that just one strategy can survive; behave hawkish against less successful opponents and dovish against more successful opponents. Moreover it is also shown that this strategy will prevail against strategies conditioned through other personal characteristics such as e.g. size, and gender.

Talk time: Thursday 24 July, 3:00-3:25     Paper with full author list: CTS.pdf (499 kB, revised July 16)

21   Dragan Filipovich:  Ambiguous Contracting: Natural Language and Judicial Interpretation

We study the relationship between ambiguity (which comes into the picture since contracts have to be written in natural language), and contractual incompleteness. The contracting process is modelled as a signalling game between the parties and the judge, with the contract as the signal. The judge is assumed to be bound by the content of the contract (in as far as it can be ascertained unambiguously). Two kind of examples are presented: The first set of examples shows how ambiguity can lead to incompleteness. Here incompleteness is a way of hedging against adverse judgements on the part of an imperfectly informed judge. The remaining example illustrates a sort of converse intuition: It shows how incompleteness might lead the contracting parties to write ambiguous contracts in order to afford a relatively well-informed judge freedom to enforce the parties' will.

Talk time: Tuesday 22 July, 10:15-10:40     Paper with full author list: ambiguouscontracts.pdf (369 kB)

22   Julio González Díaz:  From Set-Valued Solutions to Single-Valued Solutions: the Centroid

We study a general procedure which, given a set-valued solution of a TU game, provides a single-valued solution. Our solution inherits the properties of the set-valued solution. If a set of allocations is chosen based on some principles that a solution should satisfy, the single allocation that we select is consistent with those principles. Besides, it has a central position with respect to the set, to be precise, it is the center of gravity (centroid) of the set valued solution. Afterwards we analyze this solution concept for some classical set valued solutions, mainly in the core. Furthermore, we try to establish a direct connection between the Centroid and the Shapley Value.

Talk time: Thursday 24 July, 10:15-10:40     Paper with full author list: centroid.pdf (75 kB)

23   Ziv Gorodeisky:  Evolutionary Stability for Large Populations and Backward Induction

It has been shown (Hart [2002]) that the backward induction (or subgame-perfect) equilibrium of a perfect information game is the unique stable outcome for dynamic models consisting of selection and mutation, when the mutation rate is low and the populations are large, under the assumption that the expected number of mutations per generation is bounded away from zero. Here it is shown that one can dispense with this last condition. In particular, it follows that the backward induction equilibrium is evolutionarily stable for large populations.

Talk time: Tuesday 22 July, 10:50-11:15     Paper with full author list: paper.pdf (230 kB)

24   Archishman Chakraborty:  Ordinal Cheap Talk

Can comparative statements be credible even when absolute statements are not? For instance, can a professor credibly rank different students for a prospective employer even if she has an incentive to exaggerate the merits of each student? Or can an analyst credibly rank different stocks even if the client would be dubious about a recommendation to buy any one of them? We examine such problems in a multidimensional sender-receiver game where the sender has private information about multiple variables. We show that ordinal cheap talk, in which the variables are completely ordered by value or grouped into categories by value, can be credible even when interests are too opposed to support communication along any single dimension. Ordinal cheap talk is credible because it reveals both favorable and unfavorable information at the same time, thereby precluding any possibility of exaggeration. The communication gains from ordinal cheap talk can be substantial with only a couple of dimensions, and the payoffs from a complete ordering are asymptotically equivalent to full revelation as the number of variables becomes large. However, in some circumstances the sender can do better through a partial ordering that categorizes variables. Compared to other forms of cheap talk, ordinal cheap talk is exceedingly simple in that the sender only makes straightforward, comparative statements.

Talk time: Tuesday 22 July, 10:15-10:40     Paper with full author list: ordinal.pdf (328 kB, revised July 9)

25   Dorothea Herreiner:  Envy as a Secondary Criterion of Fairness

In the recent experimental literature several utility models have been suggested that address observed behavior not reducible to the pursuit of self-interest. Most models are based on some kind of social preferences, where the payoff distribution is relevant for an individual's utility. Envy is an important criterion in the theoretical literature on fair division, whose definition differs from the more casual usage of the word envy in the experimental literature. We analyze several fair division problems where envy a la Foley (1963) and social preferences can be distinguished. Envy is shown to matter, although only as a secondary criterion.

Talk time: Monday 21 July, 10:15-10:40     Paper with full author list: dorothea.txt (1 kB)

26   Shlomit Hon-Snir:  Utility Equivalence in Auctions

Auctions are considered with a (non-symmetric) independent-private-value model of valuations. It shall be demonstrated that a utility equivalence principle holds for an agent if and only if she has constant absolute risk aversion.

Talk time: Thursday 24 July, 3:35-4:00     Paper with full author list: utilpap2.pdf (163 kB)

27   Rafael Hortala-Vallve:  Qualitative Voting

As opposed to the classical voting system (one person - one decision - one vote) a new voting system is defined where agents are endowed with a given number of votes that can be distributed freely between a prearranged number of issues that have to be approved or dismissed. Its essence relies on allowing voters to express the intensity of their preferences in a simple and applicable manner. From a mechanism design perspective we first prove which allocations are implementable: for a social choice function to be implementable it should only care about the voter relative intensities between the issues at the interim stage. We also prove that this new voting system, Qualitative Voting, Pareto dominates Majority Rule in some general settings and, even more, it achieves the only ex-ante incentive compatible optimal allocation. Finally, an argument in favour of Majority Rule is presented showing that the optimal implementable allocation robust to any possible prior is the one achieved by Majority Rule.

Talk time: Tuesday 22 July, 3:35-4:00     Paper with full author list: QualitativeVotingAbstract.pdf (470 kB, revised July 9)

29   Stefan Imhof:  Stable Sequences of Political Coalitions

This paper explores a sequential coalition formation game among political parties. We introduce the non-cooperative concept of stable sequences of coalitions, a general solution to sequential coalition formation games. The main results are i) the order of the agenda matters for the equilibrium outcome, ii) punishment strategies can support otherwise unstable coalition structures, in particular the phenomenon of ``strange bedfellows'' can arise in the first round, and iii) a party which is median in all decisions is always better off in the sequential game than in a single coalition formation over two decisions, while the converse is not true.

Talk time: Monday 21 July, 3:35-4:00     Paper with full author list: Imhofgames03.pdf (57 kB, revised May 16)

30   Elena Inarra:  The Supercore for Normal Form Games

We study the supercore of a system derived from a normal form game. For the case of a finite game, we define a sequence of games and show that the supercore coincides with the set of Nash equilibrium strategy profiles of the last game in that sequence. This result is illustrated with the characterization of the supercore for the n-person prisoner's dilemma. With regard to the mixed extension of a game we prove that the supercore coincides with the set of NE whenever the game has a finite number of Nash equilibria. This coincidence is not mantained for games with infinite Nash equilibria.

Talk time: Monday 21 July, 10:15-10:40     Paper with full author list: AE.pdf (235 kB, revised June 18)

31   Sergei Izmalkov:  Multi-unit Open Ascending Price Efficient Auction

In this paper I present an open ascending price mechanism that allocates efficiently K identical objects among N bidders with interdependent values. The mechanism consists of a number of sequential English auctions with reentry and has the following attributes. In each of the individual auctions all the bidders compete simultaneously in the open ascending price format. The most distinctive feature of the mechanism is that winners are determined first, and then additional auxiliary auctions are conducted to determine prices. Total number of auctions depends only on the number of goods to be allocated and not on the number of bidders.

Talk time: Tuesday 22 July, 3:00-3:25     Paper with full author list: Izmalkov-abstract.txt (1 kB)

32   Yuan Ju:  A Compensation Rule for Project-Allocation Games

In this paper, by introducing the notions of project and proportion, we construct a simple cooperative game theoretical framework for studying a class of economic environments in which agents, with their initial endowments (specialities and proportions of projects), would work together in a joint program with one or a number of projects. In addition to studying the effects of the structures of coalitions, projects and proportions on surplus sharing, we mainly focus on the problems of compensation in cooperation. Taking the Shapley value as the benchmark, we propose a general compensation rule by which the compensator, compensatee and amount of compensation can be easily specified in a just way. Moreover, we characterize it as the unique compensation rule satisfying efficiency, symmetry, dummy player, additivity and equity. The usefulness of the framework is further illustrated by an application in the field of public sector reforms, for which we use a core-peripheral project-allocation model to investigate the problems of compensation and show that the competitiveness/bargaining power comparison among players determines the direction and the amount of compensation. Finally, we make an extension of the model and refine the compensation rule.

Talk time: Wednesday 23 July, 3:35-4:00     Paper with full author list: AbstractJu.pdf (78 kB)

36   Grigol Kharabadze:  End of Boeing's Monopoly: How Does Airbus' A380 Introduction Affect Large Commercial Aircraft Industry?

Since the first delivery of the 747, Boeing has been enjoying monopoly power in the largecommercial aircraft industry. As Airbus launches the A380 superjumbo, the monopoly era of Boeing seems to be over. The main questions this project will try to answer are: (1) how the entry of Airbus' A380 will affect the large commercial aircraft industry, i.e., how Boeing and Airbus will divide market share in this Incumbent-Entrant game; and (2) how big is the effect of the aid from European governments to Airbus. The motivation for this research project is the tension between two major civilian aircraft producers - The Boeing Company and Airbus1. Corporate tensions reached a new level after Airbus officially announced its plans for the A380 superjumbo - world's largest commercial aircraft. The first A380 is due to be delivered in March 2006. This is the beginning of the end of Boeing's more than 30 years of exclusive monopoly in the large commercial aircraft industry.
Tensions do not have only corporate character. Introduction of A380 adds another chapter in United States - European Union history of trade disputes. The A380 development is a $10.7 billion project, about one-third of which will be funded by European governments - members of the Airbus consortium. The United States has warned the European Union that any additional loans that European government - members will be making to Airbus to help fund the development of the A380 must be at the market rates in order not to violate the US - EC 1992 bilateral agreement.
In spite of all these corporate and political disputes, we believe that the questions this research project addresses can be usefully examined in terms of economic theory of market entry and incumbent response. The paper provides a simple and interesting approach to the problem of market division.

Talk time: Thursday 24 July, 10:50-11:15     Paper with full author list: AbstractGameTheoryConference.pdf (46 kB)

40   László Kóczy:  The Minimal Dominant Set is a Non-Empty Core-Extension

A set of outcomes for a TU-game in characteristic function form is dominant if it is, with respect to an outsider-independent dominance relation, accessible (or admissible) and closed. This outsider-independent dominance relation is restrictive in the sense that a deviating coalition cannot determine the payoffs of those coalitions that are not involved in the deviation. The minimal (for inclusion) dominant set is non-empty and for a game with a non-empty coalition structure core, the minimal dominant set returns this core.

Talk time: Thursday 24 July, 10:15-10:40     Paper with full author list: koczylauwersmindomset.pdf (203 kB)

41   Frederic Koessler:  Communication Equilibria with Partially Verifiable Types

This paper studies the set of equilibria that can be achieved by adding general communication systems to Bayesian games in which some information can be certified or, equivalently, in which players' types are partially verifiable. Given the information that players are able to certify, we characterize outcome-equivalent canonical equilibria for which generalized versions of the revelation principle are valid. Communication equilibria and associated canonical representations are obtained as special cases when no information can be certified.

Talk time: Tuesday 22 July, 3:00-3:25     Paper with full author list: koessler.pdf (255 kB)

43   R. Vijay Krishna:  Absence of Commitment in Principal-Agent Games

We study the instances of Principal-Agent games where the Principal cannot commit to the outcome prescribed by a mechanism. This means that the Revelation Principle does not hold. We exhibit a "cheap", pre-play procedure whereby, in a certain class of games, the players can virtually implement (in the absence of a mediator) a large subset of the equilibria implementable with the help of a mediator.

Talk time: Monday 21 July, 10:15-10:40     Paper with full author list: comm-abs.pdf (123 kB)

44   Ali Kutman:  The FBI-CIA Game

We investigate the behavior of players in a common interest strategic form game who do not communicate with each other. Moreover, the players do not know the utilities at the start of the game, but learn them as the game is repeatedly played. Each player assumes that the other players employ a fixed but unknown mixed strategy. At each stage of the game, the players simultaneously play their best response against their belief distributions for the other players, which they derive from the past history of plays. Unlike fictitious play in which the players are assumed to know the entire utility function, the players in this game base their best response decisions on their current, possibly incomplete, knowledge of the utility. We demonstrate that the sequence of belief distributions converges to the set of Nash equilibria. This concept is illustrated through an example that we call "the FBI-CIA Game".

Talk time: Tuesday 22 July, 10:15-10:40     Paper with full author list: kutmanabstract.pdf (4 kB)

45   Dmitri Kvassov:  Non-Zero-Sum Blotto Games

Two players compete in a number of simultaneous races in different locations. The players have limited resources and must decide how to allocate these to the different races. At each location the player who allocates more resources wins the prize corresponding to that location. As an example, consider two candidates for election who must allocate their campaign budgets to different states. Alternatively, consider an R and D race in which multiple patents can be won. Such games correspond to budget constrained multiple-object all-pay auctions and constitute non-zero-sum counterparts of Colonel Blotto type games introduced by Borel. I analyze a class of such games with complete information. Budget-constrained bidders simultaneously submit vectors of bids from a convex set of pure strategies, and the highest bidder at each location wins that item. The presence of the budget constraint leads to the indirect 'substitutability' among the objects: a higher bid for one object leaves less resources for others. I fully characterize the mixed-strategy equilibria in the case of two bidders and two objects for the following cases (i) identical values for the objects and identical budgets; (ii) different common values but identical budgets; (iii) identical values but different budgets. The results may be generalized for an arbitrary number of objects.

Talk time: Wednesday 23 July, 3:35-4:00     Paper with full author list: Kvassov.pdf (22 kB)

46   Theodore Lambert:  Fictitious Play Approach to a Mobile Unit Situation Awareness Problem

Until now the fictitious play approach to optimization has only been demonstrated on a dynamic traffic routing problem; therefore, it is necessary to apply this method to other problems in order to demonstrate its effectiveness as a heuristic optimization method. We used the large scale situational awareness simulation developed for the Multidisciplinary University Research Initiative (MURI) on ``Low-Energy Electronic Design for Mobile Platforms'' to test the fictitious play approach, since we already possessed bench mark solutions from a simulated annealing approach previously applied. We found that the fictitious play approach yielded similar solutions to simulated annealing and required comparable computational effort, while they both outperformed pure random search. This demonstrates the effectiveness of a fictitious play approach to optimization for the large scale situational awareness simulation, providing additional evidence as to fictitious play's value as an optimization heuristic.

Talk time: Thursday 24 July, 10:50-11:15     Paper with full author list: FictMuri.pdf (102 kB)

49   Qihong Liu:  Customer Information Sharing Among Rival Firms

The recent rapid growth of the Internet as a medium of communication and commerce, combined with the development of sophisticated software tools, are to a large extent responsible for producing a new kind of information: databases with detailed records about consumers' preferences. These databases have become part of a firm's assets, and as such they can be sold to competitors. This possibility has raised numerous concerns from consumer privacy advocates and regulators, who have entered into a heated debate with business groups and industry associations about whether the practice of customer information sharing should be banned, regulated, or left unchecked. This paper investigates the incentives of rival firms to share their customer-specific information and evaluates the welfare implications if such exchanges are banned, in the context of a perfect

Talk time: Friday 25 July, 10:15-10:40     Paper with full author list: liuserfes.pdf (49 kB, revised June 2)

50   Xiao Luo:  A Unified Approach to Information, Knowledge, and Stability

Within the context of strategic interaction, we provide a unified framework for analyzing information, knowledge, and the "stable" pattern of behavior. The major innovations are: (i) unlike the standard ad hoc semantic model of knowledge, the state space is constructed by Harsanyi's types that were explicitly formulated by Epstein and Wang (Econometrica 64, 1996, 1343-1373); (ii) players may be boundedly rational and have non-partitional information structures; and (iii) players may have general preferences, including subjective expected utility and non-expected utility. We first study the interactive epistemology. We then establish an equivalence theorem between a strictly dominated strategy and a never-best reply in terms of epistemic states. Finally, we explore epistemic foundations behind the fascinating idea of stability due to J. von Neumann and O. Morgenstern.

Talk time: Tuesday 22 July, 3:35-4:00     Paper with full author list: xluo.pdf (374 kB, revised June 16)

53   Timothy Mathews:  Non-Binding Sequential Exchange Between Discounting Agents

When exchange is sequential, and no binding agreements can be written, the agent acting first is exposed to the possibility that, even if he honors the agreement, his trading partner may subsequently choose not to do so. The primary focus of the current analysis is whether trade can successfully occur in such environments. Exchange will successfully occur so long as there are sufficiently large gains from trade for the agent acting second. As a result, the agent acting first may be better off with less relative bargaining power.
The possibility of facilitating exchange through the use of an escrow service is considered. Conditions are determined under which the agent acting first will employ such a service in order to ensure successful exchange (as opposed to ensuring successful exchange through the disposal of his own relative bargaining advantage).

Talk time: Wednesday 23 July, 10:15-10:40     Paper with full author list: MathewsPaper2.pdf (360 kB)

54   Takashi Matsuhisa:  Rational Expectations Equilibrium in Economy for Multi-Modal Logic

This article relates economies and traders' knowledge. We consider a pure exchange economy under uncertainty where the traders are assumed to have a non-partitional information structure. The purpose is to propose the notion of generalized rational expectations equilibrium for the economy, and we investigate welfare in the economy with emphasis on epistemic point of view. It is shown that Theorem 1: There exists a generalized rational expectations equilibrium for the economy. We shall characterize welfare under the generalized rational expectations equilibrium: Theorem 2: An allocation is ex-ante Pareto optimal if and only if it is a generalized rational expectations equilibrium allocation relative to some price system.

Talk time: Friday 25 July, 10:15-10:40     Paper with full author list: Matsuhisa.pdf (168 kB)

55   Vladimir Mazalov:  Location Game on the Plane

We analyze Hotelling's duopoly model on the plane. There are two players (firms) located in different points inside a circle and the customers are distributed with some density in it. The solution of two game-theoretic problems is derived. The first problem is to find the equilibrium prices for the homogeneous goods, and the second problem is to find the equilibrium allocation of the players inside the circle. The equilibrium in location game is constructed for uniform and non-uniform case.

Talk time: Wednesday 23 July, 3:00-3:25     Paper with full author list: Locator.pdf (186 kB)

59   Stefan Napel:  Power Measurement as Sensitivity Analysis - A Unified Approach

This paper proposes a unified framework that integrates the traditional index-based approach and the competing non-cooperative approach to power analysis. It rests on a quantifiable notion of ex post power as the (counterfactual) sensitivity of the expected or observed outcome to individual players. Thus, it formalizes players' marginal impact on outcomes in both cooperative and non-cooperative games, for both strategic interaction as well as purely random behavior. By taking expectations with respect to preferences, actions, and procedures one obtains meaningful measures of ex ante power. Established power indices turn out to be special cases.

Talk time: Wednesday 23 July, 3:35-4:00     Paper with full author list: NapelWidgrenPaper.pdf (305 kB)

60   Daniel Neill:  Cooperation and Coordination in the Turn-Taking Dilemma

In many real-world situations, "cooperation" in the simple sense of the Prisoner's Dilemma is not sufficient for success: instead, cooperators must precisely coordinate more complex behaviors in a noisy environment. We investigate one such model, the Turn-Taking Dilemma (TTD), a variant of the repeated Prisoner's Dilemma in which the highest total payoff is achieved not by simultaneous mutual cooperation, but by taking turns defecting (alternating temptation and sucker payoffs). The TTD more accurately models interactions where players must take short-term losses for long-term gains: situations marked by the intricate give-and-take of bargaining and compromise. Using "evolutionary dominance" as a general measure of performance, we investigated which strategies are most successful in TTD interactions. Top TTD strategies such as EXALT_2 can effectively coordinate turn-taking under noise, while exploiting cooperators and resisting exploitation by defectors; these strategies are likely to achieve success in the variety of real-world interactions modeled by the TTD.

Talk time: Tuesday 22 July, 3:00-3:25     Paper with full author list: ttdconf.pdf (230 kB)

61   Ricardo Nieva:  Coase, an Extension of the Shapley-Aumann-Myerson Solution and Misleading Policy Implications

As of Nieva (October 2002, June 2003) most games on foundations of institutions, yield empty cores provided that the value of the two identical player coalition in a third party enforcer game is high enough relative to the value of the grand coalition. We propose an extension of the Aumann-Myerson solution in which pairs of players not only propose links but propose payoffs constrained on the sum of the Myerson values of the graph implied by the prospective link. Partial results point out to the not formation of the grand coalition, whenever the core is empty in contrast to the standard solution. The latter would point out instead to a Coasian postulate of efficiency and it would be more informative to talk about institutions that are not agreed upon. With respect to the Coase invariance theorem, we give a counterexample in which allowing for externalities in coalition formation induces the grand coalition to form. This contrasts with Aviazan and Callen original example in which two firms pollute unilaterally a third one. In our case, we have a second source of externality that induces a lower payoff to the pollutee when the two polluters collude. However, we point out that allowing for nontrasferable utilities will yield robustness of Hurwicz's (1999) result: That in two person games, zero income effects or parallel preferences are necessary and sufficient for different allocation of pollution rights to influence the level of pollution. Finally, we dicuss misleading policy implications.

Talk time: Friday 25 July, 10:50-11:15     Paper with full author list: coajpet1.pdf (226 kB)

62   Ricardo Nieva:  Enforcers and Induced Empty Core Games Derived From Any TU 2-Person Game: Ineffective Implementation or Not Agreed Upon Institutions?

We add a Principal (abstract enforcer) to any 2 person TU game in strategic form because of transaction costs or extorsion. The game yields in reasonable cases an empty core when there are no externalities in coalition formation and when the principal can choose any allocation on the frontier of the individual, rational and feasible set. The principal does so by inducing "The Simultaneous and Double Extorsion Game". Only one of the identical players and the principal collude, iff the identical agents combined "might" is more than a threshold of the principal's but less than 100%, i.e."divide and rule". The threshold depends on the limit to the degree of double extorsion. Strikingly, he would prefer to induce an empty core game with an extreme level of extortion instead of a nonempty core one. The result, ie. that only an identical agent and the principal collude, is robust to allowing for variable principal "might" or harrasing ability that might induce a cooperative game with externalities in coalition formation. As solution concept, we use an extension of Myerson's (1978) Shapley value generalization to partition function games and the Aumann-Myerson link (1988) formation game.

Talk time: Wednesday 23 July, 10:15-10:40     Paper with full author list: interaer1.pdf (277 kB, revised July 20)

63   Ipek Ozkal-Sanver:  Nash Implementation via Hyperfunctions

Hyperfunctions are social choice rules which assign sets of alternatives to preference profiles over sets. So, they are more general objects compared to standard (social choice) correspondences. Thus every correspondence can be expressed in terms of an equivalent hyperfunction. We postulate the equivalence between implementing a correspondence and its equivalent hyperfunction. We give a partial charaterization of Nash implementable hyperfunctions and explore the conditions under which correspondences have Nash implementable equivalent hyperfunctions. Depending on the axioms used to extend preferences over alternatives to sets, these conditions are weaker than or logically independent of Maskin monotonicity, in any case expanding the set of Nash implementable social choice rules. In fact, social choice rules such as the majority rule and the top cycle are Nash implementable through their equivalent hyperfunctions while they are not Maskin monotonic, thus not Nash implementable in the standard framework.

Talk time: Monday 21 July, 10:15-10:40     Paper with full author list: hyperfunctions.pdf (215 kB)

64   T. Parthasarathy:  SER-SIT Stochastic Games and Vertical Linear Complementarity Problem

In this note, we consider a two-person nonzerosum finite stochastic game with SER-SIT properties, that is, with separable rewards and state independent transitions. We formulate the given problem as a vertical linear complementarity problem for the discounted and the undiscounted stochastic games. Our result generalizes an earlier result obtrained by Parthasarthy, Tijs and Vrieze.

Talk time: Friday 25 July, 10:50-11:15     Paper with full author list: ssgv.pdf (157 kB)

65   Yohan Pelosse:  Anonymous Competitive Contracts

In this paper we consider a situation in which a principal wants to reward the most productive of two agents competing over T periods while, at the same time eliciting a maximal effort level from them. Dubey and Wu (2000) and Dubey and Haimanko (2000) have shown that these two objectives cannot be satisfied simultaneously. Basically this arises because one of the agents may have a considerable lead over his rival at an interim period. For this reason, these authors advocate the use of a spot-check device so as to provide the correct incentives to the agents. However, such a mechanism suffers from a limitation because of its inability to select the biggest producer of the competition. In this paper, we show that there exists a more general mechanism that achieves the two objectives simultaneously. Our analysis is based on a function that assigns to every possible difference in the agents' output a probabitity of winning the prize. We provide a characterization of this optimal function and study its different properties.

Talk time: Monday 21 July, 10:50-11:15     Paper with full author list: acc3.pdf (290 kB)

67   Anders Poulsen:  Evolution of Preferences in a Simple Game of Life

We study the evolution of preferences when players are engaged in simultaneous and sequential move Prisoner's Dilemma games. There is, as long as each game is played with strictly positive probability, a unique asymptotically stable population where players with reciprocal, altruist and materialist preferences co-exist in the population.

Talk time: Monday 21 July, 3:35-4:00     Paper with full author list: evol.pdf (455 kB, revised July 16)

69   Indrajit Ray:  Observable Implications of Nash and Subgame-Perfect Behavior in Extensive Games

We provide necessary and sufficient conditions for observed outcomes in extensive game forms to be rationalised first, partially, as a Nash equilibrium and then, fully, as the unique subgame perfect equilibrium.

Talk time: Tuesday 22 July, 10:50-11:15     Paper with full author list: rationalisation.pdf (159 kB)

72   Francisco Sanchez Sanchez:  Decomposition Principle in Cost Games

In this work we consider cost games in characteristic function form where the players are not homogenous. It is supposed that each player is formed by a number of indistinguishable agents. We determined tariffs for the agents in such a way the amount is gathered coincide with the cost of give service to the gran coalition. The tariffs are determined supposing additivity and the principle of decomposition using the canonical dual base of the space of cooperative games.

Talk time: Wednesday 23 July, 10:15-10:40     Paper with full author list: Sanchez.pdf (103 kB)

73   M. Remzi Sanver:  Almost all Social Choice Correspondences are Subject to the Gibbard-Satterthwaite Theorem

We analyse the manipulability of social choice correspondences via hyperfunctions, i.e., functions that pick a non-empty set of alternatives at each admissible preference profile over sets of alternatives. We consider a domain of lexicographic orderings of sets which allows only two orderings for every ordering over alternatives. We show that Gibbard-Satterthwaite type impossibility results prevail on this very narrow domain which is a subset of many restricted domains defined through standard axioms to extend preferences over alternatives to sets of alternatives. Hence, we are able to verify the robustness of the Gibbard-Satterthwaite theorem, showing that it holds under almost all reasonable domain restrictions. As hyperfunctions are more general objects than regular social choice correspondences, our impossibility results carry to the standard framework.

Talk time: Monday 21 July, 10:50-11:15     Paper with full author list: ozyurtsanver.pdf (298 kB)

75   Rahul Savani:  Long Lemke-Howson Paths

The Lemke-Howson algorithm is the main algorithm for finding one equilibrium of a bimatrix game. In this paper we present a class of square bimatrix games for which the shortest Lemke-Howson path grows exponentially in the dimension of the game d. We construct the games using pairs of dual cyclic polytopes with 2d facets in d-space.

Talk time: Tuesday 22 July, 3:00-3:25     Paper with full author list: savani.txt (1 kB)

76   Jochen Schanz:  Optimal Information Disclosure for a Policymaker Targeting Aggregate Activity

This paper starts from the stylised fact that policymakers publish their information only selectively: a central bank tends not to predict a recession and the IMF is unlikely to forecast a currency crisis. The paper, then, searches for the circumstances in which such a partially-revealing reporting rule is part of an (sequential) equilibrium within a static signalling game in which market participants (the receivers) take the policymaker's reporting strategy into account when evaluating his report. The economic framework is a partial equilibrium model of an imperfectly competitive economy with uncertain demand. To circumvent full revelation, it is assumed that the policymaker fears that markets would overreact to such information if it were published. Results available so far suggest that the equilibrium reporting rule has the following properties: extreme news is withheld and intermediate news published. In addition, the higher the policymaker's incentive to increase production (i.e., the less competitive the economy is), the worse the worst news he makes public; likewise, the better the best news he makes public; the lower the market's expectation of his information if he withholds; and the better the average news he publishes.

Talk time: Thursday 24 July, 3:35-4:00     Paper with full author list: Schanzabstract.pdf (280 kB, revised July 9)

77   Burkhard Schipper:  Multi-Person Unawareness

Standard state-space models, which are widely used in economics, preclude non-trivial forms of unawareness as shown by Dekel, Lipman and Rustichini (1998). We define a generalized state-space model that allows for unawareness. In order to facilitate applications we make no explicit use of modal syntax within the sematic model. Our model satisfies all "S4" properties as well as all desiderata on unawareness proposed by Modica and Rustichini (1999), Halpern (2001) as well as Dekel, Lipman and Rustichini (1998).

Talk time: Friday 25 July, 10:50-11:15     Paper with full author list: heifetzmeierschipper.pdf (129 kB, revised May 23)

78   Karl Schlag:  On the Value of Randomizing and Limiting Memory in Repeated Decision-Making Under Minimal Regret

We search for behavioral rules that attain minimax regret under geometric discounting in the context of repeated decision making in a stationary environment where payoffs belong to a given bounded interval. Rules that attain minimax regret exist and are optimal for Bayesian decision making under the prior where learning can be argued to be most difficult. Minimax regret can be attained by randomizing using a linear function of the previous payoffs. For myopic individuals, minimax regret behavior requires only one round of memory, for intermediate discount factors two rounds of memory suffice to attain minimax regret.

Talk time: Wednesday 23 July, 10:50-11:15     Paper with full author list: regret4.pdf (290 kB)

79   Tadashi Sekiguchi:  Repeated Games with Observation Costs

This paper analyzes repeated games in which it is possible for players to observe the other players' past actions without noise but it is costly. One's observation decision itself is not observable to the other players, and this private nature of monitoring activity makes it difficult to give the players proper incentives to monitor each other. We provide a sufficient condition for a feasible payoff vector to be approximated by a sequential equilibrium when the observation costs are sufficiently small. We then show that this result generates an approximate Folk Theorem for a wide class of repeated games with observation costs. The Folk Theorem holds for a variant of prisoners' dilemma, partnership games, and any games in which the players have an ability to "burn" small amounts of their own payoffs.

Talk time: Monday 21 July, 10:50-11:15     Paper with full author list: obscostWP.pdf (254 kB)

80   Abhijit Sengupta:  Sealed Bid Second Price Auctions with Discrete Bidding

We analyze a sealed bid second price auction in a framework in which acceptable bids are restricted to a set of discrete values. It is assumed throughout that bidder valuations are independently drawn from a common continuous distribution. When bidder valuations are uniformly distributed, it is shown that there exists a unique symmetric pure strategy equilibrium characterizing bidder behavior. When following this strategy, bidders may choose to bid strictly above or strictly below their own valuation. Under such a selling mechanism allocative efficiency may be sacrificed, in that with strictly positive probability the item will be awarded to a bidder other than the bidder with the highest valuation. By way of example it is shown that, when choosing the values of an exogenously determined number of discrete bid levels, a revenue maximizing seller may wish to choose a level for the highest acceptable bid either strictly greater than, strictly less than, or exactly equal to the highest possible bidder valuation. Because of the complexity of the payoff functions of the bidders, it is not possible to specify bidder behavior in general. As a result, a numerical analysis is conducted, assuming that the acceptable bid levels are "evenly spaced" (that is, assuming that the distance between any two consecutive bids is equal to t). Based upon the results of this numerical analysis, it appears as if the expected revenue of the seller will increase as t becomes smaller (that is, as the acceptable bid points become closer to each other). However, the probability with which the item will be awarded to a bidder other than the bidder with the highest valuation does not always diminish as t is made smaller.

Talk time: Monday 21 July, 3:00-3:25     Paper with full author list: MathewsAbstract1.pdf (59 kB)

82   Rafael Tenorio:  The Impact of Individual and Group Characteristics on Strategies and Outcomes in Coordination Games: Theory and Evidence

We analyze the impact of individual and group attributes on successful play in two types of coordination games or tasks. In the first game, the likelihood of coordination depends positively on the homogeneity of group members. The converse is true in the second game (i.e., heterogeneous players tend to coordinate more successfully). The players involved in these games potentially differ in attributes such as age, gender, or cultural background. We model these potential differences as "frames" or underlying common factors, which will influence the group's ability to coordinate on salient solutions or "focal points." We then use data from the television game show "Family Feud" to evaluate the relative importance of alternative frames on the ability of groups (families) to succeed at these types of coordination games. We find that group and task characteristics are more important determinants of successful coordination than individual characteristics.

Talk time: Thursday 24 July, 3:35-4:00     Paper with full author list: StonyBrookprop03.pdf (100 kB)

83   Federico Valenciano:  Bargaining, Voting and Value

This paper addresses the following issue: If a set of agents bargain on a set of feasible alternatives 'under the shadow' of a voting rule, that is, any agreement can be enforced if a 'winning coalition' supports it, which general agreements are likely to arise? In other terms: Which is the influence that the voting rule used to settle agreements can project on the outcome? To give an answer we model the situation as an extension of Nash bargaining problem in which an arbitrary voting rule replaces the unanimity to settle agreements by n players. This provides a setting in which a natural extension of Nash's solution (consistent with Shapley's value) is obtained axiomatically by, basically, integrating into a single system Nash's and Shapley's characterizing systems.

Talk time: Friday 25 July, 10:15-10:40     Paper with full author list: bvv.pdf (164 kB)

84   Juan Vidal-Puga:  Forming Societies and the Shapley NTU Value

We design a simple protocol of coalition formation. A society grows up by sequentially incorporating new members. The negotiations are always bilateral. We study this protocol in the context of NTU games in characteristic function form. When the corresponding NTU game (N,V) satisfies that V(N) is flat, the only payoff which arises in equilibrium is the Shapley (1969) NTU value.

Talk time: Tuesday 22 July, 3:35-4:00     Paper with full author list: shapley-ntu6.pdf (299 kB)

85   Yannick Viossat:  Properties of Dual Reduction

Dual reduction, introduced by Myerson, allows to reduce games in a way that selects among correlated equilibrium distributions. Myerson's results are first recalled, then new properties of dual reduction are established. We show that generic two-player games have a unique sequence of iterative full dual reductions. We compare dual reduction to other correlated equilibrium refinements. Finally, we review and connect the linear programming proofs of existence of correlated equilibria.

Talk time: Wednesday 23 July, 10:50-11:15     Paper with full author list: viossat.pdf (168 kB, revised July 17)

86   Arndt von Schemde:  Construction of Equilibrium Components with Arbitrary Index and Degree

In this talk we give a brief introduction into the theory of index and degree of Nash equilibria. After explaining the general concepts in an informal way, we will, by means of certain examples, show how Nash equilibrium components of arbitrary index (or degree) can be constructed. We will then discuss certain properties of these components and the question whether the index (or degree) of a component can be used to capture certain refinement criteria.

Talk time: Thursday 24 July, 3:35-4:00     Paper with full author list: vonSchemde.pdf (115 kB, revised July 1)

87   Bernhard von Stengel:  Computationally Efficient Coordination in Game Trees

The solution concept of 'correlated equilibrium' allows for coordination in games. For game trees with imperfect information, it gives rise to NP-hard problems, even for two-player games without chance moves. We introduce the 'extensive form correlated equilibrium' (EFCE), which extends Aumann's correlated equilibrium, where coordination is achieved by signals that are received 'locally' at information sets. An EFCE is polynomial-time computable for two-player games without chance moves.

Talk time: Wednesday 23 July, 10:15-10:40     Paper with full author list: EFCE.pdf (87 kB)

88   Jun Wako:  Two Examples in a Market with Two Types of Indivisible Good

We consider an extension of the permutation game of Tijs et al (1984) in which players are endowed with and ultimately wish to consume one unit of each of two types of good (i.e., a house and a car). We present two examples. The first is a case where even though the Corresponding Linear Program (CLP) does not solve with integers, the core of the market is not empty. The second example is a case with additively separable preferences in which there is a core vector in the market which does not correspond to any optimal dual solution of the CLP. Both examples demonstrate possible behavior that is impossible in many of the standard matching games. We show that in cases with additively separable preferences, the core-optimal dual equivalence property is recovered if each component swapping game, one with houses and the other with cars, is ``convex'' in the sense of Shapley (1971).

Talk time: Tuesday 22 July, 10:50-11:15     Paper with full author list: WQSB.pdf (208 kB, revised June 13)

89   Naoki Watanabe:  Asymptotic Properties of the Shapley Value of Patent Licensing Games

We study the asymptotic properties of the Shapley value of patent licensing games with the Cournot competition, shedding light on its relations to the nucleolus, core and bargaining set. The Shapley value of the outside patentee of a non-drastic cost-reducing innovaion converges to (a-c), which coincides with the patentee's profit through non-cooperative licensing by means of upfront fee (or royalty) in Kamien and Tauman (1986). The distance between the asymptotic Shapley value and asymptotic nucleolus becomes larger as the magnitude of the cost reduction increases. The limit core is empty, and the asymptotic Shapley value is excluded from the limit bargaining set. All the results are based on a new way of deriving a v-function from n-person games in strategic form.

Talk time: Monday 21 July, 3:00-3:25     Paper with full author list: Abs-watanabe.pdf (109 kB)

90   David Wettstein:  An Ordinal Shapley Value for Economic Environments

We propose a new solution concept to address the problem of sharing a surplus among the agents generating it. The sharing problem is formulated in the preferences-endowments space. The solution is defined in a recursive manner incorporating notions of consistency and fairness and relying on properties satisfied by the Shapley value for Transferable Utility (TU) games. We show a solution exists, and refer to it as an Ordinal Shapley value (OSV). The OSV associates with each problem an allocation as well as a matrix of concessions "measuring" the gains each agent foregoes in favor of the other agents. We analyze the structure of the concessions, and show they are unique and symmetric. Next we characterize the OSV using the notion of coalitional dividends, and furthermore show it is monotone in an agent's initial endowments and satisfies anonymity. Finally, similarly to the weighted Shapley value for TU games, we construct a weighted OSV as well.

Talk time: Friday 25 July, 10:50-11:15     Paper with full author list: osv2.pdf (366 kB)

91   Harald Wiese:  On the Application of an Outside-Option Value to the Gloves Game

Building on the Shapley value, several partitional values (or values for coalition structures) have been presented in the literature, most notably by Aumann and Drčze (1974) (AD value) and by Owen (1977). A coalition structure is a partition on the set of players; the sets making up the partition are called components. The AD value obeys component efficiency which is a sensible assumption for many applications. For example, in market games, players that end up doing business together can be grouped in components and they share the gains from trade. Also, the power within a government coalition rests with the parties involved. However, the AD value does not reflect the fact that the power of each market participant, or party within the government, depends on other trade opportunities, or other governments that might possibly form (outside options). We therefore develop a new partitional value that is close to the AD value in obeying component efficiency but does reflect outside options. In doing so, our value has to violate the null-player axiom. We apply this value to the gloves game.

Talk time: Wednesday 23 July, 3:35-4:00     Paper with full author list: gloves4.pdf (249 kB, revised July 17)

92   Jun Xue:  Sustaining Cooperation in the Repeated Prisoner's Dilemma with Local Interaction

This paper studies the repeated prisoner's dilemma in a local interaction setup. We construct a sequential equilibrium in pure strategies that sustains cooperation for sufficiently patient players. The notion of sequential equilibrium is extended to extensive form games with infinite time horizon. The strategy is embedded in an explicitly defined expectation system, which may also be viewed as a finite state automaton. The belief system is derived by perturbing the strategy appropriately.

Talk time: Friday 25 July, 10:15-10:40     Paper with full author list: introductionnew.pdf (95 kB)

93   Andriy Zapechelnyuk:  Bargaining with a Ruler: Solution Implementation via Generalized Auction

We consider an n-player bargaining problem, where one of the players (the ruler) dictates the outcome, and the others (the agents) negotiate with the ruler to achieve a desirable outcome and obtain high payoffs. We consider two (extreme) cases regarding information about players' payoff functions: Public information (all payoff functions are publicly known), and private information (each player knows only his own payoff function). In the former case, we find a unique solution to the bargaining problem satisfying certain axioms (Individual Rationality, Stability, and Monotonicity), which results that the ruler receives the highest feasible payoff, while the agents obtain only their lowest individually rational payoffs. In the latter case, we also find an axiomatic solution (satisfying Individual Rationality, Stability, and Non-manipulability), which results that the ruler receives the smallest feasible payoff; besides that, we design a direct mechanism (we call it 'generalized auction'), which implements it.

Talk time: Monday 21 July, 10:15-10:40     Paper with full author list: Zapechelnyuk.pdf (89 kB)

94   Josi Zarzuelo:  On Coalitional Semivalues

In this paper we propose a characterization of the coalitional value for transferable utility games (Owen, 1977), and we define and study coalitional semivalues, which are generalizations of semivalues (Dubey, Neyman and Weber, 1981).

Talk time: Thursday 24 July, 10:50-11:15     Paper with full author list: CS00.pdf (263 kB)

95   Anna Jaskiewicz:  On the Equivalence of Two Expected Average Reward Criteria for Zero-Sum Semi-Markov Games

In this paper we study two basic optimality criteria used in the theory of zero-sum semi-Markov games. According to the first one, the average reward for player 1 is the lim sup of the expected total rewards over a finite number of jumps divided by the expected cumulative time of these jumps. According to the second definition, the average reward (for player 1) is the lim sup of the expected total rewards over the finite deterministic horizon divided by the length of the horizon. We shall call them the ratio-average reward and time-average reward, respectively. It is known that in general these two criteria can have nothing to do with each other. In other words, they may lead to different rewards and optimal strategies for players. The ratio-average reward is somewhat easier to study and has been used by many authors in zero-sum games and in dynamic programming. Recently, some results concerning the optimality equation for semi-Markov games with Borel state space and the ratio-average criterion were given [1]. However, an equivalence result has not been reported so far for the Borel (uncountable) state space models. The aim of this paper is to show the equivalence between two expected average rewards under some geometric ergodic conditions. At the same time, we prove that the optimality equations for the models with these criteria are the same. Our proof is based on [2] and employs basic facts from renewal theory. Certain consequences of V-geometric ergodicity given in enable us to apply the optional sampling theorem of Doob, which is the core of the proof.

Talk time: Wednesday 23 July, 3:00-3:25     Paper with full author list: stbr.pdf (47 kB, revised Apr 23)

96   Wojciech Polowczuk:  On Two-Point Nash Equilibrium in Concave Bimatrix Games

The concavity of payoff functions is a very often used assumption, both in theoretical considerations and in practical applications. The classical result for games on Rk with continuous concave payoffs belongs to Nash. However, in many applications we have not continuous strategy spaces. More exactly, the decision goods are nondivisible, e.g. people, cars, shares. In such case we have finitely many actions and we obtain matrix games. Radzik studied optimal strategies in zero-sum matrix games with concavity-convexity properties. He shown that in such games there always exists a pair of optimal strategies with at most two membered carriers.
In this paper we generalize the Radzik's results to two-person non-zero-sum matrix games. The games described by such payoff matrices well approximate continuous games on the unit square with payoff functions F1(x, y) concave in x for each y, and F2(x, y) concave in y for each x. It is shown, that the optimal strategies in such games have very simple structure and a search procedure is given.

Talk time: Wednesday 23 July, 3:00-3:25     Paper with full author list: Polowczuk.pdf (49 kB, revised Apr 30)

97   Elina Eguiazarova:  Comparative Statics for the Private Provision of Public Goods

The theory of voluntary provision of public goods has received growing attention since the 1950s. A standard assumption in much of the literature is that public goods are strictly normal for all consumers at all levels of wealth. Together with the assumption of strict normality of private good, it guarantees uniqueness of Nash equilibrium and has also been proved to be sufficient condition for the free riding to be exacerbated as the group size increases. On the other hand, there are interesting examples of privately provided public good where the assumption of its strict normality is not justified. We consider the traditional model of voluntary provision of public goods with and without imposing the assumption of normality. We provide a thorough investigation of the effects on optimal contributions (total and per consumer) and optimal private consumption of exogenously changing the number of consumer. The comparative statics analysis presented in this talk relies on the approach based on lattice-theoretic methods. We first assume normality of public good and prove, using the lattice-theoretic methodology, that the free riding problem becomes worse with the number of consumer. Then we provide comparative statics results for the case where the normality assumption is relaxed and make an attempt to describe the equilibria set.

Talk time: Wednesday 23 July, 10:50-11:15     Paper with full author list: eg.pdf (62 kB, revised Apr 30)

98   Giorgos Stamatopoulos:  Innovation and Licensing in Models of Product Differentiation

In this paper we consider licensing of innovations in markets with differentiated products. We analyze models where firms compete in prices and are offered by an outsider innovator an innovation that increases the quality of their product. We examine the licensing policies of auction, fixed fee, linear royalty and their combination; the optimal number of licensees, the effect of the licensing policies on the market structure and welfare etc. We then examine the outcome of a cooperative licensing procedure between the innovator and the potential licensees where the payoff of each player is their Shapley value of an appropriately defined cooperative game.

Talk time: Wednesday 23 July, 10:15-10:40     Paper with full author list: giorgos.pdf (41 kB, revised May 11)

99   Guillaume Lacôte:  How to efficiently defeat a strategy of bounded rationality

In a given finite two-player zero-sum game if player one is sufficiently bounded in rationality it might be possible for player two to beat him, i.e. to ensure that he never gets more than his maxmin payoff in pure strategies at nearly all stages of the repeated game. The issue in this case is first to determine the relative minimum bound in complexity required for player two to defeat player one; it is then to determine how well player two performs, that is at how many stages he fails to beat player one and after which stage (if any) he can be certain to defeat him at each stage. Elaborating on recent results this paper addresses these issues in the case where bounded rationality is alternatively specified by means of finite state automata or bounded recall strategies.

Talk time: Tuesday 22 July, 10:15-10:40     Paper with full author list: lacote.pdf (232 kB, revised May 14)

100   Alexandre Marino:  Continuous Versus Discrete Market Game

De Meyer and Moussa Saley provide an endogenous justification for the appearance of Brownian Motion in Finance by modelling the strategic interaction between two asymmetrically informed market makers with a zero-sum repeated game with one-sided information. The crucial point of this justification is the appearance of the normal distribution in the asymptotic behavior of Vn(P) on the square root of n. In De Meyer and Moussa Saley's model, agents can fix a price in a continuous space. In the real world, the market compels the agents to post prices in a discrete set. The previous remark raises the following question: " Does the normal still appear in the asymptotic analyze for the discrete market game? ". The main topic is to prove that for all discretization of the set price, Vn(P) over the square root of n converges uniformly to 0. Despite of this fact, we don't reject De Meyer, Moussa analysis: when the size of the discretization step is small as compared to the square root of n, the continuous market game is a good approximation of the discrete one.

Talk time: Tuesday 22 July, 10:50-11:15     Paper with full author list: marino.pdf (35 kB, revised May 21)

102   Ram Orzach:  Private Information and Nonbinding Arbitration: A Proposal for Reducing the Costs of Litigation

This paper analyzes a procedure called mediation, that is really a form o f nonbinding arbitration, applied to cases filed in U.S. courts. Under the exist ing rules, a party who rejects an award proposed by the mediator is liable for s anctions unless the rejection turns out to be justified, i.e., unless the trial verdict is more favorable to the rejecting party than the mediation award. This penalty is designed to induce acceptance of the mediation award by both parties , in order to minimize the frequency of trial.
We find this procedure to be flawed since it is myopic. It may be private ly optimal for the parties to mislead the mediator, with the result that the med iation award deviates substantially from the claim's true value. This increases the likelihood the mediation award is rejected, thus increasing the probability of trial. We propose an alternative procedure, under which a party would be liab le for sanctions if, and only if, she deliberately provided false information to the mediator. In our example each party has private information, and the media tor must acquire all his information from the parties. In comparison to the exi sting practice, our procedure has a lower frequency of trial, and provides an ex ante gain to both parties.

Talk time: Tuesday 22 July, 10:50-11:15     Paper with full author list: introSB.txt (2 kB, revised June 4)

103   Eran Shmaya:  Two Player Non Zero-sum Stopping Games in Discrete Time

A two player stopping game is played in stages. At every stage, each player can stop or continue. If both players continue, the game moves to the next stage. If one of the player stops, the game terminates with final payoff that depends on the stage and the set of players that stopped. If the game never terminates the final payoff is zero. We prove that the game admits epsilon-equilibrium in randomized strategies for every epsilon > 0.
The proof uses Ramsey Theorem in order reduce the problem to that of studying properties of epsilon-equilibria in a simple class of stochastic games with finite state space. We also generalize the necessary corollary of Ramsey Theorem to a stochastic setup.

Talk time: Tuesday 22 July, 3:35-4:00     Paper with full author list: shmaya.pdf (316 kB, revised June 4)

104   Abdel-Hameed Nawar:  Internet Auctions with Traffic Congestion

This paper addresses the issue of timing of bids in a model of internet auction with traffic congestion. In a recent paper, Roth and Ockenfels (2002) have proposed a model of internet auction and have shown that there is an equilibrium where every player acts only in the last period of the game. In their model, time is a continuous interval [0, 1) with a distinct last period t = 1. There are two players and valuation of each player can take two values: high or low. In the model of Roth and Ockenfels, there is traffic congestion only in the last period, i.e., a bid submitted in the last period is transmitted successfully with probability p, where 0 < p < 1, while in any other period, all bids are transmitted with probability one. The result of Roth and Ockenfels rely on two key aspects: (i) time before the last period is continuous, so that there is always time to react to any bid, and (ii) other players punish a deviating player by taking the effort of bidding their valuations even though they have zero probability of earning a positive payoff. In this paper, we develop a model of internet auction where time is discrete. Further, we propose a realistic mechanism of bid transfer by making it dependent on the number of submitted bids. First, we show that under suitable assumptions on the bid transfer mechanism, there is a symmetric subgame-perfect equilibrium where every player bids his true valuation unless his bid is transmitted or the current highest bid exceeds his valuation. Then, we make the following reasonable assumption on the behavior of the players: no player acts at a node where he has zero probability of earning a positive payoff. Under this assumption, it is shown that the equilibrium described above is in fact the unique symmetric subgame- perfect equilibrium. Thus, the "last minute bidding" phenomenon of Roth and Ockenfels is not sustained when we consider a discrete-time internet auction.

Talk time: Thursday 24 July, 3:00-3:25     Paper with full author list: nawar.pdf (43 kB, revised June 16)

105   Debapriya Sen:  General Licensing Schemes for a Cost-Reducing Innovation

Optimal combinations of upfront fee and royalty are considered for a cost-reducing innovation in a Cournot oligopoly industry. The consumers are better off, firms are worse off and welfare is increased due to the innovation. The post-innovation price and payoff of any firm is higher with an incumbent innovator. An incumbent innovator sells the license to every firm except perhaps one. This is true for an outsider innovator only for less significant innovations, while for significant innovations, the license is sold to only two firms and a natural duopoly is created. The private value of the patent is increasing in the magnitude of the innovation for both types of innovators. Compared to an outsider, an incumbent producer has higher incentives to develop significant innovations if she assigns a high probability to the event that someone else would succeed to innovate in case she fails, while the converse holds if this probability is small. Finally, for significant innovations, the industry size that provides the highest incentive to innovate increases in the magnitude of the innovation.

Talk time: Wednesday 23 July, 10:50-11:15     Paper with full author list: sentauman.pdf (248 kB, revised June 16)

106   Rabah Amir:  Merger Performance under Uncertain Efficiency Gains

In view of the uncertainty over the ability of merging firms to achieve efficiency gains, we model the post-merger situation as a Cournot oligopoly wherein the outsiders face uncertainty about the merged entity's final cost. At the Bayesian equilibrium, a bilateral merger is profitable provided the non-merged firms sufficiently believe that the merger will generate large enough efficiency gains, even if ex post none actually materialize. The eects of the merger on market performance are shown to follow similar threshold rules. The findings are broadly consistent with stylized facts. An extensive welfare analysis is conducted, bringing out the key role of efficiency gains and the different implications of consumer and social welfare standards.

Talk time: Friday 25 July, 10:50-11:15     Paper with full author list: ADX91.pdf (641 kB, revised June 27)

107   Oleksii Birulin:  Public Goods with Congestion: A Mechanism Design Approach

I consider the problem of efficient provision of the public good with congestion in the setting with asymmetric information. I show, in particular, that when congestion is taken into account, in a wide class of economies it is possible to construct an incentive compatible mechanism that always produces the good at the efficient level, balances the budget and satisfies each consumerís voluntary participation constraint. This result is in contrast with the corresponding impossibility result for pure public goods due to Rob (1989) and Mailath and Postlewiate (1990).

Talk time: Thursday 24 July, 10:15-10:40     Paper with full author list: congestionjuly3.pdf (294 kB, revised July 2)

Last change: Wed Dec 10 11:48:13 GMT 2003 by Bernhard von Stengel