Bernhard von Stengel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Bernhard von Stengel has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- Rahul Savani
University of Liverpool
4 shared publications - Penélope Hernández
University of Valencia ERI-CES
2 shared publications Bernd Gaertner
1 shared publication- Christoph Ambuehl
Dalle Molle Institute for Artificial Intelligence (IDSIA) 6928 Manno Switzerland
1 shared publication - David Avis
Kyoto University
1 shared publication - Gabriel D. Rosenberg
Yale Law School, New Haven, USA
1 shared publication
Latest Publications
- 3 February 2017
- Published by Taylor & Francis in The Mathematical Gazette
- Vol. 101 (550) , 172
Jane Austen, game theorist
- 3 February 2017
- Published by Taylor & Francis in The Mathematical Gazette
- Vol. 101 (550) , 172
Jane Austen, game theorist
- 27 January 2016
- Published by Wiley in International Journal of Economic Theory
- Vol. 12 (1) , 7-27
Unit vector games
McLennan and Tourky showed that “imitation games” provide a new view of the computation of Nash equilibria of bimatrix games with the Lemke–Howson algorithm. In an imitation game, the payoff matrix of one of the players is the identity matrix. We study the more general “unit vector games,” which are already known, where the payoff matrix of one player is composed of unit vectors. Our main application is a simplification of the construction by Savani and von Stengel of bimatrix games where two basic equilibrium‐finding algorithms take exponentially many steps: the Lemke–Howson algorithm, and support enumeration.
- 27 January 2016
- Published by Wiley in International Journal of Economic Theory
- Vol. 12 (1) , 7-27
Unit vector games
McLennan and Tourky showed that “imitation games” provide a new view of the computation of Nash equilibria of bimatrix games with the Lemke–Howson algorithm. In an imitation game, the payoff matrix of one of the players is the identity matrix. We study the more general “unit vector games,” which are already known, where the payoff matrix of one player is composed of unit vectors. Our main application is a simplification of the construction by Savani and von Stengel of bimatrix games where two basic equilibrium‐finding algorithms take exponentially many steps: the Lemke–Howson algorithm, and support enumeration.
- 1 December 2014
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 62 (6) , 1221-1235
Nash Codes for Noisy Channels
This paper studies the stability of communication protocols that deal with transmission errors. We consider a coordination game between an informed sender and an uninformed receiver, who communicate over a noisy channel. The sender’s strategy, called a code, maps states of nature to signals. The receiver’s best response is to decode the received channel output as the state with highest expected receiver payoff. Given this decoding, an equilibrium or “Nash code” results if the sender encodes every state as prescribed. We show two theorems that give sufficient conditions for Nash codes. First, a receiver-optimal code 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 transmission: under a minimal “monotonicity” requirement for breaking ties when decoding, which holds generically, every code is a Nash code.
- 1 December 2014
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 62 (6) , 1221-1235
Nash Codes for Noisy Channels
This paper studies the stability of communication protocols that deal with transmission errors. We consider a coordination game between an informed sender and an uninformed receiver, who communicate over a noisy channel. The sender’s strategy, called a code, maps states of nature to signals. The receiver’s best response is to decode the received channel output as the state with highest expected receiver payoff. Given this decoding, an equilibrium or “Nash code” results if the sender encodes every state as prescribed. We show two theorems that give sufficient conditions for Nash codes. First, a receiver-optimal code 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 transmission: under a minimal “monotonicity” requirement for breaking ties when decoding, which holds generically, every code is a Nash code.
- 10 April 2014
- Published by Springer Nature in Computational Management Science
- Vol. 12 (1) , 5-33
Game Theory Explorer: software for the applied game theorist
- 10 April 2014
- Published by Springer Nature in Computational Management Science
- Vol. 12 (1) , 5-33
Game Theory Explorer: software for the applied game theorist
- 2 April 2014
- Published by Springer Nature in Mathematical Programming
- Vol. 150 (1) , 153-178
Oriented Euler complexes and signed perfect matchings
- 2 April 2014
- Published by Springer Nature in Mathematical Programming
- Vol. 150 (1) , 153-178
Oriented Euler complexes and signed perfect matchings
- Open Access
Game Theory Explorer - Software for the Applied Game Theorist
This paper presents the "Game Theory Explorer" software tool to create and analyze games as models of strategic interaction. A game in extensive or strategic form is created and nicely displayed with a graphical user interface in a web browser. State-of-the-art algorithms then compute all Nash equilibria of the game after a mouseclick. In tutorial fashion, we present how the program is used, and the ideas behind its main algorithms. We report on experiences with the architecture of the software and its development as an open-source project.
Open AccessGame Theory Explorer - Software for the Applied Game Theorist
This paper presents the "Game Theory Explorer" software tool to create and analyze games as models of strategic interaction. A game in extensive or strategic form is created and nicely displayed with a graphical user interface in a web browser. State-of-the-art algorithms then compute all Nash equilibria of the game after a mouseclick. In tutorial fashion, we present how the program is used, and the ideas behind its main algorithms. We report on experiences with the architecture of the software and its development as an open-source project.
- Open Access
Nash Codes for Noisy Channels
This paper studies the stability of communication protocols that deal with transmission errors. We consider a coordination game between an informed sender and an uninformed decision maker, the receiver, who communicate over a noisy channel. The sender's strategy, called a code, maps states of nature to signals. The receiver's best response is to decode the received channel output as the state with highest expected receiver payoff. Given this decoding, an equilibrium or "Nash code" results if the sender encodes every state as prescribed. We show two theorems that give sufficient conditions for Nash codes. First, a receiver-optimal code 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 transmission: Under a minimal "monotonicity" requirement for breaking ties when decoding, which holds generically, EVERY code is a Nash code.
Open AccessNash Codes for Noisy Channels
This paper studies the stability of communication protocols that deal with transmission errors. We consider a coordination game between an informed sender and an uninformed decision maker, the receiver, who communicate over a noisy channel. The sender's strategy, called a code, maps states of nature to signals. The receiver's best response is to decode the received channel output as the state with highest expected receiver payoff. Given this decoding, an equilibrium or "Nash code" results if the sender encodes every state as prescribed. We show two theorems that give sufficient conditions for Nash codes. First, a receiver-optimal code 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 transmission: Under a minimal "monotonicity" requirement for breaking ties when decoding, which holds generically, EVERY code is a Nash code.
- Open Access
Rank-1 Games With Exponentially Many Nash Equilibria
The rank of a bimatrix game (A,B) is the rank of the matrix A+B. We give a construction of rank-1 games with exponentially many equilibria, which answers an open problem by Kannan and Theobald (2010).
Open AccessRank-1 Games With Exponentially Many Nash Equilibria
The rank of a bimatrix game (A,B) is the rank of the matrix A+B. We give a construction of rank-1 games with exponentially many equilibria, which answers an open problem by Kannan and Theobald (2010).
- Open Access
Optimal Lower Bounds for Projective List Update Algorithms
The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized combination of BIT and the TIMESTAMP algorithm TS. This and almost all other list update algorithms, like MTF, are projective in the sense that they can be defined by looking only at any pair of list items at a time. Projectivity (also known as "list factoring") simplifies both the description of the algorithm and its analysis, and so far seems to be the only way to define a good online algorithm for lists of arbitrary length. In this paper we characterize all projective list update algorithms and show that their competitive ratio is never smaller than 1.6 in the partial cost model. Therefore, COMB is a best possible projective algorithm in this model.
Open AccessOptimal Lower Bounds for Projective List Update Algorithms
The list update problem is a classical online problem, with an optimal competitive ratio that is still open, known to be somewhere between 1.5 and 1.6. An algorithm with competitive ratio 1.6, the smallest known to date, is COMB, a randomized combination of BIT and the TIMESTAMP algorithm TS. This and almost all other list update algorithms, like MTF, are projective in the sense that they can be defined by looking only at any pair of list items at a time. Projectivity (also known as "list factoring") simplifies both the description of the algorithm and its analysis, and so far seems to be the only way to define a good online algorithm for lists of arbitrary length. In this paper we characterize all projective list update algorithms and show that their competitive ratio is never smaller than 1.6 in the partial cost model. Therefore, COMB is a best possible projective algorithm in this model.
- 24 March 2009
- Published by Springer Nature in Economic Theory
- Vol. 42 (1) , 1-7
Computation of Nash equilibria in finite games: introduction to the symposium
- 24 March 2009
- Published by Springer Nature in Economic Theory
- Vol. 42 (1) , 1-7
Computation of Nash equilibria in finite games: introduction to the symposium