# Piecewise linear hamiltonian flows associated to zero-sum games: Transition combinatorics and questions on ergodicity

@article{Ostrovski2011PiecewiseLH, title={Piecewise linear hamiltonian flows associated to zero-sum games: Transition combinatorics and questions on ergodicity}, author={Georg Ostrovski and Sebastian van Strien}, journal={Regular and Chaotic Dynamics}, year={2011}, volume={16}, pages={128-153} }

In this paper we consider a class of piecewise affine Hamiltonian vector fields whose orbits are piecewise straight lines. We give a first classification result of such systems and show that the orbit-structure of the flow of such a differential equation is surprisingly rich.

#### Figures from this paper

#### 11 Citations

Dynamics of a continuous piecewise affine map of the square

- Mathematics
- 2014

We present a one-parameter family of continuous, piecewise affine, area preserving maps of the square, which are inspired by a dynamical system in game theory. Interested in the coexistence of… Expand

Hamiltonian flows with random-walk behaviour originating from zero-sum games and fictitious play

- Mathematics
- 2011

In this paper we introduce Hamiltonian dynamics, inspired by zero-sum games (best response and fictitious play dynamics). The Hamiltonian functions we consider are continuous and piecewise affine… Expand

Asymptotics in a family of linked strip maps

- Mathematics
- 2015

Abstract We apply round-off to planar rotations, obtaining a one-parameter family of invertible maps of a two-dimensional lattice. As the angle of rotation approaches π / 2 , the fourth iterate of… Expand

From Darwin to Poincaré and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory

- Computer Science, Mathematics
- WINE
- 2019

It is proved that, if and only if, the system has an interior Nash equilibrium, the dynamics exhibit Poincare recurrence, i.e., almost all orbits come arbitrary close to their initial conditions infinitely often, and two degrees of freedom is sufficient to prove periodicity. Expand

Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System

- Computer Science
- AAMAS
- 2019

This work establishes a formal and robust connection between multi-agent systems and Hamiltonian dynamics -- the same dynamics that describe conservative systems in physics and provides a type of a Rosetta stone that helps to translate results and techniques between online optimization, convex analysis, games theory, and physics. Expand

The route to chaos in routing games: When is price of anarchy too optimistic?

- Mathematics, Computer Science
- NeurIPS
- 2020

A stress test for classic routing games with arbitrarily many strategies, polynomial cost functions, non-atomic as well as atomic routing games and heteregenous users shows that every system has a carrying capacity, above which it becomes unstable. Expand

Fictitious Play: Convergence, Smoothness, and Optimism

- Computer Science, Mathematics
- ArXiv
- 2019

Karlin's conjecture that FP converges at a rate of $O(1/\epsilon^2)$ if the game matrix is diagonal and ties are broken lexicographically is shown, and a matching lower bound under this tie-breaking assumption is shown. Expand

Payoff Performance of Fictitious Play

- Computer Science, Mathematics
- ArXiv
- 2013

It is shown that in many games, fictitious play outperforms Nash equilibrium on average or even at all times, and moreover that any game is linearly equivalent to one in which this is the case. Expand

Fictitious play in 3x3 games: Chaos and dithering behaviour

- Mathematics, Computer Science
- Games Econ. Behav.
- 2011

This paper continues to study a family of games which generalise Shapley's example by introducing an external parameter, and proves that there exists an abundance of periodic and chaotic behaviour with players dithering between different strategies. Expand

Fast Convergence of Fictitious Play for Diagonal Payoff Matrices

- Computer Science, Mathematics
- SODA
- 2021

It is shown that Karlin's conjecture is indeed correct for the class of diagonal payoff matrices, as long as ties are broken lexicographically, and this bound is tight by showing a matching lower bound in the identity payoff case under the lexicographic tie-breaking assumption. Expand

#### References

SHOWING 1-10 OF 15 REFERENCES

Hamiltonian flows with random-walk behaviour originating from zero-sum games and fictitious play

- Mathematics
- 2011

In this paper we introduce Hamiltonian dynamics, inspired by zero-sum games (best response and fictitious play dynamics). The Hamiltonian functions we consider are continuous and piecewise affine… Expand

Non-Smooth Dynamical Systems

- Mathematics
- 2000

Some general theory of differential inclusions.- Bounded, unbounded, periodic, and almost periodic solutions.- Lyapunov exponents for non-smooth dynamical systems.- On the application of Conley index… Expand

Piecewise-smooth Dynamical Systems: Theory and Applications

- Mathematics
- 2007

Qualitative theory of non-smooth dynamical systems.- Border-collision in piecewise-linear continuous maps.- Bifurcations in general piecewise-smooth maps.- Boundary equilibrium bifurcations in… Expand

A new class of Hamiltonian flows with random-walk behavior originating from zero-sum games and Fictitious Play

- Mathematics
- 2009

In this paper we relate dynamics associated to zero-sum games (Fictitious play) to Hamiltonian dynamics. It turns out that the Hamiltonian dynamics which is induced from fictitious play, has… Expand

Fictitious play in 2×n games

- Mathematics, Computer Science
- J. Econ. Theory
- 2005

A simple geometric proof of the conjecture that convergence to equilibrium holds generally for 2xn games is given. Expand

Existence of Solutions to Differential Inclusions

- Physics
- 1984

In what follows we shall deal with the existence and properties of solutions to differential inclusions of the form
$$x'\left( t \right) \in F\left( {x\left( t \right)} \right)$$
(1)
or
… Expand

Fictitious play in 3×3 games: The transition between periodic and chaotic behaviour

- Mathematics, Computer Science
- Games Econ. Behav.
- 2008

It is shown that the periodic behaviour in Shapley's example at some critical parameter value disintegrates into unpredictable (chaotic) behaviour, with players dithering a huge number of times between different strategies. Expand

Differential inclusions set-valued maps and viability theory

- Mathematics
- 1984

0. Background Notes.- 1. Continuous Partitions of Unity.- 2. Absolutely Continuous Functions.- 3. Some Compactness Theorems.- 4. Weak Convergence and Asymptotic Center of Bounded Sequences.- 5.… Expand

Piecewise smooth dynamical systems

- Mathematics, Computer Science
- Scholarpedia
- 2008

One of the books that can be recommended for new readers is piecewise smooth dynamical systems, which is not kind of difficult book to read. Expand

NON-COOPERATIVE GAMES

- Mathematics
- 1951

we would call cooperative. This theory is based on an analysis of the interrelationships of the various coalitions which can be formed by the players of the game. Our theory, in contradistinction, is… Expand