{'fraction_non_alphanumeric': 0.06604254595926692, 'fraction_numerical': 0.014488853638500977, 'mean_word_length': 4.207005899705015, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Performance-maximizing large contests

Many sales, sports, and research contests are put in place to maximize contestants’ performance. We investigate and provide a complete characterization of the prize structures that achieve this objective in settings with many contestants. The contestants may be ex ante asymmetric in their abilities and prize valuations, and there may be complete or incomplete information about these parameters. The prize valuations and performance costs may be linear, concave, or convex. A main novel takeaway is that awarding numerous different prizes whose values gradually decline with contestants’ ranking is optimal in the typical case of contestants with convex performance costs and concave prize valuations. This suggests that many real-world contests can be improved by increasing the number of prizes and making them more heterogeneous. The techniques we develop can also be used to formulate and solve other contest design questions that have so far proven intractable.


Introduction
Contests are used in a variety of settings to motivate people and increase their performance.
Cisco Systems, one of the largest technology companies, regularly runs contests among its thousands of partners to boost sales. 1 HubSpot, a three-billion dollar software company, and Clayton Homes, the largest builder of manufactured housing and modular homes in the United States, are two other examples. 2 In the context of entertainment, sporting contests play an important role. In the context of academia, funding agencies administer large contests that motivate researchers to generate high-quality research proposals. The widespread use of contests makes contest design relevant and important for many real-world domains, but at this time many aspects of contest design are not well understood.
This paper improves our understanding of contest design by characterizing the prize structures that maximize contestants' aggregate performance in contests with many contestants. 3 More precisely, given a prize budget, we investigate how many prizes should be awarded and how the budget should be allocated among the prizes to induce maximal performance.
Should a small number of high-value prizes be awarded, or a larger number of lower-value prizes? Or perhaps awarding prizes of different values is optimal? And if so, how should the prize values change with their rank order?
Our main qualitative finding characterizes the optimal prize structures in the most relevant case of players with convex performance costs and concave prize valuations. In this case, the performance-maximizing contest awards many prizes, all of them different, with gradually decreasing values. This is because both convex costs and concave valuations push toward gradual prize structures. But we also find that the qualitative effects of convex costs and concave valuations on the optimal prize structure are not identical. In particular, the 1 3 Examples of contests with many contestants include sales competitions in large firms, sports competitions such as marathons, and research grant competitions.
optimal number of prizes depends more heavily on the curvature of the costs. With linear costs, the optimal number of prizes, while still large, is significantly smaller than the number of contestants, even if valuations are very concave. In contrast, if costs are convex and the marginal cost at zero performance is zero, then even with linear valuations almost every contestant is optimally awarded a positive prize.
We obtain our results in a relatively general environment with many contestants. Each contestant chooses a performance and pays the associated cost, and the prizes are awarded according to the rank order of the performances. 4 The contestants may be ex-ante asymmetric in their abilities and prize valuations, and there may be complete or incomplete information about these parameters. Contestants' prize valuations and performance costs may be linear, concave, or convex. We consider all possible prize structures, including identical prizes, heterogeneous prizes, and a combination of identical and heterogeneous prizes.
This is important, because restricting the prize structures a priori may rule out the optimal ones.
Solving for equilibrium in the contest environment we consider is an intractable problem.
We deal with difficulty by using the approximation approach for large contests developed by Olszewski and Siegel (2016). In that paper, we considered large contests with a fixed prize structure, and showed that players' equilibrium behavior is approximated by the unique single-agent mechanism that assortatively allocates a continuum of prizes to a continuum of agent types and gives the lowest type a utility of 0. This result allows us to formulate the contest design problem in this paper as a tractable single-agent mechanism design problem, which we then solve.
The rest of the paper is organized as follows. Section 2 describes the contest environment and the contest design problem. Section 3 solves the problem when players have linear costs, and Section 4 extends the analysis to more general costs. Section 5 presents a comparative statics result and discusses how to endogenize the prize budget. Section 6 discusses several related papers. Section 7 concludes. The appendix contains the proofs and some material omitted from the main text. The online appendix contains a few additional results.

Model
A contest is a game in which players compete for prizes. Each player is characterized by a type  ∈ [0 1], which is drawn from a player-specific distribution (independently across players), and each prize is characterized by a number  ∈ [0], where  = 0 corresponds to "no prize" and is the highest possible prize. For concreteness, we will assume that prizes are monetary, so  is simply an amount of money. 5 Each player chooses her performance  ≥ 0, the player with the highest performance obtains the highest prize, the player with the second-highest performance obtains the second-highest prize, and so on. Ties are resolved by a fair lottery. The utility of a player of type  from choosing performance  and obtaining prize  is where  (0) =  (0) = 0, and prize valuation  and performance cost  are continuously differentiable and strictly increasing. Notice that functions  and  are common to all players.
Notice also that the game is strategically equivalent to one in which players have private information about their performance cost, as in Spence's (1973) signalling model, by dividing the utility by  to obtain  () −  () . This has no effect on the results. We assume that sufficiently high performance levels are prohibitively costly, that is,  ()   () for large enough , so no player chooses performance higher than  −1 ( ()). The functional form (1) and special cases thereof have been assumed in numerous existing papers on contests (see, for example, Clark and Riis (1998), henceforth: CR, Moldovanu and Sela (2001), henceforth: MS, Bulow and Levin (2006), henceforth: BL, Siegel (2010), and Xiao (2016)).
Our focus is on contests with a large (but finite) number of players and prizes. Olszewski and Siegel (2016) (henceforth: OS) showed that all the equilibria of such large contests are closely approximated by the unique single-agent mechanism in a specific environment that implements the assortative allocation of prizes to agent types and gives the lowest type a utility of 0. More precisely, let  be a distribution of types with a continuous, strictly positive 5 More generally, the number  represents the prize's cost, so prize  costs .
density , and let  be some (not necessarily continuous) distribution of prizes. We interpret  as the average distribution of players' types in the large contest and  as the empirical distribution of prizes. It is important that we do not restrict , since we will optimize over prize distributions, and any exogenous restriction on the optimal prize distribution would restrict the scope of our analysis. The assortative allocation assigns to each type  prize That is, the quantile in the prize distribution of the prize assigned to type  is the same as the quantile of type  in the type distribution. It is well known (see, for example, Myerson (1981)) that the unique incentive-compatible mechanism that implements the assortative allocation and gives type  = 0 utility 0 specifies for every type  performance Roughly speaking, the approximation shows that in any equilibrium of a large contest a player with type  with high probability chooses a performance close to   () and obtains a prize close to   (), which gives her a utility close to  ().
The intuition for why this single-agent mechanism approximates the equilibria of large (finite) contests is that, given players' equilibrium strategies, with a large number of players the law of large numbers implies that each bid leads to an almost deterministic rank-order quantile (in the distribution of bids) and thus to an almost deterministic prize. In the limit we obtain an "inverse tariff" that maps bids to prizes. Utility (1) implies that higher types choose higher bids from any tariff, so the mechanism induced by the inverse tariff implements the assortative allocation. Any player can bid 0 and obtain the lowest prize, so the utility of type 0 is 0. The appendix formalizes the approximation (see OS for additional details).
We point out that the single-agent setting is not a contest with a continuum of players who compete against each other, but rather a single privately-informed agent who faces a mechanism that implements the assortative allocation for a fixed distribution of prizes.
The aforementioned approximation results of OS, which justify our study of the single-agent mechanism design setting, allow us to avoid having to study a "limit contest," which would involve several conceptual and technical difficulties. In the rest of paper we focus on the single-agent mechanism to investigate the performance-maximizing prize distributions.
Remark 1 The bound is the highest possible value of any single prize. We require this bound because the approximation results of OS rely on the compactness of the spaces of types and prizes. 6 Such a bound is not an issue for the analysis of contests with a fixed prize structure. It is also not an issue for the analysis of the optimal prize structures in settings in which such a bound arises naturally, as the result of policy, fairness considerations, or technological limitations. But imposing such a bound in other settings may be restrictive, since the per-capita prize budget we impose in Section 2.1 does imply any bound as the number of contestants grows large. To apply our results to settings in which a bound may be restrictive, we will find the optimal prize distributions for all, and then take the limit of the optimal structures as diverges to infinity.

Performance maximization
We are interested in the prize distributions  that maximize the aggregate performance   (·) subject to a prize budget of  in the single-agent mechanism that implements the assortative allocation and gives the lowest type utility 0. The formal statement of the problem is as follows: where G is the set of all possible prize distributions. The appendix shows that the prize distributions that solve (3) approximate the prize structures that maximize aggregate performance in large (finite) contests, subject to a per-capita prize budget of  , 7 in a lowerand upper-hemicontinuous sense. 6 The necessity of assuming compactness will also be apparent in the later steps of the analysis. In some cases, it will be optimal to spend the entire budget on the highest possible prizes. With no bound on the prize sizes, an optimal prize structure would not exist. 7 For example, a contest with 10,000 contestants and a budget of $1,000,000 would have a per-capita prize budget of  = 100. As we consider larger and larger contests, we require the overall budget to scale proportionally in order to maintain the per-capita prize budget.
The constrained maximization problem (3) is related to the theory of optimal taxation with Rawlsian social preferences (see, for example, Salanié (2003), pages 84-87). To see the relationship, consider an optimal taxation setting with a continuum of agents, each of whom is characterized by his privately-known productivity . The population productivity distribution is  . Each agent chooses how much output to produce. An agent with productivity  who chooses output  incurs cost (). Output is observable. Before the agents make their output choices, the social planner commits to a tax schedule, which specifies a tax amount for every level of output. Each agent consumes whatever remains from the output he produces after taxes. Denote by () the output chosen by type  and by () the con- This gives a maximization problem similar to (3), in which the agents' utility  − () is somewhat different from the utility  () −  ()  in our setting. Again, such an optimal taxation problem is not a natural one because of the constraint.
We begin by solving (3) in the relatively simple case of linear performance costs.

Linear cost functions
With linear costs  () =  we can use (2) and integration by parts to rewrite (3) as For some intuition for why the objective in (4) approximates the expected average performance in large contests, observe that this function coincides with the expected revenue from a bidder in a single-object independent private-value auction if we let  ¡   () ¢ be the probability that the bidder wins the object when his type is  (Myerson (1981)). In the auction setting, increasing the probability that type  obtains the object along with the price the type is charged allows the auctioneer to capture the entire increase in surplus for this type, but requires a decrease in the price that higher types are charged to maintain incentive compatibility. This net increase in revenue, or "virtual value," also coincides with a monopolist's marginal revenue (Bulow and Roberts (1989)). In a large contest, increasing the prize that type  obtains also allows the designer to capture the entire surplus increase for this type, because the higher prize increases this type's competition with slightly lower types until the surplus increase from the higher prize is exhausted. But the prize increase also decreases the competition of higher types for their prizes, since the prize of type  becomes more attractive to them.
To get a sense for the solution of (4), suppose that instead of solving for the optimal prize distribution  we wanted to solve for the optimal assortative allocation   of prizes to types (which determines  by   () =  −1 ( ())). Then, if we assumed that the optimal   was sufficiently smooth, we could put a Lagrange multiplier  in the constraint and obtain that for any type  such that   () takes an interior value (i.e., in (0 1)), we would have the first-order condition To guarantee that the solution   is non-decreasing we make the following monotonicity assumption: This monotonicity condition leads to the objective in (4) having increasing differences in   () and , and corresponds to Myerson's (1981) "regular case." 8 Since we are interested in conditions that more directly characterize the optimal prize distribution , we rewrite the first-order condition by substituting  =  () to obtain where It is helpful to think of  −1 as mapping every quantile in the type distribution to its corresponding prize in the assortative allocation.
The following lemma characterizes the optimal distributions . Despite the straightforward derivation of (5) above, the proof of the lemma is not completely straightforward because we cannot assume that the optimal  is differentiable (or even continuous) or that  −1 takes interior values (i.e., in (0 1)).
The parameter  in Case 1 is the shadow price of the budget constraint, that is, by how much the aggregate performance increases if the budget is increased slightly. This shadow price can be used to determine the optimal budget when the budget is endogenous, as discussed in Section 5. 8 In the online appendix we show that many of the results for linear costs also hold without Assumption 1.

Concave, linear, and convex prize valuations
When the budget is large enough, the curvature of the prize valuation  does not affect the optimal prize distribution. To see this, observe that maximizing the objective in (4) pointwise while ignoring the budget constraint leads to choosing the highest possible prize, , for types    * and the lowest possible prize, 0, for types    * , where  * ∈ (0 1) is the unique type (by Assumption 1) that satisfies  * − (1 −  ( * ))  ( * ) = 0. This gives us the following observation.
, then for any function  the optimal prize distribution consists of a mass 1 −  ( * ) ∈ (0 1) of the highest possible prize,, and a mass  ( * ) of prize 0.
Observation 1 shows that with a sufficiently large budget it is optimal to award a set of identical prizes, as in the all-pay auctions studied by CR, rather than heterogeneous prizes, as in, for example, the all-pay auctions studied by BL, or a combination of identical and heterogeneous prizes. Notice that the optimal mass of prizes, 1 −  ( * ), is independent of the size of the highest possible prize,.
When the budget is lower than (1 −  ( * )), the curvature of the prize valuation  affects the optimal prize distribution. We first present the simpler result for linear or convex functions .
) and  is weakly convex, then the optimal prize distribution consists of a mass  of the highest possible prize,, and a mass 1 −  of prize 0.
Proposition 1 shows that awarding identical prizes remains optimal when the budget is low, provided that agents' marginal prize utility is nondecreasing. If the highest possible prize is increased, fewer maximal prizes are optimally awarded. The limit as grows arbitrarily large corresponds to a single grand prize.
Observation 1 and Proposition 1 show that when the budget is large (regardless of the curvature of ) and when the marginal prize utility is increasing, the optimal prize distribution does not depend on the precise functional form of . With a small budget and decreasing marginal prize utility the optimal prize distribution depends more heavily on . We first provide a qualitative characterization of the optimal prize distribution in this case, and then a full characterization for strictly concave functions . Proposition 2 shows that decreasing marginal prize utility optimally leads to awarding intermediate prizes, whose values gradually decrease with players' performance ranking.
Among the (positive) prizes, only the highest possible prize,, may optimally be awarded to multiple players. The following proposition shows that this generally does not occur when is sufficiently large, so the constraint that no prize can exceed does not bind for sufficiently large.
Proposition 3 Suppose that   (1 −  ( * )). Let  max be an optimal prize distribution when is the highest possible prize. If  is weakly concave (but not linear on [0]), and  0 () → 0 as  → ∞, then there exists an such that  0 max =  max for any 0 ≥, and this  max may have an atom only at prize 0.
We now provide a full characterization of the optimal prize distribution when    (1 −  ( * )) and  is strictly concave. Since the optimal  is strictly increasing (part 2 of Proposition 2),  −1 is continuous, so we have  0 (0)  ( min ) = . Thus, then we also have  0 () ( max ) ≥  (because we are in Case 1 of Lemma 1), so we obtain  0 ()  ( max ) = . Thus, In addition, and Thus,  −1 is pinned down by . The value of  is determined by the fact that (14) holds as an equality (because   (1 −  ( * ))).

An example
To demonstrate the usefulness of the above characterization, we now derive the optimal  −1 for contests with prize valuations  () =  1 for   1 (and any type distribution  ). We assume that the highest possible prize is large enough that  max = 1 (see Proposition 3), which also implies that   (1 −  ( * )), so the entire budget is used. Since  0 (0) = ∞, for  ∈ ( *  1]. Thus, Substituting this expression for  (−1) into (9) we obtain

More general cost functions
With non-linear costs  the analysis is substantially more complicated. Nevertheless, conditions similar to the ones in Lemma 1 can be derived and used to characterize the optimal prize distributions. We provide these conditions in Lemma 2 in the appendix. In the appendix we also formulate Assumption 2, which generalizes Assumption 1 for the case of non-linear costs. Assumption 2 plays a similar role to that of Assumption 1 in the case of linear costs, and facilitates an analytical characterization of the solution. 9 Assumption 2 is satisfied, for example, whenever  is nondecreasing (for any cost function ).
The assumption imposes no restriction on the prize valuation .

Concave and linear prize valuations with convex costs
We now characterize the optimal prize distribution when the prize valuation  is concave or linear and the costs are convex. This will generalize Proposition 2 and highlight additional features of the optimal prize distribution implied by convex costs. As we will see, the effects of concave prize valuations and convex costs on the optimal prize distribution are qualitatively similar, but not identical. It is also possible to generalize the results from Section 3.1 for convex prize valuations to concave costs, but this case seems less relevant for economic applications. Lemma 2 in the appendix, which is the analogue of Lemma 1 for nonlinear costs, can also be used to study the optimal prize distribution for convex prize valuations Proposition 4 highlights some similarities and differences between the effects on the optimal prize distribution of convex costs and concave prize valuations. When the budget is 9 We strongly conjecture that, similarly to the case of linear costs, many of the results for general costs also hold without Assumption 2. costs a slight change in the prize a type is awarded induces a larger change in that type's performance when the prize is 0 than when the prize is. It therefore cannot be optimal to award prize 0 to some type and prize to a slightly higher type, since a slight increase in the former type's prize along with a corresponding decrease in the latter type's prize increases these types' aggregate performance without significantly affecting all higher types' performance. In addition, if the marginal performance cost at 0 is 0, then every positive type is optimally awarded a positive prize. This is because a marginal cost of 0 implies that the marginal of the inverse function, i.e., the marginal increase in performance associated with a marginal increase in cost, is infinity. This in turn means that a slight increase from 0 in the prize awarded to a positive type, which leads to an increase in the performance cost this type incurs, generates an increase in that type's performance that infinitely outweighs the decrease in the performance of higher types. It is therefore optimal to have almost every type participate in the contest and obtain a positive prize, unlike with linear costs.

An example
With convex costs and concave valuations we cannot provide a full characterization of the optimal prize distribution similar to the one following Proposition 3 for linear costs and concave valuations. This is because that characterization uses Lemma 1, which relies on the marginal prize valuation  (·) being independent of the optimal prize distribution, whereas the corresponding marginal prize valuation  (·) for convex costs (defined in the appendix) depends on the optimal prize distribution. Nevertheless, Proposition 4 and Lemma 2 in the appendix can be used to explicitly derive the optimal prize distribution once functional forms are specified. We illustrate this with an example, which also highlights the two differ-ences described above between the optimal prize distribution with linear costs and concave valuations and the optimal prize distribution with convex costs.
Suppose that the prize valuation is linear ( () = ), the costs are quadratic ( () =  2 ), and the type distribution  is uniform. Proposition 4 shows that the optimal prize distribution  assigns positive probability to the set of intermediate prizes (0) and may have atoms only at 0 and. In the appendix, we use the conditions in Case 1 of Lemma 2 to derive  −1 . Suppose first that, the highest possible prize, is at least 4 . Then This distribution is independent of, so the bound on the highest possible prize is not binding, and the associated aggregate performance is p 3.
Consistent with Proposition 4, every positive type obtains a positive prize, the prizes increase gradually from 0 to 4 , and there are no atoms (see Figure 1 below). Now suppose that is less than 4 . Then, as long as ≥ 85, we have . Every positive type still obtains a positive prize, and the prizes increase gradually from 0 to, but there is also a mass (4 −)  (3) of prize (see Figure 1 below). If falls below 85, then the budget in excess of 58 is optimally not used, so the optimal prize distribution coincides with the one for = 85.
Notice that unlike the case of linear costs, and consistent with Proposition 4, even when the budget is large ( ≥ 58) the optimal prize distribution still awards all prizes between 0 and, and every positive type obtains a prize. Figure 1: The optimal prize distribution for = 1 and  = 14 (red) and  = 58 (green)

Discussion
In addition to characterizing the optimal prize distribution, our methods can also be used to derive comparative statics. We provide one result here; additional results are in the online appendix. This result shows that a first-order stochastic dominance (FOSD) shift in the type distribution increases the aggregate performance for any prize distribution.
Proposition 5 If e  FOSD  , then for any prize distribution  the aggregate performance is higher under e  than under  . In particular, for the optimal prize distributions the aggregate performance is higher under e  than under  .
While it may seem intuitive that a more able pool of players will generate higher equilibrium performance, this is not always the case in contests with a small number of players.
To see this, consider a two-player all-pay auction with complete information and one prize.
The prize is  = 1, the prize valuation function satisfies  (1) = 1, and the cost function is , which monotonically increase in  1 and monotonically decrease in Thus, an increase in player 2's type, even when accompanied by a small increase in player 1's type, decreases the expected aggregate bids. The intuition is that the increased asymmetry between the players, which discourages competition, outweighs the increase in their types, which encourage higher bids. The intuition for Proposition 5 is that in a large contest competition is "localized" in the sense that players compete against players with similar types. 10 Therefore, any decrease in local competition between some types resulting from a FOSD shift in players' type distribution is more than compensated for by an increase in local competition between some higher types.
Our approach can also illustrate how to determine the optimal budget  (recall that  was so far assumed exogenous). Suppose that the budget cost is strictly increasing, 10 A discussion of this phenomenon appears in Bulow and Levin (2006 show that Case 1 of Lemmas 1 and 2 applies. The shadow cost  is then the marginal budget benefit, so the optimal budget  can be identified by comparing the marginal budget cost to . As an example, consider the contest with = 1,  () = √ ,  () = , and  uniform for The following figure depicts the optimal prize distributions for different budgets  ≤ 12. The prize distributions were computed by using (10) for  ≤ 16 (which implies that  max = 1 and there is no mass of prize = 1), and by using the more general characterization from Section 3.1 for   16 (which implies that  max  1 and there is a mass of prize = 1). 11 Figure 2: The optimal prize distributions as the budget varies from 0 to 12.
The characterization from Section 3.1 shows that  = 1 √ 24 for  ≤ 16, and  = 11 The optimal distributions are 12 Consistent with Observation 1,  = 0 for  = 12, so the budget will never optimally exceed 12. With a linear budget cost of  , for example, the optimal budget is  = 124, and with a quadratic cost of  2 the optimal budget is  = 314.

Existing work
Several previous papers consider maximizing the expected aggregate output (or effort) in various contests. The two closest to our work, Glazer and Hassin (1988) and MS (Moldovanu and Sela (2001)), examine this maximization with respect to the prize structure subject to a budget constraint. 13 Both papers study contests in which players' utilities are special cases of (1).
Glazer and Hassin (1988) analyze contests in which contestants are randomly drawn from a population, and use a somewhat specific concept of equilibrium, 14 which facilitates their analysis in a manner similar to that in which our limit approach facilitates the analysis of large contests. They derive an optimal prize structure in two cases. First, when contestants' ability is uniformly distributed in the population, the costs are linear, and prize valuations are weakly concave, they obtain a result that corresponds to our Propositions 1 and 2. Second, when all contestants have identical abilities, they show that the optimal prize structure has  − 1 equal prizes and one prize of 0. This result is specific to discrete contests. 15 MS restrict attention to the symmetric equilibria of discrete contests with ex-ante symmetric contestants, incomplete information, and linear prize valuations, but their results 12 The maximal average performance is The difference between the functional forms is due to the atom at the highest possible prize, 1, which appears when the budget exceeds 16. 13 Moldovanu, Sela, and Shi (2007) and Immorlica, Stoddard, and Syrgkanis (2015) study this maximization in the context of social status. Xiao (2018) numerically computes the optimal division of a budget between two prizes when contestants have linear costs and no private information.
14 They disregard the consistency condition between the distribution of abilities in the population and the equilibrium distribution of output of a randomly chosen contestant. 15 It can be shown in our setting, and consistent with their result, that when the limit distribution of types  converges to a Dirac distribution, the optimal prize distribution also converges to a Dirac distribution.
apply to any number of players. They show that for weakly concave costs, it is optimal to award the entire budget as a single prize. 16 MS also show that with convex costs awarding the entire budget as a single prize may be inferior to splitting the budget between two prizes.

Concluding remarks
This paper investigates the performance-maximizing prize structures in contests with many contestants. Our key qualitative finding is that concave prize valuations and convex perfor- Our approach can also be used to investigate many other contest design questions. One example is maximizing the expected aggregate performance when not all prize structures are available (for instance, all prizes must be identical), or when the budget is also determined optimally (as discussed in Section 5). Another example is maximizing a weighted sum of contestants' performance. For example, the designer may want to maximize the aggregate performance of contestants whose type exceeds a certain cutoff, or the aggregate performance of the highest-performing  percent of contestants. Our analysis can be extended to capture both scenarios. 18 As an example, consider mathematical olympiads, and suppose that the goal is to identify and encourage the development of the most mathematically gifted individuals. This would correspond in our setting to maximizing the aggregate performance of a top fraction of the players. In this case, a minor modification of our analysis implies that it is optimal to spend the entire budget on prizes for this top fraction of contestants.
Conditional on this top fraction, the optimal prize distribution is the one that maximizes the aggregate performance for a distribution of types that is the conditional distribution of the types in the top fraction.
More generally, our techniques can be used to investigate various contest design objectives. This can be done by identifying the corresponding objectives in the limit setting and showing that they approximate the ones in large contests. An optimization problem would then be formulated and solved, possibly using the methods we develop here.

Appendix
Approximating the equilibria of large contests with a fixed prize structure by a single-agent mechanism. Consider a sequence of contests parameterized by the number  of players and prizes (since a prize  = 0 corresponds to "no prize" it is without loss of generality to have the same number of players and prizes). In the -th contest, let player 's type   be distributed according to a cdf   that does not have an atom at 0, and let   1 ≤   2 ≤ · · · ≤    be the set of prizes. Olszewski and Siegel (2019) show that every contest has an equilibrium in distributional strategies (Milgrom and Weber (1985)). The equilibrium approximation technique requires the contests in the sequence to become increasingly similar in some sense as  increases. To formalize this requirement, let   = ( is the expected percentile ranking of type  in the -th contest given the random vector of players' types. Denote by   the empirical prize distribution of the  prizes, which assigns a mass of 1 to each prize    (recall that there is no uncertainty about the prizes). We require that   converge pointwise to a distribution  that has a continuous, strictly positive density  , and that   converge pointwise to some (not necessarily continuous) distribution  at all points of continuity of . OS provide several examples to illustrate the convergence of   and   . The following approximation result appears as Corollary 2 in OS. 19 Theorem 1 (OS) For any   0 there is an  such that for all  ≥ , in any equilibrium of the -th contest each of a fraction of at least 1 −  of the players  obtains with probability at least 1 −  a prize that differs by at most  from   (   ), and chooses performance that is with probability at least 1 −  within  of   (   ).
Optimal prize distributions in the single-agent setting approximate optimal prize structures in large contests. When    () is the performance of player  of type  in the -th contest, the expected average performance is ( 1 1 ) The budget per capita is  : The reason that we work with averages is to avoid the quantities becoming infinitely large as  tends to infinity.
We first observe that given a converging sequence of contests, Theorem 1 implies that the expected average performance for large  is approximated by the aggregate performance in the mechanism that implements the assortative allocation in the limit setting: ( 1 2 ) Corollary 1 For any   0 there is an  such that for all  ≥ , in any equilibrium of the -th contest the expected average performance (11) is within  of (12).
Corollary 1 applies to a given limit distribution  (its proof and that of the additional results appear at the end). Consider a sequence of type distributions that converges to distribution  with a continuous, strictly positive density  , and denote by   max the empirical distribution of prizes that maximizes the equilibrium expected average performance in the -th contest over all equilibria and all sets of prizes   1 ≤ · · · ≤    whose average is no greater than  . We denote by   max the maximal expected average performance attained by   max . For the limit setting, we denote by M the set of prize distributions that maximize (12) subject to the budget constraint R 0  () ≤  . An upper hemi-continuity argument, given in the appendix, shows that a maximizing distribution exists.

Claim 1
The set M is not empty.
Denote by  the corresponding maximal value of (12) subject to the budget constraint.
The next proposition formalizes the convergence using any metrization of the weak * -topology on the space of prize distributions. 20 Proposition 6 1. For any   0, there is an  such that for every  ≥ ,   max is within  of some distribution in M. In particular, if there is a unique prize distribution  max that maximizes (12) subject to the budget constraint, then   max converges to  max . 2.   max converges to . 3. For any   0, there are an  and a   0 such that for any  ≥  and any empirical prize distribution   of  prizes that is within  of some  in M, the expected average performance in any equilibrium of the -th contest with empirical prize distribution Part 1 of Proposition 6 shows that the optimal prize distributions in large contests are approximated by the prize distributions that maximize (12) subject to the budget constraint.
Part 2 shows that the maximal expected average performance is approximated by the maximal value of (12) subject to the budget constraint. 21 Part 3 shows that any prize distribution that is close to a prize distribution that maximizes (12) subject to the budget constraint generates an expected average performance (in any equilibrium) that is close to maximal. For 20 Convergence in weak * topology is equivalent to the convergence of CDFs at the points in which the limit is continuous. Roughly speaking, a prize distribution  0 is close to a prize distribution  if the graph of the CDF of  0 lies in a small neighborhood of the graph of the CDF of . 21 The rates of convergence result in OS also indicates that if the optimal prize distribution satisfies the conditions in their Section 6, then the maximal expected average performance is within  of the maximal value of (12) if 1 is smaller than an expression of order − 2  ln .
example, given a prize distribution  that maximizes (12) subject to the budget constraint, the set of  prizes defined by    =  −1 () for  = 1   generates, for large , an expected average performance that is close to maximal; moreover, the average prize   for the so defined distributions   converges to the average prize  for the distribution .
Proof of Corollary 1. Theorem 1 shows that for large , in any equilibrium of the -th contest the expected average performance is within 2 of where the equality follows from the definition of   . In addition, which follows from the fact that   is monotonic and the assumption that  is continuous, Proof of Claim 1. Let (  ) ∞ =1 be a sequence on which (12) converges to its supremum, and which satisfies the budget constraint. By passing to a convergent subsequence (in the weak * -topology) if necessary, assume that   converges to some . We will show below that (  ) −1 converges almost surely to  −1 . This will imply that ( converges almost surely to   () =  −1 ( ()), and since functions  and  −1 are continuous, also that (  )  () given by (2) with  replaced with   converges almost surely to   () given by (2). This will in turn imply that the value of (12) with (  ) −1 instead of  −1 converges to the value of (12). Finally, as   satisfies the budget constraint,  satisfies the budget constraint as well. Indeed, the budget constraints are integrals of a continuous function (mapping  to ) with respect to distributions  and   , respectively, and weak *topology may be alternatively defined as convergence of integrals of continuous functions.

Suppose now that for some
for arbitrarily large . Passing to a subsequence if necessary, assume that the inequality holds for all , and that (  ) −1 () converges to some  ≥  −1 () + . Then, there exists a prize  such that  −1 ()     and  is continuous at . We have that   (), as for large enough . This yields (  ) −1 () ≤ , contradicting the assumption that (  ) −1 () converges to   .
Proof of Proposition 6. Since every sequence of distributions has a converging subsequence in weak * -topology, suppose without loss of generality that   max converges to some distribution . Denote the value of (12) under distribution  by  . If Part 1 is false, then   ∈ M, so   . The distribution  satisfies the budget constraint, since distributions   max satisfy the budget constraint. Consider a distribution  max ∈ M, and for every  consider an empirical distribution   of a set of  prizes, such that   converges to  max in weak * -topology. For example, such a set of  prizes is defined by    =  −1 max () for  = 1  . Corollary 1 shows that for large  the expected average performance in any equilibrium of the -th contest with empirical prize distribution   exceeds ( + ) 2. On the other hand, Corollary 1 also shows that for large  the expected average performance in any equilibrium of the -th contest with empirical prize distribution   max falls below ( + ) 2. This contradicts the definition of   max for large .
For Part 2, Corollary 1 applied to the sequence   defined above implies that lim inf   max ≥ . If lim sup   max  , then there is a corresponding subsequence of   max . A converging subsequence of this subsequence has a limit . For this , the value of (12) is by Corollary 1 strictly larger than , a contradiction.
For Part 3, notice that the proof of Claim 1 also implies that the set  is closed in weak * -topology. Thus, if part 3 were false, there would exist a sequence of contests with empirical prize distributions   converging to some  in , such that the expected average performance in an equilibrium of the -th contest with empirical prize distribution   would be lower than   max − . This would contradict Part 2 and Corollary 1.
Proof of Lemma 1. We first substitute  =  () to rewrite the problem as maximizing ( 1 4 ) Let  be an optimal distribution, and suppose that  min   max . We now show that The idea is that if this were not the case, e.g., if we had  instead of =, then we could increase  −1 around  and decrease  −1 around , thereby increasing the aggregate performance. We must be careful, however, not to violate the budget constraint, and to maintain the monotonicity of  −1 .
These properties will be easier to control if we first approximate  −1 by a piecewise constant function.
The value of (13) with ( e   ) −1 instead of  −1 is higher than with (  ) −1 instead of  −1 , because  is an increasing function.
The second condition in Case 1 and the condition in Case 2 are obtained by analogous arguments, noticing that  min  0 (since  (0)  0) and, since  is increasing and continuous, Proof of Proposition 1. Weak convexity implies that  min =  max , so only prizes 0 and  are awarded. Otherwise, since  0 and  −1 are weakly increasing and  is strictly increasing, Proof of Proposition 2. Observe that  min   max . Indeed, since  0 (0)   0 (), )   violates the budget constraint (14). This yields the first part of 1. For the second part, notice that  −1 () strictly increases in  on interval ( min   max ), so  does not have atoms there. This follows from the fact that  0 ( −1 ())  () =  on ( min   max ] and the fact that  () strictly increases in .
To see 2, note that  0 is strictly decreasing and, by assumption, continuous. Thus, right-continuous at  min , then the fact that  0 (0)  ( min ) ≤  and the assumption that  0 is strictly decreasing would violate the condition  0 ( −1 ())  () =  for  slightly higher than  min . 22 Thus,  −1 is continuous on [ min   max ], which means that  strictly increases on which can happen when  max  1, then  −1 ( max )   −1 (1) =, which also completes the proof, as otherwise the fact that  0 () ( max ) ≥  and the assumption that  0 is strictly decreasing would violate the condition  0 ( −1 ( max ))  ( max ) = .
Proof of Proposition 3. Let  min ,  max , and  denote  min ,  max , and  for a given . The proof of Proposition 2 shows that  min   max for all. We claim that  weakly increases with. Suppose to the contrary that  0   00 for some 0  00 .
Since  is increasing, this implies that  Thus, as the inverse of any cdf is increasing, we again obtain (c), except that this time Optimality conditions for general costs. To develop the conditions satisfied by an optimal prize distribution for non-linear costs it is useful to substitute  =  −1 () and (2) into the aggregate performance 23 Therefore, (  max ) −1 converges pointwise to some  −1 on [0 1), even when  0 () 9 0 as  → ∞. We cannot conclude, however, that this  −1 is an inverse cdf. For example,  −1 can be a constant function equal to 0.
is the cost of the performance of type  in quantile  =  () and () = (  ()). Notice that e  () is well defined even when function  −1 () is not monotone. We will consider such functions in some of our proofs. It is also useful to rewrite the budget constraint as Similarly to Section 3, to derive the conditions for optimality it is useful to consider the effect of a slight increase ∆ in the value of  −1 at quantile  on the aggregate performance (15). In the case of linear cost , the effect was to generate an increase of where  () was the marginal virtual performance. With non-linear costs, the marginal virtual performance  () (given by (18)  It increases the integrand for  ∈ (2   ( + 1)2  ], to a first-order approximation, by (the union of the shaded and darkened rectangles in Figure 3). For any   , it decreases the integrand for  ∈ (2   ( + 1)2  ], to a second-order approximation, by (the shaded square in Figure 3).
before the increase after the increase Figure 3: , to a first-order approximation, letting  = ( + 1)2  , we express the total increase in (15) as ( 1 7 ) Recalling that e  () is the cost of the performance of type  in quantile  =  (), we can interpret as the marginal virtual performance of the type in quantile : a marginal increase in the prize allocated to this type intensifies competition for this prize and exhausts the corresponding increase in allocation utility (the first term on the right-hand side of (18)), but reduces competition by all higher types (the second term on the right-hand side of (18)).
With non-linear costs these effects depend on the prizes allocated to lower types (through e  ()), because they determine the current performance, which affects the marginal cost of performance. This dependency disappears with linear cost  () = , in which case  () coincides with  ().
With linear costs, Assumption 1 guarantees that the maximizer  −1 of the relaxed problem is nondecreasing. Indeed, if  −1 () were lower on an interval (2   ( + 1)2  ] than on an interval (2   ( + 1)2  ] for some   , we could exchange the two values, generating a higher increase on (2   ( + 1)2  ] than a decrease on (2   ( + 1)2  ]. The assumption that  () is strictly increasing would be a natural counterpart of Assumption 1 in the more general setting. Unfortunately,  () involves the endogenous variable  −1 (through e  ()), which would make the assumption unattractive; moreover, it would no longer serve its purpose, because exchanging the values of would affect the value of  (). We instead make the following assumption, expressed only in terms of the primitives of the model, which guarantees directly that exchanging the values of  −1 on the two intervals is beneficial, and therefore guarantees that the maximizer of the relaxed problem is nondecreasing. For the assumption, recall that no player chooses performance higher than  −1 ( ()), and let  = min { 0 () :  ∈ [0  −1 ( ())]} and We restrict attention to continuously differentiable density functions  .
where if  = 0 the second fraction is equal to ∞, −∞, or 0 when its numerator is positive, negative, or 0, respectively. Assumption 2 generalizes Assumption 1, because when  =  = 1 the left-hand side of (19) is equal to  0 (). In addition, the set of primitives for which Assumption 2 holds is generic in the sense that if it holds for some pair of a continuous derivative of a cost function and a continuous derivative of a density function, then it holds for all such pairs that are sufficiently close to it in the sup norm.
Equipped with (18), we obtain the following analogue of Lemma 1.
Lemma 2 Given a prize distribution , let  min ≤  max in [0 1] be such that  −1 () = 0 for  ≤  min ,  −1 () = for    max , and  −1 () ∈ (0) for  ∈ ( min   max ). If  is an optimal prize distribution, then it satisfies the following conditions: If  min   max (Case 1): Then, there exists a  ≥ 0 such that for  ∈ ( min   max ]; in addition, and if  max  1. If  min =  max (Case 2): Then, The difference between Case 2 in Lemma 2 and Case 2 in Lemma 1 arises because  () is continuous at every , whereas  () is left-continuous at every  but changes discontinuously at quantiles  at which  −1 () increases discontinuously. In particular, if  min =  max , then e  ( min ) = 0 (type  min obtains prize 0 and chooses performance 0) but e  () =  (0)  () for all    max (types above  max obtain prize and choose the performance with cost  (0)  (), which makes type  min =  max =  (0) indifferent between choosing this performance and obtaining prize and choosing performance 0 and obtaining prize 0).
A more subtle difference from Lemma 1 relates to (21). The intuition for (21) is that if the inequality were reversed, then in the relaxed problem increasing  −1 () for  slightly below  min by decreasing  −1 () for  in ( min   max ) would increase the aggregate performance.
This relies on  min  0, which is always the case with linear costs (because  (0)  0). More generally, however, it can be that  min = 0 (see part 3 of Proposition 4). But in this case (21) follows from (20) directly, because  −1 (), and therefore  (), are continuous at  = 0.
by  ( min ), 24 which would reduce the cost of providing the prizes without changing each type's performance. The prizes  −1 () for  close to 1 could then be increased, which would increase the aggregate performance.
Proof of Lemma 2. The idea of the proof is analogous to that of the proof of Lemma 1.
As in that proof, suppose that  min   max , that is, we are in Case 1; the condition in Case 24 The new inverse prize distribution would assign prize . This maintains the same value of (2) for every .
2 is obtained by analogous arguments. For an optimal distribution , approximate  −1 by a sequence of inverse distribution functions ((  ) −1 ) ∞ =1 that are constant on intervals (2   ( + 1)2  ] and with values in the set (20) is violated, we construct functions (  ) −1 (also constant on intervals (2   ( + 1)2  ] and with values in the set {0 12   22    (2  − 1)2   1}) such that the value of the objective (15) with (  ) −1 instead of  −1 exceeds, for large enough , that of (15) for  −1 . This part of the proof replicates the argument from the corresponding part of the proof of Lemma 1, and will be omitted. If for a large enough  function (  ) −1 is nondecreasing, it is an inverse distribution function. We then obtain a contradiction to the optimality of  −1 , which completes the proof. If function (  ) −1 is not monotone, we define another function ³ e  ´− 1 whose value on interval (0 12  ] is equal to the lowest value of (  ) −1 over intervals , whose value on interval (12   22  ] is equal to the second lowest value of (  ) −1 on these intervals, and so on. We will complete the proof by showing that the value of (15) is no lower for ( e   ) −1 than for (  ) −1 for sufficiently large 's.
To show this, we will consider only two adjacent intervals (2   ( +1)2  ] and (2   ( + where   , and estimate the effect on (15) of changing the value of (  ) −1 on (2   ( + 1)2  ] to  and changing the value of (  ) −1 on (2   ( + 1)2  ] to . We will use the same symbol ( e   ) −1 to denote the function obtained from (  ) −1 as a result of this change, and we will sometimes use symbol ∆ to denote 12  .
The exchange of  and  does not affect the integrand of (15) on the intervals lower than (2   ( + 1)2  ]. It affects the value of e  on interval (2   ( + 1)2  ], increasing it by some e ∆  , as well as the value of e  on interval (2   ( + 1)2  ], increasing it by some e ∆  .
As a result of the change in e  on the two intervals, (15) increases by This is easiest to see by looking at Figure 4 Similarly, Using the mean value theorem, the increase in (15) caused by changing the value of e  on intervals (2   ( + 1)2  ] and (2   ( + 1)2  ] can be expressed as for some e   between e (( + 1)2  ) + e ∆  and e (( + 1)2  ), and some e   between e (( + 1)2  ) + e ∆  and e (( + 1)2  ). The exchange of  and  also affects the integrand of (15) on the intervals higher than We can estimate this change in the integrand, as we did for the intervals (2   ( + 1)2  ] and (2   ( + 1)2  ], by using the mean value theorem. On each interval (2   ( + 1)2  ], where  , the integrand increases by for some e .
Setting  = ( + 1)2  and dividing the aggregate increase in (15) (which appears in all expressions), we obtain By using the mean value theorem twice on (24), once in the first line and once in the second where 0 ≤   ≤ ∆.
Applying the mean value theorem again, (25) is equal to for some  0 ∈ [ − ∆ +   + ]. By continuity of  and  0 , (26) is equal to where (∆ 2 ) is an expression that tends to zero faster than ∆ 2 .
We could then not have (20) for both  =  and  = .
For Part 2, notice that e  () increases discontinuously when  −1 () increases discontinuously. So, if ( −1 ) 0 is strictly decreasing, a discontinuity in  −1 () would leads to a discontinuous decrease in the left-hand side of (20). Thus,  −1 is continuous on ( min   max ]. If  −1 were not right-continuous at  min , then (20) and (21) could not both be satisfied, because of the discontinuous decrease of ( −1 ) 0 at  min (and, if  is strictly concave, also a discontinuous decrease of  0 ). Thus,  strictly increases on (20) and (22) could not both be satisfied, because of the discontinuous decrease in the left-hand side of (20) at  max .
For Part 3, suppose that  min  0. If  −1 is discontinuous at  min , then (21) cannot hold.
And if  −1 is continuous at  min  0, then (), and so the left-hand side of (20), diverge to ∞ for  that tends to  min from the right, so (20) is violated for 's close to  min .
Proof of Proposition 5. Choose some prize distribution . By looking at the areas below the graphs of  and  −1 (where () = (  ())) in the square [0 ] × [0 ()], we obtain that the cost of the performance of type  in the mechanism that implements the assortative allocation satisfies Thus, the aggregate performance is equal to where the equality follows from the change of variables  =  () and the identity  ( −1 ()) =  ( −1 ()). 26 Since a FOSD shift in  decreases  and therefore  pointwise, it increases  −1 pointwise, and therefore increases (28).
Deriving the optimal prize distribution for the example in where  min is the "lowest prize" awarded. By parts 2 and 3 of Proposition 4,  min = 0 and  min = 0.
Consider first ≥ 4 . Suppose that  max = 1 and the entire budget is used. Substituting the expression for  −1 () into the budget constraint with equality, we obtain  = 1 √ 12 , which gives  −1 () = 4 3  . Thus,  −1 does not exceed ≥ 4 . Substituting  −1 into the objective, the aggregate performance is p 3, which increase in the budget  , so it is indeed optimal to use the entire budget. Moreover, we cannot have  max  1, because the budget constraint would be violated: on [ max  1] the prize would be, higher than with  max = 1, and in order to have  −1 ( max ) =, the value of  would have to be lower than that with  max = 1, which implies a pointwise higher value of  −1 on [0  max ] than with 26 Even though  −1 may be discontinuous, because  −1 may be discontinuous, it is monotonic, so the change of variables applies. 27 The solution can be verified to be differentiable. 28 We will show that an optimal prize distribution  with differentiable inverse  −1 exists. No other prize distribution will lead to higher average performance, since the average performance corresponding to any prize distribution can be approximated arbitrarily closely by the average performance corresponding to a prize distribution with a differentiable inverse.
. Substituting the expression for  max into the expression for , and substituting the resulting expression for  into the expression for Substituting this  −1 into the objective, the aggregate performance This expression increases for  in [4 58], and decreases for  in [58]. 29 Therefore, this expression is the maximal aggregate performance for  in [4 58]. Any budget in excess of 58 will optimally not be used. 29 No budget above  will ever be used, since  is the cost of awarding all types the highest possible prize. To get a sense for this convergence of   and   to limit distributions  and , consider two extreme cases: asymmetric contests with complete information, and symmetric contests with incomplete information. A simple way to construct a converging sequence of contests with complete information is first to choose the desired limit distributions  and , and then to set player 's deterministic type in the -th contest to be    =  −1 () (so    is a Dirac distribution concentrated on    ) and prize  in the -th contest to be    =  −1 (), where Then, the -th contest is one of complete information,   converges to  , and   converges to .
One example is contests with identical prizes and players who differ in their valuations for a prize. For this, consider  () = ,  uniform, and  that has () = 1− for all  ∈ [0 1) and (1) = 1, where  ∈ (0 1) is the limit ratio of the number of identical (non-zero) prizes to the number of players. Then    = ,    = 0 if  ≤ 1 − , and    = 1 if   1 − . The -th contest is an all-pay auction with  players and pq identical (non-zero) prizes, and the value of a prize to player  is . Such contests were studied by CR, who considered competitions for promotions, rent seeking, and rationing by waiting in line.
Another example with complete information is contests with heterogeneous prizes and players who differ in their constant marginal valuation for a prize. For this, consider  () =  and  and  uniform. Then    =  and    = . The -th contest is an all-pay auction with  players and  heterogeneous prizes, and the value of prize  to player  is  2 .
Such contests were studied by BL, who considered hospitals that have a common ranking for residents and compete for them by posting wages. 1 Many other asymmetric contests with complete information can be accommodated, including contests for which no equilibrium characterization exists. One such class of examples, for which no equilibrium characterization exists, is contests with a combination of heterogeneous and identical prizes.
At the other extreme we have symmetric contests with incomplete information, in which players have the same iid type distributions    =   that converge to distribution  . This case includes the setting of MS. Beyond these extreme cases, our model also accommodates large contests with incomplete information and ex-ante asymmetric players. 2 No equilibrium characterization exists for such settings.

Assortative allocation and transfers
For example, in the setting corresponding to CR the assortative allocation assigns prize 0 to types  ≤ 1 −  and assigns one of the identical positive prizes to each type   1 − .
In the setting corresponding to BL, the assortative allocation assigns prize  to type , and the associated performance is   () =  2 2.
2 Comparative statics on the optimal prize distribution We restrict attention to linear costs  () =  and consider how varying the limit type distribution  affects the optimal prize distribution . For this let  () =  − (1 −  ())  ().
We denote by e  a second limit type distribution with corresponding optimal prize distribution e  (we will use˜for all the relevant variables under ). The case of a large budget and valuation function  is weakly convex, then Proposition 1 in the main text shows that the optimal prize distribution consists of a mass  of the highest possible prize and a mass 1 −  of prize 0. In particular, it is independent of the limit type distribution.
The remaining case of   (1 −  ( * )) and strictly concave  is less straightforward and more interesting. Unlike the case of a large budget, as long as   Proposition 1 Suppose that  is strictly concave and  () is weakly convex and strictly decreasing in . Then  −1 crosses e  −1 once, from below, and therefore e  SOSD .
The assumption in Proposition 1 that  () is decreasing implies that FOSD  . Thus, Proposition 1 roughly says that the optimal heterogeneity in prizes is lower when the population of contestants is sufficiently more able. The next result shows that under an additional condition every player type optimally obtains a lower prize when the population of contestants is sufficiently more able.
Proposition 2 Suppose that  is strictly concave,  () is weakly convex and strictly decreasing in , and e  () ≤  () for every type . Then e   () ≤   () for every type , that is, every type optimally obtains a lower prize under e  than under  .
The ranking e  ≤  holds, for example, when e  dominates  in the hazard ratio sense, which is implied by domination in the the likelihood ratio sense (so e  is a weakly increasing function). For a class of distributions that satisfy the conditions of Propositions 1 and 2, consider the family of cdf s   for   0. For any    0, let e  () =    and  () =   .
We have which is strictly decreasing and convex, since  − e   0. In addition, and  * = 1  + 1 . Figure 1: The optimal inverse prize distribution (left) and corresponding assortative allocations (right) for various values of  Consistent with Proposition 1, the optimal inverse prize distributions for lower values of  cross those for higher values of  once, from below, and are therefore more dispersed.
Consistent with Proposition 2, every type optimally obtains a lower prize as  increases. Note that as  increases the mass 1− * of types that obtain a prize increases (since  * = 1 ( + 1) decreases), but the set of types [ *  1] that obtain a prize shrinks (since  * = ( + 1) −1 increases).
We now consider the effect of increasing the budget  on the optimal prize distribution.
By Observation 1 in the main text, such an increase only has an effect when the budget is not large (  (1 −  ( * ))). In this case, the increase leads to a FOSD shift in the optimal prize distribution, for any distribution  and regardless of whether  is convex or concave. Every type obtains a weakly higher prize, because the type distribution does not change.
Proposition 3 If  is weakly convex or concave, an increase in the budget  leads to a FOSD shift in the optimal prize distribution. In particular, every type obtains a weakly higher prize.

Proofs
Proof of Proposition 1. We first observe that if  −1 crosses e  −1 once, from below, that is, if for some ∈ (0 1) we have  −1 () ≤ e  −1 () for  ∈ [0] and  −1 () ≥ e  −1 () for  ∈ [ 1], then e  SOSD . Indeed, since   (1 −  ( * )) and the condition on  () implies that e  FOSD  , we have that    If we had that   ≤   , where   and   are the shadow prices for the lower and higher budget, respectively, then we would also have that  −1  () ≤  −1  () for all  (see the proof of Proposition 2). But then the budget constraint would not hold with equality for the higher budget. Thus      , so  −1  () ≥  −1  () for all  (again, see the proof of Proposition 2), which is a FOSD shift in the optimal prize distribution.

Relaxing Assumption 1
We now discuss the optimal prize distribution for linear costs in the case when Assumption 1 is not satisfied. We will provide only heuristic, informal arguments, but the reader will see that making the arguments rigorous should not encounter any major difficulty.
Suppose that the range of 's is divided into a large number of small (infinitesimal) intervals, on which we will increase the value of  −1 progressively by small (infinitesimal) moves of a size ∆, until we exhaust the entire budget. By raising  −1 on such an interval by ∆, we increase, up to a first-order approximation, the objective function by  0 (·)(·)∆, where the value of  is taken at any point from the interval, and the value of  0 is taken at the current value of  −1 on this interval. However, in order to maintain the monotonicity of  −1 when we increase its value on an interval , we must increase its value also on all intervals  0 higher than  on which the value of  −1 is the same as that on . Thus, we always want to increase the value of  −1 on an interval  such that the average value of  0 (·)(·) across all intervals  0 is the highest.
When  is increasing, as assumed in the main text, the average value of  0 (·)(·) is initially the highest for the highest interval. So, we begin with raising  −1 on the highest interval by ∆. When, in addition,  0 is increasing, this makes the average value of  0 (·)(·) even higher for the highest interval, without affecting the average values for the other intervals. 3 So, we raise  −1 on the highest interval until we reach its bound of. Next, we raise  −1 on the second highest interval, and we continue in this manner until we exhaust the budget. This yields Proposition 1 in the main text.
When, in turn,  0 is decreasing (assume strictly for the sake of our argument), raising  −1 makes the average value of  0 (·)(·) lower for the highest interval. This ultimately makes the average highest for the second highest interval. (Notice that the average on the secondhighest interval will be equal just to the value on that interval, after we first raise the value on the highest interval.) And we will then begin raising  −1 on the second-highest interval.
We will never raise  −1 on the second-highest interval to a value strictly higher than that on the highest interval, because  is increasing. Ultimately, we will make the average highest on the third-highest interval. We will not stop until we reach the lowest interval, because any nontrivial increase in  −1 on an interval reduces  0 (·) by more than enough to offset the just slightly lower value of (·) on the adjacent lower interval. 4 This yields Proposition 2 in the main text.
These arguments imply a number of claims even when  is not increasing. Claim 1. If  is weakly convex, then the optimal prize distribution consists of: (1) a mass of prize and a mass of prize 0; or (2) a mass of prize, a mass of some intermediate prize  ∈ (0), and a mass of prize 0.
Indeed, notice that even though  is no longer increasing,  0 (·)(·) still takes the highest value on the highest interval , since (1) = 1 is the highest possible value of . Raising  −1 increases the value of  0 (·)(·) on the highest interval , without affecting the value on the intervals lower than . So, we keep raising  −1 on the highest  until reach the bound of . And then we go to the second highest interval. However, as  is no longer increasing, we may at some moment happen to go to an interval lower than the next highest one; and then we may exhaust the remaining budget before reaching the bound of on that interval  and all higher intervals on which the value of  −1 is the same as that on . If this happens, the optimal prize distribution has the form as described in (2). 4 Of course, the continuity of  (·) is essential here. Corollary 1 If  is weakly convex, and is sufficiently large, then the optimal prize distribution consists of a mass of prize and a mass of prize 0.
Indeed, the previous argument implies that the budget is exhausted at the highest intervals.
Claim 2. If  is strictly concave, then any optimal prize distribution assigns a positive mass to the set of intermediate prizes (0), and any optimal prize distribution awards all prizes up to the highest prize awarded. That is,  strictly increases on [0  −1 (1)].
As before, we first raise  −1 on the highest interval . Raising  −1 makes the value of  0 (·)(·) on  lower. This ultimately makes the value of  0 (·)(·) higher for the second highest interval. And we then begin raising  −1 on the second highest interval, and continue going down to lower and lower intervals. We will not stop until we exhaust the budget or run out of intervals on which (·) is positive, because any nontrivial increase in  −1 on any interval reduces  0 (·) by more than enough to offset a slightly lower value of (·) on the adjacent highest interval.
Notice, however, that we may make discrete jumps on the way down to lower and lower intervals when (·) takes higher values on lower intervals. This implies that even if  is strictly concave, an optimal prize distribution may have atoms at prizes other than 0 and. Finally, it can be readily checked that Claim 2, except the statement that  strictly increases on [0  −1 (1)], holds true even when  is only weakly concave but not linear on [0].