All presentations are in PDF format; typical file size is 1MB. The files represent the newest version, older talks may have been different (and sometimes had different titles). Please do not use these slides without my permission. Thanks!

- Computationally efficient coordination in game trees
- Equilibrium Algorithms for Two-Player Games
- Finding all Nash equilibria of a bimatrix game
- Games, Geometry, and the Computational Complexity of Finding Equilibria
- Geometric Views of Linear Complementarity Algorithms and Their Complexity
- Hard-to-Solve Bimatrix Games
- Leadership Games
- Nash Codes for Noisy Channels
- Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)
- Strategic Characterization of the Index of an Equilibrium

**Abstract:**
The solution concept of ``correlated equilibrium''
allows for coordination in games.
For game trees with imperfect information, it gives rise to
NP-hard problems, even for two-player games without chance
moves.
We introduce the ``extensive form correlated equilibrium''
(EFCE), which extends Aumann's correlated equilibrium,
where coordination is achieved by signals that are
received ``locally'' at information sets.
An EFCE is polynomial-time computable
for two-player games without chance moves.

(Joint work with Francoise Forges.)

**Talks given:**

- 27 January 2006, Workshop on Strategic Communication and Networks, University of Valencia, Spain.
- 24 April 2004, Game Theory Seminar, Waseda University, Tokyo, Japan.
- 13 September 2003, Workshop on Complexity in Economic Theory, Cowles Foundation for Research in Economics, Yale University, New Haven, Connecticut, USA.
- 23 July 2003, 14th International Conference on Game Theory at Stony Brook, New York, USA.
- 11 February 2002, Mittagsseminar, Department of Computer Science, ETH Zurich, Switzerland.
- 20 December 2001, Seminar, University of Paris X and THEMA, France.
- 18 October 2001, Economics Seminar, University of Stockholm, Sweden.

Survey in the Handbook of Game Theory

**Abstract:**
We survey algorithms for finding equilibria of
two-player games in strategic form and extensive form.
The main tool are polyhedra that show a player's
mixed strategies and the other player's pure best responses.
For extensive games, the exponential size of the strategic
form is avoided by using the "sequence form" which has the
same size as the game tree.

**Talks given:**

- 10 September 2008, Invited talk at GAMES 2008, Annual Workshop of the ESF Networking Program on Games for Design and Verification, Warsaw, Poland.
- 29 April 2008, AEOLUS Spring School on Algorithmic Principles of Selfishness and Mechanism Design, Paderborn, Germany.
- 27-28 June 2006, Summer School on Game Theory in Computer Science, University of Aarhus, Denmark.

**Abstract:**
We describe algorithms for finding all Nash equilibria of a
two-player game in strategic form. We present two algorithms
that extend earlier work. Our presentation is
self-contained, and explains the two methods in a unified
frame-work using faces of best-response polyhedra. The
first method lrsNash is based on the known vertex
enumeration program lrs, for "lexicographic reverse search".
It enumerates the vertices of only one best-response
polytope, and the vertices of the complementary faces that
correspond to these vertices (if they are not empty) in the
other polytope. The second method is a modification of the
known EEE algorithm, for "enumeration of extreme equilibria".
We report on computational experiments that compare the two
algorithms, which show that both have their strengths and
weaknesses.

(Joint work with David Avis, Gabriel Rosenberg,
and Rahul Savani.)

**Talks given:**

- 26 March 2007, DIMAP Workshop on Algorithmic Game Theory, University of Warwick

Song "Find the longest path" by Dan Barrett (MP3-file).

**Abstract:**
Game-theoretic problems have found massive recent interest
in computer science. Obvious applications arise from the
internet, for example the study of online auctions.
In theoretical computer science, some of the most intriguing
open problems concern the time that an algorithm needs to
find a Nash equilibrium of a game. We give a survey of
these open problems, which depend on the type of game
considered. For bimatrix games, Nash equilibria are best
understood geometrically, but recent results seem to make
it unlikely that a "polynomial-time" algorithm for finding
a Nash equilibrium exists. Zero-sum "simple stochastic
games", on the other hand, are likely to be solvable in
polynomial time, but a corresponding algorithm continues to
be elusive. The talk is directed at a general audience, not
at experts in computational complexity.

**Talks given:**

- 13 July 2006, Invited plenary talk, 17th International Conference on Game Theory, Stony Brook, New York, USA.

We review two main geometric views of the algorithms by Lemke-Howson and Lemke: the polyhedral view, which describes the nonnegativity (feasilibity) constraints, and the "complementary cones" view, which maintains complementarity. Using complementary cones, Lemke's algorithm is seen as inverting a piecewise linear map along a line segment. One new result is that the underlying "LCP map" is surjective for the equilibrium problem (requiring only that the LCP matrix is positive), so the algorithm can be started anywhere. A second result shows that the Lemke-Howson algorithm is a special case of this description, giving it a unified view with Lemke's algorithm.

(Joint work with Rahul Savani.)

**Talks given:**

- 18 February 2009, Game Theory and Computer Science Day, Chevaleret, University of Paris 6
- 17 May 2006, Workshop on Complexity of Games, Polyhedra and Lattice Points, ETH Zurich, Switzerland.
- 25 July 2005, Mathematics department, George Mason University, Virginia, USA.
- 21 July 2005, Workshop on Game Theory and Computer Science, Stony Brook, New York, USA.
- 19 July 2005, Seminar, GERAD, University of Montreal, Canada.

**Abstract:**
A bimatrix game is a two-player game in strategic form, a
basic model in game theory. A Nash equilibrium is a pair of
(possibly randomized) strategies, one for each player, so
that no player can do better by unilaterally changing his or
her strategy. The exact computational complexity of finding
one Nash equilibrium of a bimatrix game is open. Already a
subexponential algorithm would be a major breakthrough in
the field.

In this talk, which will introduce the main concepts and
geometric tools, we show that the commonly used Lemke-Howson
algorithm for finding one equilibrium of a bimatrix game is
exponential. This question had been open for some time.
The algorithm is a pivoting method similar to the simplex
algorithm for linear programming. We present a class of
square bimatrix games for which the shortest Lemke-Howson
path grows exponentially in the dimension d of the game.
We construct the games using pairs of dual cyclic polytopes
with 2d facets in d-space. An extension of this work gives
games where in addition to long Lemke-Howson paths, a
trivial "support guessing" algorithm also takes exponential
time on average.

(Joint work with Rahul Savani.)

**Talks given:**

- 22 May 2013, Seminar, Computational Optimization Group, Imperial College, London.
- 22 June 2012, with title "Constructing and computing equilibria for two-player games", Computational Mathematics/Tutte Colloquium, University of Waterloo, Canada
- 15 September 2009, with title "Constructing and computing equilibria for two-player games", ERI-CES Seminar, University of Valencia, Spain
- 1 July 2009, with title "Constructing and computing equilibria for two-player games", Invited Plenary Talk, SING 5, Spanish-Italian-Netherlands meeting on Game Theory, Amsterdam, The Netherlands
- 22 May 2007, Microeconomics Seminar, IGIER, Bocconi University, Milan, Italy.
- 27 February 2007, Seminar, Computer Science Department, University of Liverpool.
- 24 November 2006, Departmental Seminar, Department of Computer Science, University of Bath.
- 28 June 2006, Summer School on Game Theory in Computer Science, Aarhus University, Denmark.
- 15 June 2006, Colloquium, Faculty of Economics and Business Administration, University of Maastricht, The Netherlands.
- 13 June 2006, Invited guest speaker, 2006 Colloquium, Deutsche Forschungsgemeinschaft, Research Centre 1126 on ``Algorithms for large and complex networks'', Technical University of Aachen, Germany.
- [given by Rahul Savani] 12 May 2006, Computer Science Seminar, University of Leicester.
- [given by Rahul Savani] 6 April 2006, 22nd British Colloquium for Theoretical Computer Science (BCTCS), Swansea University.
- 9 February 2006, Centre for Computational Finance and Economic Agents Seminar, University of Essex.
- 30 January 2006, Departmental Research Seminar, Department of Computer Science, Durham University.
- [given by Rahul Savani] 13 December 2005, Mittagsseminar, Department of Computer Science, ETH Zurich, Switzerland.
- 30 September 2005, Computer Science Seminar, University of Warwick.
- 2 March 2005, Pure Mathematics Seminar, University College London.
- 28 February 2005, Game Theory Seminar, Ecole Polytechnique and Universities of Paris I - VI - Dauphine, France.
- 22 February 2005, Laboratory for Foundations of Computer Science Seminar, University of Edinburgh.
- [short version, given by Rahul Savani] 18 October 2004, 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy. Paper.
- 10 November 2003, Seminar, Department of Mathematical Sciences, Brunel University.
- [given by Rahul Savani] 13 September 2003, Workshop on Complexity in Economic Theory, Cowles Foundation for Research in Economics, Yale University, New Haven, Connecticut, USA.
- 11 September 2003, Colloquium in Computer Science, Brown University, Providence, Rhode Island, USA.
- 15 July 2003, Dagstuhl Seminar 03291, Algorithmic Game Theory and the Internet, Schloss Dagstuhl, Germany.

**Abstract:**
A "Leadership Game" is obtained from a game in strategic
form by letting on player become the "leader", who can
**commit** to a strategy, against which the other player or
players (called "followers") react. The classic
example is the Stackelberg game, which is the leadership
game obtained from the Cournot duopoly game of quantity
competition, the oldest formally defined "game".

First, we present a simple result on "follower payoffs in
symmetric duopoly games", where we give a general and very
short proof of the following property of a leadership game
for a symmetric duopoly game, for example of price or
quantity competition. Under certain standard assumptions,
The follower's payoff is either **higher** than the leader's, or
**lower** than even in the simultaneous game. A possible
interpretation is that ``endogenous'' timing is difficult
since the players either want to move both second or both
first. Apart from the surprising result, the setup
introduces key concepts of game theory and its modelling
assumptions using only simple mathematics, and a very
basic economic model.

Secondly, we study leadership games for the mixed extension of a finite game, where the leader commits to a mixed, that is, randomized strategy. In a generic two-player game, the leader payoff is unique and at least as large as any Nash payoff in the original simultaneous game. In non-generic two-player games, which are completely analyzed, the leader payoffs may form an interval, which as a set of payoffs is never worse than the Nash payoffs for the player who has the commitment power. In other words, the power to commit never hurts, even when best responses are not unique.

**Talks given:**

- 11 November 2005, Economics Seminar, University of Alicante, Spain.
- 18 January 2005, Pure Mathematics Seminar, Royal Holloway, University of London.
- 20 May 2004, STICERD Interdisciplinary Seminar in Game Theory, London School of Economics.
- 25 March 2004, Seminar, Department of Value and Decision Science, Tokyo Institute of Technology, Tokyo, Japan.
- 22 November 2003, Game Theory Workshop, Waseda University, Tokyo, Japan.
- 13 February 2003, Seminar in Economics and Econometrics, University of Cergy-Pontoise, France.

**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.

(Joint work with P. Hernández)

**Talks given:**

- 18 October 2012, University of California at San Diego, California
- 23 May 2012, Workshop in Economic Theory, Queen Mary University of London
- 21 February 2012, Computer Science Seminar, University of Liverpool
- 13 September 2011, Conference on Mathematical Aspects of Game Theory and Applications, Toulouse, France
- 21 June 2011, Tel Aviv International Workshop on Game Theory, Israel
- 19 June 2011, Seminar, The Weizmann Institute, Israel
- 10 March 2011, Seminar on Discrete Mathematics and Game Theory, LSE

**Abstract:**
Existence of an equilibrium in various economic models can
be shown to exist by following a certain combinatorially
defined path, for example of edges of a labeled polytope
similar to the simplex algorithm for linear programming.
In addition, such a path has a direction that defines the
"index" of an equilibrium. Examples include Sperner's
lemma about completely labeled simplices and Nash equilibria
in games. We present a general model of "pivoting systems"
that shows the essence of the path-following and the
directedness argument. We also present a connection of
bimatrix games where the paths are exponentially long with
signed perfect matchings in Euler graphs, and an algorithm
that gives a polynomial-time "shortcut" for these paths.
We also present a concept of orientation for the "Euler
complexes" or oiks introduced by Edmonds, which generalizes
the orientability of abstract simplicial manifolds.

Our exposition uses colorful pictures and examples
wherever possible.

(Joint work with L. Vegh)

**Talks given:**

- 6 December 2012, Seminar, University of Paris, Dauphine
- 29 November 2012, Kolloquium, University of Maastricht, The Netherlands
- 19 November 2012, Seminar, University of Cambridge
- 17 July 2009, Invited Plenary Talk, International Conference on Game Theory, Stony Brook, NY, USA
- 30 June 2009, BRICKS Workshop on Game Theory and Multiagent Systems, CWI, Amsterdam, The Netherlands
- 7 April 2009, Conference in Honour of Jack Edmonds on Pretty Structures, Existential Polytime and Polyhedral Combinatorics, Paris, France

**Abstract:**
The central solution concept for strategic games is the Nash
equilibrium. Every equilibrium has an index, which is an
integer describing a geometric-topological concept related
to the sign of a determinant, essentially a positive or
negative orientation. The sum of all indices over all
equilibria is +1. The index is related to concepts of
"stability", e.g. with respect to perturbing the game data
(equilibrium components with index 0 can disappear), or with
respect to evolutionary dynamics, for example. The index is
typically described very technically.

We give a new construction that allows to visualize the
index in a low-dimensional picture, for example the plane
for a 3 x n game, for any n. We prove that the index can be
characterized in strategic terms: an equilibrium has index
+1 if and only if it can be made the unique equilibrium of
the game by adding suitable strategies.

(Joint work with Arndt von Schemde.)

**Talks given:**

- 15 April 2009, CRETA Marie Curie Workshop, University of Warwick
- 1 April 2009, Workshop New Topics on Game Theory, Seville, Spain
- 24 March 2009, Bellairs Workshop on Algorithmic Game Theory, Barbados
- 8 September 2008, Transatlantic Theory Workshop, Paris School of Economics, France.
- 15 July 2008, Third World Congress of the Game Theory Society, Kellogg School of Management, Northwestern University, Evanston, USA.
- 10 June 2008, Conference on Dynamics and Optimization, University of Paris 6, France.
- 30 April 2008, Symposium on Algorithmic Game Theory (SAGT), Paderborn, Germany.
- 22 April 2008, DIMAP Seminar, University of Warwick, United Kingdom.
- 11 March 2008, Seminar, Department of Computer Science, University of Aarhus, Denmark.
- 15 December 2005, Mittagsseminar, Department of Computer Science, ETH Zurich, Switzerland; old slides.
- 15 July 2005, Invited plenary talk, 16th International Conference on Game Theory, Stony Brook, New York, USA.
- 23 May 2005, Game Theory Seminar, Ecole Polytechnique and Universities of Paris I - VI - Dauphine, France.
- 21 April 2005, Mini-Symposium on Games and Dynamics, London School of Economics.

Back to Bernhard von Stengel's homepage