Online Combinatorial Auctions
Online Combinatorial Auctions
复制标题
在线组合拍卖
DOI：
10.1137/1.9781611976465.70
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zhang, Hanrui
中科院分区：
文献类型：
--
作者：
Deng, Yuan;Panigrahi, Debmalya;Zhang, Hanrui
我们研究在线环境中的组合拍卖，目标是社会福利最大化。在此问题中，每天都有新商品上市，并且必须在其各自的到期日期之前售出。我们为广泛研究的子模块和 XOS 估值类别设计了在线拍卖，并显示了以下结果： - 对于子模块估值，我们给出了对抗性估值的 O(logm) 竞争机制和贝叶斯估值的 O(1) 竞争机制，其中是项目总数。这两种机制对于短视智能体（即不了解未来的智能体）来说计算效率高且普遍真实。对于 XOS 估值，我们表明即使在贝叶斯设置中也没有在线机制可以实现 o((m/logm)1/3) 的竞争比。即使我们不要求机制的真实性和/或计算效率，我们的下限也成立。这在 XOS 估值与其在线组合拍卖的子模块估值子类之间建立了鲜明的分离。相比之下，离线拍卖不存在这种分离，其中子模块和 XOS 估值的最佳界限对于对抗性设置（Assadi 和 Singla，FOCS 2019）为 O((log logm)3)，对于贝叶斯设置（Düttinget al., FOCS 2017）为 O(1)。与上述相反，如果物品不会过期并且只需要在市场收盘前出售，那么我们会给出以下折扣：离线到在线机制，保留所有子附加估值（包括 XOS 和子模块估值）的竞争比，从而实现与各自最佳离线机制相同的界限。
We study combinatorial auctions in online environments with the goal of maximizing social welfare. In this problem, new items become available on each day and must be sold before their respective expiration dates. We design online auctions for the widely studied classes of submodular and XOS valuations, and show the following results:– For submodular valuations, we give anO(logm)-competitive mechanism for adversarial valuations and anO(1)-competitive mechanism for Bayesian valuations, wheremis the total number of items. Both these mechanisms are computationally efficient and universally truthful for myopic agents, i.e., agents with no knowledge of the future.– For XOS valuations, we show that there is no online mechanism that can achieve a competitive ratio ofo((m/logm)1/3) even in a Bayesian setting. Our lower bound holds even if we do not require truthfulness and/or computational efficiency of the mechanism.This establishes a sharp separation between XOS valuations and its subclass of submodular valuations for online combinatorial auctions. In contrast, no such separation exists for offline auctions, where the best bounds for both submodular and XOS valuations areO((log logm)3) for adversarial settings (Assadi and Singla, FOCS 2019) andO(1) for Bayesian settings (Düttinget al., FOCS 2017).In contrast to the above, if items do not expire and only need to be sold before the market closes, then we give a reduction from offline to online mechanisms that preserves the competitive ratio for all subadditive valuations (that includes XOS and submodular valuations), thereby achieving the same bounds as the respective best offline mechanisms.
登录
查看更多内容
次加法组合拍卖的 O(log log m) 预言不等式
DOI：
--
发表时间：
2020
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Paul Dütting;Thomas Kesselheim;Brendan Lucier
通讯作者：
Brendan Lucier
使用（近似）次加性代理改进组合福利最大化的预言不等式
DOI：
--
发表时间：
2022
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Hanrui Zhang
通讯作者：
Hanrui Zhang
影响因子：
8.2
作者：
N. Nisan
通讯作者：
N. Nisan
DOI：
--
发表时间：
2008
期刊：
Algorithmic Game Theory
影响因子：
--
作者：
Richard Cole;Shahar Dobzinski;Lisa Fleischer
通讯作者：
Lisa Fleischer
DOI：
--
发表时间：
2012
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Shahar Dobzinski;J. Vondrák
通讯作者：
J. Vondrák