Optimal Contest Beyond Convexity
A new paper proves the best way to incentivize effort is to give top prize to #1, zero to last, and equal prizes to everyone else.
A team of computer scientists has cracked a fundamental problem in contest design, a classic area of game theory and mechanism design. In their STOC'26 paper 'Optimal Contest Beyond Convexity,' Negin Golrezaei, MohammadTaghi Hajiaghayi, and Suho Shin asked: how should a designer with a fixed budget allocate prizes to contestants based on their ranked performance to best incentivize costly effort? Their surprising answer is a simple, universal structure: give the highest possible prize to the first-place finisher, give zero to the last-place finisher, and give equal prizes to every single contestant in the middle ranks.
This result is powerful because it holds for a vast range of objectives a designer might have, including non-convex goals that were previously intractable. These objectives subsume classic measures like maximizing social welfare, the average quality of outcomes, or even complex 'S-shaped' functions relevant to recommender systems. The researchers achieved this by connecting the problem to advanced mathematical concepts like Schur-convexity and the total positivity of Bernstein polynomials. Crucially, their structural characterization enables a fully polynomial-time approximation scheme (FPTAS), turning a complex high-dimensional optimization into a solvable problem. This provides a practical tool for designing everything from online competitions to internal corporate incentive schemes.
- Proves optimal prize structure is 'top-heavy, bottom-zero, middle-flat': p₁ ≥ p₂ = ... = pₙ₋₁ ≥ pₙ = 0.
- Applies to broad, non-convex objectives including social welfare and S-shaped functions, solving previously open problems.
- Provides a fully polynomial-time approximation scheme (FPTAS), making optimal contest design computationally feasible.
Why It Matters
Provides a mathematically proven blueprint for designing effective competitions and incentive systems in tech platforms, hiring, and innovation challenges.