|
Abstracts |
|
University Paris Dauphine The limit game approach in stochastic games Abstract 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. |
|
Bar-Ilan University Online concealed correlation and bounded rationality [pdf] Abstract
"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. |
|
IST Austria Computational and Strategy Complexity for Subclasses of Stochastic Games Abstract
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. |
|
The University of Manchester Sex And Portfolio Investment Abstract
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. |
|
Indiana University and Simon Fraser University Periodicity in Streams (joint work with Hossein Jowhari and Mert Saglam) Abstract
"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. |
|
The Hebrew University of Jerusalem and Microsoft Research A Stable Marriage Requires Communication (joint work with Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum) Abstract
"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. |
|
Hebrew University of Jerusalem Complexity of Correlated Equilibria, and Smooth and Leaky Calibration (joint work with Noam Nisan and Dean Foster) Abstract
(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. |
|
CNRS and Ecole Polytechnique Acyclic Gambling Games (joint work with Jérôme Renault) Abstract
"A gambling game is a two player zero stochastic game, played in discrete time, where each player controls a gambling house. |
|
CNRS More about more about optimal use of communication resources Abstract
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. |
|
ETIS, UMR 8051 / ENSEA, Université Cergy-Pontoise, CNRS, Empirical Coordination with Two-Sided State Information and Correlated Source and State [pdf] Abstract
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. |
|
University of Aarhus Algebraic sampling theorems with applications to stochastic games Abstract We discuss applications of algebraic sampling theorems of Basu, Pollack and Roy to two-person zero-sum stochastic games. |
|
LSE The complexity of interacting automata [pdf] (joint work with Olivier Gossner and Penelope Hernandez) Abstract
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. |
|
Rutgers University Money as Minimal Complexity [pdf] Abstract
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. |
|
UPMC-Paris6 stochastic games and non expansive maps Abstract
Recent results on stochastic games and non expansive maps. |
|
HEC Paris Markov Perfect Equilibria in Stochastic Revision Games [pdf] Abstract
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. |
|
Université Paris 1 Pathwise uniform value in Partially Observable Markov Decision Process (joint work with Bruno Ziliotto) Abstract
"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$. |
|
Universite Paris-Dauphine Operator approach to stochastic games with varying stage duration Abstract
"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." |
|
Université Toulouse 1 Capitole A Tauberian theorem for nonexpansive operators and applications to zero-sum stochastic games [pdf] Abstract 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. |
