Picking the Right Winner: Why Tie-Breaking in Crowdsourcing Contests Matters

1 Introduction

In crowdsourcing contests, tasks are presented to a group of contestants and a contest is held to determine the best solution to each task. Each task (e.g., translation, logo design, software development) is described in words, offers a monetary reward for the best solution (or sometimes for more than one solution) chosen by the organizer of the contest, and has a deadline. In recent years, platforms for crowdsourcing contests have grown rapidly (e.g., "Taskcn.com", "TopCoder", "99Design"). In particular, the design market is increasingly turning to crowdsourcing as a source of labor. Crowdsourcing contests platforms allow the organizers of the contests access to a wide variety of contestants worldwide while offering a prize that is usually much smaller than an advertising firm's fee for the same service.

∗The work was supported by ISF grant 2167/19. All missing proofs can be found in the full version on arXiv.

Hand in hand with the growth in crowdsourcing activity, the literature on crowdsourcing contests is also expanding (see [Vojonovic, 2015; Segev, 2020] for an extensive review). The prevailing paradigm in this literature is that each submission is endowed with a measure called "quality", which is a function (deterministic or stochastic) of the contestant's effort and ability. Given the qualities of the submissions, the winner is either the contestant with the highest quality submission or is chosen randomly from all contestants but with a probability that increases in the quality of the submission. This paradigm does not fit all types of crowdsourcing contests. As an example consider design contests in which it is relatively easy to distinguish between high and low quality submissions. However, often, there is no objective measure for picking the best submission. A different domain in which a similar difficulty occurs is coding contests. In this domain, the organizer can run a test to check the correctness of the submissions. The organizer then needs to pick a submission from all those that passed the test. The second choice is a subjective one.

In this paper, we consider an alternative model that we believe is more appropriate for domains in which there is only a partial objective measure of quality, one that only separates between "good" and "bad" submissions. In our model, each player's ability is modeled as a probability of producing a successful submission. Therefore, each submission is either successful (i.e., of high quality) or not. Under this framework, it is often the case that there is more than one successful submission. Thus, a crucial ingredient in choosing the winner is breaking ties between successful submissions. To break those ties, the organizer can use public information on the contestants. For example, the number of contests they participated in and the number of contests they won. One natural way of breaking ties is to pick the contestant who won the most contests or the one with the highest ratio of successes among the successful submissions. Such a choice is consistent with the halo effect [Nisbett and Wilson, 1977] which makes people believe that those that previously succeeded will continue to succeed. Other organizers might prefer to choose the submission of the contestant that won the least many contests so far, assuming that it will probably be more unique than the potentially more generic design of a "constant" winner. We observe that when the players know the tie-breaking rule, different tiebreaking rules may induce different equilibria. This suggests that the issue of tie-breaking, which is often overlooked, can significantly affect the players' behavior.

Model. We have a set N of n players competing in a complete information contest. Player i's probability of producing a successful submission is pi. We refer to this parameter as player i's ability and refer to a player that produced a successful submission as a successful player. 1 We assume, without loss of generality, that p1 ≥ p2 ≥ . . . ≥ pn. We assume that all players have a fixed cost of 1 for participating in the contest. The winner of the contest receives a reward of R. The winner is selected from all the players that succeeded according to a deterministic tie-breaking rule π. π is a permutation over the players' indices, and the winner is the successful player that is first according to π. Formally, player i wins if it is successful and for every other successful player j it holds that π(i) < π(j). The tie-breaking rule is known to the players ahead of time. Two tie-breaking rules of interest are πs(i) = i, which breaks ties in favor of strong players, and πw(i) = n + 1 - i, which breaks ties in favor of weak players. 2

In our model, the players only need to decide whether they want to participate in the contest or not. A player chooses to participate if its expected payoff is at least 0. An additional player in this game is the organizer. The organizer chooses the reward to maximize its expected utility in equilibrium. As for the tie-breaking rule, we discuss both scenarios in which the tie-breaking rule is chosen endogenously by the organizer and cases in which it is chosen exogenously by the platform. To focus on the effect of the tie-breaking rule on the chosen equilibrium, we assume that the organizer only cares that at least one of the submissions is successful. In this case, it gets a utility of V and pays the reward R. The organizer's expected utility is defined according to the set of players participating in the equilibrium, given the reward R. Formally, let S(R) denote the set of players that participate in equilibrium. The utility of the organizer is p(S(R))(V -R), where p(S) is the probability that at least one player in S is successful.

Results. We show by a simple constructive argument that our game has essentially a unique Nash equilibrium (i.e., a unique set of players that choose to participate), given the tiebreaking rule and the reward R. As a result, the problem of the organizer of choosing a reward is well-defined. We show that the organizer can compute in poly-time the reward that maximizes its utility under any tie-breaking rule. When ties are broken in favor of strong players, the argument is quite straightforward. In this case, the organizer will choose a reward that motivates the best k players, for some 1 ≤ k ≤ n, to participate. The reward motivating such a set S can be determined by the minimal reward required for player |S| to join (note that this player is both the weakest player in S and the player that has the maximal probability that a player prior to it will be successful). Thus, the organizer has only n optional subsets to check. For other tie-breaking rules, the problem is much more involved. Nonetheless, we can still narrow down the number of optional sets to n. To this end, we show that for any 1 ≤ k ≤ n, the only relevant set of size k is the one that is motivated by the minimal reward. We then show a polytime algorithm that identifies these sets when all abilities are rational numbers.

1 This modeling is closely related to the modeling of [Kleinberg and Oren, 2011] for research contests.

2 Note that in crowdsourcing sites it is possible to estimate the players' abilities from public information and break ties according to this estimate.

Observe that the tie-breaking rule directly influences the reward required to motivate the players to participate. In particular, the reward required to motivate all the players in S is the reciprocal of the minimal probability of a player in S to collect the reward. This is the probability that the player is successful and all players prior to it are unsuccessful. Notice that this probability depends on the player's location in the order and its ability. For this reason, the tie-breaking rule that induces some set S for a minimal reward R (if such exists) will always place the players in S first and order them in decreasing order of their indices (e.g., weakest players first). Intuitively speaking, this spreads the probability of collecting the reward more evenly by reducing the probability of a weak player succeeding and not getting the reward at the expense of increasing this probability for stronger players. This discussion suggests that πw (i.e., ties are broken in favor of weaker players) is a useful tie-breaking rule. Indeed, if there exists a reward R motivating equilibrium S when ties are broken according to πw then, the reward R motivating it is minimal. However, many subsets cannot be supported by πw and in such cases, the utility of the organizer can be higher with a different tie-breaking rule. For example, we show that there are cases in which the utility of the organizer is greater when ties are broken in favor of stronger players.

Next, we show that the natural rule of breaking ties in favor of stronger players (i.e., πs) is relatively good. In particular, the utility of the organizer using πs is at least 1/(3-p1) of its utility under the optimal tie-breaking rule. We also show that the organizer's utility for using any tie-breaking rule π is at least 1/2 its utility when using πs. Using similar techniques we also show that the multiplicative gap in the utility of the organizer under any two tie-breaking rules is bounded by 1/3.

Finally, we consider the price of anarchy of our game. The price of anarchy is defined as the ratio of the social welfare of the optimal solution and the social welfare of the Nash equilibrium. We define the social welfare of the game to be the sum of the players' utilities and the organizer's utility. This means that the reward that the organizer gives cancels out the reward that the players receive. Hence, the social welfare when the players in S participate is p(S) · V - |S|. We show that the price of anarchy is bounded by lnn and that this bound is tight when ties are broken according to πs. To better understand what drives this price of anarchy, we contrast this result with the case that all players have the same ability. In the latter case, we show that the price of anarchy is substantially smaller and bounded by 3/2. This suggests that diversity in terms of the different abilities of the players may harm efficiency.

RelatedWork. A significant body of theoretical work (see [Segev, 2020] for a survey) aims to relax some of the assumptions in the classic contest theory literature (e.g., [Konrad, 2009; Vojonovic, 2015]) to suggest models that apply to the crowdsourcing world. This includes both empirical work (see e.g., [Archak, 2010; Zheng et al., 2011; Araujo, 2013; Liu et al., 2014])) and theoretical work (e.g.,[Archak and Sundararajan, 2009; Chawla et al., 2015; Cavallo and Jain, 2012]). Most of the works consider a model in which the submission's quality is a function of the effort invested. A couple of works study a model similar to ours in which the players only need to decide whether to participate or not. In [Ghosh and Hummel, 2012; Ghosh and Kleinberg, 2016] a player's type qi is also the (deterministic) quality of its submission and the winners are determined according to the qualities of participating players. In [Levy et al., 2017; Levy et al., 2018] the authors assume that the quality is drawn from a continuous CDF on some interval. This leads to a completely different analysis.

Only a few works in contests theory study tie-breaking rules. [Llorente-Saguer et al., 2018] show in an experiment that a tie-breaking rule that favors weak players diminishes their discouragement significantly and increases their effort. This is in line with our findings, as we show that such a tiebreaking rule may do very well under some circumstances. In a multi-battle contest, [Konrad and Kovenock, 2009] analyze different tie-breaking rules that affect the results only if both contestants' valuations for the reward in a given battle is zero. In sequential bidding contests, the common assumption (e.g., in [Segev and Sela, 2014]) is that ties are broken in favor of contestants that arrive later. Our model assumes that contestants' characteristics determine how ties between successful submissions are broken and not the time of the submission, especially since in many crowdsourcing contests platforms, a contestant may enter the contest more than once and change her submission.

In a different context, the issue of tie-breaking rules is also prominent in [Kleinberg and Oren, 2011]. They study a model of multiple research contests and essentially show that there exists a tie-breaking rule in which the optimal solution is a Nash equilibrium.

Finally, there is already theoretical evidence that suggests that "leveling the playing field" by giving weak players an advantage (in the form of a headstart or handicap for other players) may increase the overall expected effort and the social welfare, see e.g., [Zhu, 2021; Franke et al., 2018]. Our analysis contributes to this literature by showing that breaking ties in favor of weak players may have a similar effect.

2 Notation and Preliminaries

The utility of player i ∈ S when S is the set of players that participate and a deterministic tie-breaking rule π is used is uπi (S) = R · (pi · ∏{j∈S|π(j)<π(i)} (1 - pj)) - 1.

A useful quantity is the probability that a player i ∈ S is chosen to get the reward when S is the set of players that participate in the contest. This is also its marginal contribution (according to π) to the probability that the contest is successful: p(i) π (S) = pi · ∏{j∈S|π(j)<π(i)} (1 - pj). 3 With this notation uπi (S) = p(i) π (S) · R- 1. We assume that a player participates in the contest if and only if its expected utility is at least 0.

We observe that the Nash equilibrium in the game induced by the choice of R is unique. To see why this is the case, observe that we can construct the equilibrium by going over the players in the order of π and asking each player if it wants to join the contest, given the choices of all players prior to it. Let p(S) = 1 - ∏i∈S (1 - pi) denote the probability that at least one of the players in S is successful. We refer to p(S) as the success probability of S. Let Sπ (R) denote the set of players that participate in the unique Nash equilibrium induced by the reward R when ties are broken according to π. With this notation, the utility of the organizer is p(Sπ (R))(V - R). The organizer chooses R in order to maximize its utility. We denote by uπo (V ) the utility of the organizer when ties are broken according to π for the reward maximizing its utility when its value for a successful contest is V . We say that a reward R motivates or induces a set of players S if S is an equilibrium for the reward R.

We note that the minimal reward R that motivates a set of players S (if such exists) equals the reciprocal of the minimal probability of a player in S to collect the reward. Formally, let i = argminj∈S p(j) π (S), then R = 1 p(i) π (S) . The organizer can always motivate the best player (e.g., player 1) by the reward 1 p1 and the set of all players by the reward 1 p(i) π (N) , where player i is the player with the minimal probability to collect the reward when all the players in N participate in the contest (its identity is determined by the tie-breaking rule).

3 Choosing the Optimal Reward

We begin by observing that computing the reward when ties are broken according to πs (e.g., in favor of stronger players) is easy. This is because the only subsets that can be motivated are those that include the k strongest players for 1 ≤ k ≤ n and the minimal rewards motivating these subsets are easy to compute. Computing the reward maximizing the utility of the organizer under an arbitrary tie-breaking rule is not as simple. One reason for this is that the success probability (i.e., p(S(R))) is not monotone increasing in R. This is demonstrated by the following example:

Example 1. Consider a 3-player instance with the following probabilities : p1 = 3/4, p2 = 1/2, p3 = 1/3 and the tiebreaking order πw (ties are broken in favor of weaker players). The unique equilibrium for R1 = 8/3 is {1, 2} while the unique equilibrium for R2 = 3 is {2, 3}.

Despite the lack of monotonicity in the reward, we obtain a polynomial-time algorithm for computing a reward maximizing the organizer's utility. First, we show that it is still the case that the organizer can restrict its optimization to choosing one of at most n optional subsets, each of different size. Then, we craft a binary search algorithm to identify these n optional subsets in polynomial time.

3 When π is clear from the context we omit the subscript of π.

Theorem 1. For any deterministic tie-breaking rule π, the organizer can compute the reward maximizing its utility in polynomial time.

Proof. (sketch) Let Rk denote the minimal reward that motivates some set Sk that includes exactly k players for 1 ≤ k ≤ n, if such exists. We first show that the equilibriummaximizing the organizer's utility is one of the sets S1, . . . , Sn that are induced by the rewards R1, . . . , Rn.

The reason for this is that in Lemma 1 below, we show that if there are two rewards R′ > R ≥ 0 that motivate equilibria with the same number of players (i.e., |Sπ (R)| = |Sπ (R′ )|), then the success probability of the players in Sπ (R) is greater than the success probability of the players in Sπ (R′ ) (i.e., p(Sπ (R′ )) < p(Sπ (R))). In particular, in Lemma 1 we show that every player l ∈ Sπ (R) \ Sπ (R′ ) can be matched with a player in Sπ (R′ ) \ Sπ (R) with a lower ability. Thus, if |Sπ (R)| = |Sπ (R′ )|, then p(Sπ (R′ )) < p(Sπ (R)).

Next, we show that the rewards R1, . . . ,Rn can be computed in polynomial time. The crucial property for showing this is monotonicity in the reward in terms of the number of players participating in equilibrium. Formally, Lemma 1 implies that for any two rewards R′ > R ≥ 0, we have that |Sπ (R′ )| ≥ |Sπ (R)|. This monotonicity gives rise to a binary search algorithm for computing the minimal reward motivating an equilibrium of k players. Note that the value of Rn is easy to compute, hence the search space of the algorithm is [0,Rn]. Since our search space is continuous, we will stop searching when the interval reaches a certain size ε to guarantee that the algorithm ends. The challenge here is to choose ε such that the algorithm's running time is polynomial and that we could infer the exact value of Rk or determine that no such value exists. We show that if the players' abilities are rational numbers then we can implement the algorithm in time that is polynomial in the input to the problem.

The proof of Lemma 1 builds on the following observation: Observation 1. For every reward R > 0 and every tiebreaking rule π, if i ∈ Sπ (R) then, for each j /∈ Sπ (R) such that π(j) < π(i) we have that pj < pi.

Proof. Let S = Sπ (R). We compare the utilities of players i and j for participating. Since player j does not participate, we have that: uπi (S) = R· pi · ∏{l∈S|π(l)<π(i)} (1-pl)-1 is greater than uπj (S ∪{j}) = R· pj · ∏{l∈S∪{j}|π(l)<π(j)} (1pl) - 1. Observe that since π(j) < π(i), the players in S that are before j in the order are a subset of the players that are before i in the order. Thus, the probability that all players in S prior to j fail (i.e., ∏{l∈S∪{j}|π(l)<π(j)} (1 - pl)) is at least as large as the probability that all player in S prior to i fail (i.e., ∏{l∈S|π(l)<π(i)} (1 - pl)). Hence, the only reason for player j not to participate when player i participates is that pj < pi.

Lemma 1. Consider two rewards R′ > R ≥ 0 and a tiebreaking rule π. There exists a matching that matches any player l ∈ Sπ (R) \ Sπ (R′ ) to a player j ∈ Sπ (R′ ) \ Sπ (R) such that π(j) < π(l) and pj < pl.

Proof. (sketch) Let S = Sπ (R) and S′ = Sπ (R′ ). Denote by J = S′ \S the set of players that joined the contest following the increase of the reward from R to R′ , and by L = S \ S′ the set of players that left the contest. By Observation 1, for each l ∈ L and j ∈ J such that π(j) < π(l) we have that pj < pl. Thus, to complete the claim, it suffices to show that there exists a matching that matches each player l ∈ L with a player j ∈ J such that π(j) < π(l). To this end, we represent the players that joined and left S when we increased R to R′ by placing them in a sequence according to their order in π. We show that every prefix of this sequence has at least as many players in J as in L. To see why this suffices to prove the claim, we can think of the sequence of players joining and leaving as a sequence of parentheses in the sense that "(" corresponds to a player that joined S and ")" to a player that left S. We also have that each prefix of this sequence includes at least as many "(" marks as ")" marks. This, in turn, implies that adding |J|-|L| ")" marks to the end of the sequence will make this a balanced sequence of parentheses. In the balanced sequence, each "(" mark could be uniquely matched to ")" mark. This matching induces a matching of all ")" marks to "(" marks in the original sequence. This implies that each l ∈ L player could be matched to a different player j ∈ J, such that π(j) < π(l).

4 Comparison Between Deterministic Tie-Breaking Rules

We now consider an organizer that can also choose the tiebreaking order. We show that there exists a tie-breaking order of a specific structure that the organizer can choose to maximize its utility. In this order, we first place the players that participate in equilibrium in decreasing order of indices and then the rest of the players in an arbitrary order:

Proposition 1. Let π and R be the pair of tie-breaking rule and reward maximizing the organizer's utility. Then, the organizer has the same utility for R and an order in which the players in Sπ (R) are the first players and they are ordered in decreasing order of their indices (i.e., increasing abilities).

Proof. Let S = Sπ (R). Let π′ denote an order which is induced by π in which the first |S| places include only players from S and their internal order is determined according to π. It is easy to see that all players in S will still participate in the equilibrium induced by π′ and R. If there is no pair of players i, j ∈ S such that j < i (pi > pj) and π′ (i) < π′ (j) then π′ has the required structure. Else, let j, i ∈ S be a pair of players such that j < i and π′ (i) < π′ (j). Consider an order ˜π which is identical to π′ except we swap between the locations of i and j (e.g., ˜π(i) = π′ (j) and ˜π(j) = π′ (i)). We claim that for the reward R it is still the case that all the players in S participate in equilibrium. To see why, observe that when all the players in S participate each player t such that π′ (t) < π′ (i) has the same probability to collect the reward in π′ and in ˜π (e.g., p(t) π′ (S) = p(t) ˜π (S)). For player j we have that p(j) ˜π (S) ≥ p(j) π′ (S) since the set of players before j in ˜π is a subset of the set of players before j in π′ . Since pj < pi, the probability to collect the reward of any player t such that π′ (i) < π′ (t) < π′ (j), can only increase in ˜π. Finally, notice that player i still wants to participate since its probability to collect the reward at ˜π(i) is greater than the probability of player j in π′ (j) to collect the reward (e.g., p(i) ˜π (S) > p(j) π′ (S)) and player j chose to participate in π′ .

As a corollary, we get that when V is large enough and the organizer maximizes its utility by motivating all the players to participate, the utility of the organizer is maximized by breaking ties in favor of weaker players:

Corollary 1. For any p1, . . . , pn, there exists V ′ such that whenever V > V ′ the organizer will maximize its utility by breaking ties according to πw.

Essentially, for any set S the organizer can motivate S or a superset of S by setting R = 1 pi ∏j∈S|j>i (1-pj) where

player i ∈ argminj∈S p(j) π (S) and π is the order defined in Proposition 1. This leads us to the question of which subset should the organizer motivate. We observe that the organizer will only consider subsets that include the strongest player (e.g., player 1). To see why this is the case, let π and R be the tie-breaking rule and reward maximizing the organizer's utility and assume that 1 ̸∈ Sπ (R). By Proposition 1 we can assume without loss of generality that in π the players of Sπ (R) are ordered in decreasing order. Since 1 ̸∈ Sπ (R) we have that the player that is placed in the |Sπ (R)| location in the order is player j > 1 (i.e., π-1 (|Sπ (R)|) = j > 1). Now, suppose we use the order π′ which is identical to π except that π′ (1) = |Sπ (R)| and π′ (j) = π(1). In that case, we get that for the same reward R player 1 will participate in equilibrium together with all the players in Sπ (R)\{j}, hence the success probability of the organizer may only increase. This proves the following observation:

Observation 2. An organizer that can choose both π and R will always motivate a subset that includes player 1.

At first glance, one might suspect that the organizer will only motivate subsets that include the best k players for some value of 1 ≤ k ≤ n. Interestingly, as demonstrated by the following example, this is not always the case:

Example 2. Consider a 3-player instance such that p1 = 6/8, p2 = 5/8, p3 = 4/8. The set that the organizer chooses to motivate for V = 14 is {1, 3}.

The previous observation suggests that computing the optimal ordering may be difficult. Moreover, there are many cases in which the organizer cannot choose the tie-breaking rule. One reason for this might be that the platform may demand that the same tie-breaking rule will be used across all contests. Which tie-breaking rule should the platform choose in this case? Proposition 1 suggests that πw which breaks ties in favor of weaker players may be a good choice as each set that can be motivated by πw will be motivated by the minimal reward. The reason for this is that both in π and πw the players in S have the same internal order. The only different is that in πw there could be other players that are interleaved in the ordering of those players. However, since these players do not participate they do not affect the required reward. This proves the following claim:

Claim 1. Consider an equilibrium S that is motivated by reward R when ties are broken according to πw. Then, any other tie-breaking rule π that motivates S requires a reward R′ ≥ R.

Despite the apparent potential of breaking ties in favor of weaker players, breaking ties in favor of stronger players is arguably more common in practice. The next theorem tells us that using this tie-breaking rule may be a reasonable choice as the organizer's loss in utility from using it instead of the optimal tie-breaking rule is bounded by a small constant:

Theorem 2. For any V > 0 the utility of the organizer for

using any tie breaking rule π is at most 3-p1 times its utility for using πs. Formally, uπo (V )

Proof. Let Rs and Rπ denote the rewards that maximize the organizer's utility for πs and π respectively. Observe that since under πs the organizer maximizes its utility by setting Rs we have that uπs o (V ) ≥ p(Sπs (Rπ)(V -Rπ). This implies that:

We now bound the gaps between the success probability of the players participating in equilibrium under different tiebreaking rules but with the same reward. To simplify notation let Sπ = Sπ (Rπ) and Ss = Sπs (Rπ). Let T = Sπ \ Ss denote the set of players that participate in π but do not participate in πs. Note that T ̸= ∅ since p(Sπ) > p(Ss) and that the players in Ss are the |Ss| strongest players (e.g., Ss = {1, . . . , |Ss|}). Let j ∈ T be the player with maximal π(j). Note that j > |Ss| since Ss consists of the strongest players. This implies that p(T \{j}) ≤ p(Ss) since Rπ ·pj (1-p(T \{j})-1 ≥ 0 but Rπ ·p|S|+1(1-p(Ss))-1 < 0 and pj ≤ p|Ss|+1. Thus,

Observe that by submodularity of the probability function we have that (1-p(Ss))p|Ss|+1 p(Ss) ≤ 1 |Ss| . Thus, we get:

Note that the bound of 3 is only obtained when |Ss| = 1. Qualitatively speaking, as V increases the reward that the organizer chooses to give in the optimal tie-breaking rule also increases. As a result the size of Ss should increase and the bound will approach 2.

Even though, πw guarantees the minimal reward for the sets it supports, some times using πs can be better. 4 More generally, the following proposition tells us that the benefit to the organizer from using πs over using any other tie-breaking rule is bounded by 2.

Proposition 2. For any V > 0 the utility of the organizer when applying πs is at most twice its utility when applying any tie-breaking order π. Formally, uπs o (V ) uπo (V ) ≤ 2.

Finally, we show that by applying techniques similar to the proof of Theorem 2 we can bound the ratio between the organizer's utility under any two arbitrary orderings:

5 Price of Anarchy

We establish an upper bound of about ln(n) on the price of anarchy under any tie-breaking order. Recall that the price of anarchy is defined as follows: let S denote the set of players that participate in the equilibrium that is induced by the reward R maximizing the organizer's utility and O the set of players that participate in the optimal solution. The price of anarchy is PoA = p(O)·V-|O| p(S)·V-|S| we show that PoA ≤ Hn = ∑ni=1 1i . Moreover, we show that the bound is tight when ties are broken according to πs. Finally, we consider the case when all players have identical success probabilities and show that the bound on the price of anarchy drops to a small constant.

Theorem 3. Under any tie-breaking rule π the price of anarchy is at most Hn ≈ ln(n).

Proof. (sketch) Recall that S is the set of players that participate in equilibrium and O = {1, . . . , |O|} is the set of players that participate in the optimal solution. The crux of the proof is looking at the social welfare of the optimal solution as the sum of marginal contributions of each player under the order π: p(O) · V - |O| = ∑i∈O (p(i) (O) · V -1). Recall that p(i) (S) = pi · ∏j∈S:π(j)<π(i) (1 - pj). We separately bound each marginal contribution p(i) (O)·V-1 p(S)·V-|S| . Let R = 1 p(j) (S) where j = argmink∈S p(k) (S) denote the reward motivating S under the tie-breaking rule π. Observe that p(S) · V -|S| ≥ p(S)(V -R) since the expected reward that the organizer pays has to be at least the cost of the players for participating. Hence, we instead bound p(i) (O)·V-1 p(S)(V -R) which allows us to use the fact that S maximizes the organizer's utility more easily.

We show that for each i ∈ O we have that p(i) (O)·V-1 p(S)(V-R) ≤ 1 |S(Ri(O))| where Ri(O) = 1 p(i) (O) . The reward Ri(O) is the reward that motivates all the players in B(i) = {j ∈ O : p(j) (O) ≥ p(i) (O)} to participate (in case all the players not in B(i) do not participate). Since the organizer prefer R over Ri(O) we have that p(S) · (V -R) ≥ p(S(Ri(O))) · (V -Ri(O)). Since Ri(O) = 1 p(i) (O) it is clearly the case that the marginal contribution (according to π) to the success probability of any player j ∈ S(Ri(O)) is at least p(i) (O). Thus, p(S(Ri(O)) ≥ |S(Ri(O))| · p(i) (O) which implies that,

4 See the full version for such example.

Note that the right handside equals 1 |S(Ri(O))| . Thus, to complete the proof we show that for any i ∈ O, the number of players participating in the equilibrium induced by Ri(O) is at least |B(i)|. Notice that if we sort the values of |B(i)| in increasing order we get, by definition of B(i) that for each 1 ≤ k ≤ n the value at rank k is at least k. Hence, we con-

In the full version we show that our bound is tight for πs: Theorem 4. When ties are broken by πs, for any n > 0 and 0 < δ < 1 n-1 there exists an n-player instance that has price of anarchy of Hn - δ(n - Hn).

Next we show that a property driving this relatively high price of anarchy is that the abilities of the players are different. We show that when all players have identical abilities (denoted by p), the price of anarchy is bounded by 3/2. The maximal PoA is achieved when n players participate in the optimal solution, but the organizer prefer to motivate a set of ⌊ 1 2 n⌋ players. In this case as p goes to 0 the PoA is approaching 4n+4 3n+2 . This bound is decreasing in n and its maximal value is 3/2 for n = 2.

Proposition 4. The price of anarchy with n symmetric bidders is tightly bounded by 4n+4 3n + 2 .

6 Conclusions

In this paper, we defined and analyzed a novel model for participation in a crowdsourcing contest. Our paper highlights the vital role of the tie-breaking rule in motivating different equilibria. Our analysis highlights two specific tie-breaking rules: (1) the natural rule of breaking ties in favor of stronger players that guarantees the organizer a 1/3 of its utility under any other rule (2) the more surprising rule of breaking ties in favor of weak players that guarantees that the organizer pays the minimal reward for any equilibrium that this tie-breaking rule can support.

Our focus in this work was on deterministic tie-breaking rules. As part of future work, it will be interesting to contrast our results with random tie-breaking rules. Analyzing such rules is much more challenging as it is no longer the case that the equilibrium is unique. Thus, we need to make some assumptions on the organizer's expectations about which equilibrium will be played.