# contests_to_incentivize_a_target_group__bb51c85c.pdf

Contests to Incentivize a Target Group

Edith Elkind , Abheek Ghosh and Paul W. Goldberg Department of Computer Science, University of Oxford {edith.elkind,abheek.ghosh,paul.goldberg}@cs.ox.ac.uk

We study how to incentivize agents in a target subpopulation to produce a higher output by means of rank-order allocation contests, in the context of incomplete information. We describe a symmetric Bayes Nash equilibrium for contests that have two types of rank-based prizes: (1) prizes that are accessible only to the agents in the target group; (2) prizes that are accessible to everyone. We also specialize this equilibrium characterization to two important sub-cases: (i) contests that do not discriminate while awarding the prizes, i.e., only have prizes that are accessible to everyone; (ii) contests that have prize quotas for the groups, and each group can compete only for prizes in their share. For these models, we also study the properties of the contest that maximizes the expected total output by the agents in the target group.

1 Introduction

Contests situations where multiple agents compete for valuable prizes are prevalent in many real-life situations, including sports, R&D races, crowdsourcing, college admissions and job recruitment.1

The dominant paradigm in contest theory is to assume that the principal designs the prize structure so as to incentivize the agents to produce a higher total output. In this model, the designer values the contribution from each agent equally, i.e., the marginal output produced by any agent contributes the same marginal value to the designer s objective. In this paper, we break away from this assumption: instead, we assume that the agents belong to two different groups and the designer may want to prioritize one group the target group over the other, non-target group. Contests that give special importance to agents from a particular group are not uncommon in practice. Conferences give best student paper awards, in addition to best paper awards.

Full version of the paper is available at http://arxiv.org/abs/22 04.14051. 1See the book by Vojnovic [2016] for an introduction to contest theory and relevant resources.

Many competitions and hackathons are organized to elicit engagement from underrepresented groups: for example, recently Microsoft organized a hackathon as an intervention to get women interested in AI.2 Contests are widely used for crowdsourcing, which is also an important source of training data for machine learning algorithms; in this context, eliciting input from disadvantaged groups is particularly important, as it helps the algorithms to learn decision-making rules that reﬂect opinions and preferences of such groups. Our work provides a better understanding of how to encourage contributors from such groups. In this paper, we study an incomplete information (Bayesian) model. We assume that each agent is associated with an ability, which captures the amount of output they can produce per unit effort. In an incomplete information model for contests, it is generally assumed that the abilities of the agents are selected i.i.d. from a given distribution F. In our model, based on the assumption that the agents belong to one of the two groups, the abilities of the agents in the target and the non-target group are sampled from two distinct distributions F and G, respectively. Each agent belongs to the target group with a ﬁxed probability µ.3 The agents know the prize allocation scheme, their own ability, and the prior distributions of other agents abilities. They act strategically to maximize their expected utility, where the utility of an agent is the prize they receive minus the effort they exert, and reach a Bayes Nash equilibrium. The contest designer knows the prior distributions of the agents abilities, and therefore can reason about the equilibrium behavior of the agents. She designs the prize allocation scheme so as to elicit equilibrium behavior that optimizes her own objective. We assume that the contest designer has a budget of 1 to use for the prizes. The contest ranks the agents based on their outputs and awards the prizes based on the ranks. In our general model, we assume that contests have two sequences of prizes, one available to all agents, and the other available to the target group only. A conference sponsoring a best student paper

2https://news.microsoft.com/europe/features/bridging-the-stem -divide-ai-hackathon-helps-young-women-excel-in-computer-sci ence/ 3We assume that µ is known based on historical data on the number of participants from the target group compared to the total number of participants. Similarly, the distributions F and G are also known from historical data.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

award in addition to a best paper award is an example of such a contest. We also study two speciﬁc variants of this model. In the ﬁrst variant, all prizes in the contest are equally accessible to all agents, and there are no group-speciﬁc prizes. One could come across such a design preference in situations where the contest designer does not want to discriminate among the agents, but still wants to incentivize an underrepresented agent group. In this case, the contest does not discriminate while awarding the prizes, but the design of the prize structure (i.e., the value of the ﬁrst prize, second prize, and so on) can incorporate the information about the ability distribution of the agents. This model captures an equal opportunity employer that treats all applicants equally, but has a preference to increase the diversity in the workplace. In the second variant, the contest has group-speciﬁc prizes only, with no prizes available to the entire population; examples include a hackathon for women in CS, or a hiring/scholarship contest with a strict group-speciﬁc quota. We assume that the contest designer wants to maximize the expected output of the agents in the target group only. With minor changes, the techniques can be extended to an objective that maximizes the weighted sum of the group outputs and other similar objectives.

1.1 Our Contribution We initiate a theoretical study of contest design to elicit higher participation by agents from under-represented groups, and propose tractable models for doing so. We analyze the equilibrium behavior of the agents for three cases: general prizes only, where there is a sequence of rank-ordered prizes accessible to all agents, whether in the target or the non-target group; group-speciﬁc prizes only, where there are two different sequences of prizes, each accessible to one of the groups; both general and target group-speciﬁc prizes, where there are prizes accessible to both groups as well as prizes accessible to the target group only. The techniques used to analyze the equilibrium in these contests can be extended to related prize structures. Based on these equilibrium characterizations, we study the properties of the contest that maximizes the total expected output of the agents from the target group. For the setting where all prizes are general, we prove that the optimal contest awards a prize of 1/ℓto the ﬁrst ℓagents and 0 to the remaining agents, where ℓis a function of the relative frequency of target group agents, µ, and the ability distributions of the target group, F, and the non-target group, G. We give a closed-form formula for ℓ. We also study the effect of ﬁrstorder and second-order stochastic dominance of F on G, and vice versa, on the optimal contest. For the setting where all prizes are group-speciﬁc, we show that it is optimal to award the full prize budget to the top-ranked agent, irrespective of the distributions F and G. This result matches similar results on maximizing total output [Moldovanu and Sela, 2001]. We also compare general prizes and group-speciﬁc prizes, and show that either of these choices may be preferred depending upon the distributions F and G, and also upon the frequency of the target group agents in the population, µ, even if F = G. All proofs and a few additional examples are given in the full version of the paper.

1.2 Related Work We discuss literature in contest theory directly relevant to our work; we point the readers to the book by Vojnovic [2016] for a broader survey on contest theory. Moldovanu and Sela [2001] characterize the Bayes Nash equilibrium for contests with rank-order allocation of prizes assuming incomplete information with i.i.d. types; Chawla and Hartline [2013] prove the uniqueness of this equilibrium. Moldovanu and Sela [2001] also show that awarding the entire prize to the top-ranked agent is optimal when the agents have (weakly) concave cost functions, but the optimal mechanism may have multiple prizes for convex cost functions. In contrast, we observe that even for linear cost functions, it may be beneﬁcial to have multiple prizes to maximize the expected output from the target group. The standard assumption in mechanism design and its subarea of contest design is that the agents types are sampled i.i.d. from some distribution. Our paper extends the equilibrium analysis of Moldovanu and Sela [2001] to an asymmetric model where the agents are from two groups with different distributions. Amann and Leininger [1996] study an asymmetric model with two agents with types sampled independently from two different distributions; our analysis uses the idea of the function k introduced by them, see Theorem 1. Characterizing equilibrium in contests with many agents with types sampled independently from different distributions has remained technically challenging; recently Olszewski and Siegel [2016; 2020] made progress by assuming very large numbers of agents and prizes, where an individual agent has inﬁnitesimal effect on the equilibrium. Bodoh-Creed and Hickman [2018] model afﬁrmative action in college admissions using contests. Their model has general non-linear utility and cost functions, but, like Olszewski and Siegel [2016; 2020], they assume that the numbers of agents and prizes are very large. They give ﬁrst-order equilibrium conditions and show that two types of afﬁrmative actions (i) admissions preference schemes, where the outputs of agents from the target group are (artiﬁcially) ampliﬁed before ranking and prize allocation, and (ii) quotas, where there are separate pools of seats for the different groups (similar to our group-speciﬁc prizes only model, Section 3.3) have the same sets of equilibria with identical actions by the agents and identical outcomes. Our model makes a stronger linearity assumption regarding the utility and the cost functions, which allows us to better characterize the equilibrium and study the optimal contest (prize) design problem. There is a long line of literature on the effect of different types of afﬁrmative action on contests. This literature generally assumes that there is only one prize, which either gets allocated to the top-ranked agent or gets allocated proportionally (Tullock [1980] contests and their generalizations), and the contest designer introduces different kinds of interventions in the allocation of this prize. One such intervention is favoritism, where the objective is to maximize the total output by giving head-starts or handicaps to certain agents (see, e.g., [Kirkegaard, 2012; Fu and Wu, 2020; Deng et al., 2021]). A head-start adds a bonus to an agent s output, while a handicap decreases an agent s score by a ﬁxed percentage. See [Chowdhury et al., 2020] for a survey on

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

contests and afﬁrmative action. Our work deviates from the widely studied objective of maximizing total output, by focusing on the output of a target group. Several papers have studied objectives other than the total output, such as maximum individual output [Chawla et al., 2019], cumulative output from the top k agents [Archak and Sundararajan, 2009; Gavious and Minchuk, 2014], total output of agents producing output in a given range [Elkind et al., 2021]. Elkind et al. [2021] target agents based on their output level, and therefore, effectively, based on their abilities; our work targets agents based on their group association, with the assumption that exogenous factors may have caused agents in some groups to have acquired less ability. There are also several papers that perform equilibrium analysis and optimal contest design in the complete information setting (e.g., [Baye et al., 1996; Barut and Kovenock, 1998; Siegel, 2009]).

2 Model and Preliminaries

There are n agents. Any given agent belongs to the target (resp., non-target) group with probability µ (resp., (1 µ)), independently of the other agents. Let v = (v1, v2, . . . , vn) be the ability proﬁle of the agents, where vi values are independent and identically distributed (i.i.d.) random variables from continuous and differentiable distributions F or G with support [0, 1], depending upon whether agent i belongs to the target or the non-target group, respectively. Let f and g be the probability density functions (PDFs) of F and G. The n agents simultaneously produce the output proﬁle b = (bi)i [n], so that the cost of agent i is bi/vi. The contest awards two sequences of prizes w1 w2 . . . wn and ω1 ω2 . . . ωn, where the prize wj is given to the j-th ranked agent overall (we call these prizes general prizes), and the prize ωj is given to the j-th ranked agent among the agents in the target group (we call these group-speciﬁc prizes), with ties broken uniformly.4 We assume that P j wj + P j ωj 1, i.e., the contest designer has a unit budget. Given a vector of outputs b, let the allocation of general prizes be given by x(b) = (xi,j(b))i,j [n], where xi,j = 1 if agent i is awarded the j-th prize and xi,j = 0 otherwise. Similarly, let y(b, t) = (yi,j(b, t))i,j [n] be the allocation of target group prizes, where t = (ti)i [n] is the group label vector; ti {T, N}, ti = T if the agent is in the target group, ti = N if not. We shall suppress the notation for t and write y(b) instead of y(b, t). If agent i is in the target group, her utility is given by

u T (vi, b, t) = X

j [n] wjxi,j(b) + X

j [n] ωjyi,j(b) bi/vi

4In our model, it does not matter how we break ties, so w.l.o.g., we can assume uniform tie breaking. In more detail, for a tie to happen, two players must produce exactly identical output. In our setting, this happens with zero probability, as there are no point masses in the probability distributions F and G, and the distributions of the output generated by the agents (that we derive as a result of our equilibrium analysis) also do not have any point masses.

j [n] wjxi,j(b) + X

j [n] ωjyi,j(b)

where the equivalence is true because scaling the utility function by a constant does not change the strategy of an agent. Similarly, the utility of an agent i in the non-target group is given by

u N(vi, b, t) = vi X

j [n] wjxi,j(b) bi. (2)

2.1 Mathematical Preliminaries Let p H j (v) denote the probability that a value v [0, 1] is the j-th highest among n i.i.d. samples from a distribution H, given by the expression

p H j (v) = n 1 j 1

H(v)n j(1 H(v))j 1.

A key role in the Bayes Nash equilibrium of rank-order allocation contests is played by the order statistics. Let f H n,j be the PDF of the j-th highest order statistic out of n i.i.d. samples from H (with PDF h), given by the expression

f H n,j(v) = n! (j 1)!(n j)!H(v)n j(1 H(v))j 1h(v).

(3) We shall also frequently use the following two identities for order statistics:

H(v)f H n 1,j(v) = n j

n f H n,j(v);

(1 H(v))f H n 1,j(v) = j

nf H n,j+1(v).

Deﬁnition 1 ((Weak) First-Order Stochastic (FOS) Dominance). A distribution F FOS dominates another distribution G, if for every x, F gives at least as high a probability of receiving at least x as does G: 1 F(x) 1 G(x) F(x) G(x). Deﬁnition 2 ((Weak) Second-Order Stochastic (SOS) Dominance). A distribution F SOS dominates another distribution G, if for every x: R x [F(t) G(t)]dt 0.

FOS dominance implies SOS dominance. Another sufﬁcient condition for SOS dominance: F SOS dominates G if G is a mean-preserving spread of F. Let us denote the inner product of two functions ψ, φ : [0, 1] R+ by

0 ψ(x)φ(x)dx.

When appropriately normalized, ψ, φ measures the similarity between the functions ψ and φ.

2.2 Equilibrium and Objective Function We shall study the Bayes Nash equilibrium of the agents, where the agents in the target group use a symmetric strategy α(v) (symmetric across the agents in the group), where α(v)

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

is the output of an agent with ability v; similarly, the agents in the non-target group use a symmetric strategy β(v). The objective of the contest designer is to maximize the expected total output generated by the agents in the target group: X

i [n] Evi F [α(vi)] P[ti = T] = n µ Evi F [α(vi)],

which is equivalent to maximizing Ev F [α(v)] because n and µ are (ﬁxed) parameters given to the model.

3 Equilibrium Analysis In this section, we characterize a symmetric Bayes Nash equilibrium (symmetric across the agents in a given group). We ﬁrst solve for the equilibrium of the contest with both general and target group-speciﬁc prizes, then we specialize it for the two special cases: (1) only general prizes; (2) only group-speciﬁc prizes.

3.1 Both Target Group and General Prizes In the next theorem, we focus on contests that have a sequence of general prizes (wj)j [n] and a sequence of target group-speciﬁc prizes (ωj)j [n]. We will characterize a Bayes Nash equilibrium where a player in the target group plays an action α(v) as a function of her ability v F and a player in the non-target group plays an action β(v) as a function of her ability v G. Note that all the players in the target group use the same strategy α and the players in the non-target group use the same strategy β. Theorem 1. A contest with general prizes (wj)j [n] and target group-speciﬁc prizes (ωj)j [n] has a Bayes Nash equilibrium where an agent with ability v [0, 1] uses strategy α(v) if she is in the target group and strategy β(v) if she is in the non-target group, where α(v) and β(v) are deﬁned as:

0 (µf(k(y))k (y) + (1 µ)g(y))A(y)ydy,

( β(k 1(v)), 0 v k(1) β(1) + R v k(1) µf(y)C(y)ydy, k(1) v 1 ,

where: k is a function deﬁned over [0, 1] and is the solution to the following ordinary differential equation, with boundary condition k(0) = 0,

k (v) = (1 µ)g(v)(v k(v))A(v) µf(k(v))(k(v)A(v) + k(v)B(v) v A(v)).

A(v) = P j [n] wjψj(µF(k(v)) + (1 µ)G(v)).

B(v) = P j [n] ωjψj(µF(k(v)) + (1 µ)).

C(v) = P j [n](wj + ωj)ψj(µF(v) + (1 µ)).

ψj(x) = n 1 j 1 xn j 1(1 x)j 2((n j) (n 1)x).

Notice that Theorem 1 does not provide a closed-form solution for α(v) and β(v), it rather provides a characterization using the function k(v) that relates α(v) and β(v). Standard equilibrium analysis techniques using ﬁrst-order equilibrium

conditions will give a system of differential equations in α(v) and β(v). Using the function k(v) = α 1(β(v)), we convert this system of differential equations in α(v) and β(v) to a comparatively simpler single ﬁrst-order explicit ordinary differential equation in only one dependent variable k(v). After solving the ordinary differential equation for k(v), we can use k(v) to compute α(v) and β(v) as described in the theorem statement. This technique of using the function k(v) is motivated by the work of Amann and Leininger [1996], where they use to it analyze two-agent asymmetric contests. If the distributions F or G, or the prizes (wj)j [n] or (ωj)j [n], are non-trivial, then it may be intractable to calculate the analytical solutions for α(v) and β(v) derived in Theorem 1, but numerical solutions may be computed. An example in the full version of the paper illustrates the use of Theorem 1 to compute α(v) and β(v) for a particular instantiation of the problem. Theorem 1 characterizes an equilibrium assuming that all players in a given group use the same strategy (α(v) or β(v)), and that α(v) and β(v) are strictly increasing and (almost everywhere) differentiable functions of v. We believe that these assumptions are reasonable and the equilibrium is the most natural one for this model. It remains open to prove the uniqueness of this equilibrium or to characterize the set of all possible equilibria.

3.2 General Prizes Only A contest designer may want to only award prizes that are equally accessible to all the agents. This model is particularly appealing for several real-life applications, because, although the design of the prize structure may incorporate distributional information about the ability of the agents in the two groups, the contest itself is completely unbiased. In our model, this design choice corresponds to setting ωj = 0 for all j [n]. For this case, the expected utility for a target group agent and a non-target group agent for a given pair of ability v and output b is the same. We can specialize the equilibrium characterization in Theorem 1 to this case as follows: Theorem 2. A contest with only general prizes (wj)j [n] has a Bayes Nash equilibrium where an agent with ability v [0, 1] in the target or non-target group uses the strategy α(v), where α(v) is deﬁned as:

j [n 1] (wj wj+1) Z v

0 yf µF +(1 µ)G n 1,j (y)dy.

This equilibrium is unique, as follows from a result by Chawla and Hartline [2013]. They prove that if a contest is anonymous (does not discriminate among the agents) and the abilities of the agents are sampled i.i.d. from a distribution, then the equilibrium is unique. With only general prizes, the contest is (i) anonymous because the general prizes are awarded without any bias towards players from any group, and (ii) effectively, the abilities of the agents are sampled i.i.d. from the distribution µF(v) + (1 µ)G(v).

3.3 Group-Speciﬁc Prizes Only In this case, there are no general prizes accessible to agents from both groups: all the prizes are allocated based on strict

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

quotas for the groups. This model is similar to the model of seat quotas for college admissions studied by Bodoh-Creed and Hickman [2018]. Technically, in this case we assume that wj = 0 for all j [n]. Here we focus on the target group; a similar result also holds for the non-target group, if there are any prizes reserved for them. Theorem 3. A contest with target only group-speciﬁc prizes, (ωj)j [n], has a Bayes Nash equilibrium where an agent with ability v [0, 1] in the target group uses strategy α(v), where α(v) is deﬁned as:

j [n 1] (ωj ωj+1) Z v

0 yf µF +(1 µ) n 1,j (y)dy.

Chawla and Hartline [2013] s uniqueness result also applies to this equilibrium characterization, as it did for only general prizes (Section 3.2). We can transform an instance of our problem (without changing its set of equilibria) to satisfy these requirements: the abilities of the players are picked i.i.d. from the distribution µF(v) + (1 µ) and the contest awards prizes without discriminating among the players.

4 Designing Prizes to Incentivize the Target Group Based on the equilibrium characterizations in the previous section, in this section we investigate the properties of the optimal contest that maximizes the total output of the target group. We characterize the optimal contests for only general prizes and for only group-speciﬁc prizes. Characterization of the optimal contest for both general and group-speciﬁc prizes is a non-trivial open problem because of the absence of a closed-form equilibrium characterization for the case (the characterization in Theorem 1 involves an ordinary differential equation). In the full version of the paper, we compare the choice between only general and only group-speciﬁc prizes; we observe that either of them may be a better choice depending upon the situation. Even if the distributions of the target and the non-target group are the same, the relative frequency of target group agents, measured by µ, determines which prize allocation scheme is better. If µ is sufﬁciently high, then it is better to have only group-speciﬁc prizes, while the converse is true if µ is very low.

4.1 General Prizes Only The strategy used by the agents in the target group is α(v), as derived in Theorem 2. It can be rewritten as

j [n 1] (wj wj+1) Z v

0 yf µF +(1 µ)G n 1,j (y)dy

j [n 1] γj 1 j

0 yf µF +(1 µ)G n 1,j (y)dy, (4)

where γj = j(wj wj+1). Instead of optimizing over (wj)j [n], we can optimize over (γj)j [n 1] with constraints γj 0 and P j γj = 1, to ﬁnd the optimal contest that maximizes the target group s output.

Theorem 4. The contest with only general prizes that maximizes the expected total output of the agents in the target group awards a prize of 1/k to the k top-ranked agents and a prize of 0 to the remaining n k agents, where k is deﬁned as

k arg max j [n 1] ψ, f µF +(1 µ)G n,j+1

for ψ(x) = x(1 F (x)) 1 µF (x) (1 µ)G(x).

Let H(x) denote µF(x) + (1 µ)G(x). The function ψ(x) = x 1 F (x)

1 H(x) in Theorem 4 is independent of the prize structure: it depends only on µ, F, and G, which are parameters given to the contest designer. The function f H n,j+1(x) is the PDF of the (j + 1)-th highest order statistic of the distribution H. The optimal j = k maximizes the inner product between ψ and f H n,j+1, and therefore, the similarity between them. In other words, the optimal j = k selects the order statistic that is as similar to ψ as possible. Note that when we are maximizing the total output, then instead of an inner product of the order statistic with ψ(x) in Theorem 4, we take an inner product with just x. As x is monotonically increasing, the order statistic that is most similar to x and that maximizes the inner product with x is the one with j = 1, as shown by Moldovanu and Sela [2001]. This provides an argument in favor of allocating the entire prize budget to the ﬁrst prize. In contrast, when we focus on the target group only, it may be optimal to distribute the prize among several top-ranked agents. This also means that we may lose a portion of the total output, and this loss can be Ω(n) as shown in Example 1. Also, by the single-crossing property, see Vojnovic [Vojnovi c, 2016] Chapter 3, if we ﬂatten the prize structure then we increase the output of the agents with low ability and decrease the output of the agents with high ability. We have partially omitted calculations from the examples in this section. These examples are presented in the full version of the paper with more details. Example 1. Let F(x) = 1 (1 x)n 1, G(x) = ((n 1)x F(x))/(n 2), and µ = 1/(n 1). We get H(x) = µF(x) + (1 µ)G(x) = x, which is the uniform distribution over [0, 1]. Note that ψ(x) = x(1 F (x))

1 H(x) = x(1 x)n 2. It can be checked that the order-statistic that maximizes the inner-product with ψ(x) is f H n,n 1(x) = n(n 1)x(1 x)n 1. So, the optimal value is k = n 2. The total output generated for k = n 2 is 2 n(n+1). On the other hand, we know that the expected total output is maximized by j = 1 and is equal to (n 1) n(n+1). The ratio between the two quantities is (n 1)/2 = Ω(n). In the above example, the distribution of the target group F was ﬁrst-order stochastic (FOS) dominated by the distribution of the general population H. For this case, we observed that awarding prizes to more than one agent increases the expected output of the target group. F being FOS dominated by H means that the agents in the target group have lower ability than the general population. As ﬂattening the prize structure increases the output of the lower ability agents and decreases

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

the output of the higher ability agents, it makes sense that having a ﬂatter prize structure incentivizes them. The above result raises the question: What if the target group is equally able or stronger than the general population, i.e., if the distribution of the ability of an agent in the target group, F, FOS dominates the distribution of the ability of an agent in the non-target group, G; is it then optimal to award the prize to the top-ranked agent only? When F = G = H, we know that it is optimal to give prize to the top-ranked agent only, so when F FOS dominates H, one might expect this to be the case as well. However, the example below illustrates that this is not true.5

Example 2. Let µ = 1/8, F(x) = 1 S(x), G(x) = (x µF(x))/(1 µ), where S(x) is given by:

1, if x < 3/4 16(1 x)2, if 3/4 x < 15/16 1 x, if x 15/16 .

It can be veriﬁed that F(x) and G(x) are continuous cumulative distribution functions. The distribution of the general population is H(x) = µF(x) + (1 µ)G(x) = x. Also, F(x) H(x) for every x (and strict for some values of x), and therefore, F FOS dominates H. The optimal number of prizes k need not be 1; for example, for n = 50, k = 11. Now we consider the case where F and H have the same mean but different variance, which implies second-order stochastic (SOS) dominance. The distribution with lower variance SOS dominates the one with higher variance, assuming both distributions have the same mean. The results are similar to FOS dominance: it may be optimal to have multiple prizes irrespective of whether F or H has a higher variance, as shown in the following examples. Note that FOS dominance implies SOS dominance, but not vice-versa. Example 3. Let µ = 2/3, F(x) = 3x2 2x3, and G(x) = 3x 6x2 + 4x3. Observe that H(x) = µF(x) + (1 µ)G(x) = x, and the variance of H is 1/12 while the variance of F is 1/20, and both have mean 1/2. Solving for k , we get k = 5n

2. For example, for n = 50, k = 19. Example 4. Let µ = 1/4, F(x) = 1 S(x), and G(x) = (x µF(x))/(1 µ), where S(x) is given by:

1 48x/31, if x < 31/96 1/2, if 31/96 x < 3/4 8(1 x)2, if 3/4 x < 7/8 1 x, if x 7/8

It can be checked that F(x) and G(x) are valid and for the distribution of the general population we have H(x) =

5In the preliminaries we assumed F to be continuous, strictly increasing, and differentiable in [0, 1]. In the following and the subsequent examples, the distribution F is continuous and weakly increasing but may not be strictly increasing and differentiable everywhere. If F is not strictly increasing, we can add a slight gradient to resolve the issue; on the other hand, we can smooth out the ﬁnite number of points where it is not differentiable. These changes will have a minimal effect on the objective value and our analysis holds. For ease of presentation, we shall not discuss these issues.

µF(x) + (1 µ)G(x) = x. It can also be checked that the mean of all the distributions is 1/2, and the variance of H is 1/12 0.083 while the variance of F is 6703/55296 0.121 > 1/12. The optimal number of prizes k need not be 1; for example, for n = 50, k = 11.

4.2 Group-Speciﬁc Prizes Only In this section, we study the optimal prize structure when the prizes are accessible to the target group only. This models situations when there are separate contests for the target and the non-target group (there can be a separate contest for only non-target group agents, this will not have any affect on the strategy of the target group agents). We see that the optimal contest allocates the entire prize budget to the ﬁrst prize, i.e., gives a prize of 1 to the top-ranked agent in the group (Theorem 5). The proof of Theorem 5 extends the techniques used to provide a similar result for total output [Moldovanu and Sela, 2001].

Theorem 5. The contest with only group-speciﬁc prizes that maximizes the output of the target group awards a prize of 1 to the top-ranked agent and 0 to others.

5 Conclusion

Our paper studies rank-order allocation of prizes that aim to maximize the output of a target group. We provide equilibrium characterization for these contests and study the properties of the optimal contest. For unbiased contests (i.e., with general prizes only), although it is preferable to award the prize to the top-performing player if the target group players are similar to the overall population, if the target group players are very different, then we may want to ﬂatten out the prize structure. This does not only mean that we ﬂatten out the prizes if the target group players are weaker than others; we also demonstrate that if the target group players are stronger but quite different from others, it may still be a good idea to ﬂatten out the prizes. However, for contests with ﬁxed prize quotas (i.e., with group-speciﬁc prizes only), it may not be useful to ﬂatten the prizes. Comparing unbiased contests and ﬁxed quota contests, the size of the target group in proportion to the size of the population plays an important role. An important open problem is to understand the properties of the optimal contest that has both group-speciﬁc and general prizes. We characterize the equilibrium for this problem and analyze the optimal contest for speciﬁc sub-cases, but the general problem is open. One way to make this tractable may be to assume large numbers of agents and prizes; such assumptions allow for a stronger and more tractable equilibrium characterization by making the inﬂuence of an individual agent inﬁnitesimal [Olszewski and Siegel, 2016]. Our work focused on contests with a rank-order allocation of prizes with incomplete information and linear cost functions. Instead of rank-order allocation of prizes, we can study a proportional allocation of prizes or its generalizations (see, e.g., [Tullock, 1980]); one motivation for proportional allocation is the randomness and unpredictability of outcome in the real world. Similarly, we may relax the assumption of linear cost functions, or we can study complete information models instead of incomplete information.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Ethical Statement

There may be both short-term and long-term implications for designing contests speciﬁcally to incentivize a target group. For example, even if the contest itself is unbiased (Section 4.1), optimizing the expected total output of the players in the target group may mean that we decrease the expected total output of the entire population, and in particular decrease the expected total output of the non-target group. Moreover, such effects can be stronger if the target group forms a smaller fraction of the participants. Our analysis and examples try to capture such effects. For any given contest, this means that we are optimizing for the target group with a cost to society. But for a longer time frame, the answer is less obvious, and we believe that it is out of the scope of our paper. This question concerns whether practices such as afﬁrmative action have an overall positive or negative impact on the society in the long run. Our paper addresses the following question: if we do want to use afﬁrmative action in contests to incentivize the target group (with particular design choices, such as the prize allocation scheme being unbiased), how do we do it most effectively, and how does it affect the output of all the players in the given contest.

Acknowledgements

We would like to thank the reviewers for their valuable feedback. The second author is supported by Clarendon Fund and SKP Scholarship.

[Amann and Leininger, 1996] Erwin Amann and Wolfgang Leininger. Asymmetric all-pay auctions with incomplete information: the two-player case. Games and Economic Behavior, 14(1):1 18, 1996.

[Archak and Sundararajan, 2009] Nikolay Archak and Arun Sundararajan. Optimal design of crowdsourcing contests. In Proceedings of the 13th International Conference on Information Systems, 2009.

[Barut and Kovenock, 1998] Yasar Barut and Dan Kovenock. The symmetric multiple prize all-pay auction with complete information. European Journal of Political Economy, 14(4):627 644, 1998.

[Baye et al., 1996] Michael R Baye, Dan Kovenock, and Casper G De Vries. The all-pay auction with complete information. Economic Theory, 8(2):291 305, 1996.

[Bodoh-Creed and Hickman, 2018] Aaron L Bodoh-Creed and Brent R Hickman. College assignment as a large contest. Journal of Economic Theory, 175:88 126, 2018.

[Chawla and Hartline, 2013] Shuchi Chawla and Jason D Hartline. Auctions with unique equilibria. In Proceedings of the 14th ACM Conference on Electronic Commerce, pages 181 196, 2013.

[Chawla et al., 2019] Shuchi Chawla, Jason D Hartline, and Balasubramanian Sivan. Optimal crowdsourcing contests. Games and Economic Behavior, 113:80 96, 2019.

[Chowdhury et al., 2020] Subhasish M Chowdhury, Patricia Esteve-Gonz alez, and Anwesha Mukherjee. Heterogeneity, leveling the playing ﬁeld, and afﬁrmative action in contests. SSRN:3655727, 2020. [Deng et al., 2021] Shanglyu Deng, Qiang Fu, and Zenan Wu. Optimally biased Tullock contests. Journal of Mathematical Economics, 92:10 21, 2021. [Elkind et al., 2021] Edith Elkind, Abheek Ghosh, and Paul Goldberg. Contest design with threshold objectives. In Proceedings of the 17th Conference on Web and Internet Economics, page 554, 2021. Ar Xiv preprint 2109.03179. [Fu and Wu, 2020] Qiang Fu and Zenan Wu. On the optimal design of biased contests. Theoretical Economics, 15(4):1435 1470, 2020. [Gavious and Minchuk, 2014] Arieh Gavious and Yizhaq Minchuk. Revenue in contests with many participants. Operations Research Letters, 42(2):119 122, 2014. [Kirkegaard, 2012] Ren e Kirkegaard. Favoritism in asymmetric contests: Head starts and handicaps. Games and Economic Behavior, 76(1):226 248, 2012. [Moldovanu and Sela, 2001] Benny Moldovanu and Aner Sela. The optimal allocation of prizes in contests. American Economic Review, 91(3):542 558, 2001. [Olszewski and Siegel, 2016] Wojciech Olszewski and Ron Siegel. Large contests. Econometrica, 84(2):835 854, 2016. [Olszewski and Siegel, 2020] Wojciech Olszewski and Ron Siegel. Performance-maximizing large contests. Theoretical Economics, 15(1):57 88, 2020. [Siegel, 2009] Ron Siegel. All-pay contests. Econometrica, 77(1):71 92, 2009. [Tullock, 1980] Gordon Tullock. Efﬁcient rent-seeking. In James Buchanan, Robert Tollison, and Gordon Tullock, editors, Toward a Theory of the Rent Seeking Society, pages 131 146. Texas A & M University, College Station, Texas, USA, 1980. [Vojnovi c, 2016] Milan Vojnovi c. Contest Theory: Incentive Mechanisms and Ranking Methods. Cambridge University Press, Cambridge, UK, 2016.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)