arXiv cs.AI· Trung Thanh Nguyen, Khaled Elbassioni, J\"{o}rg Rothe·· 3 天前AI 评分10
加权最大最小份额分配不可分杂务的近似比上界改进
Improving the Bounds on Approximating Weighted Maximin Share for Chores
AI 导读
针对任意正权重与加性非负成本函数下的不可分杂务分配问题，研究证明每个实例都存在 4.124234528-WMMS 公平分配，并给出在权重与成本均为二进制有理数时，可在多项式时间内计算出 4.12424-WMMS 分配的算法。同时构造出一族成本严格为正且排序相同的实例，其最优 WMMS 近似因子收敛到 e，从而将此前 Li 等人给出的 [2,12] 区间收窄至 [e,4.12424]。
正文 · AI 翻译
摘要：我们研究在具有任意正权重和可加非负成本函数的智能体之间分配不可分割杂务的问题。若每个智能体产生的成本至多为其加权最大最小份额的 $\alpha$ 倍，则称该分配是 $\alpha$-加权最大最小份额（WMMS）公平的。我们证明每个实例都允许一个 $4.124234528$-WMMS 分配。此外，对于所有权重和成本均为以二进制表示的有理数的实例，我们给出一个算法，可在关于智能体数量、杂务数量以及输入总二进制编码长度的多项式时间内计算出一个 $4.12424$-WMMS 分配。作为这些上界的补充，我们构造了一族具有严格正且顺序相同的成本的实例，其最优 WMMS 近似因子收敛到 $e$。综合来看，我们的结果将 Li 等人~\cite{LWX26} 所建立的前已知最佳差距 $[2,12]$ 大幅缩小至 $[e,4.12424]$。
| 学科： | 计算机科学与博弈论（cs.GT）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.15520 [cs.GT] |
| （或 arXiv:2610.15520v1 [cs.GT] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.15520 arXiv 颁发的 DOI 通过 DataCite（待注册） |
提交历史
来自：Trung Nguyen [查看电子邮件]
[v1]
2026年10月11日星期日 10:37:27 UTC（64 KB）
来源：arXiv cs.AI · arxiv.org