Dynamic pricing schemes were introduced as an alternative to posted-price mechanisms. In contrast to static models, the dynamic setting allows to update the prices between buyer-arrivals based on the remaining sets of items and buyers, and so it is capable of maximizing social welfare without the need for a central coordinator. In this paper, we study the existence of optimal dynamic pricing schemes in combinatorial markets. In particular, we concentrate on multi-demand valuations, a natural extension of unit-demand valuations. The proposed approach is based on computing an optimal dual solution of the maximum social welfare problem with distinguished structural properties. Our contribution is twofold. By relying on an optimal dual solution, we show the existence of optimal dynamic prices in unit-demand markets and in multi-demand markets up to three buyers, thus giving new interpretations of results of Cohen-Addad et al. and Berger et al. , respectively. Furthermore, we provide an optimal dynamic pricing scheme for bi-demand valuations with an arbitrary number of buyers. In all cases, our proofs also provide efficient algorithms for determining the optimal dynamic prices.
翻译:动态定价计划是作为上市价格机制的替代物而引入的。与静态模式相反,动态环境允许根据剩余一批物品和买主更新买家之间的价格,从而能够在不需要中央协调员的情况下实现社会福利最大化。在本文中,我们研究了在组合市场中存在最佳动态定价计划的问题。我们特别侧重于多需求估值,即单位-需求估值的自然延伸。拟议方法的基础是计算具有独特结构特性的最大社会福利问题的最佳双向解决方案。我们的贡献是双重的。我们依靠一种最佳的双向解决方案,表明在单位-需求市场和多达三个多需求市场中存在最佳动态价格,从而分别对Chohen-Addad等人和Berger等人的结果作出新的解释。此外,我们为双需求估值提供了最佳动态定价计划,并有任意数量的买家。在所有情况下,我们的证据也为确定最佳动态价格提供了高效的算法。