Abstracts

Miquel Oliu Barton

University Paris Dauphine

The limit game approach in stochastic games

This paper is concerned with the asymptotically optimal strategies in stochastic games with a general evaluation of the stream of stage payoffs. It has been conjectured that these strategies can be obtained by playing the optimal stationary strategies of the discounted game, with a discount factor being the relative weight of the current stage over the remaining fraction of the game. We prove this conjecture in some cases by using a non-algebraic approach recently introduced by the author.

Gilad Bavly

Bar-Ilan University

Online concealed correlation and bounded rationality

"Correlation of players’ actions may evolve in the common course of the play of a repeated game with perfect monitoring (“online correlation”). In this paper we study the concealment of such correlation from a boundedly rational player. We show that “strong” players, i.e., players whose strategic complexity is less stringently bounded, can orchestrate the online correlation of the actions of “weak” players, where this correlation is concealed from an opponent of “intermediate” strength. The feasibility of such “online concealed correlation” is reflected in the individually rational payoff of the opponent and in the equilibrium payoffs of the repeated game.

This result enables the derivation of a folk theorem that characterizes the set of equilibrium payoffs in a class of repeated games with boundedly rational players and a mechanism designer who sends public signals.

The result is illustrated in two models, bounded recall strategies and finite automata."

Krishnendu Chatterjee

IST Austria

Computational and Strategy Complexity for Subclasses of Stochastic Games

The talk will present a survey of several papers related to subclasses of stochastic games. We will focus on two aspects: (1) computational complexity to solve the subclasses; and (2) strategy complexity, in terms of randomization and memory, required to play close to optimally in such games. We will also discuss the most interesting and long-standing open problems for the subclasses.

Omer Edhan

The University of Manchester

Sex And Portfolio Investment

We attempt to answer why sex is nearly ubiquitous when asexual reproduction is ostensibly more efficient than sexual reproduction. From the perspective of a genetic allele, each individual bearing that allele is akin to a stock share yielding dividends equal to that individual's number of offspring, and the totality of individuals bearing the allele is its portfolio investment. Alleles compete over portfolio growth, and evolutionary reproduction strategies are essentially on-line learning algorithms seeking improved portfolio growth, with sexual reproduction a goal-directed algorithmic exploration of genotype space by sampling in each generation. The model assumes a stochastically changing environment but not weak selection. We show that in finite population models the algorithm of sexual reproduction yields, with high probability, higher expected growth than the algorithm of asexual reproduction does, proposing this as an explanation to why a majority of species reproduce sexually.

Funda Ergun

Indiana University and Simon Fraser University

Periodicity in Streams

(Joint work with Hossein Jowhari and Mert Saglam)

"In this talk we consider sublinear space algorithms for detecting periodicity over data streams. A sequence of length n is said to be periodic if it consists of repetitions of a block of length p for some p ≤ n/2. We first give a 1-pass randomized streaming algorithm that uses polylog space and reports the shortest period if the given stream is periodic. At the heart of this result is a 1-pass O(logn logm) space streaming pattern matching algorithm. This algorithm uses similar ideas to Porat and Porat’s algorithm in FOCS 2009 but it does not need an offline pre-processing stage, and is simpler.

In the second part, we focus on streams that are ""close"" to being periodic (with an unknown period), and summarize our work on randomized algorithms to approximate to (2 + epsilon) and (1 + epsilon) factors, in small space, the stream's distance to periodicity, i.e., the minimum number of characters that need to be changed in order to make the stream fully periodic.

Yannai Aharon Gonczarowski

The Hebrew University of Jerusalem and Microsoft Research

A Stable Marriage Requires Communication

(Joint work with Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum)

"The Gale-Shapley algorithm for the Stable Marriage Problem is known to take Θ(n^2) steps to find a stable marriage in the worst case, but only Θ(n*logn) steps in the average case (with n women and n men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that Θ(n^2) queries are required in a model that allows certain natural random-access queries to the participants’ preferences. A significantly more general – albeit slightly weaker – lower bound follows from Segal’s general analysis of communication complexity, namely that Ω(n^2) Boolean queries are required in order to find a stable marriage, regardless of the set of allowed Boolean queries.

Using a reduction to the communication complexity of the disjointness problem, we give a far simpler, yet significantly more powerful argument showing that Ω(n^2) Boolean queries of any type are indeed required for finding a stable – or even an approximately-stable – marriage. Notably, unlike Segal’s lower bound, our lower bound generalizes also to (A) randomized algorithms, (B) even only determining whether a proposed marriage is stable or far from stable, (C) allowing arbitrary separate preprocessing of the women’s preferences profile and of the men’s preferences profile, and (D) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage.

Sergiu Hart

Hebrew University of Jerusalem

Complexity of Correlated Equilibria, and Smooth and Leaky Calibration

(Joint work with Noam Nisan and Dean Foster)

(1) (with Noam Nisan) We consider the complexity of finding a Correlated Equilibrium (CE) in an n-player game in a model that allows the algorithm to make queries for players' utilities at pure strategy profiles. Randomized regret-matching dynamics are known to yield an approximate CE quickly: in time that is polynomial in the number of players n. We show that both randomization and approximation are necessary: no efficient _deterministic_ algorithm can reach an approximate CE, and no efficient randomized algorithm can reach an _exact_ CE.

(2) (with Dean Foster) We propose to smooth out the calibration score which measures how good a forecaster is, by combining together nearby forecasts. While regular calibration can be guaranteed only by randomized forecasting procedures, we show that smooth calibration can be guaranteed by deterministic procedures. As a consequence, it does not matter if the forecasts are leaked, i.e., made known in advance: smooth calibration can nevertheless be guaranteed (while regular calibration cannot). Moreover, our procedure has finite recall, is stationary, and all forecasts lie on a finite grid. We also consider related problems: online linear regression, weak calibration, and uncoupled dynamics in n-person games.

Rida Laraki

CNRS and Ecole Polytechnique

Acyclic Gambling Games

(Joint work with Jérôme Renault)

"A gambling game is a two player zero stochastic game, played in discrete time, where each player controls a gambling house.

A gambling house Γi of player i is a measurable function that assigns to each xi∈Xi a nonempty set Γi(xi) of probability measures defined on the Borel subsets of Xi, where Xi is a metric compact set. Think to two players in a Casin0 where xi is the fortune of player i and Γi(xi) is the set of gambles available to player i when his fortune is xi.

The gambling game is played as follows. At stage t=1,..., knowing the past history of states (x11,x21,...,x1t,x2t), each player i chooses simultaneously as his opponent a probability σit∈Γi(xit). The new states xit+1, i=1,2, are selected according to σit. The pair (x1t+1,x2t+1) is publicly announced and the game moves to stage t+1.

For each discount factor λ∈]0,1[, one can associate a game with total payoff ∑∞t=1λ(1−λ)t−1u(x1t,x2t), where u is some continuous utility function. A standard approach proves that this discounted game has a value vλ, which is the unique fixed point of a λ-Shapley operator.

We prove that, if the gambling houses are non-expensive and irreversible, the asymptotic value limλ→0vλ exists and may be characterized as the unique fixed point of a pair of functional equations which extends the Mertens-Zamir system and the “R\'eduite' operator.


Samson Lasaulce

CNRS

More about more about optimal use of communication resources

The main purpose of this talk is to present several extensions of the work by Gossner, Hernandez, and Neyman (Econometrica 2006). Their original paper provides a characterization of equilibrium payoff of a game involving two agents and nature. One agent is fully aware at any stage of the future realizations of the nature state while the other agent has only a strictly causal knowledge of it. This talk will be focused on the problem of detemining feasible payoffs and several assumptions in particular in terms of monitoring structure will be relaxed.

LE TREUST MAEL

ETIS, UMR 8051 / ENSEA, Université Cergy-Pontoise, CNRS,

Empirical Coordination with Two-Sided State Information and Correlated Source and State

The coordination of autonomous agents is a critical issue for decentralized communication networks. Instead of transmitting information, the agents interact in a coordinated manner in order to optimize a general objective function. A target joint probability distribution is achievable if there exists a code such that the sequences of symbols are jointly typical. The empirical coordination is strongly related to the joint source-channel coding with two-sided state information and correlated source and state. This problem is also connected to state communication and is open for non-causal encoder and decoder. We characterize the optimal solutions for perfect channel, for lossless decoding, for independent source and channel, for causal encoding and for causal decoding.

Peter Bro Miltersen

University of Aarhus

Algebraic sampling theorems with applications to stochastic games

We discuss applications of algebraic sampling theorems of Basu, Pollack and Roy to two-person zero-sum stochastic games.

Ron Peretz

LSE

The complexity of interacting automata

(Joint work with Olivier Gossner and Penelope Hernandez)

This paper studies the interaction of two automata of size m and shows how they can be identied as a more complex automaton of size comparable to m log(m). The set of plays generated by two correlated automata is characterised by studying a statistical property of random plays induced by probability measures on the set of pairs of automata with m states each. We provide possibility and impossibility results regarding the empirical distributions of those distributions. Our results have implications on the correlated min-max value of repeated games played under automaton size constraints.

Siddhartha Sahi

Rutgers University

Money as Minimal Complexity

We consider a fairly general class of mechanisms for commodity exchange. Our first main result is that the imposition of certain natural conditions, embodying ""fairness"" and ""convenience"", reduces this large class to a finite set, with one mechanism for each connected graph on the set commodities.

We next define the notion of the ""complexity"" of a mechanism and show, using graph-theoretic arguments, that as the number of commodities becomes large there is a ""unique"" minimally complex mechanism. This minimal mechanism corresponds to a star-shaped graph with central commodity playing the role of a money.

Sylvain Sorin

UPMC-Paris6

stochastic games and non expansive maps

Recent results on stochastic games and non expansive maps.

Tristan Tomala

HEC Paris

Markov Perfect Equilibria in Stochastic Revision Games

This is joint work with Stefano Lovo (HEC Paris). We introduce the model of Stochastic Revision Games where a finite set of players control a state variable and receive payoffs as a function of the state at a terminal deadline. There is a Poisson clock which dictates when players are called to choose of revise their actions. This paper studies the existence of Markov perfect equilibria in those games. We give an existence proof assuming some form of correlation.

Xavier Venel

Université Paris 1

Pathwise uniform value in Partially Observable Markov Decision Process

(Joint work with Bruno Ziliotto)

"In several standard models of dynamic programming (gambling houses, MDPs, POMDPs), we prove the existence of a very robust notion of value for the infinitely repeated problem, namely the pathwise uniform value. This solves two open problems. First, this shows that for any $\epsilon>0$, the decision-maker has a pure strategy $\sigma$ which is $\epsilon$-optimal in any $n$-stage game, provided that $n$ is big enough (this result was only known for behavior strategies, that is, strategies which use randomization). Second, the strategy $\sigma$ can be chosen such that under the long-run average cost criterion $\m{E}\left(\liminf_{n \rightarrow+\infty} \frac{1}{n} \sum_{m=1}^n g_m \right)$, the decision-maker has more than $\lim_{n \rightarrow +\infty} v_n-\epsilon$.

Guillaume Vigeral

Universite Paris-Dauphine

Operator approach to stochastic games with varying stage duration

"We study the links between the values of stochastic games with varying stage duration h, the corresponding Shapley operators T and $T_h = hT + (1 − h)Id$ and the solution of $f'_t = (T−Id)f_t. Considering general non expansive maps we establish two kinds of results, under both the discounted or the finite duration framework that apply to the class of “exact” stochastic games. On the one hand, for a fixed horizon or discount factor, the value converges as the stage duration go to 0. On the other hand, the asymptotic behavior of the value as the horizon goes to infinity, or as the discount factor goes to 0, does not depend on the stage duration."

Bruno Ziliotto

Université Toulouse 1 Capitole

A Tauberian theorem for nonexpansive operators and applications to zero-sum stochastic games

We prove a Tauberian theorem for nonexpansive operators, and apply it to the model of zero-sum stochastic game. Under mild assumptions, we prove that the value of the lambda-discounted game v_{lambda} converges uniformly when lambda goes to 0 if and only if the value of the n-stage game v_n converges uniformly when n goes to infinity. This generalizes the Tauberian theorem of Lehrer and Sorin (1992) to the two-player zero-sum case. We also provide the first example of a stochastic game with public signals on the state and perfect observation of actions, with finite state space, signal sets and action sets, in which for some initial state k_1 known by both players, (v_{lambda}(k_1)) and (v_n(k_1)) converge to distinct limits.