Communications of the ACM

tional allocation. 14 For the game that models the contest with proportional allocation, the total effort in the pure-strategy Nash equilibrium cannot be increased by excluding some of the players from competition.

Simultaneous contests. In the context of online services, a contest is often run simultaneously with other contests. For example, in competition-based crowdsourcing services, there are typically many open contests at any given time. Similarly, in online labor marketplaces, there are usually many open jobs at any given time. Multiple open contests provide players with alternative options to invest efforts, which can have a significant effect on the effort invested in any given contest. A player can invest effort only in a limited number of contests over a period of time, or he or she has a limited effort budget to invest over available contests. A worker may only be able to produce a high-quality work by focusing to a small number of projects at any given time, or he or she may only be able to devote a limited number of work hours per week. Game theory provides us with a framework to study the relation between the values of prizes offered by different contests and the effort investments across different contests in a strategic equilibrium.

We consider games that model si-
multaneous standard all-pay contests
that offer prizes of arbitrary values.
Such games have been studied for dif-
ferent types of production costs. We
first consider the case where produc-
tion costs are such it is feasible for
each player to participate in at most
one contest, in which he or she incurs
a unit marginal production cost. In
such a game, strategic decision mak-
ing of a player consists of two compo-
nents: choosing in which contest to
invest effort, and deciding how much
effort to invest in the chosen contest.
This strategic decision making is in-
formed by the available information,
which consists of the values of prizes
offered by different contests and the
prior information about the skills of
players. We consider the game with
incomplete information, where the
skill parameters of players are inde-
pendent and identically distributed
according to a prior distribution.
This game has a symmetric Bayes-
the prize allocated to a highest-effort
player. For more details about smooth
allocations, see, for example, Corchon
and Dahm10 and Vojnović. 42

One may ask how do equilibrium outcomes in the game that models the standard all-pay contest compare with those in the game with a smooth prize allocation, say, according to proportional allocation. A first notable difference is that unlike the game that models the standard all-pay contest, the game with proportional allocation has a pure-strategy Nash equilibrium, which is unique.

The total effort in any pure-strategy Nash equilibrium is guaranteed to be at least v2/2. The total effort increases in the highest-skill parameter v1 and it can be larger than v2. This is in contrast to the game that models the standard all-pay contest, where the total effort in any mixed-strategy Nash equilibrium is at most v2. One may ask whether there exists a smooth allocation of prizes that guarantees the total effort to be within a constant factor of v1 in any pure-strategy Nash equilibrium. The answer is negative. 41 This gives us a useful insight that randomized prize allocations can achieve a larger total effort, but there are fundamental limits that cannot be surpassed.

The maximum individual effort can be an arbitrarily small fraction of the total effort; for example, this is so for the simple game instance with equally skilled players by taking the number of players to be sufficiently large. This is in contrast to the game that models the standard all-pay contest where we noted that in any mixed-strategy Nash equilibrium, the expected maximum individual effort is at least 1/2 of the expected total effort.

The social welfare in any pure-strategy Nash equilibrium of the game with proportional allocation is always at least 3/4 of the optimum value, a result by Johari and Tsitsiklis. 21 It has been shown the game with proportional allocation is a smooth game (for example, see Roughgarden34), which implies that the expected social welfare is at least 1/2 of the optimum value in any mixed-strategy Nash equilibrium.