Abstract


Title : On symmetry in routing games

Speaker : Eitan Altman (INRIA)

Abstract: In their pioneering work, Orda, Rom and Shimkin have showed that under mild conditions, symmetric routing games have a potential and have a unique equilibrium. We first extend this result to the case that symmetry holds for a subclass of players. We show that while this does not guarantee anymore uniqueness, still, any equilibrium has a "local potential" in the sense that it can be obtained by replacing the subset of symmetric players by a single player that maximizes some potential. We use this to generalize the results of Haurie and Marcott on convergence of the Nash equilibrium to the Wardrop equilibrium as the number of players grow. We then extend the previous results to more general forms of symmetry.


Title : Rational Expectations in Games: Challenging Nash Equilibrium

Speaker : Robert Aumann (The Hebrew University of Jerusalem)
Coauthor : Jacques Dreze (Université catholique de Louvain)

Abstract: A player i's actions in a game are determined by her beliefs about other players; these depend on the game's real-life context, not only its formal description. Define a game situation as a game together with such beliefs; call the beliefs -and i's resulting expectation- rational if there is common knowledge of rationality and a common prior. In two-person zero-sum games, i's only rational expectation is the game's value. In an arbitrary game G, we characterize i's rational expectations in terms of the correlated equilibria of the doubled game 2G in which each of i's strategies in G appears twice.


Title : Equilibria in Nonatomic Games with a Continuum of Groups

Speaker : Paulo Barelli (University of Rochester)
Coauthor : John Duggan (University of Rochester)

Abstract: We study large games with a product structure on the player set. Players are characterized by the group that they belong and by their individual characteristics. We obtain existence of pure strategy Nash equilibria allowing for infinite dimensional externalities, captured by the average action profile of each group. We allow for non ordered preferences and non compact action sets. The cost is that the action sets must be finite dimensional. We then extend our analysis to Bayesian games with finitely many players, by interpreting one of the components of the player set as the outcomes of randomization devices.


Title : On the Dynamics of the Handicap Principle

Speaker : Pierre Bernhard (INRIA)

Abstract: We recall Zahavi's "Handicap Principle" and its interpretation by Grafen, using the standard concept of games of signalling. Then we sketch a preliminary investigation of the evolutionary dynamics behind the related Bayesian equilibrium, using the replicator dynamics model.


Title : Relaxed Nash Equilibrium Concepts for Discontinuous Games

Speaker : Philippe Bich (U. Paris 1 and PSE)
Coauthor : Rida Laraki (CNRS Polytechnique)


Title : Sex and Evolutionary Stability

Speaker : Ken Binmore (Bristol University)
Coauthor : Larry Samuelson (Yale University)

Abstract: We study evolutionary games in which the rest points of the evolutionary dynamic cluster in connected components, focusing on what we call the Resource Game as a canonical example. The long-term outcome in such games can depend critically on second-order forces that were excluded from the evolutionary dynamics because they are typically insignificant compared with selection pressures. We show that the influence of second-order forces on long-term outcomes can depend on whether the reproduction underlying the evolutionary dynamics is sexual or asexual. An implication is that care is needed in adopting the convenience of an asexual model when examining the behavior of a sexual population in games with nontrivial components of rest points.

Keywords: Second-order forces, drift, stability, sexual reproduction, evolutionary dynamics, replicator dynamics, mutation.


Title : 2-player zero-sum stochastic differential games on a Wiener- and on a Wiener-Poisson space

Speaker : Rainer Buckdahn (Université de Bretagne Occidentale)

Abstract: In this talk, based on recent common work by Buckdahn and Li (2008), Buckdahn, Li and Hu, as well as on the overview paper by Buckdahn, Cardaliaguet and Quincampoix (2010), the problem of existence of a value for a 2-player zero-sum stochastic differential games for a nonlinear payoff is revisited. This approach represent an alternative to that in the pioneering paper on 2-player zero-sum stochastic differential games stochastic differential games by Fleming and Souganidis (1989) on the Wiener space and that by Biswas (2009) on a Winer-Poisson space. Unlike their approach we allow our control processes for a game over the time interval [t,T] to depend on the past of the driving Brownian motion before time t. Once having shown that the upper and lower value functions in our approach are deterministic -which is not evident in our framework- we can prove with the help of Pengs method of backward stochastic differential equations (1997) in a rather straight-forward manner, without additional technical notions like r-strategies, and without approximations, first the dynamic programming principle for the upper and the lower value functions, and after, on the basis of the dynamic programming principle, the fact that both functions are the viscosity solutions of their own associated Hamilton-Jacobi-Bellman-Isaacs equation. Both equations coincide under Isaacs condition and so do the upper and the lower value function, i.e., the game has a value.While the above mentioned papers consider games of the type strategy against control, we consider here games of the type nonanticipating strategy with delay against nonanticipating strategy by adopting the concept developed by Cardaliaguet and Rainer (2009)


Title : Continuous time games with imperfect information.

Speaker : Pierre Cardaliaguet (Univ. Paris-Dauphine)
Coauthor : Catherine Rainer (Université de Bretagne Occidentale)

Abstract: In this talk we will present some recent results on two player, zero sum, continuous time games with imperfect information. These are games in which the time is infinitely divisible and where the players have private information on the system. We will show that, although these games present features which are close to the Aumann-Maschler theory for repeated games with imperfect information (e.g., convexity properties of the value, notion of dual games, etc...), they also possess some specific structure, in particular a characterization in terms of partial differential equations (PDE). The interest of such PDE is to allow for a characterization of the optimal strategies of the players.


Title : Stochastic approximations methods in game theory

Speaker : Mathieu Faure (GREQAM, U. Méditerrannée)

Abstract: We show how stochastic approximations theory provide powerful tools to derive asymptotic results in the context of learning and evolution in games. These methods consist in relating the asymptotic behavior of a stochastic process (e.g. our state variable) to the limit behavior of some mean deterministic dynamics.


Title : Strategic disclosure of random variable

Speaker : Janos Flesch (Maastricht University)
Coauthor : Andres Perea (Maastricht University)

Abstract: We consider a game G(n) played by two players. There are n independent random variables Z(1),…,Z(n), each of which is uniformly distributed on [0,1]. Both players know n, the independence and the distribution of these random variables, but only player 1 knows the vector of realizations z := (z(1),…,z(n)) of them. Player 1 begins by choosing an order z(k(1)),…,z(k(n)) of the realizations. Player 2, who does not know the realizations, faces a stopping problem. At period 1, player 2 learns z(k(1)) . If player 2 accepts, then player 1 pays z(k(1)) euros to player 2 and play ends. Otherwise, if player 2 rejects, play continues similarly at period 2 with player 1 offering z(k(2)) euros to player 2. Play continues until player 2 accepts an offer. If player 2 has rejected n-1 times, player 2 has to accept the last offer at period n. This model extends Moser's (1956) problem, which assumes a non-strategic player 1.

We examine different types of strategies for the players and determine their guarantee-levels. Although we do not find the exact max-min and min-max values of the game G(n) in general, we provide an interval I(n) = [a(n),b(n)] containing these such that the length of I(n) is at most 0.07 and converges to 0 as n tends to infinity. We also point out strategies, with a relatively simple structure, which guarantee that player 1 has to pay at most b(n) and player 2 receives at least a(n). In addition, we completely solve the special case G(2) where there are only two random variables.


Title : Dynamic Information Aggregation with Strategic Experts: A Heuristic Approach

Speaker : Fabrizio Germano (U. Pompeu Fabra)


Title : Deciding the value 1 problem for blind games

Speaker : Hugo Gimbert (LABRI, Université de Bordeaux)

Abstract: We consider the value 1 problem for stochastic games: given a stochastic game with a reachability objective and finitely many states and actions, we want an algorithm to decide whether this game has value 1.
In the case of stochastic games with full monitoring, the problem can be decided in polynomial time. For games with partial observation, the problem is undecidable, even for one player blind games. However, we exhibit class of one-player blind games for which the problem is decidable, using algebraic techniques developed by Simon.


Title : Sequential equilibrium in games with infinite length

Speaker : Julio Gonzalez-Diaz (University of Santiago de Compostela)
Coauthor : Eran Shmaya (Northwestern University)

Abstract: Although originally defined for games with finite length, sequential equilibrium has also been used in the literature to study games with infinite length. In this paper we present several natural extensions of the notion of sequential equilibrium to this setting. Then, we study the logical relations between the different definitions and present a few examples to illustrate the differences between them.


Title : An entropy approach to merging and reputations

Speaker : Olivier Gossner (Paris School of Economics and London School of Economics)

Abstract: We apply relative entropy techniques on merging problems and derive bounds on the value of reputation.


Title : A Folk Theorem for Finitely Repeated Games with Public Monitoring

Speaker : Johannes Horner (Yale)
Coauthor : Jerome Renault (TSE)

Abstract: We adapt the methods from Abreu, Pearce and Stacchetti (1990) to finitely repeated games with imperfect public monitoring. Under a combination of (a slight strengthening of) the assumptions of Benoît and Krishna (1985) and those of Fudenberg, Levine and Maskin (1994), a folk theorem follows.


Title : Equilibrium for discontinuous games and optimal regulation in electricity markets

Speaker : Alejandro Jofre (University of Chile)
Coauthor : Juan Escobar (Stanford University) and Nicolas Figueroa (University of Chile)

Abstract: In this presentation electricity markets are considered including a transmission network, producers generating electricity and an agent doing coordination (Independent System Operator, ISO). Production is organized by means of an auction. Once producers simultaneously bid cost functions, the ISO decides the quantity each generator produces and the flows through the network lines. Producers play strategically with the ISO. When bidding, each firm tries to obtain revenues as high as possible. We prove existence of equilibrium for this discontinuous game and then by using optimal mechanism design, we derive an optimal regulation mechanism for pricing and compare its performance with the bayesian version of the usual price equal to Lagrange multiplier. Finally, we develop the sensitivity analysis with respect to probabilities distributions involved.


Title : Full Disclosure in Organizations

Speaker : Frederic Koessler (Paris School of Economics - CNRS)
Coauthor : Jeanne Hagenbach (Ecole Polytechnique - CNRS)

Abstract: We characterize sufficient conditions for full and decentralized information disclosure in organizations with asymmetrically informed and self interested agents with quadratic loss functions. Incentive conflicts arise because agents have different (and possibly interdependent) ideal actions and different incentives to coordinate with each others. A
fully revealing sequential equilibrium exists in the disclosure game when agents' types are independently distributed, but may fail to exist with correlated types. With common value informational incentive constraints are satisfied ex post, so a fully revealing equilibrium exists even when players' types are correlated.


Title : Information constraints based on coding theorems

Speaker : Samson Lasaulce (LSS Supelec)
Coauthor : Mael Le Treust (LSS Supelec)

Abstract: This talk aims at showing how results from network information theory, coding theorems for multiuser channels in particular, can be used to establish some constraints on the messages sent by the players through the communication graph of the game under consideration and on the admissible set of payoffs.


Title : The Computational Complexity of Games and Markets

Speaker : Andy McLennan (University of Queensland)

Abstract: The paper: a) surveys some recent developments in theoretical computer science concerning the computational complexity of games and economies; b) comments on the scientific consequences of complexity for our understanding of how markets operate.
Any algorithm computing an approximate fixed point of a Brouwer function specified by an oracle has a worst case running time that is exponential in the product of the dimension of the problem and the number of digits of accuracy. Now consider a Brouwer function specified by a Turing machine that computes the function's value at any input. An important series of papers in 2005 resulted in two polynomial time algorithms, the first of which passes from the given Turing machine to a two person normal form game, and the second of which passes from any Nash equilibrium of this game to an approximate fixed point of the function.
Chen et. al. provide two other important polynomial time algorithms. The first of these passes from a two player game to an exchange economy in which each agent has a concave piecewise linear additively separable utility function in which the marginal utility of each good takes on two values. The second passes from a Walrasian equilibrium of this economy to a Nash equilibrium of the given game.
Thus, up to polynomial time transformations, computing an equilibrium of an exchange economy in the indicated class is, in the worst case, as hard as computing an equilibrium of a two person game, and this is in turn as hard as computing an approximate fixed point of any Brouwer function specified by a Turing machine. In itself these and related results do not imply that any particular set of markets cannot be equilibrating, but they do strongly suggest that we should expect full equilibration to be precluded by complexity considerations in some settings.
What should we expect to observe when a system of markets is complex? In two respects financial markets resemble recreational games such as chess, go, bridge, and poker: a) the interactions are zero sum, so cooperation is relatively unimportant; b) by using buy-and-hold strategies one can largely refrain from playing the game. In the mentioned games the strategies employed by successful players are so complex that they cannot be fully described, and from a scientific point of view they should be regarded as unobservable. In each of the mentioned games, the very best players are much better than all but a small number of competitors. Thus we should expect that in complex financial markets simple strategies will not yield excess returns, in line with the empirical literature related to the efficient markets hypothesis, but also that large economic rents will accrue to the most skillful traders, as is strongly suggested by some data.


Title : Random belief learning; a principled smooth best response

Speaker : David Leslie (U. Bristol)


Title : TBA

Speaker : J.F. Mertens (CORE, Louvain-la-Neuve)


Title : Higher Order Game Dynamics

Speaker : Panayotis Mertikopoulos (Ecole Polytechnique)
Coauthor : Rida Laraki (Ecole Polytechnique)
Abstract: Traditional game dynamics in continuous time are first order dynamical systems where payoffs determine the momentum of change (i.e. the growth rate) of the players' strategies. In this paper, we examine what happens beyond first order by considering second (or higher) order game dynamics where payoffs are instead interpreted as forces - and not momenta - of change.
It turns out that writing down a higher order dynamical system which respects the simplicial structure of the game's strategy space is a challenge in itself, so our first task is to derive a wide class of higher order dynamics for evolution and learning. Then, by specializing to the higher order version of the replicator (and other payoff monotonic) dynamics, we illustrate how classical results on the extinction of dominated strategies and the folk theorem need to be modified in higher order settings. In particular, we show that dominated strategies become extinct in nth-order dynamics n orders of magnitude faster than they do in the standard first order setting; similarly, strict equilibria remain asymptotically stable in all orders and nth-order trajectories converge to them n orders of magnitude faster than first order ones. On the other hand, we show that interior equilibria (even evolutionarily stable ones) cannot be attracting beyond first order, and we examine the various types of behavior (chaotic orbits and strange attractors) that this lack of stability leads to.


Title : TBA

Speaker : Bernard De Meyer (CES-Paris 1-PSE)


Title : Continuous-time stochastic games

Speaker : Abraham Neyman (Hebrew University, Jerusalem)

Abstract: We define and study continuous-time stochastic games. Equilibrium is defined unambiguously, and it is proved that every continuous-time stochastic game with finitely many states and actions has a uniform equilibrium payoff. This is in sharp contrast to the discrete-time case where existence is unknown.
In addition, we derive analog results of all the main results of the discounted and undiscounted discrete-time stochastic game. These include the existence of a stationary equilibrium in the discounted non-zero-sum game, the existence of a (uniform) value in two-person zero-sum undiscounted games, and all the results stemming from the algebraic approach to discrete-time stochastic game.


Title :Extending the Condorcet Jury Theorem to a general dependent jury

Speaker : Bezalel Peleg (Hebrew University of Jerusalem)
Coauthor : Shmuel Zamir (Hebrew University of Jerusalem)

Abstract: We investigate necessary and sufficient conditions for the existence of Bayesian-Nash equilibria that satisfy the Condorcet Jury Theorem (CJT). In the Bayesian game G_n among n jurors, we allow for arbitrary distribution on the types of jurors. In particular, any kind of dependency is possible. If each juror i has a "constant strategy", s_i (that is, a strategy that is independent of the size of the jury), such that s = (s_1, s_2, . . . , s_n . . .) satisfies the CJT, then by McLennan (Am Political Sci Rev 92:413-419, 1998) there exists a Bayesian-Nash equilibrium that also satisfies the CJT. We translate the CJT condition on sequences of constant strategies into the following problem:

(**) For a given sequence of binary random variables X = (X^1,X^2, . . . , X^n, . . .) with joint distribution P, does the distribution P satisfy the asymptotic part of the CJT?

We provide sufficient conditions and two general (distinct) necessary conditions for (**).We give a complete solution to this problem when X is a sequence of exchangeable binary random variables.


Title : On the Dynamics of the Handicap Principle

Speaker : Vianney Perchet (ENS-Cachan & Paris 7)
Coauthor : Marc Quincampoix (UBO)

Abstract: Instead of studying sequences of payoffs in a repeated game, we look at the occupation measure on the action spaces induced by the strategies. We define a new abstract repeated game where the outcome at each stage is the maximal information obtained by players, represented as a probability measure. The objective of a player, in this so-called purely informative game, is that the averages of these probability measures converge - with respect to the Wasserstein quadratic distance - to a given set.
We extend the approachability theory developed by Blackwell to this new non-Hilbertian framework, by introducing a notion of a local inner product on the information space. This allows us to propose an equivalent definition of a B-set (which we call B'-set) and we show that a set is approachable if and only if it contains a B'-set. This property can be used to provide a necessary and sufficient condition for the approachability of non-convex sets in usual games with partial monitoring, i.e. where players do not observe their opponent's action but receive signals. And it also coincides with the previously known characterizations of approachable convex sets.


Title :Voting on randomly generated proposals

Speaker : Arkadi Predtetchinski (Maastricht University)
Coauthor : Jean-Jacques Herings (Maastricht University)

Abstract: We study a model of multilateral bargaining where the proposals put to vote arrive randomly. At each period of time the proposal is randomly drawn from a finite set of available alternatives, and the players simultaneously vote on the selected proposal. If the set of players who vote in favor of the proposal is decisive, the proposal is implemented, the players receive their respective payoffs, and the game terminates.
Otherwise, the next period begins. Delay is costless. We consider subgame perfect equilibria in stationary strategies that are weakly undominated in stage games (called voting equilibria). We examine the connections between voting equilibria and the core and give sufficient conditions for the existence of voting equilibria. A characterization of voting equilibria using the players' risk coefficients is provided in the class of 3-player games with three alternatives exhibiting a Condorcet cycle.


Title : Games with incomplete information in continuous time and for continuous type

Speaker : Catherine Rainer ( Université de Bretagne Occidentale)
Coauthor : Pierre Cardaliaguet (Univ. Paris-Dauphine)

Abstract: We consider a two-player zero-sum game with integral payoff and with incomplete information on one side, where the payoff is chosen among a continuous set of possible payoffs. We prove that the value function of this game is solution of an auxiliary optimization problem over a set of measure-valued processes. Then we use this equivalent formulation to characterize the value function as the viscosity solution of a special type of a Hamilton-Jacobi equation. This paper generalizes the results of a previous work of the authors (2009), where only a finite number of possible payoffs is considered


Title : Secure message transmission on directed networks

Speaker : Ludovic Renou (University of Leicester)
Coauthor : Jérome Renault (GREMAQ,TSE) and Tristan Tomala (HEC)

Abstract: Consider a sender S and a receiver R as two distant nodes in an directed graph G. The sender has some private information (a secret), unknown to the receiver and all other nodes in the graph. There is a collection A of potential adversaries; each A in A is a set of nodes in the graph (excluding S and R). For instance, A might be the collection of all set of nodes with at most k elements.
Secret communication between the sender and the receiver is possible if there exists a protocol (profile of behavioral strategies) such that the following two requirements hold: if all nodes abide by the protocol, 1) the receiver correctly learns the secret of the sender and 2) no adversary A in A gets additional information about the secret.
Strongly secure communication between the sender and the receiver is possible if there exists a protocol such that the following requirements hold: 1) secret communication between the sender and the receiver is possible, 2) for any adversary A in A, for any deviation of the adversary A, the receiver correctly learns the secret with arbitrary high probability and no adversary, including A, gets additional information about the secret.
We show that secret communication is possible if and only if the the graph G is weakly A-connected, i.e., for each adversary A in A, there exists a (directed or undirected) path from S to R that does not intersect A.
Additionally, we show that strongly secure communication is possible if and only if for each A in A, the G\A has a strongly 1-connected subgraph that is A-connected, i.e., for each A' in A, there exists a (directed or undirected) path from S to R that does not intersect A'\ A in G\A.
We relate these results to the problem of (partial) implementation of social choice functions on networks.


Title : Sequential Equilibria of Multi-Stage Games with Infinite Sets of Types and Actions

Speaker : Philip J. Reny (University of Chicago)
Coauthor : Roger B. Myerson (University of Chicago)

Abstract: We formulate a definition of basic sequential equilibrium for multi-stage games with infinite type sets and infinite action sets, and we prove its general existence. We then explore several difficulties of this basic concept and propose a definition of extended sequential equilibrium to resolve a problem with step-strategy approximations while maintaining general existence.


Title : Ellsberg Games

Speaker : Frank Riedel (Bielefeld University)
Coauthor : Linda Sass (Bielefeld University)

Abstract: Ambiguity can be used as a strategic device in some situations. To demonstrate this, we develop a framework for normal form games that allows players to use ambiguity strategically. In an Ellsberg game, players may use Anscombe--Aumann acts in addition to the standard objective mixed strategies. We assume that players are ambiguity--averse in the sense of Gilboa and Schmeidler. While classical Nash equilibria remain equilibria in the new game, there arise new Ellsberg equilibria that can be quite different from Nash equilibria. A negotiation game with three players illustrates this finding. We highlight some conceptually interesting properties of Ellsberg equilibria in two person games with conflicting interests.


Title : The Price of Anarchy: Out-of-Equilibrium Guarantees, Intrinsic

Speaker : Tim Roughgarden (Stanford University)

Abstract: The price of anarchy is a measure of the inefficiency of decentralized behavior that has been successfully analyzed in many applications, including network routing, resource allocation, network formation, and even models of basketball. It is defined as the worst-case ratio between the welfare of a Nash equilibrium and that of an optimal solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach an equilibrium. We introduce "smoothness arguments", which yield performance guarantees that apply even when players fail to reach a Nash equilibrium. We explain a sense in which the price of anarchy of selfish routing is "intrinsically robust". We describe recent applications of smoothness arguments to the analysis of Bayes-Nash equilibria of auctions, and also a "local" refinement that yields the first tight bounds on the price of anarchy in atomic splittable routing games.


Title : Sampling Best Response Dynamics and Deterministic Equilibrium Selection

Speaker : Bill Sandholm (U. Wisconsin)
Coauthor : Daisuke Oyama (U. of Tokyo) and Olivier Tercieux (PSE)

Abstract: We consider a model of evolution in games in which a revising agent observes the actions of a randomly-sized random sample of opponents and then chooses a best response to the distribution of actions in the sample. We call the resulting deterministic evolutionary dynamics sampling best response dynamics. We provide conditions on the distribution of sample sizes under which an iterated p-dominant equilibrium is almost globally asymptotically stable under these dynamics. We also show that in generic supermodular games, an equilibrium is stable under the dynamic with fixed sample size k if and only if it is iterated 1/k-dominant. Since our selection results are for deterministic dynamics, any selected equilibrium is reached quickly; in particular, the long waiting times associated with equilibrium selection in stochastic stability models are absent.


Title : A Stochastic Version of Colonel Blotto Game

Speaker : Marco Scarsini (LUISS, Roma and HEC, Paris)
Coauthor : Yosef Rinott (Hebrew University of Jerusalem and LUISS, Roma) and Yaming Yu (University of California, Irvine)

Abstract: We consider a stochastic version of the well-known Blotto game, called the gladiator game. In this zero-sum allocation game two teams of gladiators engage in a sequence of one-to-one fights in which the probability of winning is a function of the gladiators' strengths. Each team's strategy consist the allocation of its total strength among its gladiators. We find the Nash equilibria of the game and compute its value. To do this, we study interesting majorization-type probability inequalities concerning linear combinations of Gamma random variables. The model can be used to analyze some interesting reliability situations.


Title : Control problems and occupational measures

Speaker : Oana Serea (U. Perpignan & UPMC)



Title :The determinacy of infinite games with eventual perfect monitoring

Speaker : Eran Shmaya (Northwestern U)

Abstract: An infinite two-player zero-sum game with a Borel winning set, in which the opponent's actions are monitored eventually but not necessarily immediately after they are played, is determined. The proof relies on a representation of the game as a stochastic game with perfect information, in which Chance operates as a delegate for the players and performs the randomizations for them, and on Martin's Theorem about determinacy of such games.


Title : Attainability in Repeated Games with Vector Payoffs

Speaker : Eilon Solan (Tel Aviv University)
Coauthor : Dario Bauso (Universita Degli Studi di Palermo) and Ehud Lehrer (Tel Aviv University and INSEAD)

Abstract: We study two-player repeated games with vector payoffs in continuous time and introduce the concept of attainable sets of payoff vectors. A set A of payoff vectors is called strongly attainable by player 1 if player 1 has a strategy such that the distance between A and the total payoff up to time T goes to 0 as T goes to infinity. The set A is called attainable by player 1 if for every epsilon > 0, player 1 has a strategy that ensures that this distance is asymptotically at most epsilon. This concept is motivated by applications in multi-inventory control. We provide geometric characterization for the attainability of a specific vector x, as well as to the attainability of all vectors.


Title : Robust approachability and regret minimization in games with partial monitoring

Speaker : Gilles Stoltz (CNRS--ENS--INRIA \& HEC Paris)
Coauthor : Shie Mannor (Technion) and Vianney Perchet (Univ. Paris Diderot)

Abstract: We develop a variant of approachability for games where there is ambiguity in the obtained reward that belongs to a set, rather than being a single vector. Using this variant we tackle the problem of approachability in games with partial monitoring and develop simple and efficient algorithms (i.e., with constant per-step complexity) for this setup. We finally consider external and internal regret in repeated games with partial monitoring, for which we derive regret-minimizing strategies based on approachability theory.


Title : Robust Rationalizability under Almost Common Certainty of Payoffs

Speaker : Satoru Takahashi (Princeton University)
Coauthor : Stephen Morris (Princeton University) and Olivier Tercieux (PSE)

Abstract: An action is robustly rationalizable if it is rationalizable for every type who has almost common certainty of payoffs. We illustrate by means of an example that an action may not be robustly rationalizable even if it is weakly dominant, and argue that robust rationalizability is a very stringent refinement of rationalizability. Nonetheless, we show that every strictly rationalizable action is robustly rationalizable. We also investigate behavioral implications of almost common certainty of certainty of own payoffs.


Title : Robust Equilibria in Sequential Games under Almost Common Belief

Speaker : Olivier Tercieux (PSE)
Coauthor : Satoru Takahashi (Princeton University)

Abstract: We analyze the robustness of equilibria in sequential games when there is almost common belief about payoffs. We show that a generic extensive-form game may have no robust equilibrium strategy, but has at least one robust equilibrium outcome, which is induced by some proper equilibrium. Therefore, backward induction leads to a unique robust outcome in a generic perfect-information game. We also discuss close relation between robustness to incomplete information and strategic stability.

Title : Population Dynamics in Stochastic Games

Speaker : Frank Thuijsman (Maastricht University)
Coauthor : Janos Flesch (Maastricht University), T. Parthasarathy and Philippe Uyttendaele (Maastricht University)

Abstract: We examine a generalization of the concepts Evolutionary Stable Strategy and Replicator Dynamics to the framework of stochastic games. Rather than having a unique fitness matrix according to which the population distribution changes in time, we allow for a finite set of stochastically interrelated fitness matrices that all have their impact on the way the population distribution develops. Using this generalization to some special classes of stochastic games we show that a number of results from the classical one state model extend straightforwardly to the multi-state model. Relations with fictitious play processes are exhibited as well.


Title : Cognitive Games and Cognitive Traps

Speaker : Jean Tirole (TSE)

Abstract : We define cognitive games as games in which players first search for and communicate information, and then play a game (e.g., contract) under the resulting information structure. We show that individually optimal and anticipated cognition can, under some circumstances, be expected to be strategic complements: A higher level of anticipated cognitive activity raises a suspicion and incentivizes the player to indeed engage in more cognition. The framework and insights unify several contributions to the literature.


Title : Perfect equilibrium in games with compact action spaces

Speaker : Dries Vermeulen (Maastricht University)
Coauthor : Elnaz Bajoori (University of Maastricht) and Janos Flesch (University of Maastricht)

Abstract: We investigate the relations between different types of perfect equilibrium, introduced by Simon and Stinchcombe (1995) for games with compact action spaces and continuous payoffs. Simon and Stinchcombe distinguish two approaches to perfect equilibrium in this context, the classical "trembling hand" approach, and the so-called "finitistic" approach. We propose an improved definition of the finitistic approach, called global-limit-offinite perfection, and prove its existence. Despite the fact that the finitistic approach appeals to basic intuition, our results-specifically examples (1) and (2) seem to imply a severe critique on this approach. In the first example any version of finitistic perfect equilibrium admits a Nash equilibrium strategy profile that is not limit admissible. The second example gives a completely mixed (and hence trembling hand perfect) Nash equilibrium that is not finitistically perfect. Further examples illustrate the relations between the two approaches to perfect equilibrium and the relation to admissibility and undominatedness of strategies.


Title : Recursive methods in dynamic bayesian games

Speaker : Nicolas Vieille (HEC)


Title : Existence of the limit value of two person zero-sum discounted repeated games via comparison theorems

Speaker : Guillaume Vigeral (Université Paris Dauphine)
Coauthor : Sylvain Sorin (Université Paris 6)

Abstract: We give new proofs of existence of the limit of the discounted values for two person zero-sum games in the following frameworks: incomplete information, absorbing, recursive. The idea of the new proofs is to use some comparison criteria.


Title : Monotonic dynamics and dominated strategies

Speaker : Yannick Viossat (CEREMADE, Université Paris-Dauphine)

Abstract: We study a model of multilateral bargaining where the proposals put to vote arrive randomly. At each period of time the proposal is randomly drawn from a finite set of available alternatives, and the players simultaneously vote on the selected proposal. If the set of players who vote in favor of the proposal is decisive, the proposal is implemented, the players receive their respective payoffs, and the game terminates.
We survey and unify results on elimination of dominated strategies by monotonic evolutionary dynamics. We show a dual of a result due to Hofbauer and Weibull ("Evolutionary Selection against Dominated Strategies", JET 71, 558-573, 1996): in a sense to be defined, concave monotonic dynamics always eliminate mixed strategies strictly dominated by a pure strategy, and they are essentially the only dynamics with this property.


Title : Codes for Noisy Channels

Speaker : Bernhard von Stengel (LSE)
Coauthor : Penelope Hernandez (CORE, Université Catholique de Louvain)

Abstract: We consider a coordination game between a sender and a receiver who communicate over a noisy channel.
The sender wants to inform the receiver about the state by transmitting a message over the channel. Both receive positive payoff only if the receiver decodes the received signal as the correct state. The sender uses a known "codebook" to map states to messages. When does this codebook define a Nash equilibrium?
The receiver's best response is to decode the received signal as the most likely message that has been sent. Given this decoding, an equilibrium or "Nash code" results if the sender encodes every state as prescribed by the codebook, which is not always the case. We show two theorems that give sufficient conditions for Nash codes. First, the "best" codebook for the receiver (which gives maximum expected receiver payoff) defines a Nash code.
A second, more surprising observation holds for communication over a binary channel which is used independently a number of times, a basic model of information theory: Given a consistent tie-breaking decoding rule which holds generically, ANY codebook of binary codewords defines a Nash code. This holds irrespective of the quality of the code and also for nonsymmetric errors of the binary channel.


Title : An overview of S-adapted equilibria and their applications

Speaker : Georges Zaccour (Chair in Game Theory and Management, GERAD, HEC Montréal)

Abstract: In a first part of the paper, we expose a general theory of games that are played on uncontrolled event trees , {i.e., }games where the transition from one node to another is nature's decision and cannot be influenced by the players' actions. We interpret the concept of $S$-adapted strategies using the classical context of games in extensive form, and we discuss the existence and uniqueness of $S$-adapted equilibria. Next, we extend the concept of S-adapted strategies to multistage games, and provide a maximum principle. In the second part, we discuss some real applications of this class of games to energy markets.


Title : The Strategic Use of Seller Informationin Private-Value Auctions

Speaker : Shmuel Zamir (Center for the Study of Rationality, H. University Jerusalem)
Coauthor : Todd Kaplan (U. Exceter)

Abstract : In the framework of a first-price private-value auction, we study the seller as a player in a game with the buyers in which he has private information about their realized valuations. We find that depending upon his information, set of signals, and commitment power, he may strategically transmit messages to buyers in order to increase his revenue. In an environment where the seller knows the rankings and lacks any commitment power, we find that the seller is unable to exploit his information. However, in an environment where the seller knows the realized valuations and can credibly announce either the true rankings or the true values (or announce nothing at all) but cannot commit as to which of these truthful messages to announce, then it is indeed possible to increase his revenue. If the seller, in addition, can commit to the full signaling strategy, then his expected revenue will be even higher. We believe that this line of research is fruitful for both better understanding behavior in auctions and finding paths to higher seller revenue.
 

Title : Simple optimal strategies: from multi-armed bandits to Markov Decision Processes

Speaker : Wieslaw Zielonka (LIAFA, Université Paris 7)

Abstract: We examine the problem of the existence of optimal deterministic stationary strategies for finite state Markov Decision Processes with payoff mapping that does not depend on the past.
We associate with such a Markov Decision Process M a family F of multi-armed bandits. The arms of each bandit are independent irreducible Markov chains. A multi-armed bandit B from F is said to have a simple optimal strategy if B has an arm such that the strategy consisting in pulling this arm at each stage maximizes the expected payoff. It is shown that if the multi-armed bandits from F have simple optimal strategies then the Markov Decision Process M has an optimal deterministic stationary strategy. We illustrate with examples how this result provides a simple method for proving the existence of optimal deterministic stationary strategies for Markov Decision Processes.

Comments