2025/10/07 by Mertzanidis, Marios, Terzoglou, Athina
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2510.05474
Myerson's seminal characterization of the revenue-optimal auction for a single item \citemyerson1981optimal 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 \citepavlov2011optimal,hart2017approximate, daskalakis2018transport, GIANNAKOPOULOS2018432, departing from the two-item setting only when prior distributions are uniformly distributed \citemanelli2006bundling, daskalakis2017strong,giannakopoulos2018sjm. In this work, we build upon the bi-valued setting introduced by Yao \citeYAOBICDSIC, 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 \citedaskalakis2014complexity, xi2018soda. We finally generalize the discrete analog of a result from~\citedaskalakis2017strong, 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 OPT - ε revenue for large enough values.