Optimal Rank Lotteries for Truthful Unit-Interval Covering

Abstract

In truthful interval covering, each agent has a private interval of unit length, and the goal is to decide where to place a public unit interval so as to minimize the total uncovered length while incentivizing the agents to be truthful. Previous work proposed a universally strategyproof lottery over order-statistic mechanisms with approximation ratio at most $5/3$, and established a lower bound of $3/2-o(1)$ for this class of mechanisms. We close this gap by characterizing the approximation ratio of every report-independent lottery over order-statistics. In particular, we show that, for every $n\ge 2$, the optimal approximation ratio for this class is $\frac{3}{2}-\frac{1}{2\lfloor n/2\rfloor }$. Beyond rank lotteries, we show that every universally strategyproof randomized mechanism has approximation ratio at least $9/8$.