Competition Among Contests: a Safety Level Analysis

1 Introduction

A contest is an abstract game-theoretic notion that captures many realistic situations where multiple players compete to win prizes. In addition to the many classic applications in economics and political sciences, new applications emerge following the success of the Internet economy. For example, in Amazon's Mechanical Turk (www.mturk.com), each outsourced task is in fact a contest; the website 99designs (www.99designs.ca) has the option to "Open your brief to our entire design community. Designers submit their ideas and you pick your favorite design." and so on.

A large body of literature on contest design aims to understand what contest rules will best serve the interest of the contest designer. Most of this literature focuses on the case of a single contest, where the contestants can choose whether to participate in the contest (and how much effort to invest) but do not need to choose between several possible contests. In the context of the above crowdsourcing examples, this is clearly a limiting assumption. On 99designs, for example, each designer needs to decide how to split her effort among the many potential contests she is being offered. [Segev, 2019] argues that it is a "theoretical challenge" to describe such an economy of competing contests.

In this paper we study a model of two competing contests. There are n contestants, each has a bounded total effort to split among the two contests. Each contest designer has a fixed total divisible prize to offer and designs a contest in order to maximize the sum of efforts invested in it. This goal of receiving the maximal possible sum of efforts is seen in reality many times. For example, Amazon's mechanical turk is used to hand out research questionnaires or run research experiments (e.g. in Psychology, Behavioral Economics, etc). Others use it to tag/label pictures. And so on. In these cases, the contest designer cares about the total effort (of all the contestants) in order to receive as many questionnaires, labeled images, etc. Many additional such examples exist.

We assume a general class of contest success functions (CSFs) and prize structures that determines how the prize is awarded to the contestants as an arbitrary function of the efforts they put in the contest. To tractably focus on a general competition structure on the side of the contest designers, we assume homogeneous contestants that have the same quasilinear utility function, which is in the spirit of [Siegel, 2009]. The game that we study has two stages. First, contest designers simultaneously choose their CSFs and prize structures (these two are jointly termed here a "contest policy"). Second, contestants simultaneously decide how much effort to invest in each contest, respecting the overall bound on their sum of efforts.

We study the "safety level" solution concept [Tennenholtz, 2002],[Feige et al., 2013]. A contest C1 of contest designer 1 obtains a safety level x if, for any contest C2 of contest designer 2, and any pure or mixed Nash equilibrium (NE) of the second stage of the game, the total effort invested in the first contest is at least x. This solution concept has robustness advantages similar to dominant strategies and the max-min concept, since the contest designer does not need to assume that her opponent chooses a specific equilibrium play, in fact it does not need to know anything about the opponent, not even that the opponent is rational. The safety level guarantee holds for any contest the opponent chooses. In addition, [Feige et al., 2013] shows that if an action of some player in an abstract game has a safety level of x then the utility of this player in any subgame-perfect equilibrium of this game is at least x. In our terminology, this means that if some contest policy has a safety level of x then the sum of efforts invested in this contest in any subgame-perfect equilibrium is at least x. Thus, a safety level analysis also provides important insights regarding the properties of equilibrium outcomes.

We analyze the safety level provided by the following "exclusive proportional" contest policy (EPP): the contest C divides the prize equally among contestants that invest their total effort in C. Normalizing the sum of efforts of all contestants to 1, our analysis studies the safety level of the proportional exclusive contest policy as a function of the "relative prize power" of the contest, which is the ratio between the prize of the first contest designer and the sum of prizes of the two contests. This is a simple contest policy that could be easily implemented in many case. In our previous example of research questionnaires on Amazon's turk, such a requirement translates to rewarding only fully completed questionnaires. We conduct an extensive analysis of the safety level of EPP, showing that it results in near optimal utility to the contest designer who chooses it.

1.1 RelatedWork

A closely related paper is [Feige et al., 2013]. It studies a competition among auctions that sell several identical items. Both our safety level analysis as well as the definition of EPP are inspired by that paper. However, since [Feige et al., 2013] study a market model, the utility function that they study is inappropriate to a contest setting. In particular, it fully ignores the cost of effort and the attitude of the player towards risk. [Siegel, 2009] gives a general formulation of a utility function of contestants that we incorporate in our model.

Multiple Competing Contests. [DiPalantino and Vojnovic, 2009] study a model with identical competing contests (winner takes it all) that differ only in the prize size. [Azmat and M¨oller, 2009] allow a more general prize structure in a similar model. Both papers focus on analyzing the effect of the prize size/structure on the participation decisions of the players. [Azmat andM¨oller, 2018] incorporated two different types of contests (high and low) while using a similar prize structure. [Morgan et al., 2017] analyzed the effect of showup, fees, number of prizes and discriminativeness on participation in contests. In the current paper we allow a much larger class of contest types. Two papers that study an inherently different model of competing contests are [M¨oller, 2012] and [Moldovanu and Sela, 2006]. The first one studies how to preserve competition over time. In such a case, even the loser in a contest should receive a portion of the prize. In the second paper contest designers do not compete but rather cooperate as they are controlled by the same designer. A contest designer can split the total prize to many sub-contests, to improve expected total as well as highest effort.

Single Contests. One of the many surveys of the literature is [Corch´on, 2007]. Most of the literature including the recent one focuses on various aspects in the design of a single contest. For example, [Levy and Sarne, 2018] compare "simple" versus "complicated" contests, showing empirically that there is no advantage for the latter type. [Gao et al., 2012] studies contests where the contestants are partitioned to groups, and showed that small groups are better than large ones. [Levy et al., 2017] study how to design a contest which maximizes the quality of the best contributors. A similar approach has been used by [Xu and Larson, 2014] that describe how to self-exclude contestants with low-expertise.

Blotto Games. In our terminology, a Blotto game is a setting of competing contests where all contest policies are identical and fixed. The contests in the Blotto game setting are not strategic entities and the analysis in this literature focuses on the Nash equilibria in the contestants game. Recent literature on Blotto games focuses on the computational aspect of finding a Nash equilibrium [Behnezhad et al., 2017], [Ahmadinejad et al., 2019], [Vu et al., 2018b] and [Łatek et al., 2009]. [Vu et al., 2018a] suggest a theoretical bound on the approximation error as a function of the game's parameters. A variation of this game that considers players preferences has been solved by [Palmieri and Lallouet, 2017]. [Kohli et al., 2011] analyzed empirically the results of a Blotto game played over a social network.

2 Model and Preliminaries

We study the following complete information two stage game, G. There are n contestants denoted with index i and two contests denoted with index j. Contest j = 1, 2 can offer a total fully divisible prize of at most Qj (where Qj is fixed). For simplicity we normalize Q1 +Q2 = 1 and denote Q1 = t and Q2 = 1-t where t ∈ [0, 1]. All contestants have the same maximal effort to invest, B.

In the first stage of the game, contest designers simultaneously declare their contest policy which determines the amount of prize that contestant i receives from contest j as a function of the effort that contest designer j receives from all contestants. Formally, a contest policy j = 1, 2 is a function fj : [0,B]n -→ [0,Qj]n , such that ∑ni=1 fi,j(¯bj ) ≤ Qj where ¯bj ∈ [0,B]n is the vector of efforts invested in contest j and fi,j(¯bj ) denotes the i'th coordinate of fj(¯bj ). We emphasize that we allow the contest designers to choose any contest policy from this general class, which captures various prize structures as an arbitrary function of the efforts they put in the contest.

Given the two contest policy functions f1, f2 declared by the two contest designers, in the second stage of the game we have a game among the contestants which we denote as G(f1, f2): contestants simultaneously choose their effort invested. The effort is denoted by bi,j where contestant i invests effort bi,j ∈ [0,B] in contest j and for any i, ∑j bi,j ≤ B. We denote bi = (bi,1, bi,2) ,¯bj = (b1,j, ..., bn,j) ,¯b = (b1, ..., bn) , ¯b-i = (b1, ..., bi-1, bi+1, ..., bn).

The resulting utility of contest designer j is uj(¯bj ) = ∑i bi,j. The resulting utility of a contestant, which depends on the amount of prize obtained and the effort invested, is:

where g1(·) represents the utility gained from prize and g2(·) represents the utility gained from leisure. Throughout, we assume the standard quasi-linear utility function: g2(x) = x and g1(x) = αxβ , where 0 ≤ β ≤ 1 represents the curvature of the function thus the risk aversion of the contestant, and

α ≥ 1 captures a more general substitution effect allowing for one unit of the prize to be worth more than one unit of effort (as α increases the prize is valued more relative to the cost of effort and a larger β implies less risk-aversion).

When n is fixed we can normalize B to be any constant to our choice. However, in part of our analysis we will study the asymptotic properties of the game when n goes to infinity. In this case if B is a constant, the total amount of the effort grows to infinity as n goes to infinity which does not make sense as the amount of the prize is still a constant. We therefore choose to set B = 1n in order to keep the overall amount of effort in the game to be a constant normalized to 1.

2.1 Safety Level and the Exclusive Proportional Policy

As discussed in the introduction, our solution concept is that of a safety level:

Definition 1. The safety level (SL) of a contest policy function fj is defined as follows:

where Fj is the set of all contest policy functions of contest designer j, and the set of Nash Equilibria (NE) effort's of contestants that we consider for the game G(fj , f-j ) includes all pure as well as mixed NE of the game.

Our purpose is to identify a contest policy f ∗ with SL(f1 = f ∗ ) ≈ t. This will imply that, by playing a best response, contest designer 2 can achieve a utility of not much more than 1 - t (since the total sum of efforts of all contestants is 1). On the other hand, in a symmetric way, contest designer 2 can achieve a utility of not much less than 1 - t by choosing f2 = f ∗ . Thus, although f ∗ may not be an exact equilibrium, it provides the contest designer who chooses to use it a utility which is close to the best possible utility in any equilibrium outcome. Moreover, this is achieved without knowing the contest policy of the opponent and without assuming that an equilibrium play is actually materialized. Thus, a safety level analysis does not restrict attention to f ∗ , but rather show that a contest designer can choose f ∗ without losing much utility even if the opponent is able to choose an arbitrary contest policy which belongs to a very general and large class of contest policies as we have defined above. In addition it will turn out that this f ∗ is a very simple contest policy which can be easily implemented.

Specifically, inspired by [Feige et al., 2013] we define the following "Exclusive Proportional Policy" (EPP) function:

In words, the exclusive proportional policy function allocates the prize of contest designer 1 equally among all contestants that gave all their effort to contest designer 1 (these are the exclusive contestants), and does not allocate anything else to non-exclusive contestants.

Clearly, if contest 1 uses the f EPP , any contestant will choose to invest an effort which is either 0 or B in contest 1. More formally, any Nash equilibrium outcome of this game is of the following form: With some probability Pi we have bi = (B, 0) and with probability 1-Pi we have bi = (0, bi,2) where bi,2 ∈ [0, B] could be some random variable.

Throughout, we fix f1 = f EPP , any arbitrary f2, and any arbitrary NE (that can be non-pure) in the contestants game G(f1 = f EPP , f2). We denote by x = ∑i bi,1 the random variable that is the effort of contest designer 1 given the realization of effort bi,1 of all contestants to contest designer 1 according to the NE strategies. The expected sum of effort invested in the first contest is E[x]. We remark that a pure or non-pure NE in the game G(f1, f2) need not necessarily exist if we assume a continuous choice of efforts in the range [0,B]. However if we discretize the range (as finely as we wish) Nash's theoremwill imply existence.

Example 1. Consider the following simple example, assuming g1(x) = 1.5·x, g2(x) = x (a linear utility function). The contest policy functions of the contest designers are f1(·) = f2(·) = f EPP , the relative prize power of contest designer 1 is Q1 = t = 0.25 and the number of contestants is n = 4. One can verify that ¯b = ((B, 0), (0,B), (0,B), (0,B)) is a pure NE. Another, non-pure, NE is that all players invest effort bi = (B, 0) with probability Pi = 0.25 and effort bi = (0, B) with probability 1 - Pi = 0.75. In both of these NE, E[x] = 0.25. In fact, one can verify that in this example, any pure or non-pure NE of this game has E[x] = 0.25.

The main point that we will show in this paper is that when the number of contestants n is large, the safety level that EPP provides is close to t which is the best possible. The following example shows that the assumption of many contestants is important since, with a small number of contestants, the safety level of EPP could be even zero.

Example 2. Consider the case where Q1 = t = 0.2, n = 2, and f1(·) = f2(·) = f EPP , and β = 1. When α = 1, in all NE one of the contestants will invest full effort in contest 2 while the other contestant will not participate in any contest. When α = 1.5, in the unique NE both contestants will invest full effort in contest 2. With these parameters, the first contest will receive a non-zero effort in some Nash equilibria only when n ≥ 4.

3 Safety Levels in Nash Equilibria

Our first step in the safety level analysis is to develop an inequality that must be satisfied in any NE of the game G(f EPP , f2). Using this inequality will then provide a lower bound on E[x]. 1

Assumption 1. The analysis in this section holds for any utility function in the general form of Eq. 1 where the gi(·) functions (for i = 1, 2) satisfy:

1. gi(·) is monotone non-decreasing and concave.
2. gi(0) = 0 and gi( 1 z ) is convex in z ∈ (0, 1].
3. The inverse function g-1 1 (z) is well-defined for any

1 This is not the best lower bound but for quasi-linear utility functions it turns out to be asymptotically optimal.

Quasi-linear utility functions satisfy the first two properties for any α ≥ 1 and any 0 ≤ β ≤ 1 and the third property when β = 1. When β < 1 the third property is satisfied iff g1 ( Q1 1+n ) - g2(B) ≥ 0 which holds for all sufficiently large n, in particular when (n+1)/n 1β ≤ Q1.

Theorem1. If Assumption 1 holds, then in any (pure or nonpure) NE of G(f1 = f EPP , f2) where f2 can be any arbitrary contest policy as defined in Section 2, the following equation must hold:

The following lemma is key to the proof of Theorem 1:

Lemma 1. In all NE (either pure or non-pure), for any contestant i s.t. Pi < 1,

Before proving this lemma, we first show how it implies Theorem 1. Recall that E[x] = ∑i E[bi,1] = ∑i (Pi · 1n + (1 - Pi) · 0) = ∑i Pi n . Now,

where the transition from the third line to the forth line follows from Lemma 1. As this is exactly the claim in Theorem 1, we have shown how the lemma implies the theorem.

The rest of this section proves Lemma 1. Since Pi ≥ 0, a necessary condition for a NE is:

(if Pi > 0 then this is an exact equality and if Pi = 0 then the action bi,1 = 0 is not worse than the action bi,1 = 0.)

Since g1(·) is concave, Jensen's inequality allows us to upper bound the right hand side of Eq. 5, as follows. 2

2 Recall Jensen's Inequality: Let g : R -→ R be convex on [a,b]. Let X be a random variable such that P[a ≤ X ≤ b] = 1, Then, g(E[X]) ≤ E[g(X)]. If the g is concave the inequality is reversed.

(Regarding the last transition in the above equation, note that fi,2(¯b) is a random variable, hence we can use Jensen's Inequality.) Combining with Eq. 5 we have therefore obtained:

Lemma 2. For any contestant i′ ,

Now starting on the left hand side of Eq. 5

where the last equality follows since x (which is the effort of contest designer 1) is equal to B = 1n times the number of contestants who submitted their full effort to contest designer 1. The next two inequalities follow from the claims whose numbers are indicated below the inequality signs:

By using this inequality and Equation 6, and applying g-1 1 (·) on both sides,

This concludes the proof of Lemma 1.

4 The Safety-Level of EPP

Applying the quasi-linear utility function into Eq. 2 from the previous section, we obtain:

Using Mathematica c© we numerically solve Eq. 7. The main conclusions are:

1. In the limit as n goes to infinity (for any constant α, β) the safety level converges to the relative prize power t (Fig. 1, 2, 3).
2. As β decreases (more risk aversion) the convergence rate is faster (Fig. 2).
3. As α increases the convergence rate is faster (Fig. 3).
4. For any constant α, β, n, the safety level as a function of the relative prize power t is convex (Fig. 1). I.e., the marginal benefit from a slight increase in the relative prize power is higher for a contest designer who already has a larger relative prize power. This effect is less significant as n and/or α become larger.

To conclude, as the number of contestants n grows, the safety level becomes close to linear in t. Thus, α and β does not significantly impact the safety level when n is large. An additional way to see this is to plug in the quasi-linear utility function in Eq. 7:

Figure 3: The effect of the number of contestants (n, on the x-axis, in log scale) on the safety level (on the y-axis) of contest designer 1, with g1(x) = αxβ , g2(x) = x and β = 0.6, t = 0.5. Each curve represents a different value of α. Note the convergence to the dashed curve (t).

implying that, in the limit as n goes to infinity (and any constant α ≥ 1, β < 1), E[x] ≈ t.

4.1 The case of risk-neutrality (β = 1)

The previous conclusion holds for β < 1 and we complete the picture for the case of β = 1 which corresponds to the important case of risk-neutrality. Applying the linear utility function into equation 2:

Our lower bound on the effort of the first contest designer for the case of a linear utility function is then:

In the sequel we refer to our lower bound on the safety level, i.e., the RHS of this equation, as SLlinear(n, α, t). We next discuss some implications of this lower bound.

A Large Number of contestants. Our main goal is to analyze the effect of α on the safety level, as a function of the relative prize power. However there is also a third parameter which is the number of contestants n which could potentially complicate the picture. We proceed by first showing that the safety level converges relatively quickly to its limit as n grows. We then analyze the effect of α on the safety level, as a function of the relative prize power t, in this limit.

Figure 4 shows the safety level of the first contest designer as a function of the number of contestants, for α = 1.5 and various values of t. It is clear from the figure that the safety level in each case quickly converges to its limit as n grows. For example, comparing the safety level at n = 100 and at n = 1000, the difference is less than 5% for t ≥ 0.3 (for higher values of α the difference is even smaller). This limit can be calculated explicitly from equation 10, obtaining:

Recall that our main motivating question is to understand the influence of the relative prize power of contest designer 1 on the safety level that contest designer 1 can obtain with the EPP strategy. Since SLlinear(n, α, t) becomes very close to SLlinear(n → ∞, α, t) already for moderate values of n, it makes sense to examine this question assuming n = ∞. As expected SLlinear(n → ∞, α, t = 0) = 0 and SLlinear(n → ∞, α, t = 1) = 1 (recall that we assume α ≥ 1). Figure 5 completes the picture for all values 0 < t < 1, by showing the safety level of contest designer 1 as a function of the relative prize power t assuming n → ∞, for various values of α. As can be seen from the figure, this connection is sub-linear and convex, and as α increases this connection becomes closer to a linear connection (see more details on the convexity of this connection below). Analytically, the slope is d dt SLlinear(n → ∞, α, t) = α √1+2α(1-2t)+α2 . As α increases, this slope becomes closer to 1, i.e., limα→∞ d dt SLlinear(n → ∞, α, t) = 1.

Is the bound in Eq. 11 tight? The bound in Eq. 11 is quite far from linear for small α's, even in the limit as n goes to infinity. This is in sharp contrast to the case of β < 1. For example, when α = 1 and t = 0.5, the bound that this equation gives is about 0.292893 which is very far from t = 0.5 which is the bound that we get for any β < 1 and n → ∞. This naturally raises the question of whether our analysis in the linear case is tight, or whether the bound in Eq. 11 is too loose. We show via an example that this bound is tight, and that the gap between β < 1 and β = 1 is real.

To see this, consider the case of a linear utility with α = β = 1. Contest 1 uses EPP and contest 2 equally divides the prize among all contestants that invest in contest 2 an effort of at least some fixed ϵ > 0. The following equation gives a sufficient condition for a pure NE in which x contestants invest full effort in contest 1 (the utility of each one is the middle term in the equation) and the rest invest an effort of ϵ in contest 2 (the utility of each one is the right term in the equation). Both terms are required to be larger than 1n since this is the utility from not investing any effort in any contest. The middle term is the utility of a contestant that invests an effort of B in contest 1. The right-most term is the utility a contestant that invests an effort of ϵ in contest 2. The equality of these two terms means that we are in a NE.

Figure 5: The effect of the relative prize power of contest designer 1 (t, on the x-axis) on the safety level (on the y-axis) of contest designer 1, with g1(x) = αx. Each curve represents a different α. This plot assumes a large number of contestants as shown in Eq. 11.

Taking for example t = 0.5 and rearranging, we have

When ϵ → 0, x → 0.293 · n. (This also implies that if we choose a very small ϵ, the utility from participating in one the contests will be larger than 1n .) Thus, in this example, even for very large n's, the utility of contest 1 that uses EPP will be less than 0.3 while its relative prize power is 0.5. The lower bound that Eq. 11 gives, which is equal to 0.292893 in this case, is very close to the actual utility obtained in the above example.

The convexity of the safety level (for any finite number of contestants n). In fact it turns out that the convexity of the safety level function holds for every n and α:

Proof. The second derivative of equation 10 w.r.t. t is:

The numerator is non-negative. Define z to be the argument in the denominator z(n, α, t) = (n(1 - α) - 1)2 + 4n(1 + α - tα - ntα). z(n, α, t = 1) = (nα - n - 1)2 > 0 and the derivative with respect to t is ∂ ∂t z(n, α, t) = -4nα(1 + n) < 0. Therefore ∀t ≤ 1, z(n, α, t) ≥ z(n, α, t = 1) > 0

Large α values. The coefficient α represents the substitution relation between cost of effort and prize. As α becomes larger a contestant is willing to invest more effort for the same amount of prize. As shown in figure 5, as α grows, the safety level becomes closer to a linear function. Using equation 9 and taking the limit α -→ ∞ we have (1-t) 1-E[x] ≥ nα ( αt 1+nE[x] - 1n ) = nt 1+nE[x] - 1 αn ≈ nt 1+nE[x] . For large values of α we therefore obtain the approximation E[x] ≈ t - 1-t n . Comparing to [Feige et al., 2013], their model can be viewed as assuming α → ∞ since they assume that contestants do not have any utility(positive or negative) for any effort invested. Indeed, under such an assumption, they showed a lower bound on the safety level of E[x] ≥ t - 1n , which is consistent with our result, and which our result generalizes for all values of α.

5 Conclusions and Future Directions

This paper models competition among two contest designers and the resulting n contestants game. We show that the simple and natural exclusive proportional policy obtains a safety level that approaches the relative prize power t of the contest when the number of contestants n or the substitution parameter α are large. This means that a contest designer that uses it obtains utility not much smaller than the utility that can be obtained in any equilibrium outcome.

We have found that the safety level function is convex with respect to the relative prize power. Moreover the safety level of the contest designers converges very fast with respect to the number of contestants when contestants are risk-averse (β < 1). The convexity of the safety level with respect to the relative prize power implies that a contest designer who has a larger relative prize power will gain more from growing. Therefore, for future research we would suggest to model a multi-round game, where in every round contests initially decide on the size of their prizes (which is fixed in our model), and this could possibly be related to the gains of the contests from previous rounds. Another more technical interesting question is to determine whether there is a contest policy that provides a higher safety level in the various cases where exclusive proportional policy is sub-linear, and, more generally, to provide tight characterizations of equilibrium outcomes.

In this paper we assume that effort is observable, in order to force exclusiveness. In a model of identical contestants, we believe this is reasonable as effort can be deduced from the observable quality of the outcome (e.g., a full questionnaire). In future work it could be interesting to study whether contest policies that do not require exclusiveness are able to provide the same safety level guarantees as EPP.

Acknowledgments

This research was supported by the ISF-NSFC joint research program (grant No. 2560/17).