在未知物品价值下，公平分配资源并最大化最低收益。
Bandit Max-Min Fair Allocation
- 结合带子博弈与资源分配算法，动态调整分配策略。
- 理论证明最大遗憾上界为 $O(m oot{T}{\ln T}/n + m\sqrt{T \ln(mnT)})$。
- 适用于多智能体公平分配场景，如资源调度、在线匹配等。
本文研究一种新型决策问题——带子最大最小公平分配（BMMFA）问题。目标是在重复分配不可分物品给多个具有可加估值的代理时，最大化所有代理中的最小效用。该问题的关键特征在于：每个代理对物品的估值仅通过半带子反馈观察到，而现有工作假设每轮开始时即可获得物品价值；此外，算法的奖励函数不随轮次可加，与多数带子设置不同。本文首个贡献是提出一种算法，其渐近遗憾上界为 $O(m\sqrt{T}\ln T/n + m\sqrt{T \ln(mnT)})$，其中 $n$ 为代理数，$m$ 为物品数，$T$ 为时间范围。该结果基于带子技术与竞争分析文献中资源分配算法的新颖组合。第二个贡献是给出了遗憾下界 $Ω(m\sqrt{T}/n)$。当 $T$ 远大于 $n$ 时，上下界差距仅为 $T$ 的对数因子。
原文摘要 · Abstract (English)
In this paper, we study a new decision-making problem called the bandit max-min fair allocation (BMMFA) problem. The goal of this problem is to maximize the minimum utility among agents with additive valuations by repeatedly assigning indivisible goods to them. One key feature of this problem is that each agent's valuation for each item can only be observed through the semi-bandit feedback, while existing work supposes that the item values are provided at the beginning of each round. Another key feature is that the algorithm's reward function is not additive with respect to rounds, unlike most bandit-setting problems. Our first contribution is to propose an algorithm that has an asymptotic regret bound of $O(m\sqrt{T}\ln T/n + m\sqrt{T \ln(mnT)})$, where $n$ is the number of agents, $m$ is the number of items, and $T$ is the time horizon. This is based on a novel combination of bandit techniques and a resource allocation algorithm studied in the literature on competitive analysis. Our second contribution is to provide the regret lower bound of $Ω(m\sqrt{T}/n)$. When $T$ is sufficiently larger than $n$, the gap between the upper and lower bounds is a logarithmic factor of $T$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。