Optimal Contest beyond Convexity

In the contest design problem, initiated by Lazear and Rosen (JPE’81), there are n strategic contestants, each of whom decides an effort level. A contest designer with a fixed budget must then design a mechanism that allocates a prize pi to the i-th rank based on the outcome, to incentivize contestants to exert higher costly efforts and induce high-quality outcomes. In this paper, we significantly deepen our understanding of optimal mechanisms in the complete information setting by considering nonconvex objective functions in contestants’ qualities. Notably, our results accommodate the following objective functions: (i) any convex combination of user welfare (motivated by recommender systems) and the average quality of contestants that is neither convex nor concave, (ii) arbitrary posynomials over quality. In particular, these subsume classic measures in mechanism design such as social welfare, order statistics, and (inverse) S-shaped functions, which have received little or no attention in the contest literature to the best of our knowledge. Surprisingly, across all these regimes, we show that the optimal mechanism is highly structured: it allocates potentially higher prize to the first-ranked contestant, zero to the last-ranked one, and equal prizes to the all intermediate contestants, p1 ≥ p2 = … = pn−1 ≥ pn = 0. In some special cases, we observe a stark phase transition between two extreme mechanisms: (i) policy (p1 = 1, p2 = … = pn = 0) and (ii) policy (p1 = … = pn−1=1/(n−1), pn = 0) depending on the objective and cost function, cementing and unifying evidences witnessed in the literature. More importantly, thanks to the structural characterization, we obtain a fully polynomial-time approximation scheme given a value oracle. Our technical results rely on Schur-convexity (or concavity) of Bernstein basis polynomial–weighted functions, total positivity and variation diminishing property. En route to our results, we obtain a surprising reduction from a structured high-dimensional nonconvex optimization to a single-dimensional optimization by connecting the shape of the gradient sequences of the objective function to the number of transition points in optimum, which might be of independent interest.