Hallucinating Flows for Optimal Mechanisms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915535765110784 |
|---|---|
| author | Mertzanidis, Marios Terzoglou, Athina |
| author_facet | Mertzanidis, Marios Terzoglou, Athina |
| contents | Myerson's seminal characterization of the revenue-optimal auction for a single item \cite{myerson1981optimal} 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 \cite{pavlov2011optimal,hart2017approximate, daskalakis2018transport, GIANNAKOPOULOS2018432}, departing from the two-item setting only when prior distributions are uniformly distributed \cite{manelli2006bundling, daskalakis2017strong,giannakopoulos2018sjm}. In this work, we build upon the bi-valued setting introduced by Yao \cite{YAO_BIC_DSIC}, 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 \cite{daskalakis2014complexity, xi2018soda}. We finally generalize the discrete analog of a result from~\cite{daskalakis2017strong}, 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 $\mathrm{OPT} - ε$ revenue for large enough values. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_05474 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hallucinating Flows for Optimal Mechanisms Mertzanidis, Marios Terzoglou, Athina Computer Science and Game Theory Myerson's seminal characterization of the revenue-optimal auction for a single item \cite{myerson1981optimal} 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 \cite{pavlov2011optimal,hart2017approximate, daskalakis2018transport, GIANNAKOPOULOS2018432}, departing from the two-item setting only when prior distributions are uniformly distributed \cite{manelli2006bundling, daskalakis2017strong,giannakopoulos2018sjm}. In this work, we build upon the bi-valued setting introduced by Yao \cite{YAO_BIC_DSIC}, 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 \cite{daskalakis2014complexity, xi2018soda}. We finally generalize the discrete analog of a result from~\cite{daskalakis2017strong}, 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 $\mathrm{OPT} - ε$ revenue for large enough values. |
| title | Hallucinating Flows for Optimal Mechanisms |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2510.05474 |