Hallucinating Flows for Optimal Mechanisms

Myerson’s seminal characterization of the revenue-optimal auction for a single item remains a cornerstone of mechanism design. However, generalizing this framework to multi-item settings has proven exceptionally challenging. Even under restrictive assumptions, closed-form characterizations of optimal mechanisms are rare and are largely confined to the single-agent case, departing from the two-item setting only when prior distributions are uniformly distributed. In this work, we build upon the bi-valued setting introduced by Yao (EC 2017), where each item’s value has support 2 and lies in $\{a,b\}$. Yao’s result provides the only known closed-form optimal mechanism for multiple agents. We extend this line of work along three natural axes, establishing the first closed-form optimal mechanisms in each of the following settings: (i) $n$ i.i.d. agents and $m$ i.i.d. items, (ii) $n$ non-i.i.d. agents and two i.i.d. items, and (iii) $n$ i.i.d. agents and two non-i.i.d. items. Our results lie at the limit of what is considered possible, since even with a single agent and $m$ bi-valued non-i.i.d. items, finding the optimal mechanism is #P-Hard. We finally generalize the discrete analog of a result from Daskalakis et al. (Econometrica 2017), showing that for a single agent with $m$ items drawn from arbitrary (non-identical) discrete distributions, grand bundling is optimal when all item values are sufficiently large. We further show that for any continuous product distribution, grand bundling achieves $\mathsf{OPT} - \epsilon$ revenue for large enough values.