Through the lens of Tullock contests, we take a fresh look at the contest game for crowdsourcing reviews [12] as a Tullock contest game with discrete strategies: Each of n players, 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 almosttightness 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 [41]. In contrast, there is some constant ε > 0 such that computing an additive ε-approximate pure Nash equilibrium for it is in PPAD.– Wepropose 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
Mixed Nash Equilibria in Discrete Tullock Contests
Bilo, Vittorio;
2025-01-01
Abstract
Through the lens of Tullock contests, we take a fresh look at the contest game for crowdsourcing reviews [12] as a Tullock contest game with discrete strategies: Each of n players, 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 almosttightness 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 [41]. In contrast, there is some constant ε > 0 such that computing an additive ε-approximate pure Nash equilibrium for it is in PPAD.– Wepropose 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| File | Dimensione | Formato | |
|---|---|---|---|
|
SAGT2025.pdf
non disponibili
Tipologia:
Versione editoriale
Licenza:
Copyright dell'editore
Dimensione
565.1 kB
Formato
Adobe PDF
|
565.1 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.


