📈 economics

Fair Allocation with Optional Selling

이 논문은 에이전트가 시장 가격으로 물품을 판매할 수 있는 상황에서 불가분 재화의 공정한 배분을 조사하며, MMS 및 EFX와 같은 표준적인 공정성 개념을 이러한 하이브리드 설정에 적응시키고, 재화와 수익의 분배를 균형 있게 맞추는 배분에 대한 존재성 보장 및 근사 상한을 확립한다.

원저자: Uriel Feige, Yotam Gafni

게시일 2026-08-26

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Uriel Feige, Yotam Gafni

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

공정 분할(Fair division)은 인간 협력의 역사만큼이나 오래된 문제인, 어떻게 하면 모두가 자신이 공정한 몫을 받았다고 느끼도록 자원을 나누는가에 전념하는 수학 및 경제학 분야이다. 수십 년 동안 연구자들은 집, 자동차, 또는 희귀 도서 수집품처럼 나눌 수 없는 것들을 어떻게 나눌 것인가를 연구해 왔다. 이러한 시나리오에서 목표는 누구도 다른 사람이 받은 것에 대해 시기심을 느끼지 않거나, 각자의 개인적 선호도에 따라 최소한의 만족 수준을 보장받는 배치를 찾는 것이다. 그러나 이러한 고전적 모델들은 대상이 현재의 형태 그대로 유지된다고 가정한다. 이들은 매우 흔한 현실 세계의 선택지인 '물건을 현금으로 팔 수 있는 능력'을 간과한다. 예를 들어, 이혼 과정에서 한 부부는 집을 한 명이 소유하고 다른 한 명은 아무것도 받지 못하게 하는 것보다, 집을 팔아 그 돈을 나누는 것이 더 나은 해결책이라고 결정할 수 있다. 이러한 판매라는 단순한 옵션은 가능한 것들의 지형을 완전히 바꾸어 놓지만, 동시에 이전 이론들이 다루지 않았던 새로운 복잡성을 도입한다.

와이즈만 과학 연구소의 우리엘 페이게(Uriel Feige)와 요탐 가프니(Yotam Gafni)는 사람들이 남은 물건과 그 결과로 생긴 현금을 나누기 전에 시장 가격으로 물건을 팔 수 있는 상황에서 어떤 일이 발생하는지를 탐구하며 이 공백을 메우고 있다. 그들의 연구는 근본적인 질문을 던진다. 만약 사람들이 물건을 팔 수 있다면, 공정한 결과를 보장하는 것이 더 쉬워질까, 아니면 더 어려워질까? 그들은 판매가 더 많은 가능성을 열어주기는 하지만, 판매가 금지된 전통적인 설정에 비해 특정 유형의 공정성을 보장하는 것을 실제로 더 어렵게 만든다는 것을 발견했다. 연구진은 사람들이 보유하게 될 물건의 가치와 판매를 통해 받는 돈을 모두 고려하는 새로운 공정성 측정 방식을 개발했다. 그들은 두 사람의 경우, 판매 옵션을 고려한 후에도 아무도 다른 사람의 묶음에 대해 시기심을 느끼지 않도록 하는 가장 강력한 공정성 표준을 만족하는 분할을 찾는 것이 항상 가능하다는 것을 증명했다. 그러나 사람의 수가 늘어날수록 보장되는 수준은 약간 약해진다. 세 사람의 경우, 모든 사람이 자신의 절대적인 최대 가능 공정 몫을 얻는 것을 보장하는 것은 불가능하다는 것을 보여주었으며, 어떤 경우에는 최선이 이론적 이상치의 특정 비율에 그칠 수 있음을 보여주었다.

연구진은 또한 더 큰 집단에 대해 이러한 공정 몫을 얼마나 잘 근사할 수 있는지 조사했다. 그들은 어떤 수의 사람들에게라도 물건과 돈을 나누어 모두가 보장된 최소 몫의 2/3 이상을 받을 수 있는 방법이 항상 존재함을 입증했다. 이는 판매가 추가된 복잡한 상황에서도 매우 높은 수준의 공정성이 여전히 달성 가능하다는 것을 보여준다는 점에서 중요한 결과이다. 나아가, 그들은 이러한 몫 기반의 공정성을 강한 의미의 무시 없는 공정성(envy-freeness)과 결합할 수 있다는 것을 발견했는데, 이는 아무도 자신의 물건과 현금 묶음을 다른 사람의 묶음과 교환하는 것을 선호하지 않는 상태를 의미한다. 그들은 "론 디바이더(Lone Divider)"법이라 알려진 알고리즘을 응용하여 이를 달성했다. 이 방법은 한 사람이 분할안을 제안하고 다른 사람들이 선호하는 부분을 선택하는 방식이다. 판매가 포함된 새로운 설정에서는, 제안하는 사람이 현명하게 선택되어야 하며, 판매가 남은 참가자들에게 불공정하게 피해를 주는 것을 방지하기 위해 묶음이 특정한 방식으로 구조화되어야 하므로 이 접근 방식을 신중하게 수정해야 했다.

이 논문에서 가장 놀라운 발견 중 하나는 판매가 있는 설정과 없는 설정 사이의 차이점이다. 저자들은 세 명의 사람과 여덟 개의 물건이 포함된 구체적인 사례를 구성했는데, 만약 판매가 허용된다면 모든 사람이 자신의 이상적인 몫 중 12분의 11 이상을 얻는 것을 보장하는 것이 불가능하다. 판매가 불가능한 전통적인 설정에서 동일한 시나리오에 대한 최선의 알려진 한계치는 훨씬 높으며, 이는 판매 능력이 오히려 이론적으로 가능한 것과 실제로 보장할 수 있는 것 사이의 간극을 더 넓힌다는 것을 의미한다. 이 역설적인 결과는 판매가 유연성을 제공하지만, 고가의 물건이 낮은 가격에 팔려 남아 있는 물건들이 모든 사람의 요구를 충족시키기에 불충분해지는 새로운 종류의 위험을 초 함께 도입한다는 점을 시사한다. 연구진은 또한 사람들이 싫어하는 과업인 '잡무(chores)'와 관련된 시나리오도 탐구했는데, 여기서 비용을 지불하고 일을 외주 주는 옵션은 물건을 파는 것과 동일한 역할을 한다. 그들은 유사한 패턴을 발견했으며, 누군가에게 일을 대신 시키기 위해 비용을 지불하는 능력이 남은 작업의 완벽한 공정한 분배를 보장하기를 더 어렵게 만든다는 것을 보여주었다.

이 논문은 또한 이러한 공정한 할당이 컴퓨터에 의해 효율적으로 계산될 수 있는지를 묻는 실무적인 측면도 다룬다. 저자들은 특히 두 사람의 경우, 합리적인 시간 내에 공정한 분할을 찾을 수 있음을 보여주었다. 더 큰 집단의 경우, 그들은 이상적인 공정 몫에 임의로 가까워질 수 있는 알고리즘을 개발했는데, 이는 충분한 컴퓨팅 능력이 있다면 이론적인 최선에 거의 근접한 솔루션을 찾을 수 있음을 의미한다. 또한 그들은 절단된 비례 몫(truncated proportional share)에 기반한 특정 유형의 공정성 보장이 빠르게 계산될 수 있으며 무시 없는 조건과 결합될 수 있음을 증명했다. 이 연구는 시장과 개인의 선호도가 공정 분할 문제에서 어떻게 상호작용하는지를 이해하기 위한 견고한 틀을 제공하며, 이혼 재산 분할부터 상속 자산 분할에 이르기까지 다양한 상황에 적용할 수 있는 새로운 도구를 제공한다. 판매가 하나의 옵션인 세상에서 무엇이 가능한지를 엄밀하게 정의함으로써, 연구진은 자원이 돈으로 전환될 수 있는 상황에서 우리가 정확히 어떤 보장에 의지할 수 있는지 명확히 하였다.

기술 요약: 선택적 판매가 포함된 공정 배분

문제 정의

본 논문은 에이전트들이 재화에 대해 주관적인 가치 함수를 보유하고 있으나, 동시에 재화에 외생적인 시장 가격이 존재하는 환경에서 분할 불가능한 재화를 공정하게 배분하는 문제를 다룹다. 전통적인 분할 불가능한 재화 모델과 달리, 이 설정은 "외부 옵션(outside option)"을 도입한다. 즉, 에이전트는 자신의 재화를 시장 가격으로 판매하기로 선택할 수 있다. 이러한 판매로부터 발생하는 수익은 분할 가능하며, 모든 에이전트에게 균등한 가산적(additive) 가치를 지닌다.

핵심 과제는 다음을 동시에 결정하는 배분 메커니즘을 설계하는 것이다:

어떤 재화의 집합을 판매할 것인가.
남은 미판매 재화를 어떻게 배분할 것인가.
판매된 재화로부터 발생한 금전적 수익을 어떻게 분배할 것인가.

목표는 이러한 하이브리드 환경에 맞춰 표준적인 몫 기반(share-based) 및 시기심 기반(envy-based) 보장 조건을 적응시킨 공정성 개념을 충족하는 것이다. 저자들은 재화와 돈 모두에 대해 가산적 가치를 가정한다.

공정성 개념

본 논문은 두 가지 범주의 공정성 정의를 적응시킨다:

몫 기반 개념 (Share-Based Notions):
- 최대 최소 몫 (Maximin Share, MMS): 에이전트가 어떤 재화를 판매할지 최적으로 결정한 후, 남은 재화와 수익을 $n$ 개의 번들로 나누어 그중 가장 가치가 낮은 번들을 받는 것을 보장하는 최대 가치로 정의된다. 표준적인 MMS와 달리, 에이전트는 판매 결정과 분할을 동시에 최적화한다.
- 절단 비례 몫 (Truncated Proportional Share, TPS): 분할 불가능한 설정에서의 TPS 개념을 확장한 것으로, 모든 재화 $g$ 에 대해 $\max\{p(g), \min\{v(g), t\}\}$ 의 합을 $n$ 으로 나눈 값이 $t$ 가 되게 하는 가장 큰 값 $t$ 로 정의된다.
시기심 기반 개념 (Envy-Based Notions):
- SEF1 및 SEFX (강한/판매 가능 시기심 없는 상태): 이는 EF1 및 EFX의 적응형이다. 할당이 SEFX라는 것은 임의의 에이전트 $i$ 와 다른 에이전트 $j$ 에 대해, $j$ 가 자신의 재화 중 하나를 보유하는 대신 판매하여 시장 가격을 받는다고 가정하더라도 $i$ 가 $j$ 의 번들을 시기하지 않음을 의미한다. 형식적으로, 모든 재화 $g \in A_j$ 에 대해 $\bar{v}_i(A_i) + P_i \ge \bar{v}_i(A_j \setminus \{g\}) + p(g)$ 를 만족해야 한다 (여기서 $\bar{v}_i(g) = \max\{v_i(g), p(g)\}$ 이다).

방법론 및 알고리즘

저자들은 선택적 판매로 인한 복잡성을 처리하기 위해 "Cut & Choose", "Bag-Filling", "Lone Divider" 패러다임의 변형을 포함한 다양한 알고리즘 기법을 사용한다.

Cut & Give ( $n=2$ ): 두 명의 에이전트를 위해 저자들은 "Cut & Give" 프로토콜을 도입한다. 한 에이전트(Cutter)가 자신의 MMS를 바탕으로 분할안을 제안한다. 다른 에이전트(Giver)가 해당 번들이 수용 가능하다고 판단하면 이를 수락한다. 만약 그렇지 않다면, Giver는 자신의 의도된 재화를 판매하고 Cutter의 판매를 취소함으로써, 두 에이전트 모두의 MMS와 SEFX를 만족하는 새로운 번들을 생성한다.
가상 재화를 이용한 Bag-Filling (TPS): $n/(2n-1)$ -TPS를 달성하기 위해, 저자들은 "움직이는 칼(moving knife)" 접근법을 사용한다. 높은 시장 가격을 가진 재화는 에이전트들의 최소 몫 요구를 충족하기 위해 즉시 판매된다. 남은 수익은 "가상 재화"로 취급된다. 이후 백 채우기(bag-filling) 절차를 통해 에이전트가 요구되는 임계값에 도달할 때까지 번들을 할당한다.
정형 분할 (MMS를 위한 Lone Divider): 일반적인 $n$ 에 대해, 저자들은 Lone Divider 방법을 적응시킨다. 핵심 혁신은 가장 높은 MMS를 가진 에이전트가 제안하는 "정형 분할(canonical partitions)"의 구축이다. 이 분할은 "순수 번들"(수익 없음), "단일 항목 번들"(하나의 재화와 최대 하나의 다른 판매된 재화로부터의 수익 결합), 그리고 단일 "잔여물" 번들로 구성된다. 이러한 구조는 에이전트가 거부한 번들이 다른 사람에게 할당될 경우 입게 되는 손실을 제한하며, 특히 강제 판매로 인한 손실을 제한한다.
고가치 품목 처리: 알고리즘에는 MMS 임계값을 크게 상회하는 재화를 처리하기 위한 예비 단계가 포함되어 있다. 이는 특정 에이전트를 만족시키기 위해 판매하거나 직접 할당함으로써, 남은 문제가 근사 프레임워크에 부합하도록 보장한다.

주요 결과

1. 결합된 몫 및 시기심 보장

두 명의 에이전트 ( $n=2$ ): 항상 MMS와 SEFX를 동시에 만족하는 할당이 존재한다. 이는 $n \ge 3$ 인 표준 설정에서 완전한 MMS를 달성하는 것이 일반적으로 불가능하다는 점을 고려할 때 매우 강력한 결과이며, 여기서는 강력한 시기심 없는 개념과 함께 MMS가 달성된다.
일반적인 에이전트 ( $n \ge 2$ ): $n/(2n-1)$ -TPS와 SEFX를 동시에 만족하는 할당이 존재한다. $n/(2n-1)$ 비율은 SEFX 요구 조건 없이도 TPS에 대한 최선의 가능한 근사 비율임이 증명되었다.

2. MMS 근사 경계

세 명의 에이전트 ( $n=3$ ): 본 논문은 판매가 있는 설정과 없는 설정 사이의 정량적 격차를 규명한다. 표준적인 분할 불가능한 설정(판매가 없는 경우)에서 $m=8$ 개의 품목에 대해 완전한 MMS가 보장되는 반(기존 최선 알고리즘의 경계는 $39/40$ ) 반면, 판매 설정에서는 어떤 할당도 $11/12$ -MMS 이상의 가치를 보장하지 못하는 사례가 존재한다.
일반적인 에이전트 ( $n \ge 4$ ): 저자들은 $2/3$ -MMS 할당을 제공한다. 이는 (일부 이전 연구에서 발견되는 $O(1/n)$ 가산 항이 없는) 표준 분할 불가능 설정에서의 최선 알려진 근사 비율과 일치한다.
특수 사례 ( $n=3$ ): 일반 $n$ 에 대한 접근법과 $n=2$ 를 위한 완전 MMS 알고리즘을 결합함으로써, 저자들은 세 명의 에이전트에 대해 $3/4$ -MMS 할당을 달축한다.

3. 계산 복잡도

MMS 계산: 정확한 MMS 값을 계산하는 것은 $n=2$ $n = 2$ 일 때 약한 NP-난해(weakly NP-hard)이며, 일반적인 $n$ $n$ 에 대해서는 강한 NP-난해(strongly NP-hard)이다. 그러나 본 논문은 다음을 제공한다:
- 고정된 $n$ 에 대한 의사 다항 시간(pseudo-polynomial time) 알고리즘.
- MMS 값 및 분할을 계산하기 위한 다항 시간 근사 스킴 (PTAS).
TPS 계산: TPS는 다항 시간에 효율적으로 계산 가능하다.
결합된 보장: $n/(2n-1)$ -TPS 및 $\epsilon$ -SEFX를 동시에 만족하는 할당을 위한 FPTAS가 존재한다.

4. 확장

동일 수익 (Equal Proceeds): 판매 수익을 모든 에이전트에게 균등하게 분배해야 하는 제한된 설정을 분석한다. 이 경우, 근사 보장은 $1/n$ -TPS로 떨어지며, MMS 보장은 제한 없는 경우보다 현저히 약해질 수 있다.
업무(Chores)와 아웃소싱: 에이전트가 시장 비용으로 업무를 "아웃소싱"할 수 있는 업무(음의 가치) 모델로 확장한다. 결과는 재화 설정과 유사하다: 2-MMS 근사가 가능하지만, 표준적인 분할 불가능한 업무 설정보다 근사 격차가 더 크다.

의의 및 주장

본 논문은 시장 옵션이 가용할 때 공정한 배분을 위한 "최상의 두 세계(Best of Both Worlds)" 프레임워크를 제공한다고 주장한다. 주요 기여는 다음과 같다:

이론적 격차 식별: 판매 옵션의 도입이 가용한 결과의 집합을 확장함에도 불구하고, 역설적으로 특정 공정성 보장(특히 $n=3$ 에서의 MMS)을 근사하는 것을 (순수 분할 불가능 설정에 비해) 더 어렵게 만들 수 있음을 보여준다.
강건한 알고리즘: 판매 결정의 최적화라는 추가된 복잡성에도 불구하고, 기존의 최선 알려진 MMS 근사 비율을 성공적으로 회복하는 정형 분할, 수정된 Lone Divider와 같은 새로운 알고리즘 기법을 개발한다.
통합된 공정성: 몫 기반 보장(MMS/TPS)을 강력한 시기심 없는 개념(SEFX)과 단일 할당 내에서 성공적으로 통합하여, 높은 수준의 몫 근사가 이 설정에서 강력한 시기심 없는 상태를 배제하지 않음을 보여준다.

저자들은 자신의 결과가 여러 경우(예: TPS에 대한 $n/(2n-1)$ 경계)에서 타이트(tight)함을 강조하며, $n=3$ 에 대한 부정적 결과( $11/12$ 격차)는 현재의 알고리즘적 한계가 아니라 모델 자체의 증명 가능한 제한 사항임을 밝힌다.