Optimal Mechanism Design for Single-Minded Agents
Optimal Mechanism Design for Single-Minded Agents
复制标题
单心智能体的最优机制设计
DOI：
10.1145/3391403.3399454
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Weinberg, S. Matthew
中科院分区：
文献类型：
--
作者：
Devanur, Nikhil R.;Goldner, Kira;Saxena, Raghuvansh R.;Schvartzman, Ariel;Weinberg, S. Matthew
我们认为最佳的（收入最大化）机制设计的interdimensional设置，其中一个维度是“价值”的买家，另一个是一个“类型”，捕捉一些辅助信息。一个典型的例子是联邦快递问题，Fiat et al. [2016]描述了单个代理的最佳机制。另一个例子是当类型编码买方的预算[DW 17]。我们要解决的问题是，这种特征化能走多远。特别是，我们考虑了专一代理的设置。卖家有不同的商品。一个购买者对一个特定的物品子集S有一个估价v，只有当他得到S中的所有物品（可能还有其他一些物品）时，他才能得到价值vif和。确定性机制（即公布价格）对于满足“边际收益递减”（DMR）属性的分配是最优的。在这种情况下，我们给出了一个明确的最佳机制的建设。在没有DMR假设的情况下，结果取决于表示类型之间的偏序的最小有向无环图（DAG）的结构。当DAG的出度最多为1时，我们将最优机制刻画为FedEx;这可以被认为是FedEx刻画的推广，因为FedEx对应的DAG是一条线。令人惊讶的是，如果没有DMR假设，当DAG至少有一个节点的出度至少为2时，我们证明了这种特征是没有希望的。最小的这样的例子发生在具有3个类型的DAG上。我们证明了在这种情况下菜单复杂度是无界的，对于任意M，存在分布在（v，S）对上，使得最优机构的菜单复杂度至少为M。对于3种类型的情况，我们还表明，对于所有的分布都存在一个最优机制的finitemenu复杂性。这是在相反的情况下，你有2个异质项目与添加剂的效用，菜单的复杂性可能是不可数无限[DDT 15，MV 07]。此外，我们证明了最优机制，多单位定价（没有DMR假设）也可以有无限的菜单复杂性，我们进一步提出了一个扩展，其中最佳机制的菜单复杂性可以是可数无限的，但不是无限的总之，这些结果表明，在跨维度设置的最佳机制都令人惊讶地丰富比单维设置，但也大大比多维设置更有结构。
We consider optimal (revenue maximizing) mechanism design in the interdimensional setting, where one dimension is the 'value' of the buyer, and the other is a 'type' that captures some auxiliary information. A prototypical example of this is the FedEx Problem, for which Fiat et al. [2016] characterize the optimal mechanism for a single agent. Another example of this is when the type encodes the buyer's budget [DW17]. The question we address is how far can such characterizations goIn particular, we consider the setting of single-minded agents. A seller has heterogenous items. A buyer has a valuation vfor a specific subset of items S, and obtains value vif and only if he gets all the items in S(and potentially some others too).We show the following results. Deterministic mechanisms (i.e. posted prices) are optimal for distributions that satisfy the "declining marginal revenue" (DMR) property. In this case we give an explicit construction of the optimal mechanism. Without the DMR assumption, the result depends on the structure of the minimal directed acyclic graph (DAG) representing the partial order among types. When the DAG has out-degree at most 1, we characterize the optimal mechanism àla FedEx; this can be thought of as a generalization of the FedEx characterization since FedEx corresponds to a DAG that is a line. Surprisingly, without the DMR assumption andwhen the DAG has at least one node with an out-degree of at least 2, then we show that there is no hope of such a characterization. The minimal such example happens on a DAG with 3 types. We show that in this case the menu complexity is unboundedin that for any M, there exist distributions over (v,S) pairs such that the menu complexity of the optimal mechanism is at least M. For the case of 3 types, we also show that for all distributions there exists an optimal mechanism of finitemenu complexity. This is in contrast to the case where you have 2 heterogenous items with additive utilities for which the menu complexity could be uncountably infinite [DDT15, MV07].In addition, we prove that optimal mechanisms for Multi-Unit Pricing (without a DMR assumption) can have unbounded menu complexity as well, and we further propose an extension where the menu complexity of optimal mechanisms can be countably infinite, but not uncountably infinite. Taken together, these results establish that optimal mechanisms in interdimensional settings are both surprisingly richer than single-dimensional settings, yet also vastly more structured than multi-dimensional settings.
登录
查看更多内容
均匀分布拍卖的二元性和最优性
DOI：
10.1145/2600057.2602883
发表时间：
2014
期刊：
Proceedings of the fifteenth ACM conference on Economics and computation
影响因子：
--
作者：
Yiannis Giannakopoulos;E. Koutsoupias
通讯作者：
E. Koutsoupias
满足私人需求的最优多单元机制
DOI：
--
发表时间：
2017
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Nikhil R. Devanur;Nima Haghpanah;Alexandros Psomas
通讯作者：
Alexandros Psomas
彩票定价
DOI：
--
发表时间：
2015
期刊：
Journal of Economics Theory
影响因子：
--
作者：
Patrick Briest;Shuchi Chawla;Robert D. Kleinberg;S. Weinberg
通讯作者：
S. Weinberg
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Y. Lequain
通讯作者：
Y. Lequain
DOI：
10.1145/2764468.2764539
发表时间：
2014-09
期刊：
Proceedings of the Sixteenth ACM Conference on Economics and Computation
影响因子：
--
作者：
C. Daskalakis;Alan Deckelbaum;Christos Tzamos
通讯作者：
C. Daskalakis;Alan Deckelbaum;Christos Tzamos