### 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 neces-sary and sufficient for approximation: For all instances, there exists a mechanism guaranteeing a multiplicative (1-n)-approximation to the optimal revenue with menu complexity O(n3=2 q minfn;ln(vmax)g) = O(n2/n), where vmax denotes the largest value in the support of integral distributions. There exist instances where any mechanism guaranteeing a multiplicative (1- O(1=n^{2}))-approximation to the optimal revenue requires menu complexity (n2). 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.

Original language | English (US) |
---|---|

Title of host publication | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |

Editors | Artur Czumaj |

Publisher | Association for Computing Machinery |

Pages | 2026-2035 |

Number of pages | 10 |

ISBN (Electronic) | 9781611975031 |

DOIs | |

State | Published - Jan 1 2018 |

Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States Duration: Jan 7 2018 → Jan 10 2018 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |
---|---|

Country | United States |

City | New Orleans |

Period | 1/7/18 → 1/10/18 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'The menu complexity of "one-and-a-half-dimensional" mechanism design'. Together they form a unique fingerprint.

## Cite this

*29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018*(pp. 2026-2035). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.132