The Experts below are selected from a list of 309 Experts worldwide ranked by ideXlab platform
Christopher Umans  One of the best experts on this subject based on the ideXlab platform.

On the Complexity of Succinct ZeroSum Games
computational complexity, 2008CoAuthors: Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher UmansAbstract:We study the complexity of solving succinct ZeroSum Games, i.e., the Games whose payoff matrix M is given implicitly by a Boolean circuit C such that M ( i , j ) = C ( i , j ). We complement the known EXP hardness of computing the exact value of a succinct ZeroSum game by several results on approximating the value. (1) We prove that approximating the value of a succinct ZeroSum game to within an additive error is complete for the class promise  $$S^{p}_{2}$$ , the “promise” version of $$S^{p}_{2}$$ . To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP ^ NP algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct ZeroSum game. As a corollary, we obtain, in a uniform fashion, several complexitytheoretic results, e.g., a ZPP ^ NP algorithm for learning circuits for SAT (Bshouty et al., JCSS , 1996) and a recent result by Cai ( JCSS , 2007) that $$S^{p}_{2} \subseteq$$ ZPP ^ NP . (3) We observe that approximating the value of a succinct ZeroSum game to within a multiplicative factor is in PSPACE , and that it cannot be in promise  $$S^{p}_{2}$$ unless the polynomialtime hierarchy collapses. Thus, under a reasonable complexitytheoretic asSumption, multiplicativefactor approximation of succinct ZeroSum Games is strictly harder than additiveerror approximation.

on the complexity of succinct Zero Sum Games
Conference on Computational Complexity, 2005CoAuthors: Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher UmansAbstract:We study the complexity of solving succinct ZeroSum Games, i.e., the Games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the known EXPhardness of computing the exact value of a succinct ZeroSum game by several results on approximating the value. (1) We prove that approximating the value of a succinct ZeroSum game to within an additive factor is complete for the class promiseS/sub 2//sup p/, the "promise" version of S/sub 2//sup p/. To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP/sup NP/ algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct ZeroSum game. As a corollary, we obtain, in a uniform fashion, several complexitytheoretic results, e.g., a ZPP/sup NP/ algorithm for learning circuits for SAT (Bshouty et al., 1996) and a recent result by Cai (2001) that S/sub 2//sup p/ /spl sube/ ZPP/sup NP/. (3) We observe that approximating the value of a succinct ZeroSum game to within a multiplicative factor is in PSPACE, and that it cannot be in promiseS/sub 2//sup p/ unless the polynomialtime hierarchy collapses. Thus, under a reasonable complexitytheoretic asSumption, multiplicative factor approximation of succinct ZeroSum Games is strictly harder than additive factor approximation.

On the Complexity of Succinct ZeroSum Games (Preliminary Version)
2004CoAuthors: Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher UmansAbstract:We study the complexity of solving succinct ZeroSum Games, i.e., the Games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the known EXPhardness of computing the exact value of a succinct ZeroSum game by several results on approximating the value. (1) We prove that approximating the value of a succinct ZeroSum game to within an additive factor is complete for the class promiseS p 2, the “promise”

IEEE Conference on Computational Complexity  On the complexity of succinct ZeroSum Games
20th Annual IEEE Conference on Computational Complexity (CCC'05), 1CoAuthors: Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher UmansAbstract:We study the complexity of solving succinct ZeroSum Games, i.e., the Games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i, j) = C(i, j). We complement the known EXPhardness of computing the exact value of a succinct ZeroSum game by several results on approximating the value. (1) We prove that approximating the value of a succinct ZeroSum game to within an additive factor is complete for the class promiseS/sub 2//sup p/, the "promise" version of S/sub 2//sup p/. To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP/sup NP/ algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct ZeroSum game. As a corollary, we obtain, in a uniform fashion, several complexitytheoretic results, e.g., a ZPP/sup NP/ algorithm for learning circuits for SAT (Bshouty et al., 1996) and a recent result by Cai (2001) that S/sub 2//sup p/ /spl sube/ ZPP/sup NP/. (3) We observe that approximating the value of a succinct ZeroSum game to within a multiplicative factor is in PSPACE, and that it cannot be in promiseS/sub 2//sup p/ unless the polynomialtime hierarchy collapses. Thus, under a reasonable complexitytheoretic asSumption, multiplicative factor approximation of succinct ZeroSum Games is strictly harder than additive factor approximation.
Alexander J. Zaslavski  One of the best experts on this subject based on the ideXlab platform.

Dynamic ZeroSum Games with Linear Constraints
Turnpike Theory of ContinuousTime Linear Optimal Control Problems, 2015CoAuthors: Alexander J. ZaslavskiAbstract:In this chapter we study the existence and turnpike properties of approximate solutions for a class of dynamic continuoustime twoplayer ZeroSum Games without using convexityconcavity asSumptions. We describe the structure of approximate solutions which is independent of the length of the interval, for all sufficiently large intervals and show that approximate solutions are determined mainly by the objective function, and are essentially independent of the choice of interval and endpoint conditions.

Dynamic DiscreteTime ZeroSum Games
Turnpike Phenomenon and Infinite Horizon Optimal Control, 2014CoAuthors: Alexander J. ZaslavskiAbstract:In this chapter we study the existence and structure of solutions for dynamic discretetime twoplayer ZeroSum Games and establish a turnpike result. This result describes the structure of approximate solutions which is independent of the length of the interval, for all sufficiently large intervals. We also show that for each initial state there exists a pair of overtaking equilibria strategies over an infinite horizon.

Structure of approximate solutions of dynamic continuous time ZeroSum Games
Journal of Dynamics & Games, 2014CoAuthors: Alexander J. ZaslavskiAbstract:In this paper we study a turnpike property of approximate solutions for a class of dynamic continuoustime twoplayer ZeroSum Games. These properties describe the structure of approximate solutions which is independent of the length of the interval, for all sufficiently large intervals.

Turnpike properties of approximate solutions of dynamic discrete time ZeroSum Games
Journal of Dynamics & Games, 2014CoAuthors: Alexander J. ZaslavskiAbstract:We study existence and turnpike properties of approximate solutions for a class of dynamic discretetime twoplayer ZeroSum Games without using convexityconcavity asSumptions. We describe the structure of approximate solutions which is independent of the length of the interval, for all sufficiently large intervals and show that approximate solutions are determined mainly by the objective function, and are essentially independent of the choice of interval and endpoint conditions.

The turnpike property for dynamic discrete time ZeroSum Games
Abstract and Applied Analysis, 1999CoAuthors: Alexander J. ZaslavskiAbstract:We consider a class of dynamic discretetime twoplayer ZeroSum Games. We show that for a generic cost function and each initial state, there exists a pair of overtaking equilibria strategies over an infinite horizon. We also establish that for a generic cost function f, there exists a pair of stationary equilibria strategies (xf,yf) such that each pair of “approximate” equilibria strategies spends almost all of its time in a small neighborhood of (xf,yf).
Georgios Piliouras  One of the best experts on this subject based on the ideXlab platform.

Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in ZeroSum Games
arXiv: Computer Science and Game Theory, 2019CoAuthors: Yun Kuen Cheung, Georgios PiliourasAbstract:We establish that algorithmic experiments in ZeroSum Games "fail miserably" to confirm the unique, sharp prediction of maxmin equilibration. Contradicting nearly a century of economic thought that treats ZeroSum Games nearly axiomatically as the exemplar symbol of economic stability, we prove that no meaningful prediction can be made about the daytoday behavior of online learning dynamics in ZeroSum Games. Concretely, Multiplicative Weights Updates (MWU) with constant stepsize is Lyapunov chaotic in the dual (payoff) space. Simply put, let's asSume that an observer asks the agents playing MatchingPennies whether they prefer Heads or Tails (and by how much in terms of aggregate payoff so far). The range of possible answers consistent with any arbitrary small set of initial conditions blows up exponentially with time everywhere in the payoff space. This result is robust both algorithmically as well as game theoretically: 1) Algorithmic robustness: Chaos is robust to agents using any of a general subfamily of FollowtheRegularizedLeader (FTRL) algorithms, the well known regretminimizing dynamics, even when agents mixandmatch dynamics, use different or slowly decreasing stepsizes. 2) Game theoretic robustness: Chaos is robust to all affine variants of ZeroSum Games (strictly competitive Games), network variants with arbitrary large number of agents and even to competitive settings beyond these. Our result is in stark contrast with the timeaverage convergence of online learning to (approximate) Nash equilibrium, a result widely reported as "(weak) convergence to equilibrium".

AAMAS  MultiAgent Learning in Network ZeroSum Games is a Hamiltonian System
2019CoAuthors: James P. Bailey, Georgios PiliourasAbstract:ZeroSum Games are natural, if informal, analogues of closed physical systems where no energy/utility can enter or exit. This analogy can be extended even further if we consider ZeroSum network (polymatrix) Games where multiple agents interact in a closed economy. Typically, (network) ZeroSum Games are studied from the perspective of Nash equilibria. Nevertheless, this comes in contrast with the way we typically think about closed physical systems, e.g., Earthmoon systems which move perpetually along recurrent trajectories of constant energy. We establish a formal and robust connection between multiagent systems and Hamiltonian dynamics  the same dynamics that describe conservative systems in physics. Specifically, we show that no matter the size, or network structure of such closed economies, even if agents use different online learning dynamics from the standard class of FollowtheRegularizedLeader, they yield Hamiltonian dynamics. This approach generalizes the known connection to Hamiltonians for the special case of replicator dynamics in two agent ZeroSum Games developed by Hofbauer. Moreover, our results extend beyond ZeroSum settings and provide a type of a Rosetta stone (see e.g. Table 1) that helps to translate results and techniques between online optimization, convex analysis, Games theory, and physics.

MultiAgent Learning in Network ZeroSum Games is a Hamiltonian System
arXiv: Computer Science and Game Theory, 2019CoAuthors: James P. Bailey, Georgios PiliourasAbstract:ZeroSum Games are natural, if informal, analogues of closed physical systems where no energy/utility can enter or exit. This analogy can be extended even further if we consider ZeroSum network (polymatrix) Games where multiple agents interact in a closed economy. Typically, (network) ZeroSum Games are studied from the perspective of Nash equilibria. Nevertheless, this comes in contrast with the way we typically think about closed physical systems, e.g., Earthmoon systems which move perpetually along recurrent trajectories of constant energy. We establish a formal and robust connection between multiagent systems and Hamiltonian dynamics  the same dynamics that describe conservative systems in physics. Specifically, we show that no matter the size, or network structure of such closed economies, even if agents use different online learning dynamics from the standard class of FollowtheRegularizedLeader, they yield Hamiltonian dynamics. This approach generalizes the known connection to Hamiltonians for the special case of replicator dynamics in two agent ZeroSum Games developed by Hofbauer. Moreover, our results extend beyond ZeroSum settings and provide a type of a Rosetta stone (see e.g. Table 1) that helps to translate results and techniques between online optimization, convex analysis, Games theory, and physics.

NeurIPS  Fast and Furious Learning in ZeroSum Games: Vanishing Regret with NonVanishing Step Sizes
2019CoAuthors: James P. Bailey, Georgios PiliourasAbstract:We show for the first time that it is possible to reconcile in online learning in ZeroSum Games two seemingly contradictory objectives: vanishing timeaverage regret and nonvanishing step sizes. This phenomenon, that we coin ``fast and furious" learning in Games, sets a new benchmark about what is possible both in maxmin optimization as well as in multiagent systems. Our analysis does not depend on introducing a carefully tailored dynamic. Instead we focus on the most well studied online dynamic, gradient descent. Similarly, we focus on the simplest textbook class of Games, twoagent twostrategy ZeroSum Games, such as Matching Pennies. Even for this simplest of benchmarks the best known bound for total regret, prior to our work, was the trivial one of $O(T)$, which is immediately applicable even to a nonlearning agent. Based on a tight understanding of the geometry of the nonequilibrating trajectories in the dual space we prove a regret bound of $\Theta(\sqrt{T})$ matching the well known optimal bound for adaptive step sizes in the online setting. This guarantee holds for all fixed stepsizes without having to know the time horizon in advance and adapt the fixed stepsize accordingly.As a corollary, we establish that even with fixed learning rates the timeaverage of mixed strategies, utilities converge to their exact Nash equilibrium values. We also provide experimental evidence suggesting the stronger regret bound holds for all ZeroSum Games.

EC  Multiplicative Weights Update in ZeroSum Games
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018CoAuthors: James P. Bailey, Georgios PiliourasAbstract:We study the classic setting where two agents compete against each other in a ZeroSum game by applying the Multiplicative Weights Update (MWU) algorithm. In a twist of the standard approach of [Freund and Schapire 1999], we focus on the KL divergence from the equilibrium but instead of providing an upper bound about the rate of increase we provide a nonnegative lower bound for Games with interior equilibria. This implies movement away from equilibria and towards the boundary. In the case of ZeroSum Games without interior equilibria convergence to the boundary (and in fact to the minimal product of subsimplexes that contains all Nash equilibria) follows via an orthogonal argument. In that subspace divergence from the set of NE applies for all nonequilibrium initial conditions via the first argument. We argue the robustness of this nonequilibrating behavior by considering the following generalizations: Step size: Agents may be using different and even decreasing step sizes. Dynamics: Agents may be using FollowtheRegularizedLeader algorithms and possibly apply different regularizers (e.g. MWU versus Gradient Descent). We also consider a linearized version of MWU. More than two agents: Multiple agents can interact via arbitrary networks of ZeroSum polymatrix Games and their affine variants. Our results come in stark contrast with the standard interpretation of the behavior of MWU (and more generally regret minimizing dynamics) in ZeroSum Games, which is typically referred to as "converging to equilibrium". If equilibria are indeed predictive even for the benchmark class of ZeroSum Games, agents in practice must deviate robustly from the axiomatic perspective of optimization driven dynamics as captured by MWU and variants and apply carefully tailored equilibriumseeking behavioral dynamics.
Sylvain Sorin  One of the best experts on this subject based on the ideXlab platform.

ZeroSum Games: The Finite Case
Universitext, 2019CoAuthors: Rida Laraki, Jérôme Renault, Sylvain SorinAbstract:This chapter studies ZeroSum Games, where the sets of strategies are finite. We prove the minmax theorem of von Neumann, which states that if a game is played with mixed strategies (probability distribution on strategies) then the value exists, as well as an optimal mixed strategy for each player. We then consider extensions such as Loomis’ theorem and Ville’s theorem. Finally, we introduce and study the convergence of the learning process “Fictitious Play”, where the initial game is repeated and each player plays at every period a best response to the average of the strategies played by his opponent in the past.

ZeroSum Games: The General Case
Universitext, 2019CoAuthors: Rida Laraki, Jérôme Renault, Sylvain SorinAbstract:This chapter considers general ZeroSum Games and proves various minmax theorems. We start with Sion’s theorem with geometrical and topological asSumptions on the game: convex compact strategy sets and payoff functions quasiconcave upper semicontinuous in the first variable and quasiconvex lower semicontinuous in the second variable. Then we prove the standard minmax theorem in mixed strategies for measurable bounded payoff functions, extending von Neumann’s theorem, under topological asSumptions: compact Hausdorff strategy sets and payoff functions upper semicontinuous in the first variable and lower semicontinuous in the second variable. We conclude the chapter with the introduction of the value operator and the notion of a derived game, which play an important role in the operator approach to repeated Games.

LIMIT VALUE OF DYNAMIC ZeroSum Games WITH VANISHING STAGE DURATION
Mathematics of Operations Research, 2018CoAuthors: Sylvain SorinAbstract:We consider twoperson ZeroSum Games where the players control, at discrete times {tn} induced by a partition Π of ℝ+, a continuous time Markov process. We prove that the limit of the values υΠ exist as the mesh of Π goes to 0. The analysis covers the cases of (1) stochastic Games (where both players know the state), and (2) Games with unknown state and symmetric signals. The proof is by reduction to deterministic differential Games.

Limit value of dynamic ZeroSum Games with vanishing stage duration
arXiv: Optimization and Control, 2016CoAuthors: Sylvain SorinAbstract:We consider two person ZeroSum Games where the players control, at discrete times {tn} induced by a partition $\Pi$ of R + , a continuous time Markov state process. We prove that the limit of the values v$\Pi$ exist as the mesh of $\Pi$ goes to 0. The analysis covers the cases of : 1) stochastic Games (where both players know the state) 2) symmetric no information. The proof is by reduction to a deterministic differential game.

BEST RESPONSE DYNAMICS FOR CONTINUOUS Zero{Sum Games
Discrete & Continuous Dynamical Systems  B, 2006CoAuthors: Josef Hofbauer, Sylvain SorinAbstract:We study best response dynamics in continuous time for continuous concaveconvex ZeroSum Games and prove convergence of its trajectories to the set of saddle points, thus providing a dynamical proof of the minmax theorem. Consequences for the corresponding discrete time process with small or diminishing stepsizes are established, including convergence of the fictitious play procedure.
Manuela Veloso  One of the best experts on this subject based on the ideXlab platform.

AAAI  Thresholded rewards: acting optimally in timed, ZeroSum Games
2007CoAuthors: Colin Mcmillen, Manuela VelosoAbstract:In timed, ZeroSum Games, the goal is to maximize the probability of winning, which is not necessarily the same as maximizing our expected reward. We consider cumulative intermediate reward to be the difference between our score and our opponent's score; the "true" reward of a win, loss, or tie is determined at the end of a game by applying a threshold function to the cumulative intermediate reward. We introduce thresholdedrewards problems to capture this dependency of the final reward outcome on the cumulative intermediate reward. Thresholdedrewards problems reflect different realworld stochastic planning domains, especially ZeroSum Games, in which time and score need to be considered. We investigate the application of thresholded rewards to finitehorizon Markov Decision Processes (MDPs). In general, the optimal policy for a thresholdedrewards MDP will be nonstationary, depending on the number of time steps remaining and the cumulative intermediate reward. We introduce an efficient value iteration algorithm that solves thresholdedrewards MDPs exactly, but with running time quadratic on the number of states in the MDP and the length of the time horizon. We investigate a number of heuristicbased techniques that efficiently find approximate solutions for MDPs with large state spaces or long time horizons.

Plenary learning to select team strategies in finitetimed ZeroSum Games
2007CoAuthors: Manuela VelosoAbstract:Games, by definition, offer the challenge of the presence of an opponent, to which a playing strategy should respond. In finitetimed ZeroSum Games, the strategy should enable to win the game within a limited playing time. Motivated by robot soccer, in this talk, we will present several approaches towards learning to select team strategies in such finitetimed ZeroSum Games. We will introduce an adaptive playbook approach with implicit opponent modeling, in which multiple team strategies are represented as variable weighted plays. We will discuss different plays as a function of different game situations and opponents. In conclusion, we will present an MDPbased learing algorithm to reason in particular about current score and game time left. Through extensive simulated empirical studies, we will demonstrate the effectiveness of the learning approach. In addition, the talk will include illustrative examples from robot soccer. The major part of this work is in conjunction with my PhD student Colin McMillen.

AI*IA  Learning to Select Team Strategies in FiniteTimed ZeroSum Games
Lecture Notes in Computer Science, 1CoAuthors: Manuela VelosoAbstract:Games, by definition, offer the challenge of the presence of an opponent, to which a playing strategy should respond. In finitetimed ZeroSum Games, the strategy should enable to win the game within a limited playing time. Motivated by robot soccer, in this talk, we will present several approaches towards learning to select team strategies in such finitetimed ZeroSum Games. We will introduce an adaptive playbook approach with implicit opponent modeling, in which multiple team strategies are represented as variable weighted plays. We will discuss different plays as a function of different game situations and opponents. In conclusion, we will present an MDPbased learning algorithm to reason in particular about current score and game time left. Through extensive simulated empirical studies, we will demonstrate the effectiveness of the learning approach. In addition, the talk will include illustrative examples from robot soccer. The major part of this work is in conjunction with my PhD student Colin McMillen.