Presentations (talk slides) of Bernhard von Stengel

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

Computationally efficient coordination in game trees (joint with Francoise Forges)

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.

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.

Equilibrium Computation for Two-Player Games in Strategic Form

Efficient Computation of Equilibria for Extensive Games

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.

Finding all Nash equilibria of a bimatrix game (joint with David Avis, Gabriel Rosenberg, and Rahul Savani)

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.

Talks given:

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

Games, Geometry, and the Computational Complexity of Finding Equilibria

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.

Geometric Views of Linear Complementarity Algorithms and Their Complexity (joint with Rahul Savani)

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.

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.

Hard-to-Solve Bimatrix Games (joint with Rahul Savani)

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.

Talks given:

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

Leadership Games (part 2 joint with Shmuel Zamir)

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.

Nash Codes for Noisy Channels

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

Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

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

Strategic Characterization of the Index of an Equilibrium (joint with Arndt von Schemde)

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.

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