跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文,不再错过。

覆盖计算机全学科,以 AI 为快捷入口。关注方向、作者和关键词,把发现变成持续的研究积累。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+367新增论文
+288其中 AI 相关
+33已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描:2026-11-09 10:18 · 全站最近入库:2026-11-09 10:17各信源进度 →

统计口径与数据新鲜度

统计 2026-11-08 10:46 — 2026-11-09 10:46(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-09 10:18最近发现新增版本:2026-11-09 10:17库内论文最新更新时间:2026-11-06 12:44

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

17,467 已收录论文14,949 AI 相关4,222 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-09 10:16(北京时间)
版本更新 · v3arXiv:2609.35711

论多物品拍卖中确定性的力量

On the Power of Determinism in Multi-Item Auctions

Yiannis Giannakopoulos, Johannes Hahn

AI 速读 基于摘要

作者研究单一加性买家、多件独立非同分布物品的垄断拍卖,通过拉格朗日对偶上界改进三种简单确定性拍卖相对最优真实拍卖收益的近似比。

cs.GT · cs.DM

查看原文摘要

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max\{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots,1\}$, for any discretization parameter $K$. Taking $K\to\infty$ yields the tight ratio $1+W(1/e)\approx1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.