Mixed Nash Equilibria in Discrete Tullock Contests

Bilò, Vittorio ORCID: 0000-0001-7848-4904, Mavronicolas, Marios ORCID: 0009-0009-0115-3045, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Windisch, Daniel ORCID: 0000-0001-8906-6679 (2026) Mixed Nash Equilibria in Discrete Tullock Contests. In: The International Symposium on Algorithmic Game Theory (SAGT) 2025, 2025-9-2 - 2025-9-5, Bath UK.

Text Sagt2025noColor.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (890kB) | Preview

Abstract

Through the lens of Tullock contests, we take a fresh look at the contest game for crowdsourcing reviews [11] as a Tullock contest game with discrete strategies: Each of nplayers, endowed with skills, strategically invests an effort for writing a review of some quality she chooses from a finite set [Q]; she is awarded a payment, out of a budget β, in proportion to her effort, and pays a player-specific cost, which is the product of effort and skill. So both the payment and the utility functions for a player are strictly concave in the player’s effort. Players are anonymous if skills are identical, and so is the game. We study the mixed Nash equilibria of the game, where no player could deviate to increase her expected utility; her support in a Nash equilibrium is the set of qualities she chooses with strictly positive probability. By strict concavity, mixed Nash equilibria have the Small&Consecutive-Supports property: their supports have size at most 2. We show:For the anonymous Tullock contest game, there is an algorithm to compute all symmetric Nash equilibria up to a fixed precision ϵ and determine how many of them are rational; the algorithm resorts to an optimal algorithm for root-finding in univariate polynomials and takes time ΘQ·poly(n)·log1/ϵ. The algorithm extends naturally to games with an arbitrary strictly concave utility function.For two natural definitions of Social Cost, the corresponding Mixed Price of Anarchy is upper-bounded by 1 and 2, respectively, plus an additive constant; a lower bound we provide establishes almost-tightness for the first upper bound.For two families of instances of anonymous Tullock contest games with mandatory participation and β=1, we provide (i) very simple, necessary and sufficient numerical conditions on the efforts for the existence of an (ir)rational Nash equilibrium and (ii) a single Nash equilibrium which is irrational, respectively. Hence, computing a Nash equilibrium for a Tullock contest game is outside PPAD [34]. In contrast, there is some constant ε>0 such that computing an additive ε-approximate pure Nash equilibrium for it is in PPAD.We propose a framework grounded on Algebraic Geometry as a plausible host for disentangling rational and irrational Nash equilibria in the Tullock contest game. Envisioning a reduction among contests as an isomorphism of Q-algebras, we present an isomorphism that maps rational (resp., irrational) fully mixed Nash equilibria to rational (resp., irrational) ones. As a by-product, we leverage the Algebraic Geometry framework to completely characterize the set of all Tullock contest games with n=2 and Q=2 as an algebraic variety. For the anonymous Tullock contest game, there is an algorithm to compute all symmetric Nash equilibria up to a fixed precision ϵ and determine how many of them are rational; the algorithm resorts to an optimal algorithm for root-finding in univariate polynomials and takes time ΘQ·poly(n)·log1/ϵ. The algorithm extends naturally to games with an arbitrary strictly concave utility function. For two natural definitions of Social Cost, the corresponding Mixed Price of Anarchy is upper-bounded by 1 and 2, respectively, plus an additive constant; a lower bound we provide establishes almost-tightness for the first upper bound. For two families of instances of anonymous Tullock contest games with mandatory participation and β=1, we provide (i) very simple, necessary and sufficient numerical conditions on the efforts for the existence of an (ir)rational Nash equilibrium and (ii) a single Nash equilibrium which is irrational, respectively. Hence, computing a Nash equilibrium for a Tullock contest game is outside PPAD [34]. In contrast, there is some constant ε>0 such that computing an additive ε-approximate pure Nash equilibrium for it is in PPAD. We propose a framework grounded on Algebraic Geometry as a plausible host for disentangling rational and irrational Nash equilibria in the Tullock contest game. Envisioning a reduction among contests as an isomorphism of Q-algebras, we present an isomorphism that maps rational (resp., irrational) fully mixed Nash equilibria to rational (resp., irrational) ones. As a by-product, we leverage the Algebraic Geometry framework to completely characterize the set of all Tullock contest games with n=2 and Q=2 as an algebraic variety.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences
Divisions:	Faculty of Science and Engineering Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	02 Jul 2025 08:13
Last Modified:	29 Sep 2025 09:33
DOI:	10.1007/978-3-032-03639-1_3
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3193505