跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

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

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

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

统计口径与数据新鲜度

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

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-17 23:35库内论文最新更新时间:2026-11-17 02:59

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

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

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

找到 1 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.05360

小规模智能体冗余下的近似MMS分配

Almost-MMS allocations with small agent redundancy

Uriel Feige, Vadim Grinberg

AI 速读 基于摘要

作者证明:在加法估值下,若智能体数量比物品分配所需多出εn的冗余,则n-maximin share(MMS)的近似保证ρ_{ε,n}随n增长趋于1。

cs.GT

查看原文摘要

For a fixed $ε\ge 0$, let $ρ_{ε, n}$ be the maximum value of $ρ_n$ such that, in every allocation instance with $m$ indivisible goods and $(1 + ε)n$ agents, there is a subset of $n$ agents with the following property. The allocation instance restricted to only this subset of $n$ agents has an allocation that gives each agent at least $ρ_n$-fraction of her $n$-maximin share (MMS). When $ε> 0$ we refer to $εn$ as the {\em agent redundancy}. The case $ε= 0$ is the standard setting without agent redundancy, and we use $ρ_{0,n}$ and $ρ_n$ interchangeably. For allocation instances with additive valuations, % agents, it is known that $\frac{7}{9} \le ρ_n < 1-Ω(\frac{1}{\log^2 n})$ for every $n \ge 2$ (with stronger lower bounds for small $n$). It is an open question whether $ρ_n$ tends to~1 as $n$ grows. We show that with agent redundancy, the answer to this question is positive. That is, for every $ε> 0$, $ρ_{ε, n}$ tends to~1 as $n$ grows. A straightforward corollary of this result is that for every $c > 0$, if the number of items satisfies $m \le (2 - c)n$, then the answer is positive also for $ρ_n$ (with no agent redundancy). Adapting our techniques to a related setting, we also improve a recent result of Ezra and Garbuz, and show that without agent redundancy, there always exists an allocation that gives $n - O(\log^2 n)$ agents their full MMS.