跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.24920 · v1

The Optimal Competitive Ratio for Subadditive Online Combinatorial Auctions is Less Than 1/2

次可加在线组合拍卖的最优竞争比小于1/2

首次提交 2026-11-19 02:49
版本更新 2026-11-19 02:49
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

We construct a four-buyer online combinatorial auction with independent subadditive valuations and a fixed, known arrival order in which every online rule earns strictly less than 1/21/2 of the expected offline optimum. A common partition, revealed at the third arrival, gives the first three buyers one unit of welfare per item. If the rule uses three distinct partitions, either an item allocated early contributes zero or the fourth buyer's expected value for the remaining bundle is one less than its size. We compute the optimal online and offline welfare exactly and show that a 1/21/2 guarantee always holds with at most three buyers.

作者备注:4 pages

AI 论文解读

基于摘要 · 非全文审阅

作者构造了一个四买家在线组合拍卖实例,证明任何在线规则都无法达到1/2的竞争比,而三个买家时1/2的保证总是成立。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 02:49 · 最新观测版本

The Optimal Competitive Ratio for Subadditive Online Combinatorial Auctions is Less Than 1/2

We construct a four-buyer online combinatorial auction with independent subadditive valuations and a fixed, known arrival order in which every online rule earns strictly less than 1/21/2 of the expected offline optimum. A common partition, revealed at the third arrival, gives the first three buyers one unit of welfare per item. If the rule uses three distinct partitions, either an item allocated early contributes zero or the fourth buyer's expected value for the remaining bundle is one less than its size. We compute the optimal online and offline welfare exactly and show that a 1/21/2 guarantee always holds with at most three buyers.

查看此版本解读 →查看此版本原文 ↗