← 研踪 PaperTrailarXiv: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
摘要
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 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 guarantee always holds with at most three buyers.
作者备注:4 pages
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 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 guarantee always holds with at most three buyers.
查看此版本解读 →查看此版本原文 ↗