The menu complexity of "one-and-a-half-dimensional" mechanism design
The menu complexity of "one-and-a-half-dimensional" mechanism design
复制标题
“一维半”机制设计的菜单复杂度
DOI：
10.1137/1.9781611975031.132
复制
发表时间：
2017
影响因子：
1.2
通讯作者：
S. Weinberg
中科院分区：
文献类型：
--
作者：
Raghuvansh R. Saxena;Ariel Schvartzman;S. Weinberg
我们在“联邦快递”问题的背景下研究了最佳和大约最佳拍卖的菜单复杂性，这是一个所谓的“一个半维度”的设置，其中单个出价者既有价值又有一个截止日期接收[FGKK16]。拍卖的菜单复杂性等于投标人可能会收到的不同（分配，价格）对的数量[HN13]。当投标人有$ n $可能的截止日期时，我们显示以下内容：
- 指数菜单复杂性是必要的，才能确切最佳：存在最佳机制具有菜单复杂性为$ 2^n-1 $的实例。这与Fiat等人的算法提供的上限完全匹配，并解决了他们的开放问题之一[FGKK16]。
- 完全多项式菜单复杂性是必要的，足以近似：对于所有情况，都存在一种机制，可以保证乘法（1- \ epsilon） - 对最佳收入的应用，并具有菜单复杂性$ o（n^{3/2} \ sqrt {\ frac {\ min \ {n/\ epsilon，\ ln（v _ {\ max}）}}}} {\ epsilon}} \ epsilon）$，其中$ v _ {\ max} $表示支持的最大价值积分分布。
- 存在任何保证乘法$（1-o（1/n^2））$的机制 - 与最佳收入的近似近似需要菜单复杂性$ \ omega（n^2）$。
我们的主要技术是凹功能的多边形近似[ROTE19]，我们在这里的结果应该具有独立的关注。我们进一步展示了如何使用我们的技术来解决针对预算受限的买家的最佳拍卖的菜单复杂性[DW17]的开放问题。
We study the menu complexity of optimal and approximately-optimal auctions in the context of the "FedEx" problem, a so-called "one-and-a-half-dimensional" setting where a single bidder has both a value and a deadline for receiving an [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 is $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-\epsilon)-approximation to the optimal revenue with menu complexity $O(n^{3/2}\sqrt{\frac{\min\{n/\epsilon,\ln(v_{\max})\}}{\epsilon}}) = O(n^2/\epsilon)$, where $v_{\max}$ 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 $\Omega(n^2)$.
Our main technique is the polygon approximation of concave functions [Rote19], 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.