# tractable_simple_contests__224d30b0.pdf

Tractable (Simple) Contests

Priel Levy, David Sarne and Yonatan Aumann Department of Computer Science, Bar Ilan University, Israel priel.levy@live.biu.ac.il, sarned@cs.biu.ac.il, aumann@cs.biu.ac.il

Much of the work on multi-agent contests is focused on determining the equilibrium behavior of contestants. This capability is essential for the principal for choosing the optimal parameters for the contest (e.g. prize amount). As it turns out, many contests exhibit not one, but many possible equilibria, hence precluding contest design optimization and contestants behavior prediction. In this paper we examine a variation of the classic contest that alleviates this problem by having contestants make the decisions sequentially rather than in parallel. We study this model in the setting of a simple contest, wherein contestants only choose whether or not to participate, while their performance level is exogenously set. We show that by switching to the revised mechanism the principal can not only force her most desired pure-strategies based equilibrium to emerge, but also, at times, end up with an equilibrium offering a greater expected proﬁt. Further, we show that in the modiﬁed contest the optimal prize can be effectively computed. The theoretical analysis is complemented by comprehensive experiments with people over Amazon Mechanical Turk. Here, we ﬁnd that the modiﬁed mechanism offers great beneﬁt for the principal, both in terms of an increased over-participation in the contest (compared to theoretical expectations) and increased average proﬁt.

1 Introduction Contests are important mechanisms for eliciting effort in multi-agent systems [Siegel, 2009; Fu and Lu, 2012]. As such, the analysis of contests, and equilibrium behavior therein, has been a major line of study [Moldovanu and Sela, 2006; Di Palantino and Vojnovic, 2009]. Naturally, the ultimate goal of such analysis is to enable the design of effective contests. Speciﬁcally, the equilibrium of a contest is taken to be the presumed (or expected) behavior of the players. With this presumption, determining the equilibrium of a contest allows the contest organizer to predict its outcome (or distribution on outcomes). This, in turn, aids the organizer in designing the contest, by choosing the contest with the best

expected outcome. In particular, a major design variable is the prize amount. Unfortunately, many contests exhibit not one, but many possible equilibria. In such cases, the core equilibrium analysis does not provide a way to determine which of the equilibria will be adopted by the players. So, the organizer cannot optimize the contest design, and in particular has no way to determine the optimal prize, since the effectiveness of a prize will depend on the exact equilibrium chosen by the players. In this paper we focus on simple contests [Ghosh and Kleinberg, 2016; Levy et al., 2017; Sarne and Lepioshkin, 2017]. In simple contests, players only strategize on whether or not to participate in the contest; a cost is associated with participation, but once a player decides to participate, its performance level is exogenously determined, based on some predeﬁned distribution - over which it has no control. For example, consider sport events such as the Boston Marathon. Their fame attracts world s top-runners who have to consider whether the cost of participation (e.g., ﬂight and accommodation) on the one hand, and potential opponents and awards offered on the other hand make participation worthy. Naturally, once deciding to participate they will do their best to win. Similar characteristics can be found in various Olympic sports, beauty pageants, photo contests and many more. The study of simple contests has established that these are commonly characterized by multi-equilibria [Levy et al., 2017]. This, as discussed above, poses a substantial obstacle to the design of such contests. In this paper we show that a modiﬁcation to the basic contest structure allows maintaining all the pure-strategies Nash equilibria of the basic mechanism, yet reliably single out one of these as the equilibrium that will be played. This is obtained by shifting from a parallel structure to a sequential one. The sequential nature of the revised mechanism dictates the use of a sub-game perfect Bayesian Nash equilibrium, which necessarily leads in our case to a single equilibrium, hence disambiguating the choice of the equilibrium to be used. By properly ordering the entrants, the organizer can not only force her most desired pure-strategies based equilibrium to emerge as the sub-game perfect equilibrium, but also, at times, end up with an equilibrium offering a greater expected proﬁt, that could not have held in the parallel case. Despite the continuous nature of the prize that can be awarded, we show that the optimal prize belongs to a ﬁnite set of discrete values. We provide an algo-

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

rithm to effectively compute these values, and thus determine the optimal prize. Finally, we report the results of applying the new mechanism with people, using a set of experiments carried out in Amazon Mechanical Turk (AMT). The analysis of the results reveals an over-participation phenomenon (compared to theoretical predictions) at least as great as in the parallel model. Furthermore, we show that for the settings tested, the actual performance achieved with the new mechanism is greater than with the original one.

2 The Model

The contest model used in this paper is standard and can be found in several other works [Ghosh and Hummel, 2012; Levy et al., 2017; Sarne and Lepioshkin, 2017]. It considers a contest organizer and a set A = {A1, ..., Ak} of k > 1 heterogeneous potential contestants (denoted players onwards). All players and the organizer are fully-rational and self-interested. Each player Ai A can either participate in the contest, incurring some cost ci > 0, or opt to avoid participating in the contest. The actual quality of contributions of player Ai (i.e., the performance in the contest if participating) is determined only at the time of participation, based on some probability distribution function fi(x) (where Fi(x) is the corresponding cumulative distribution function). The contest is simple in the sense that contestants do not know the actual quality of their contributions (i.e., their performance in the contest) ahead of time, hence only need to strategize on participation in the contest. In order to encourage participation in the contest the organizer offers a prize M to the player ranked ﬁrst (performancewise) in the contest. The model assumes performance and prizes are additive hence the goal of the organizer is to maximize the expected best performance obtained by players in the contest minus the prize awarded. In case none of the players choose to participate in the contest, the prize is not awarded and the performance as perceived by the organizer is zero. The goal of each player is to maximize its own expected proﬁt, deﬁned as the expected prize awarded to it minus the cost incurred if participating in the contest. Therefore in order to have at least one player participate we require M > min(ci|Ai A). It is assumed that fi(x), ci and M are all common knowledge in the sense that they are known to all players and to the organizer [Moldovanu and Sela, 2001; 2006; Luo et al., 2014; Levy et al., 2017]. While the above archetypal model has been used in prior work in its fully parallel form, i.e., all players make their decisions simultaneously, we propose the following modiﬁcation, which offers many advantages and yet does not change the essence of the resulting equilibrium. The change dictates that the contest organizer ﬁrst determines an ordering of the players, and then instead of having all players decide on participation simultaneously, each player makes its decision in its turn after realizing the decision made by all preceding players. Meaning that the player is still unaware of the performance obtained by others, however has information related to the participation decision of a subset of the others.

3 Analysis We begin with the equilibrium analysis for the case where the prize M is given. This will be used in the following section for determining the optimal (organizer s expected-proﬁt maximizing) prize.

3.1 Notation The parallel mechanism is denoted PAR, and the sequential mechanism is denoted SQ. In the sequential mechanism, the players may be ordered in different ways; SQ(π) denotes the sequential mechanism wherein π is the order of the players.

Strategies In PAR a pure strategy of a player is simply a binary decision - whether to participate or not; that is, Si {0, 1}, where 1 denotes participation and 0 nonparticipation. In SQ(π), the strategy of player Ai is a function, determining whether to participate or not given the participation pattern of the previous players. Formally, strategy Si for player Ai is a function Si : {0, 1}π 1(i) 1 {0, 1} (where π 1(i) is the location of i in the sequence π). As usual, a strategy proﬁle is a tuple of strategies S = (S1, . . . , Sk), with Si the strategy of player Ai.

Induced Participants For each strategy proﬁle S (of either PAR or SQ) there is a set of players A such that if all players play by S, then the players of A are exactly those players that end up participating in the contest. We call this the induced set of participants of S, and denote their set of indexes by P(S). Given S, P(S) can be readily computed.

3.2 Payoff Consider a strategy proﬁle S. Given that all players follow S, the expected payoff of player Ai given that the prize is M, denoted Bi(S, M), is zero if i P(S), and otherwise:

Aj =Ai,Aj P(S) Fj(y)

i.e., player Ai is awarded the prize M whenever its performance y is the maximum among all players that participate. So, for any strategy proﬁle, the payoff of each player can be effectively computed. Note that, given that all players indeed follow S, the expected payoff of any player, as well as the organizer, is fully determined by P(S). Hence, the following deﬁnition: Deﬁnition 1. Strategy proﬁles S and S are equivalent if P(S) = P(S ). In this deﬁnition, S and S may be of different mechanisms. The expected payoff of the organizer can also be effectively computed as

Borg(S, M) = Z

y= y d( F(S, y))

dy dy M (2)

where F(S, y) = Q j P(S) Fj(y) is the probability that the maximum performance obtained in a contest involving players from a set P(S) is less than y. Notice that if the organizer is interested in maximizing a different function (e.g.,

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

sum of performance rather than the best performance) then only F(S, y) needs to be modiﬁed and the remaining of the analysis holds.

3.3 Nash Equilibria We now show that we retain all pure strategy Nash equilibria (NE), when moving to SQ.

Proposition 1. For any pure-strategies Nash equilibrium S of PAR and any π, there exists an equivalent pure strategies Nash equilibrium S of SQ(π) . If S is strict then S is strict.

Proof. Deﬁne S as follows: S i(x) = 1 if i P(S) and S i(x) = 0 otherwise. That is, the players in P(S) always participate (in S ), regardless of what the other players do, while those not in P(S) never participate. This exactly mimics the behavior of Ai in S - in the PAR . So, S is equilibrium, and P(S ) = P(S).

The reverse of Proposition 1 does not hold. There may exist NE in SQ that have no equivalent NE in PAR. This is illustrated in a numerical example provided at the end of this section. As for mixed strategy equilibria that may hold for PAR, these cannot have an equivalent equilibrium in SQ contest, simply because in every instance of the game any of the players (other than the ﬁrst in the sequence) will face a different history.

Finding the NEs We have already shown that, for any given strategy proﬁle S, the payoff of each player can be effectively computed. This, in turn, provides an effective way to check if a strategy proﬁle is a NE, by considering the payoffs for all possible deviations. This, in turn, provides an effective means to compute all NEs, by considering all possible strategy proﬁles.

3.4 Sub-Game Perfect Equilibrium We have seen that all pure Nash equilibria of PAR are also Nash equilibria of SQ (up to equivalence). So, just as in PAR, there may be many Nash equilibria for SQ, no one of which necessarily dominates the others. However, SQ is a dynamic game. As such, the proper, or natural, solution concept for this model is the sub-game perfect Nash equilibrium (SPNE). We note that since SQ(π) is a game of complete information, the SPNE can be readily computed using backward induction. Note that except for ties, the sub-game perfect Nash equilibrium is unique. Meaning that if S is a strict sub-game perfect equilibrium of SQ(π) then it is the only SPNE of SQ(π). The unique SPNE of SQ(π) depends on the order π. We now show that by properly ordering the players, any NE of PAR can be obtained as a SPNE of SQ.

Proposition 2. For any S, NE for PAR, there exists a π and S , such that S is a SPNE of SQ(π) , and S and S are equivalent. If S is strict NE then S is strict SPNE.

Proof. Let π be the order in which all players in P(S) appear before those not in P(S). Using backward induction construct a SPNE for SQ(π) . If at any node in the induction the player, Ai, is indifferent between participating and not, then have her participate if i P(S) and not participate if

i P(S). By construction, this is a SPNE. By induction on the game tree it is easy to see that P(S) = P(S ).

From Proposition 2 we conclude that by switching to the sequential mechanism we can force the best (strict) purestrategy Nash equilibrium of PAR. Interestingly, at times we can do even better. We now give an example of a SPNE of SQ, which has a better expected beneﬁt (for the organizer) than any NE of PAR. The example is based on three players, A1, A2 and A3, with corresponding participation costs c1 = 0.1, c2 = 0.33 and c3 = 0.19. The performance of A1 if participating is always 56 and for A3 it is 60. If A2 participates then its performance is 55 with probability 0.4 and 70 otherwise. The prize offered is M = 0.4. The only pure-strategies NE that holds with PAR in this setting is to have only A3 participate. In this case, the expected proﬁt of the organizer is 59.6. The mixed-strategies NE in this case is (0, 7

16) which results in an expected proﬁt of 59.675. With SQ(1, 2, 3) the SPNE is to have A3 participate only if A2 does not participate; A2 participate only if A1 does not participate; and A1 not participate (see Figure 1). This results in an expected proﬁt of 63.6, i.e., a substantial improvement compared to PAR.

Figure 1: SPNE for the numerical example.

4 Optimal Prize

To ﬁnd the optimal (organizer s expected-proﬁt-maximizing) prize one presumably needs to go over all possible M values and extract SPNE for each. This is infeasible as M is continuous and as shown in our prior work even minor changes in the prize offered can result in substantial changes in the resulting equilibrium of a simple contest [Levy et al., 2017]. In this section we show that one does not need to consider the entire continuum of possible prize values, but rather only a subset of discrete values need to be evaluated. The set size is bounded by the number of possible strategy proﬁles, i.e., exponential in the number of players. Still, in many real-life contests the number of contestants is quite modest, hence our ability to effectively discretize the prize continuum enables the extraction of the optimal prize. Let SSPNE(SQ(π) , M) be the SPNE of SQ(π) when the prize is M.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Deﬁnition 2. A prize value M, for SQ(π) is critical value, if for all ϵ > 0,

SSPNE(SQ(π) , M ϵ) = SSPNE(SQ(π) , M + ϵ)

That is, M is a critical value if the SPNE of SQ(π) changes at M. We now show that while M can take a continuum of values, the number of critical values is ﬁnite. Proposition 3. For any SQ(π), over n players, the number of critical prize values is bounded by 4n 1. These critical values can be effectively computed.

Proof. Consider the game tree G associated with SQ(π). Each node v deﬁnes a sub-game, with a game tree which we denote G(v). For brevity we identify a sub-game with its sub-tree. Let A(G(v)) be the set of players of G(v), and Av the player at v. The critical values of the sub-game, denoted C(G(v)) are deﬁned analogously to those of the entire game. That is, M is a critical value of G(v) if the SPNE of G(v) changes when the prize hits M. We prove by induction (on the structure of the tree), that |C(G(v))| 4d 1, where d is the height (distance from leaf) of node v, and that C(G(v)) can be effectively computed. For v a leaf, d = 0, there is no player in the game, and hence no critical value. Consider an internal node v, of height d. Let v0, v1, be the children of v, where v1 is the sub-game induced when the player at v decides to participate, and v0 induced when she decides not to participate. By the inductive hypothesis, |C(G(vb))| 4d 1 1, b = 0, 1. Consider C = C(G(v0)) C(G(v1)). So, |C| 2 4d 1 2. The set C divides the real axis into at most 2 4d 1 1 intervals. Denote this set of intervals by I. Consider I I, and let I be the interior of I. By construction, SSPNE(G(v1), M) remains the same as long as M I , and the same for SSPNE(G(v0), M). So, as long as the prize is within I , in the SPNE of G(v), the behavior of the players of A(G(v)) remains the same, except for possibly Av. We now show that the acts of Av can add at most one critical value within each such interval. Recall that v is a node in the game tree. Thus, the path from the root to v deﬁnes the choices of the players before Av. Let Av 1 be the set of players that decide to participate along this path. Set Av1,M 1+ = P(SSPNE(G(v1), M)) - the induced set of participants of the SPNE at v1, when M I . Set A1 = Av 1 Av1,M 1+ . The set A1 is the overall set of players that would participate alongside Av, if it chooses to participate at v. The expected payoff of Av in this case is given in equation (1). So, given that the players of A1 participate, player Av should participate whenever M M , where

Aj =Av,j A1 Fj(y)

So, if this M I , then this adds one extra critical point to C(G(v)). In all, the number of critical values for G(v) is bounded by

|C| + |I| = 2 4d 1 2 + 2 4d 1 1 < 4d 1

Algorithm 1 Extracting Critical Values for SQ(π) Input: G - the game tree associated with SQ(π) Output: C - list of all critical values. 1: for i = k, ..., 1 do 2: for every v G such that Av = Aπ 1(i) do 3: if i = k then 4: Cv0 {0}; Cv1 { } 5: Av1, 1+ Av0, 1+ Av1,0 1+ Av0,0 1+ 6: end if 7: Cv Cv0 Cv1

8: Order Cv (ascending) 9: Madd 10: for j = 1, ..., |Cv| 1 do 11: M Cv[j] 12: Calculate M using (3) for A1 Av1,M 1+ Av 1 13: if M < M then 14: Av,M 1+ Av1,M 1+ {Av} 15: else if M > Cv[j + 1] then 16: Av,M 1+ Av0,M 1+ 17: else 18: Madd Madd {M } 19: Av,M 1+ Av0,M 1+ 20: Av,M 1+ Av1,M 1+ {Av} 21: end if 22: end for 23: Cv Cv Madd 24: end for 25: end for 26: return Croot

as claimed. Equation (3) gives an effective way to compute the critical values.

The process of extracting the critical values for SQ(π) is summarized by Algorithm 1. The algorithm traverses the graph G starting with the last player s nodes up the tree. For each node v it maintains the set of critical values, stored in Cv, and the identity of players that will participate in the subgame that starts at v for each M Cv, stored in Av,M 1+ . For each M Cv the algorithm calculates the value M , i.e., the minimal prize making it worthy to participate given Av1,M 1+ . If M is below M, then participation is preferred throughout the interval from M to its subsequent member in Cv. Similarly, if M is above the subsequent member in Cv, then participation is not preferred throughout the interval from M to the subsequent member. Finally, if it is in between, then M is added as a new critical value. In this case participation is not preferred in (M, M ) and is preferred in the following interval. Finally, all additional critical values (stored in Madd) are added to Cv. The algorithm returns the list of critical values corresponding to the root node, Croot. Based on the output of the algorithm one can calculate Borg(S, M) for each M Croot, taking P(S) = Aroot,M 1+ , and pick the M value for which Borg(S, M) reaches its maximum. The process should be repeated to all possible sequences π.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

5 Experimental Evaluation

With people, the performance to be obtained with the mechanisms is likely to be different from the theoretical expectations, as people are known to be bounded-rational [Kahneman, 2000; Elmalech et al., 2015; Levy and Sarne, 2016]. In this section we present the results of a comparative empirical evaluation of SQ and PAR when contestants are people.

5.1 Experimental Framework In our experimental framework, contestants were ﬁrst awarded an initial bonus of c cents and had to decide whether they want to participate in the contest and lose that bonus or not participate and keep the bonus. For each contestant choosing to participate the system draws a percentile within the range 0-100, representing the contestant s performance. The contestant ranked at the highest percentile wins a bonus M. The fact that from the contestant s point of view, the performance measure merely indicates the percentile her contribution falls in rather than its actual value to the organizer enables assigning any distribution f(x) representing the value to the organizer of the contributions obtained. In PAR contestants do not know of the participation decisions of others whereas in SQ each contestant knows about the participation decisions of those sequenced before her. From the beginning contestants become aware of the parameters c, M, the overall number of contestants k, and the way contestants performance is determined (as a random percentile). The framework was developed as a java-script web-based game.

5.2 Experimental Design We used six different experimental treatments, differing in the type of contest used (PAR and SQ) and the prize M offered (three different prizes). The number of contestants in each was k = 3. The participation cost was set to be constant (arbitrarily set to c = 5c) to provide a similar baseline to all treatments. When setting the prize M we aimed for a varied set of values within the interval of interest, 5c 15c (where the lower end is the point where the prize offered covers only one contestant s participation cost, and the upper value is where even if all three participate the prize fully covers their participation costs), hence choosing M = 6c, M = 8c, M = 11c. Subjects were recruited and interacted through Amazon Mechanical Turk, assigning each to one treatment only, i.e., using a between-subjects design to prevent any carryover effect. PAR contests were run simultaneously, whereas with SQ contests we stored the state of the contest on each stage and used it as an input for the next contestant in the sequence. Overall, we had 1200 subjects taking part in our experiments, according to the following division: 300 overall for the three PAR contests; and (b) 300 for each of the SQ contests (to allow the completion of 100 contests for each). Subjects ranged in age (21-70), gender (50% men and 50% women) and education, with a fairly balanced division between treatments.

5.3 Experimental Results We begin with analyzing the participation decisions made by participants in our experiments. One common ﬁnding in prior literature is that people tend to exert more effort in contests

Figure 2: Number of participating contestants distribution in SQ (top) and PAR (bottom).

compared to the theoretical equilibrium-based (as well as alternative model-based) predictions, leading to better expected contributions overall [Sheremeta, 2013]. In particular, this has been shown in our prior work for simple parallel contests [Levy and Sarne, 2018]. This phenomenon was explained primarily by people s non-monetary utility from winning in a contest [Sheremeta, 2010] along with a plethora of secondary explanations such as mistakes and systematic biases [Chowdhury et al., 2014], lack of experience in contests [Sheremeta, 2011] and caring about relative payoffs maximization [Mago et al., 2016]. The proposed empirical analysis thus aims to investigate both whether a similar over-participation phenomenon occurs with SQ, and if so whether to a greater or a lesser extent compared to the PAR case. Figure 2 compares the distribution of number of contestants who chose to participate in each contest mechanism with the theoretical predictions, for different prize values. The top graph depicts the results for SQ. Here, according to equilibrium predictions only the ﬁrst player should choose to participate in the contest for M = 6 and M = 8, and only the ﬁrst two players should participate for M = 11 (in both contest mechanisms). The graph however, reﬂects a substantially greater participation rate compared to theory only in 32% and 22% of the contests there was a single participating contestant, for M = 6 and M = 8, respectively. In fact, in a non-negligible portion of these contests all three contestants chose to participate. Similarly, for M = 11 in almost 30% of the contests there were three contestants choosing to participate. The average number of participants in the contest is 1.77, 1.83 and 2.21 for M = 6, M = 8 and M = 11 (where the theoretical predictions are 1, 1 and 2), respectively. A similar over-participation phenomenon is observed in the case of PAR (bottom graph). Here, for completeness we also include the theoretical participation distribution according to the mixed-strategies equilibrium (in which participa-

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Figure 3: Difference in organizer s proﬁt when using SQ contest and PAR contest for different performance ranges.

tion probability of each contestant is p = 0.177, p = 0.43 and p = 0.71 for M = 6, M = 8 and M = 11 respectively). The over-participation phenomenon holds for all three treatments, both compared to the theoretical pure-strategies and mixed-strategies based equilubria. Still, with respect to both, the over-participation is to a smaller extent compared to the ﬁndings in the SQ case the average number of participants in the contest is 1.17, 1.65 and 2.22 for M = 6, M = 8 and M = 11 (the theoretical predictions are 1, 1 and 2 in the purestrategies based equilibrium and 0.51, 1.29 and 2.13 in the mixed-strategies based equilibrium), respectively. Since the theoretical participation predictions with the two mechanisms are similar, we can reason about the difference in the extent of the over-participation reﬂected with the two mechanisms by comparing the actual number of contestants that participated in the different contests carried out with each mechanism. Here we use both the Mann-Whitney Wilcoxon test [Mann and Whitney, 1947] and t-test. The ﬁrst is a non-parametric test, checking if one population tends to have larger values than the other (hence it is the most suitable for our case), while the second is a parametric test comparing the means, and its use is legitimate in our case due to the large number of observations. With both tests we ﬁnd that the difference in participation between SQ and PAR is statistically signiﬁcant for M = 6 and non-statistically signiﬁcant for M = 8 and M = 11 (for α = 0.05). Meaning that the over-participation found with SQ is at least as great as with PAR.

Next, we compare the average proﬁt obtained with SQ compared to with PAR, taking the expected-proﬁt maximizing prize in each case. Naturally, given the over-participation results reported above, we expect a greater average proﬁt for the organizer with SQ. This is indeed reﬂected in Figure 3 which depicts the difference between the proﬁt (picking the treatment resulting in the maximum proﬁt for each method) when using SQ and PAR, for different ranges over which f(x) is deﬁned (taking it to be uniform, starting at zero), both as absolute difference and in percentages of the expected proﬁt in PAR. As can be observed from the ﬁgure, the differences are substantial and decrease as the range of values from which performance derives increases. This latter decrease is because for most ranges (30 90) the optimal prize is M = 6 for the SQ mechanism and M = 11 for PAR and the increase in proﬁt resulting from any increase in range with M = 6 is smaller than the corresponding increase with M = 11.

6 Related Work

Contests have been widely studied in literature as a means for soliciting productive effort from agents, hence their importance for mechanism design [Lazear and Rosen, 1981; Gradstein and Konrad, 1999]. As such, various contest model variants can be found in related work, differing primarily in the number of contestants and their level of heterogeneity and tendency towards risk, structure of incentives used (e.g., rewards-allocation) and the organizer s objective functions (maximizing best effort versus the sum of efforts) [Rosen, 1986; Glazer and Hassin, 1988; Clark and Riis, 1996; 1998; Moldovanu and Sela, 2001; 2006; Archak and Sundararajan, 2009; Di Palantino and Vojnovic, 2009; Chawla et al., 2012]. Alongside game-theoretic work in this domain, there is much empirical research analyzing people s behavior in contests under different settings, and in particular people s over-expenditure of effort compared to theoretical predictions [Lazear, 2000; Sheremeta, 2010; Boudreau et al., 2011; Sheremeta, 2011; 2013; Chowdhury et al., 2014; Liu et al., 2014; Levy and Sarne, 2018]. This latter phenomenon, which is also being demonstrated with the proposed SQ mechanism, received diverse explanations as discussed in the former section [Dechenaux et al., 2015]. The underlying contest model used in this paper is of a simple contest, i.e., one where contestants only strategize on participation itself. While the majority of contests body of literature has focused in effort-based contests, where the probability of winning is determined by the efforts each contestant exerts, simple contests have gained interest in recent years, primarily due to their applicability as discussed earlier in this paper [Ghosh and Hummel, 2012; Ghosh and Kleinberg, 2016; Sarne and Lepioshkin, 2017]. Alas, the study of simple contests typically assumes the contest is carried out such that all contestants make their participation decision in parallel. One exception is our prior work [Levy et al., 2017] where a strictly sequential simple contest is analyzed. That model, however, assumes complete information not only in the sense that contestants become aware of the participation decisions of others, but rather also of the performance achieved by others, prior to making their own participation decision. This latter assumption results in a critical difference in terms of the equilibrium structure and the resulting expected proﬁt to the organizer, precluding any of the beneﬁts discussed above. In particular, the equilibrium in that model variant relies on threshold-based contestants strategies and no mapping holds to the parallel model. In a more general sense, the aspect of executing a contest sequentially can be found in tournaments literature [Rosen, 1986; Clark and Riis, 1996; 1998; Gradstein and Konrad, 1999]. These, however, are very different from the model analyzed in this paper, in the sense that contestants iteratively compete against others and only those that survive a round move on to subsequent rounds.

7 Discussion and Conclusions

As proved and demonstrated throughout the paper, the choice of using SQ over the traditional parallel simple contest encompasses many advantages, among which a tight control

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

over the outcome of the contest, a guarantee for the maximum possible achievable (and at times even greater) pure-strategy Nash equilibria proﬁt of PAR, and at least the same (and at times an even greater) extent of over-participation compared to theoretical prediction when contestants are people rather than self-interested agents. The expected-proﬁt-maximizing prize determination with SQ is tractable, despite the continuous nature of the prize parameter. To the best of our knowledge this is the ﬁrst attempt to deal with the continuous nature of the prize in simple contests, as far as prize-determination is concerned. In this paper we focused on simple contests. A major future research avenue is the question of whether and how these ideas can be extended to general contests.

Acknowledgments This research was partially supported by the ISRAEL SCIENCE FOUNDATION (grants No. 1162/17 and 1083/13) and the ISF-NSFC joint research program (grant No. 2240/15).

[Archak and Sundararajan, 2009] Nikolay Archak and Arun Sundararajan. Optimal design of crowdsourcing contests. ICIS 2009 proceedings, page 200, 2009.

[Boudreau et al., 2011] Kevin J. Boudreau, Nicola Lacetera, and Karim R. Lakhani. Incentives and problem uncertainty in innovation contests: An empirical analysis. Management Science, 57(5):843 863, 2011.

[Chawla et al., 2012] Shuchi Chawla, Jason D. Hartline, and Balasubramanian Sivan. Optimal crowdsourcing contests. In Proc. of SODA, pages 856 868, 2012.

[Chowdhury et al., 2014] Subhasish M. Chowdhury, Roman M. Sheremeta, and Theodore L. Turocy. Overbidding and overspreading in rent-seeking experiments: Cost structure and prize allocation rules. Games and Econ. Behavior, 87:224 238, 2014.

[Clark and Riis, 1996] Derek J. Clark and Christian Riis. A multiwinner nested rent-seeking contest. Public Choice, 87(1):177 184, 1996.

[Clark and Riis, 1998] Derek J. Clark and Christian Riis. Inﬂuence and the discretionary allocation of several prizes. European Journal of Political Economy, 14(4):605 625, 1998.

[Dechenaux et al., 2015] Emmanuel Dechenaux, Dan Kovenock, and Roman Sheremeta. A survey of experimental research on contests, all-pay auctions and tournaments. Experimental Economics, 18(4):609 669, 2015.

[Di Palantino and Vojnovic, 2009] Dominic Di Palantino and Milan Vojnovic. Crowdsourcing and all-pay auctions. In Proc. of ACMEC, pages 119 128, 2009.

[Elmalech et al., 2015] Avshalom Elmalech, David Sarne, Avi Rosenfeld, and Eden Shalom Erez. When suboptimal rules. In AAAI, pages 1313 1319, 2015.

[Fu and Lu, 2012] Qiang Fu and Jingfeng Lu. The optimal multistage contest. J. of Economic Theory, 51(2):351 382, 2012.

[Ghosh and Hummel, 2012] Arpita Ghosh and Patrick Hummel. Implementing optimal outcomes in social computing: A gametheoretic approach. In Proc. of WWW, pages 539 548, 2012.

[Ghosh and Kleinberg, 2016] Arpita Ghosh and Robert Kleinberg. Optimal contest design for simple agents. ACM Transactions on Economic and Computation, 4(4):22:1 22:41, 2016. [Glazer and Hassin, 1988] Amihai Glazer and Refael Hassin. Optimal contests. Economic Inquiry, 26(1):133 143, 1988. [Gradstein and Konrad, 1999] Mark Gradstein and Kai A. Konrad. Orchestrating rent seeking contests. Economic Journal, 109(458):536 45, 1999. [Kahneman, 2000] Daniel Kahneman. A psychological point of view: Violations of rational rules as a diagnostic of mental processes. Behavioral and Brain Sciences, 23(5):681 683, 2000. [Lazear and Rosen, 1981] Edward P. Lazear and Sherwin Rosen. Rank-order tournaments as optimum labor contracts. Journal of political Economy, 89(5):841 864, 1981. [Lazear, 2000] Edward Lazear. Performance pay and productivity. American Economic Review, 90(5):1346 1361, 2000. [Levy and Sarne, 2016] Priel Levy and David Sarne. Intelligent advice provisioning for repeated interaction. In Proc. of AAAI, pages 842 849, 2016. [Levy and Sarne, 2018] Priel Levy and David Sarne. Understanding over participation in simple contests. In Proc. of AAAI, 2018. [Levy et al., 2017] Priel Levy, David Sarne, and Igor Rochlin. Contest design with uncertain performance and costly participation. In Proc. of IJCAI, pages 302 309, 2017. [Liu et al., 2014] Tracy Xiao Liu, Jiang Yang, Lada A. Adamic, and Yan Chen. Crowdsourcing with all-pay auctions: A ﬁeld experiment on taskcn. Management Science, 60(8):2020 2037, 2014. [Luo et al., 2014] Tie Luo, Salil S. Kanhere, and Hwee-Pink Tan. Optimal prizes for all-pay contests in heterogeneous crowdsourcing. In Proc. of MASS, pages 136 144, 2014. [Mago et al., 2016] Shakun D. Mago, Anya C. Samak, and Roman M. Sheremeta. Facing your opponents. Journal of Conﬂict Resolution, 60(3):459 481, 2016. [Mann and Whitney, 1947] Henry Mann and Donald Whitney. On a test of whether one of two random variables is stochastically larger than the other. Annals of math. stat., pages 50 60, 1947. [Moldovanu and Sela, 2001] Benny Moldovanu and Aner Sela. The optimal allocation of prizes in contests. American Economic Review, 91(3):542 558, 2001. [Moldovanu and Sela, 2006] Benny Moldovanu and Aner Sela. Contest architecture. J. of Econ. Theory, 126(1):70 96, 2006. [Rosen, 1986] Sherwin Rosen. Prizes and incentives in elimination tournaments. The American Econ. Review, 76(4):701 715, 1986. [Sarne and Lepioshkin, 2017] David Sarne and Michael Lepioshkin. Effective prize structure for simple crowdsourcing contests with participation costs. In Proc. of HCOMP, pages 167 176, 2017. [Sheremeta, 2010] Roman M. Sheremeta. Experimental comparison of multi-stage and one-stage contests. Games and Economic Behavior, 68(2):731 747, 2010. [Sheremeta, 2011] Roman Sheremeta. Contest design: An experimental investigation. Economic Inquiry, 49(2):573 590, 2011. [Sheremeta, 2013] Roman Sheremeta. Overbidding and heterogeneous behavior in contest experiments. Journal of Economic Surveys, 27(3):491 514, 2013. [Siegel, 2009] Ron Siegel. All-pay contests. Econometrica, 77(1):71 92, 2009.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)