TCS Journal 2025 Journal Article
- Vittorio Bilò
- Marios Mavronicolas
- Paul G. Spirakis
We consider a contest game with discrete strategies, modelling a contest where reviews for a proposal are crowdsourced from n players. Player i has a skill s i, strategically chooses a quality q ∈ { 1, 2, …, Q } for her review and pays an effort f q ≥ 0, strictly increasing with q. Under voluntary participation, a player may opt to not write a review, paying zero effort; mandatory participation excludes this option. For her effort, she is awarded a payment per her payment function, which is either player-invariant, like, e. g. , the popular proportional allocation, or player-specific; it is oblivious when it does not depend on the loads on other qualities. The utility to player i is the difference between her payment and her cost, calculated by a skill-effort function Λ ( s i, f q ). Skills may vary for arbitrary players; when players are anonymous, s i = 1 for each player i. In a pure Nash equilibrium, no player could increase her utility by unilaterally switching to another quality. We show the following results about the (in)existence and the computation of a pure Nash equilibrium: • A contest game with arbitrary players and player-invariant and oblivious payments is an unweighted congestion game with player-specific constants on parallel links [42]; so it has a generalized ordinal potential, the Finite Improvement Property (FIP) and a pure Nash equilibrium, which can be computed in PLS. However, under the assumption that the payment function is monotonically nonincreasing, a pure Nash equilibrium can be computed efficiently by resorting to [44, Theorem 2]. In contrast, a pure Nash equilibrium might not exist for (i) anonymous players and player-invariant but not oblivious payments, (ii) arbitrary players and proportionally allocated payments, and (iii) anonymous players and player-specific and oblivious payments; in the latter case, it is NP -hard to decide existence even if players are anonymous. These counterexamples prove the tightness of our existence result and suggest that the decision and search problems for a pure Nash equilibrium are computationally hard. • Under some mild assumptions on the efforts, the contest game with anonymous players and proportional allocation has at least one Nash equilibrium. For arbitrary players, we identify a simple condition involving both skills and efforts that suffices for the existence of a pure Nash equilibrium in the special case where the skill-effort function has the product form Λ ( s i, f q ) = s i f q. In both cases the pure Nash equilibrium is simple and computable in constant time. • Under the assumption that costs are player-consistent, there is a polynomial-time Θ ( n Q ) algorithm to decide the existence and compute a pure Nash equilibrium for constant Q, for the case of arbitrary players and player-invariant payments; so the computational problem is XP -tractable with respect to the parameter Q. Player-consistent costs means that all players are incurred the same relative costs for a given pair of qualities. The computed equilibrium is contiguous by design: players with higher skills are contiguously assigned to lower qualities. Our results indicate that the decision and search problems for pure Nash equilibria are likely to be computationally hard even in the simplest case, but can be made easy even in the hardest case by adopting simple assumptions on efforts, payments or costs, no matter whether participation is mandatory or voluntary.