421 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- University College LondonGB63 papers
- Systemic Risk CentreGB48 papers
- University of OxfordGB20 papers
- University of WarwickGB18 papers
- King's College LondonGB16 papers
- London Mathematical LaboratoryGB12 papers
- University of Illinois Urbana-ChampaignUS12 papers
- Centre National de la Recherche ScientifiqueFR11 papers
- Queen Mary University of LondonGB11 papers
- The Open UniversityGB11 papers
- City, University of LondonGB10 papers
- ETH ZurichCH10 papers
23 papers · 1 filter
A Stable-Set Bound and Maximal Numbers of Nash Equilibria in Bimatrix Games
Constantin Ickstadt, Thorsten Theobald, Bernhard von Stengel
Quint and Shubik (1997) conjectured that a non-degenerate n-by-n game has at most 2^n-1 Nash equilibria in mixed strategies. The conjecture is true for n at most 4 but false for n=…
Zero-Sum Games and Linear Programming Duality
Bernhard von Stengel
The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig (1951) is k…
Long term behavior of dynamic equilibria in fluid queuing networks
Roberto Cominetti, José Correa, Neil Olver
A fluid queuing network constitutes one of the simplest models in which to study flow dynamics over a network. In this model we have a single source-sink pair and each link has a p…
A Short Proof of Convexity of Step-out Step-in Sequencing Games
Coulter Beeson, Neil Olver
The Step out-Step in sequencing game is a particular example of a game from the sequencing game framework of Curiel, Perderzoli, and Tijs, where coalitions of players in a queue ma…
Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time
Neil Olver, Leon Sering, Laura Vargas Koch
We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from an origin to a d…
A Case Study of Agent-Based Models for Evolutionary Game Theory
Jacobus Smit, Ed Plumb
Evolutionary game theory is a mathematical toolkit to analyse the interactions that an individual agent has in a population and how the composition of strategies in this population…
Finding Nash Equilibria of Two-Player Games
Bernhard von Stengel
This paper is an exposition of algorithms for finding one or all equilibria of a bimatrix game (a two-player game in strategic form) in the style of a chapter in a graduate textboo…
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
Jugal Garg, Edin Husić, László A. Végh
We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction alg…
Fast Algorithms for Rank-1 Bimatrix Games
Bharat Adsul, Jugal Garg, Ruta Mehta +2
The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one, and shows the following: (1) For a game…
A Short Solution to the Many-Player Silent Duel with Arbitrary Consolation Prize
Steve Alpern, J. V. Howard
The classical constant-sum 'silent duel' game had two antagonistic marksmen walking towards each other. A more friendly formulation has two equally skilled marksmen approaching tar…
Best-Response Dynamics in Combinatorial Auctions with Item Bidding
Paul Dütting, Thomas Kesselheim
In a combinatorial auction with item bidding, agents participate in multiple single-item second-price auctions at once. As some items might be substitutes, agents need to strategiz…
Unit Vector Games
Rahul Savani, Bernhard von Stengel
McLennan and Tourky (2010) 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…
Recursive Inspection Games
Bernhard von Stengel
We consider a sequential inspection game where an inspector uses a limited number of inspections over a larger number of time periods to detect a violation (an illegal act) of an i…
Game Theory Explorer - Software for the Applied Game Theorist
Rahul Savani, Bernhard von Stengel
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 ni…
How to Gamble Against All Odds
Gilad Bavly, Ron Peretz
A decision maker observes the evolving state of the world while constantly trying to predict the next state given the history of past states. The ability to benefit from such predi…
VCG Auction Mechanism Cost Expectations and Variances
Svante Janson, Gregory B. Sorkin
We consider Vickrey-Clarke-Groves (VCG) auctions for a very general combinatorial structure, in an average-case setting where item costs are independent, identically distributed un…
Empirical Distribution of Equilibrium Play and Its Testing Application
Yakov Babichenko, Siddharth Barman, Ron Peretz
We show that in any -player -action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study thre…
Small-Support Approximate Correlated Equilibria
Yakov Babichenko, Siddharth Barman, Ron Peretz
We prove the existence of approximate correlated equilibrium of support size polylogarithmic in the number of players and the number of actions per player. In particular, using the…
Approximate Nash Equilibria via Sampling
Yakov Babichenko, Ron Peretz
We prove that in a normal form n-player game with m actions for each player, there exists an approximate Nash equilibrium where each player randomizes uniformly among a set of O(lo…
Digital morphogenesis via Schelling segregation
George Barmpalias, Richard Elwes, Andy Lewis-Pye
Schelling's model of segregation looks to explain the way in which particles or agents of two types may come to arrange themselves spatially into configurations consisting of large…
Rank-1 Games With Exponentially Many Nash Equilibria
Bernhard von Stengel
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…
LP-based Covering Games with Low Price of Anarchy
Georgios Piliouras, Tomas Valla, Laszlo A. Vegh
We present a new class of vertex cover and set cover games. The price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimizati…
Nash Codes for Noisy Channels
Penelope Hernandez, Bernhard von Stengel
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 decisio…