## Abstract

We explore the approximation power of deterministic obviously strategy-proof mechanisms in auctions, where the objective is welfare maximization. A trivial ascending auction on the grand bundle guarantees an approximation of min{m, n} for all valuation classes, where m is the number of items and n is the number of bidders. We focus on two classes of valuations considered “simple”: additive valuations and unit-demand valuations. For additive valuations, Bade and Gonczarowski [EC'17] have shown that exact welfare maximization is impossible. No impossibilities are known for unit-demand valuations. We show that if bidders' valuations are additive or unit-demand, then no obviously strategy-proof mechanism gives an approximation better than min{m, n}. Thus, the aforementioned trivial ascending auction on the grand bundle is the optimal obviously strategy-proof mechanism. These results illustrate a stark separation between the power of dominant-strategy and obviously strategy-proof mechanisms. The reason for it is that for both of these classes the dominant-strategy VCG mechanism does not only optimize the welfare exactly, but is also “easy” both from a computation and communication perspective. In addition, we prove tight impossibilities for unknown single-minded bidders in a multi-unit auction and in a combinatorial auction. We show that in these environments as well, a trivial ascending auction on the grand bundle is optimal.

Original language | English |
---|---|

Title of host publication | Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Editors | David P Woodruff |

Pages | 19-40 |

Number of pages | 22 |

ISBN (Electronic) | 978-1-61197-791-2 |

DOIs | |

Publication status | Published Online - 4 Jan 2024 |

Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |

### Conference

Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|

Country/Territory | United States |

City | Alexandria |

Period | 7/1/24 → 10/1/24 |

### Bibliographical note

Supported by an Azrieli Foundation fellowship, ISF grant2185/19, and BSF-NSF grant (BSF number: 2021655, NSF number: 2127781). Part of the work was done while the author wasat residence in Simons Laufer Mathematical Sciences Institute, supported by the National Science Foundation (grant numberDMS-1928930)Publisher Copyright:

Copyright © 2024 This paper is available under the CC-BY 4.0 license.

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics