TY - GEN

T1 - The menu complexity of "one-and-a-half-dimensional" mechanism design

AU - Saxena, Raghuvansh R.

AU - Schvartzman, Ariel

AU - Weinberg, S. Matthew

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 2018

Y1 - 2018

N2 - 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 ≥ 2n-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=n2))-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.

AB - 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 ≥ 2n-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=n2))-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.

UR - http://www.scopus.com/inward/record.url?scp=85045565590&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045565590&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.132

DO - 10.1137/1.9781611975031.132

M3 - Conference contribution

AN - SCOPUS:85045565590

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2026

EP - 2035

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

A2 - Czumaj, Artur

PB - Association for Computing Machinery

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

Y2 - 7 January 2018 through 10 January 2018

ER -