2025-11-16T13:10:12.550115

Online MMS Allocation for Chores

Song, Tao, Wang et al.

We study the problem of fair division of indivisible chores among $n$ agents in an online setting, where items arrive sequentially and must be allocated irrevocably upon arrival. The goal is to produce an $Î±$-MMS allocation at the end. Several recent works have investigated this model, but have only succeeded in obtaining non-trivial algorithms under restrictive assumptions, such as the two-agent bi-valued special case (Wang and Wei, 2025), or by assuming knowledge of the total disutility of each agent (Zhou, Bai, and Wu, 2023). For the general case, the trivial $n$-MMS guarantee remains the best known, while the strongest lower bound is still only $2$. We close this gap on the negative side by proving that for any fixed $n$ and $\varepsilon$, no algorithm can guarantee an $(n - \varepsilon)$-MMS allocation. Notably, this lower bound holds precisely for every $n$, without hiding constants in big-$O$ notation, thereby exactly matching the trivial upper bound. Despite this strong impossibility result, we also present positive results. We provide an online algorithm that applies in the general case, guaranteeing a $\min\{n, O(k), O(\log D)\}$-MMS allocation, where $k$ is the maximum number of distinct disutilities across all agents and $D$ is the maximum ratio between the largest and smallest disutilities for any agent. This bound is reasonable across a broad range of scenarios and, for example, implies that we can achieve an $O(1)$-MMS allocation whenever $k$ is constant. Moreover, to optimize the constant in the important personalized bi-valued case, we show that if each agent has at most two distinct disutilities, our algorithm guarantees a $(2 + \sqrt{3}) \approx 3.7$-MMS allocation.

academic

온라인 MMS 할당 (가사 분담)

기본 정보

논문 ID: 2507.14039
제목: Online MMS Allocation for Chores
저자: Jiaxin Song (University of Illinois Urbana-Champaign), Biaoshuai Tao (Shanghai Jiao Tong University), Wenqian Wang (Shanghai Jiao Tong University), Yuhao Zhang (Shanghai Jiao Tong University)
분류: cs.GT (컴퓨터 과학 - 게임 이론)
발표 시간: 2025년 10월 11일 (arXiv v2)
논문 링크: https://arxiv.org/abs/2507.14039

초록

본 논문은 온라인 환경에서 n명의 에이전트 간 분할 불가능한 가사(chores)의 공정한 할당 문제를 연구한다. 이 설정에서 항목들은 순차적으로 도착하며, 도착 시점에 어떤 에이전트에게 돌이킬 수 없이 할당되어야 하고, 최종 목표는 α-MMS 할당을 생성하는 것이다. 최근 연구들이 제한적 가정 하에서 진전을 이루었음에도 불구하고, 일반적인 경우에 알려진 최선의 보장은 여전히 자명한 n-MMS이며, 최강의 하한은 2에 불과하다. 본 논문은 임의의 고정된 n과 ε에 대해 (n-ε)-MMS 할당을 보장할 수 있는 알고리즘이 존재하지 않음을 증명함으로써 음의 결과에서 이 간격을 메운다. 동시에 min{n, O(k), O(log D)}-MMS 할당을 보장하는 온라인 알고리즘을 제시한다. 여기서 k는 모든 에이전트 중 서로 다른 음의 효용값의 최대 개수이고, D는 임의의 에이전트의 최대 및 최소 음의 효용 간의 최대 비율이다.

연구 배경 및 동기

1. 문제 정의

본 논문이 연구하는 것은 분할 불가능한 가사(chores)의 온라인 공정 할당 문제이다. 전통적인 상품(goods) 할당과 달리, 가사는 음의 효용을 가지며, 에이전트들은 가능한 한 적은 가사를 담당하기를 원한다. 온라인 설정에서 가사는 순차적으로 도착하고, 알고리즘은 각 가사 도착 시 즉시 어떤 에이전트에게 할당해야 하며, 할당 결정은 돌이킬 수 없다.

2. 연구의 중요성

이 문제는 현실에서 광범위한 응용을 가진다:

온라인 서비스 플랫폼에서 직원에게 작업 할당
시스템 부하 분산 문제
자원 스케줄링에서의 공정성 보장

3. 기존 방법의 한계

기존 연구는 다음과 같은 제한을 가진다:

매우 제한적인 가정 하에서만 자명하지 않은 결과 달성 (예: 2명 에이전트 이중값 경우)
각 에이전트의 총 음의 효용을 미리 알아야 함
일반적인 경우, 최선의 알려진 알고리즘은 자명한 n-MMS만 보장

4. 연구 동기

본 논문의 목표:

온라인 MMS 할당 문제의 이론적 극한 결정
일반적인 경우에 적용 가능한 실용적 알고리즘 설계
실제 매개변수 제약 하에서 더 나은 성능 보장 제공

핵심 기여

이론적 하한의 정확한 특성화: 임의의 고정된 n과 ε > 0에 대해 (n-ε)-MMS 할당을 보장할 수 있는 알고리즘이 없음을 증명하여 이론적 간격을 완전히 해소
범용 온라인 알고리즘: 일반적인 경우에 적용 가능한 알고리즘 제시, min{n, O(k), O(log D)}-MMS 할당 보장
매개변수화 분석: k(서로 다른 음의 효용값 개수)가 상수일 때, 알고리즘은 O(1)-MMS 보장 달성
최적화된 이중값 경우: 개인화된 이중값 경우에 대해 (2+√3) ≈ 3.7-MMS의 개선된 보장 제공
새로운 분석 기법: "Stacking Game" 프레임워크 도입, 문제를 특수한 차이 최소화 문제로 변환