Tractable (Simple) Contests

Priel Levy, David Sarne, Yonatan AumannIJCAI 2018 · DOI

TL;DR

This paper introduces a sequential decision-making mechanism for "simple contests" (where participants only decide whether to enter, not their effort level) that overcomes the common problem of multiple equilibria. By ordering participants, the organizer can guarantee a specific, desired equilibrium and potentially achieve higher profits, with an efficient method for finding the optimal prize.

What Problem Does This Paper Address?

In many real-world scenarios, like online competitions or even Olympic sports, organizers want to incentivize participation and elicit the best possible outcomes. These scenarios can often be modeled as "contests" where individuals compete for a prize. A key challenge in designing these contests is predicting how participants will behave, which is crucial for optimizing contest parameters like the prize amount. However, many contest models suffer from having multiple possible "Nash equilibria" – stable states where no participant has an incentive to unilaterally change their strategy. This multiplicity of equilibria makes it impossible for organizers to predict the outcome or design the contest effectively, as they don't know which equilibrium will be played. This paper focuses on "simple contests" where participants only decide whether to enter, and their performance is otherwise fixed. The core problem addressed is how to move from a situation with many potential outcomes to one with a predictable, optimal outcome.

Methods

The paper proposes a modification to the standard "parallel" contest model, where all participants decide simultaneously. The new approach is a "sequential" mechanism where participants make their decisions one after another, in an order determined by the organizer. This sequential structure allows the use of "sub-game perfect Bayesian Nash equilibrium" (SPNE), a stronger solution concept that, in this context, leads to a unique equilibrium. The authors prove that all pure-strategy Nash equilibria of the original parallel contest can be replicated as SPNEs in the sequential version. More importantly, they show that by carefully ordering participants, an organizer can force a specific, desired equilibrium to emerge. They also develop an efficient algorithm to compute the "critical values" of the prize, which are the specific prize amounts where the equilibrium behavior changes. This allows for the tractable computation of the optimal prize that maximizes the organizer's expected profit, even though the prize can theoretically take any continuous value.

Datasets

The paper describes experiments conducted with human participants recruited via Amazon Mechanical Turk. No specific pre-existing datasets were used for training or evaluation; rather, the experiments generated new data to compare the proposed sequential mechanism (SQ) with the traditional parallel mechanism (PAR).

Key Insights and Ideas

  • Sequentiality as a disambiguation tool: Shifting from simultaneous to sequential decisions fundamentally changes the game's structure, enabling the selection of a unique equilibrium where multiple existed before.
  • Organizer's control: The organizer gains significant control by dictating the order of participants, allowing them to steer the contest towards a preferred outcome.
  • Tractable prize optimization: The problem of finding the optimal prize, which is notoriously difficult in continuous settings with multiple equilibria, becomes tractable due to the identification of discrete "critical values" where equilibrium behavior shifts.
  • Empirical validation of over-participation: Human participants, even in the sequential setting, tend to over-participate compared to theoretical predictions, a phenomenon observed in prior work on parallel contests.

Key Results

  • The sequential mechanism (SQ) successfully replicates all pure-strategy Nash equilibria of the parallel mechanism (PAR).
  • By ordering participants, the organizer can force a specific equilibrium to be played, potentially leading to a higher expected profit than any equilibrium in the parallel setting.
  • An efficient algorithm is provided to compute the finite set of critical prize values, making optimal prize determination tractable.
  • Experimental results with human participants showed that the sequential mechanism led to increased participation and, in some cases, higher organizer profits compared to the parallel mechanism. Specifically, over-participation was observed in both SQ and PAR, but the SQ mechanism offered a greater benefit to the principal in terms of increased participation and average profit.

Limitations and Future Work

The authors acknowledge that their work focuses on "simple contests" where performance is exogenously determined. A significant future research direction is to extend these ideas to "general contests" where participants can strategically choose their effort levels. Additionally, while the paper demonstrates the tractability of finding optimal prizes, the complexity of the algorithm for computing critical values is exponential in the number of players, which could be a limitation for very large contests.

Summary updated

BibTeX
@inproceedings{levy2018tractable,
  author = {Priel Levy and David Sarne and Yonatan Aumann},
  title = {{Tractable (Simple) Contests}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/50},
}

Loading related content...

Figure