The Contest Game for Crowdsourcing Reviews

Mavronicolas, Marios ORCID: 0009-0009-0115-3045 and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2023) The Contest Game for Crowdsourcing Reviews. In: The 16th International Symposium on Algorithmic Game Theory (SAGT), 2023-9-4 - 2023-9-7, Royal Holloway University London UK.

Text SAGT23.pdf - Author Accepted Manuscript Download (590kB) | Preview

Abstract

We consider a contest game modelling a contest where reviews for a proposal are crowdsourced from n players. Player i has a skill si, strategically chooses a quality q∈ { 1, 2, …, Q} for her review and pays an effort fq≥ 0, strictly increasing with q. Under voluntary participation, a player may opt to not write a review, paying zero effort; mandatory participation does not provide 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 numbers of players choosing a different quality. The utility to player i is the difference between her payment and her cost, calculated by a skill-effort function Λ (si, fq). Skills may vary for arbitrary players; anonymous players means si= 1 for all players i. In a pure Nash equilibrium, no player could unilaterally increase her utility by switching to a different quality. We show the following results about the existence and the computation of a pure Nash equilibrium: We present an exact potential to show the existence of a pure Nash equilibrium for the contest game with arbitrary players and player-invariant and oblivious payments. A particular case of this result provides an answer to an open question from [6]. In contrast, a pure Nash equilibrium might not exist (i) for player-invariant payments, even if players are anonymous, (ii) for proportional allocation payments and arbitrary players, and (iii) for player-specific payments, even if players are anonymous; in the last case, it is NP -hard to tell. These counterexamples prove the tightness of our existence result.We show that the contest game with proportional allocation, voluntary participation and anonymous players has the Finite Improvement Property, or FIP; this yields two pure Nash equilibria. The FIP carries over to mandatory participation, except that there is now a single pure Nash equilibrium. For arbitrary players, we determine a simple sufficient condition for the FIP in the special case where the skill-effort function has the product form Λ(si,fq)=sifq.We introduce a novel, discrete concavity property of player-specific payments, namely three-discrete-concavity, which we exploit to devise, for constant Q, a polynomial-time Θ(nQ) algorithm to compute a pure Nash equilibrium in the contest game with arbitrary players; it is a special case of a Θ(nQ2(n+Q-1Q-1)) algorithm for arbitrary Q that we present. Thus, the problem is XP -tractable with respect to the parameter Q. The computed equilibrium is contiguous: players with higher skills are contiguously assigned to lower qualities. Both three-discrete-concavity and the algorithm extend naturally to player-invariant payments.

Item Type:	Conference or Workshop Item (Unspecified)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	03 Jul 2023 07:57
Last Modified:	30 Oct 2023 03:25
DOI:	10.1007/978-3-031-43254-5_5
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3171398