Papers for

game theory software developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Complexity of predicting winners in plurality voting with abstentions

Subgame-Perfect Nash Equilibria of Plurality Voting with Abstention: a PSPACE-Completeness Result for Restricted Ballots

Abstract: We consider sequential Plurality elections in which each voter may abstain or vote for a single candidate. Each voter assigns utilities to all candidates; for each voter, this induces a (weak) order over the candidates. Ties are resolved uniformly at random, and voting has a small positive cost, so that a voter prefers to abstain when their vote cannot change the election outcome. We consider a variant of this model where, for each voter, we additionally specify a prefix of her ranking, so that she is only allowed to vote for a candidate from that prefix (or abstain). We prove that for this variant of the model, deciding whether a designated candidate is among the election winners in a subgame-perfect equilibrium of the associated extensive-form game is PSPACE-complete. This partially resolves an open problem from the work of Desmedt and Elkind [2010].

Mon 21 SeptComputer Science and Game Theory
The gist
This paper looks at a type of voting where people vote one after another and may choose not to vote at all. Each voter has a list of favorite candidates and can only vote for some of the top ones in their list or abstain. The authors study how hard it is to figure out whether a certain candidate can win if everyone votes strategically, thinking about how others will vote. They find that this problem is very complex and belongs to a class called PSPACE-complete, meaning it is generally tough to solve with a computer. This answers a question left open by earlier work on voting strategy.
Open → 2609.24292v1

Finding specific Nash equilibria in games is computationally hard

Finding a Positive Index Nash Equilibrium is PPADS-Complete

Abstract: Every nondegenerate bimatrix game has a Nash equilibrium of Shapley index +1, since all equilibria are isolated, have index +1 or -1, and their indices sum to +1. We prove that the following promise search problem is PPADS-complete: given a rational bimatrix game promised to be nondegenerate, find an exact Nash equilibrium of index +1. To our knowledge, this is the first PPADS-complete equilibrium search problem whose instances are explicit rational normal form payoff matrices, rather than succinct circuits or Turing machines, and thereby addresses an open question posed by Daskalakis [Daskalakis, 2019].

Sun 20 SeptComputational ComplexityComputer Science and Game Theory
The gist
The paper shows that finding a special type of stable outcome called a Nash equilibrium with a positive index in certain two-player games is computationally difficult. Every such game has equilibria whose indices sum to one, but identifying exactly one with index +1 is proven to be hard. The authors’ result settles a previously open question by proving this problem is complete for a complexity class known as PPADS. This means that solving these games in this precise way is as hard as the hardest problems in that class.
Open → 2609.23879v1