On the Power and Limits of Dynamic Pricing in Combinatorial Markets
On the Power and Limits of Dynamic Pricing in Combinatorial Markets
复制标题
论组合市场动态定价的力量和局限性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
M. Feldman
中科院分区：
文献类型：
--
作者：
Ben Berger;Alon Eden;M. Feldman
我们研究了组合市场中最优动态定价的能力和极限，即，动态定价能带来最优的社会福利。Cohen-Addad等人[EC'16]以前的工作证明了单位需求买家的最优动态价格的存在，并显示了一个不承认这种价格的覆盖估值市场。然而，找到市场的前沿（即，估值函数），承认最优动态价格仍然是一个开放的问题。在这项工作中，我们建立了积极和消极的结果，缩小了现有的差距。
从积极的一面来看，我们提供了超越单位需求估值的市场处理工具。特别是，我们描述了多需求市场中的所有最优分配。这个特征允许我们根据它们在实现最优性中所起的作用将项目划分为等价类。使用这些工具，我们提供了一个多时间最优的动态定价算法高达3美元的多需求买家。
在消极的一面，我们建立了一个最大域定理，表明对于每一个非总替代品的估值，存在单位需求估值，使他们加入产生一个市场，不承认一个最优的动态定价。这一结果是动态定价等价于Gul和Stacchetti [JET'99]的Walrasian均衡的最大域定理。杨[JET'17]在他们的原始证明中发现了一个错误，并建立了一个不同的，无与伦比的版本的最大域定理。在我们的最大域定理的最优动态定价，我们提供了第一个完整的证明，原来的定理由古尔和Stacchetti。
We study the power and limits of optimal dynamic pricing in combinatorial markets; i.e., dynamic pricing that leads to optimal social welfare. Previous work by Cohen-Addad et al. [EC'16] demonstrated the existence of optimal dynamic prices for unit-demand buyers, and showed a market with coverage valuations that admits no such prices. However, finding the frontier of markets (i.e., valuation functions) that admit optimal dynamic prices remains an open problem. In this work we establish positive and negative results that narrow the existing gap.
On the positive side, we provide tools for handling markets beyond unit-demand valuations. In particular, we characterize all optimal allocations in multi-demand markets. This characterization allows us to partition the items into equivalence classes according to the role they play in achieving optimality. Using these tools, we provide a poly-time optimal dynamic pricing algorithm for up to $3$ multi-demand buyers.
On the negative side, we establish a maximal domain theorem, showing that for every non-gross substitutes valuation, there exist unit-demand valuations such that adding them yields a market that does not admit an optimal dynamic pricing. This result is the dynamic pricing equivalent of the seminal maximal domain theorem by Gul and Stacchetti [JET'99] for Walrasian equilibrium. Yang [JET'17] discovered an error in their original proof, and established a different, incomparable version of their maximal domain theorem. En route to our maximal domain theorem for optimal dynamic pricing, we provide the first complete proof of the original theorem by Gul and Stacchetti.
多单位市场定价
DOI：
--
发表时间：
2018
期刊：
14th Conference on Web and Internet Economics (WINE
影响因子：
--
作者：
Ezra, Tomer;Feldman, Michal;Roughgarden, Tim;Suksompong, Warut
通讯作者：
Suksompong, Warut