# The menu complexity of “one-and-a-half-dimensional” mechanism design

## Author(s): Saxena, Raghuvansh R; Schvartzman, Ariel; Weinberg, S Matthew

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr1d54d`

Abstract: | We study the menu complexity of optimal and approximately-optimal auctions in the context of the “FedEx” problem, a so-called “one-and-a-halfdimensional” setting where a single bidder has both a value and a deadline for receiving an item [FGKK16]. The menu complexity of an auction is equal to the number of distinct (allocation, price) pairs that a bidder might receive [HN13]. We show the following when the bidder has n possible deadlines: • Exponential menu complexity is necessary to be exactly optimal: There exist instances where the optimal mechanism has menu complexity ≥ 2 n −1. This matches exactly the upper bound provided by Fiat et al.’s algorithm, and resolves one of their open questions [FGKK16]. • Fully polynomial menu complexity is necessary and sufficient for approximation: For all instances, there exists a mechanism guaranteeing a multiplicative (1 − )-approximation to the optimal revenue with menu complexity O(n 3/2 q min{n/ ,ln(vmax)} ) = O(n 2/ ), where vmax denotes the largest value in the support of integral distributions. • There exist instances where any mechanism guaranteeing a multiplicative (1 − O(1/n2 ))-approximation to the optimal revenue requires menu complexity Ω(n 2 ). Our main technique is the polygon approximation of concave functions [Rot92], and our results here should be of independent interest. We further show how our techniques can be used to resolve an open question of [DW17] on the menu complexity of optimal auctions for a budget-constrained buyer. |

Publication Date: | 2018 |

Citation: | Saxena, Raghuvansh R., Ariel Schvartzman, and S. Matthew Weinberg. "The menu complexity of “one-and-a-half-dimensional” mechanism design." In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2026-2035. doi:10.1137/1.9781611975031.132 |

DOI: | 10.1137/1.9781611975031.132 |

Pages: | 2026 - 2035 |

Type of Material: | Conference Article |

Journal/Proceeding Title: | Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.