2025-11-17T18:43:12.758371

Fair and Efficient Allocation of Indivisible Mixed Manna

Barman, HV, Sethia et al.

We study fair division of indivisible mixed manna (items whose values may be positive, negative, or zero) among agents with additive valuations. Here, we establish that fairness -- in terms of a relaxation of envy-freeness -- and Pareto efficiency can always be achieved together. Specifically, our fairness guarantees are in terms of envy-freeness up to $k$ reallocations (EFR-$k$): An allocation $A$ of the indivisible items is said to be EFR-$k$ if there exists a subset $R$ of at most $k$ items such that, for each agent $i$, we can reassign items from within $R$ (in $A$) and obtain an allocation, $A^i$, which is envy-free for $i$. We establish that, when allocating mixed manna among $n$ agents with additive valuations, an EFR-$(n-1)$ and Pareto optimal (PO) allocation $A$ always exists. Further, the individual envy-free allocations $A^i$, induced by reassignments, are also PO. In addition, we prove that such fair and efficient allocations are efficiently computable when the number of agents, $n$, is fixed. We also obtain positive results focusing on EFR by itself (and without the PO desideratum). Specifically, we show that an EFR-$(n-1)$ allocation of mixed manna can be computed in polynomial time. In addition, we prove that when all the items are goods, an EFR-${\lfloor n/2 \rfloor}$ allocation exists and can be computed efficiently. Here, the $(n-1)$ bound is tight for chores and $\lfloor n/2 \rfloor$ is tight for goods. Our results advance the understanding of fair and efficient allocation of indivisible mixed manna and rely on a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) Theorem in discrete fair division. We utilize weighted welfare maximization, with perturbed valuations, to achieve Pareto efficiency, and overall, our techniques are notably different from existing market-based approaches.

academic

분할 불가능한 혼합 만나의 공정하고 효율적인 배분

기본 정보

논문 ID: 2507.03946
제목: Fair and Efficient Allocation of Indivisible Mixed Manna
저자: Siddharth Barman (Indian Institute of Science), Vishwa Prakash HV (Chennai Mathematical Institute), Aditi Sethia (Indian Institute of Science), Mashbat Suzuki (UNSW Sydney)
분류: cs.GT (컴퓨터 과학 - 게임 이론)
발표 시간: 2025년 10월 15일 (arXiv 사전인쇄본 제2판)
논문 링크: https://arxiv.org/abs/2507.03946v2

초록

본 논문은 가법적 평가를 가진 에이전트들 사이의 분할 불가능한 혼합 만나(mixed manna)의 공정한 배분 문제를 연구한다. 혼합 만나는 가치가 양수, 음수 또는 영일 수 있는 물품을 의미한다. 논문은 공정성(무시기심성의 완화에 기반)과 파레토 효율성이 동시에 달성될 수 있다는 이론적 보장을 확립한다. 구체적으로, 공정성 보장은 "k번 재배분의 무시기심성"(EFR-k) 개념에 기반한다: 최대 k개 물품의 부분집합 R이 존재하여 각 에이전트 i에 대해 R의 물품을 재배분함으로써 i에 대한 무시기심 배분 A^i를 얻을 수 있다면, 배분 A는 EFR-k이다.

연구 배경 및 동기

문제 정의

공정한 배분은 재산 분할, 작업 할당, 경계 분쟁 및 채무 배분 등 현실의 여러 시나리오에서 자주 나타나는 문제이다. 참여하는 에이전트들이 개인적 선호를 가질 때, "누가 무엇을 얻을 것인가"의 문제는 실질적 긴급성과 이론적 풍부성을 모두 갖는다.

연구 과제

혼합 만나의 복잡성: 순수한 상품(goods) 또는 가사(chores)와 달리, 혼합 만나에서 물품의 가치 부호는 에이전트마다 다를 수 있으며, 이는 배분을 더욱 복잡하게 만든다.
공정성과 효율성의 상충: 분할 불가능한 물품의 설정에서, 전통적인 무시기심성(envy-freeness)은 존재를 보장할 수 없으므로 적절한 완화 조건을 찾아야 한다.
기존 방법의 한계:
- 가사 배분의 경우, 4개 에이전트의 경우에도 EF1과 파레토 최적 배분의 존재성이 여전히 미해결
- 혼합 만나의 경우, 이 문제는 3개 에이전트의 경우에도 여전히 개방되어 있음
- 기존의 시장 기반 방법은 음수 평가에서 직접 확장될 수 없음

연구 동기

논문은 EFR-k 개념을 도입함으로써 혼합 만나의 공정하고 효율적인 배분에 대한 이론적 보장을 제공하고 효과적인 계산 알고리즘을 개발하는 것을 목표로 한다.

핵심 기여

이론적 존재성 보장: 가법적 평가를 가진 n개 에이전트의 혼합 만나 배분에 대해, EFR-(n-1)이면서 파레토 최적인 배분이 항상 존재함을 증명한다.
알고리즘 계산 가능성: 에이전트 수 n이 고정되었을 때, 다항식 시간 내에 EFR-(n-1)이면서 파레토 최적인 배분을 계산할 수 있다.
독립적인 EFR 결과:
- 혼합 만나의 EFR-(n-1) 배분을 다항식 시간 내에 계산 가능
- 모든 물품이 상품일 때, EFR-⌊n/2⌋ 배분이 존재하며 효율적으로 계산 가능
타이트성 결과:
- 가사의 경우, (n-1) 경계는 타이트
- 상품의 경우, ⌊n/2⌋ 경계는 타이트
기술적 혁신: 이산 공정한 배분에서 Knaster-Kuratowski-Mazurkiewicz (KKM) 정리를 처음으로 적용한다.

방법론 상세 설명

작업 정의

입력:

n개 에이전트, n = {1,...,n}으로 표기
m개 분할 불가능한 물품, m = {1,...,m}으로 표기
가법적 평가 함수 {vi}i∈n, 여기서 vi(t) ∈ ℝ은 에이전트 i의 물품 t에 대한 평가

출력: 배분 A = (A1,...,An), 여기서 Ai ⊆ m은 에이전트 i에 배분된 물품 집합

목표: EFR-k와 파레토 최적성을 동시에 만족하는 배분을 찾기

핵심 개념

EFR-k 정의

배분 A는 EFR-k이다 ⟺ 크기가 최대 k인 부분집합 R ⊆ m이 존재하여, 각 에이전트 i에 대해 R의 물품을 재배분함으로써 i에 대한 무시기심 배분 A^i를 얻을 수 있다.

주요 기술 구성 요소

평가 섭동: 비퇴화 조건을 얻기 위해 주어진 평가에 충분히 작은 가법적 섭동을 추가:
```
v̄i(t) = vi(t) - εi,t
```
여기서 εi,t는 (0,ε)에서 균등 무작위로 추출
가중치 오프셋: 각 가중치 벡터 w ∈ Δn-1에 대해, 각 성분을 오프셋 파라미터 η > 0으로 이동:
```
SWη(A,w) := Σi∈[n] (wi + η)v̄i(Ai)
```

KKM 커버: 각 에이전트 i에 대해, 집합 정의

Ci := {w ∈ Δn-1 : 존재하는 배분 Xi ∈ Oη(w)에서 i가 무시기심}

주요 알고리즘 프레임워크

정리 3.1의 증명 전략

섭동 평가 구성: 비퇴화 성질 보장
KKM 커버 정의: KKM 조건을 만족하는 닫힌 집합족 {Ci} 구성
KKM 정리 적용: 교집합 w* ∈ ∩i Ci 획득
계수 논증: 재배분 집합 R의 크기가 최대 n-1임을 증명

알고리즘 1: 상품의 충돌 인식 선택 수열

순수 상품의 경우, 라운드 로빈 기반 알고리즘 설계:

충돌 해결 단계: 여러 에이전트가 가장 선호하는 동일한 상품을 식별하고 재배분 집합 R에 추가
선택 단계: 활성 에이전트가 사전식 순서로 가장 선호하는 상품 선택

기술적 혁신점

KKM 정리의 새로운 응용: 고전적인 KKM 정리를 이산 공정한 배분 문제에 처음 적용하여, 기존의 시장 기반 방법과 완전히 다른 기술 경로를 제공한다.
섭동 기법: 신중하게 설계된 평가 섭동을 통해 비퇴화성을 보장하여, 가중 사회 복지 최대화 문제가 좋은 성질을 갖도록 한다.
계수 논증: 이분 그래프의 비순환성을 이용하여 재배분 집합의 크기 경계를 증명한다.

실험 설정

이론적 분석 프레임워크

이것은 이론 논문이므로, 주로 실증 실험이 아닌 수학적 증명을 통해 결과를 검증한다. 논문은 다음의 분석 프레임워크를 채택한다:

존재성 증명: KKM 정리를 사용하여 EFR-(n-1)과 PO 배분의 존재성 증명
타이트성 분석: 반례를 구성하여 경계의 타이트성 증명
알고리즘 복잡성: 알고리즘의 시간 복잡도 분석

복잡성 분석

고정 에이전트 수: EFR-(n-1)과 PO 배분을 m^poly(n) 시간 내에 계산 가능
일반 경우: EFR-(n-1) 배분을 다항식 시간 내에 계산 가능
상품 경우: EFR-⌊n/2⌋ 배분을 다항식 시간 내에 계산 가능

실험 결과

주요 이론적 결과

정리 3.1 (주요 존재성 결과)

분할 불가능한 혼합 만나와 가법적 평가를 가진 모든 공정한 배분 인스턴스는 EFR-(n-1)이면서 파레토 최적인 배분을 갖는다.

정리 4.1 (계산 가능성 결과)

고정된 수의 에이전트를 가진 혼합 만나 배분 인스턴스에 대해, 다항식 시간 내에 EFR-(n-1)이면서 파레토 최적인 배분을 계산할 수 있다.

정리 5.1 (EFR 독립 결과)

혼합 만나와 가법적 평가를 가진 공정한 배분 인스턴스에 대해, EFR-(n-1)이면서 동시에 EF1인 배분이 항상 존재하며, 다항식 시간 내에 계산 가능하다.

정리 5.4 (상품의 개선된 경계)

순수 상품의 공정한 배분 인스턴스에 대해, 알고리즘 1은 다항식 시간 내에 EFR-⌊n/2⌋ 배분을 계산한다.

타이트성 결과

정리 5.2 (가사의 타이트성)

EFR-(n-2) 배분이 존재하지 않는 가사 배분 인스턴스가 존재하며, (n-1) 경계가 타이트함을 증명한다.

정리 5.5 (상품의 타이트성)

EFR-(⌊n/2⌋-1) 배분이 존재하지 않는 상품 배분 인스턴스가 존재하며, ⌊n/2⌋ 경계가 타이트함을 증명한다.

계산 복잡성 결과

정리 A.1 (판정 문제의 복잡성)

배분 A와 양의 정수 k < n-2가 주어졌을 때, A가 EFR-k인지 판정하는 것은 NP 완전이다.

이론적 돌파: 일반 혼합 만나 설정에 대해 공정성과 효율성의 동시 보장을 처음으로 제공
기술적 혁신: KKM 정리의 이산 공정한 배분에서의 새로운 응용은 새로운 연구 방향을 개척
실용적 가치: 알고리즘 결과는 실제 응용을 위한 계산 기초 제공

한계

경계: EFR-(n-1)의 경계는 상대적으로 크며, 평균적으로 각 에이전트당 약 2개 물품의 재배분 필요
고정 에이전트 가정: 다항식 시간 알고리즘은 에이전트 수가 고정되어야 함
가법적 평가 제한: 결과는 가법적 평가 함수에만 적용 가능

향후 방향

경계 개선: 더 작은 재배분 집합 R 탐색
평가 유형 확장: 비가법적 평가 함수 고려
실제 응용: 이론적 결과를 구체적인 배분 시나리오에 적용

심층 평가

장점

이론적 기여 중대: 혼합 만나의 공정하고 효율적인 배분의 기본 문제 해결
기술 수단 참신: KKM 정리의 응용은 깊은 수학적 통찰력을 보여줌
결과 포괄적: 존재성과 알고리즘, 상한과 하한 모두 포함
증명 엄밀: 수학적 도출이 완전하고 기술적 세부사항이 적절히 처리됨

부족한 점

실용성 제한: EFR-(n-1)의 경계는 실제 응용에서 과도할 수 있음
실증 평가 부재: 이론 논문으로서 실제 데이터에 대한 성능 평가 부족
알고리즘 효율성: 고정 에이전트 수일 때 m^poly(n) 복잡도는 실제로 높을 수 있음

영향력

학술적 영향: 공정한 배분 이론에 중요한 기여를 하며 광범위한 인용 예상
방법론적 가치: KKM 정리의 응용은 더 많은 관련 연구에 영감을 줄 수 있음
실용적 전망: 실제 배분 시스템 설계에 이론적 기초 제공

적용 시나리오

유산 분할: 자산과 채무를 포함한 복잡한 분할 시나리오
작업 할당: 매력적인 작업과 비매력적인 작업을 모두 포함하는 할당
자원 관리: 수익과 비용을 동시에 고려해야 하는 자원 배분 문제

참고 문헌

논문은 공정한 배분 분야의 중요한 문헌을 인용하며, 다음을 포함한다:

Budish (2011): EF1 개념의 도입
Caragiannis et al. (2019): Nash 사회 복지와 EF1+PO의 관계
Aziz et al. (2022): 혼합 만나의 EF1 존재성
Sandomirskiy & Segal-Halevi (2022): 분수 배분의 관련 결과

종합 평가: 이것은 EFR 개념을 도입하고 KKM 정리를 적용함으로써 혼합 만나의 공정하고 효율적인 배분에 대한 중요한 이론적 보장을 제공하는 고품질의 이론 논문이다. 실용성 측면에서 일정한 한계가 있지만, 그 이론적 기여와 기술적 혁신은 공정한 배분 분야의 중요한 진전을 이룬다.