효율적인 대략 공정한 품목 할당

다양한 선호를 가진 사람들 사이에 물건을 할당할 때, 두 가지 주요 목표는 파레토 효율성과 공정성이다. 물건이 분할 불가능하기 때문에 공정한 할당이 존재하지 않을 수 있다. 예를 들어, 단 하나의 집과 두 사람이 있을 때, 집의 모든 할당은 한 사람에게는 불공평할 것이다. 따라서 최소최대몫 공정성(MMS), 항목 하나까지의 비선점성(EF1), 항목 하나까지의 비례성(PROP1), 항목 하나까지의 공평성(EQ1)과 같은 몇 가지 일반적인 근사치들이 연구되어 왔다. **효율적인 대략 공정한 항목 할당**() 문제는 파레토 효율적(PE)이면서 이러한 공정성 개념 중 하나를 만족하는 할당을 찾는 것이다. 이 문제는 2016년에 처음 제시되었고 그 이후로 상당한 주목을 받아왔다.

## 설정
M으로 표시되는 유한한 물건들의 집합이 있다. n개의 에이전트가 있다. 각 에이전트 i는 물건들의 각 부분집합에 값을 할당하는 가치 함수 Vi를 가진다. 목표는 M을 n개의 부분집합 X1,...,Xn으로 분할하고, 각 부분집합 Xi를 에이전트 i에게 할당하여, 할당이 파레토 효율적이고 대략적으로 공정하게 만드는 것이다. 대략적인 공정성에는 다양한 개념이 있다.

## 효율적인 대략적인 비선점적 할당
할당은 모든 에이전트가 자신의 몫의 가치가 다른 에이전트의 몫의 가치만큼 높다고 믿는 경우 **[[비선점성|비선점적]] (EF)**이라고 불린다. 두 에이전트 i와 j에 대해, j의 묶음에서 최대 하나의 항목이 제거되면 i가 j를 선점하지 않는 경우 **항목 하나까지의 비선점적 (EF1)**이라고 불린다. 공식적으로:

*\forall i,j: ~~~ \exists Y\subseteq X_j: ~~~|Y|\leq 1, ~~~V_i(X_i) \geq V_i(X_j\setminus Y)
일부 초기 알고리즘은 약한 형태의 효율성을 만족하지만 PE는 아닌 대략적으로 공정한 할당을 찾을 수 있었다.

* 라운드 로빈 절차는 가산 유틸리티를 가진 완전한 EF1 할당을 반환한다. 비선점 그래프 절차는 임의의 단조 선호 관계에 대한 완전한 EF1 할당을 반환한다. 둘 다 비선점 사이클이 없는 할당을 반환하도록 보장된다. 그러나 할당이 파레토 효율적이라고 보장되지는 않는다.
* 대략적인 CEEI 메커니즘은 임의의 선호 관계에 대한 부분적인 EF1 할당을 반환한다. 할당된 객체에 대해서는 PE이지만 모든 객체에 대해서는 PE가 아니다 (일부 객체는 할당되지 않을 수 있으므로).
이는 PE와 EF1을 모두 만족하는 할당을 찾는 문제로 이어졌다.

### 최대 내쉬 복지 규칙
**카라기아니스, 쿠로카와, 물랑, 프로카치아, 샤, 왕**는 PE+EF1 할당의 존재를 처음으로 증명했다. 그들은 모든 에이전트가 양의 가산 유틸리티를 가질 때, 유틸리티 곱을 최대화하는 모든 할당(내쉬 복지라고도 함)이 EF1임을 증명했다. 최대화 할당이 PE임은 명백하므로, PE+EF1 할당의 존재가 뒤따른다.

최대 곱 할당은 바람직한 속성을 가지고 있지만, 다항 시간 내에 계산할 수 없다. 최대 곱 할당을 찾는 것은 NP-난해이며 심지어 APX-hard이다. 이로 인해 최대 곱을 근사하려는 다양한 연구가 이루어졌으며, 근사 계수는 다음과 같이 개선되었다.

* 콜과 가첼리스는 2.89배 근사를 제시했다.
* 아나리, 가란, 사베리, 싱는 e배 근사를 제시했다.
* 콜, 데바누어, 가텔리스, 제인, 마이, 바지라니, 야즈단보드는 2배 근사를 제시했다.
그러나 이러한 근사치는 EF1을 보장하지 않는다. 최근의 일부 알고리즘은 대략적인 최대 곱과 공정성을 모두 보장한다.

* 바르만, 크리슈나무르티, 바이스는 의사다항 시간(아래 증가 가격 알고리즘 참조)에 PE, (1+epsilon)-EF1, 최대 곱에 대한 1.45 근사를 보장하는 알고리즘을 제시한다.
* 가그와 맥글로플린은 강력한 다항 시간 내에 PE, PROP1, 최대 곱에 대한 2-근사를 보장하는 알고리즘을 제시한다.
* 카라기아니스, 그라빈, 황은 일부 상품을 폐기함으로써 EFX, PROP1, 최대 곱에 대한 2.9-근사를 보장하는 알고리즘을 제시한다(2-근사 할당의 존재도 보여준다).

최대 곱 해법은 가치 평가가 이진일 때(각 항목의 가치가 0 또는 1) 특히 매력적이다.

* 아마나티디스, 비르파스, 필로스-라치카스, 홀렌더, 부두리스는 이진 가치 평가에서 최대 곱 해법이 EF1뿐만 아니라 EFX(어떤 재화까지도 비선점)라는 것을 증명했다. 이는 각 항목의 가치가 두 가지 값 중 하나를 가질 수 있을 때마다(반드시 0 또는 1일 필요는 없음) 성립한다. 일반적인 가산 가치 평가에서는 최대 곱이 EFX를 의미하지 않지만, 그것의 자연스러운 일반화를 의미한다.
* 할페른, 프로카치아, 프소마스, 샤는 이진 가치 평가에서 사전순 우선순위가 있는 최대 곱 규칙이 다항 시간 내에 계산될 수 있으며, 그룹-전략-불능이라는 것을 증명했다.

#### 비가산 가치 평가
에이전트의 효용이 가산적이지 않더라도, 최대 곱 해법이 반드시 EF1은 아니다. 그러나 에이전트의 효용이 적어도 준모듈러라면, 최대 곱 해법은 약한 속성인 항목 1을 제외한 한계 비선점성(MEF1)을 만족한다. 이는 각 에이전트 i가 자신의 묶음을 (j의 묶음에서 가장 좋은 항목을 제거한) 한계효용만큼 또는 그 이상으로 평가한다는 것을 의미한다. 공식적으로:
*\forall i,j: ~~~ \exists Y\subseteq X_j: ~~~|Y|\leq 1, ~~~V_i(X_i) \geq
V_i(X_i \cup (X_j\setminus Y)) - V_i(X_i) 

더 일반적인 효용 함수에 대해서도 비슷한 근사치가 발견되었다.

* 베이, 가그, 호퍼, 멜혼과 아나리, 마이, 가란, 바지라니는 각 항목 종류의 여러 단위를 가진 시장을 연구하며, 가치 평가는 하고 조각별 선형 오목이다. 이는 다른 항목 종류를 가진 묶음의 효용이 각 단일 항목 종류에 대한 효용의 합이라는 것을 의미하지만("분리 가능"의 의미), 각 항목 종류에 대해서는 가치 평가가 한계 효용 체감을 가진다는 것을 의미한다("조각별 선형 오목"의 의미). 그들은 최대 곱에 대한 2-근사를 제시한다.
* 오르테가는 이진 가치 평가를 가진 다단위 시장을 연구한다. 그는 평등주의 규칙이 로렌츠 우위적(렉시민-최적성보다 강한 속성), 효용에서 유일하며, 그룹 전략불능이라는 것을 증명한다.
* 가그, 호퍼, 멜혼은 예산 가산 가치 평가를 연구한다. 이는 준모듈러 효용의 하위 클래스이다. 그들은 입력 크기와 1/ε에 대한 다항 시간 내에 최대 곱에 대한 (2.404 + ε)-근사를 제시한다.
* 베나부, 차크라보르티, 이가라시, 지크는 이진 한계 이득을 가진 준모듈러 효용을 연구한다(즉, 각 항목은 각 묶음의 값에 0 또는 1을 더한다). 그들은 이러한 가치 평가에서 최대 곱 및 렉시민 할당 모두 EF1이며 공리주의 복지(효용의 합)를 최대화한다는 것을 증명한다.
* 바바오프, 에즈라, 파이게도 이진("이분법적") 한계 이득을 가진 준모듈러 효용을 연구한다. 그들은 로렌츠 우위적 할당을 출력하는 결정론적인 진실한 메커니즘을 제시한다. 이는 EFX이며 최대 곱이다.

#### 혼합 가치 평가
마틴과 월시는 "혼합 만나"(양수와 음수 모두를 가질 수 있는 가산 가치 평가)에서 효용의 곱을 최대화하는 것(또는 효용의 음수 곱을 최소화하는 것)이 EF1을 보장하지 않는다는 것을 보여준다. 그들은 또한 EFX3 할당이 동일한 효용을 가질 때도 존재하지 않을 수 있음을 증명한다. 그러나 삼차 효용을 가질 때, EFX와 PO 할당, 또는 EFX3과 PO 할당은 항상 존재한다. 그리고 동일한 효용을 가질 때, EFX와 PO 할당은 항상 존재한다. 이 경우 다항 시간 알고리즘이 있다.

### 가격 인상 알고리즘
**바르만, 크리슈나무르티, 바이스**는 양의 가산 가치 평가를 위한 PE+EF1 할당을 찾는 의사 다항 시간 알고리즘을 제시했다. 그들은 다음 결과를 증명했다.

* 이 알고리즘은 O(poly(m,n,vmax)) 시간에 PE+EF1 할당을 찾는다. 여기서 m은 객체의 수, n은 에이전트의 수, vmax는 항목의 가장 큰 값이다(모든 가치 평가는 정수이다).
* 동일한 알고리즘은 최대 내쉬 복지에 대한 1.45 근사를 제공한다.
* 이 알고리즘은 EF1과 부분 파레토 최적을 모두 만족하는 할당의 존재도 증명한다.

#### 기본 개념
그들의 알고리즘은 피셔 시장에서의 경쟁 균형 개념을 기반으로 한다. 다음 개념들을 사용한다.

***대략적인 EF1 할당**: 상수 e > 0이 주어졌을 때, 할당은 EF1 조건을 (1+e)의 곱셈 상수를 기준으로 만족하면 e-EF1이다. 공식적으로:
**\forall i,j: ~~~ \exists Y\subseteq X_j: ~~~|Y|\leq 1, ~~~(1+e)\cdot V_i(X_i) \geq V_i(X_j\setminus Y)
***가격 벡터**: 각 항목에 가격(실수)을 할당하는 벡터이다.
* **가성비 비율**: 에이전트 i와 객체 o에 대해, 항목에 대한 에이전트의 가치 평가와 항목 가격의 비율이다. 즉, vij / pj.
* **최대 가성비 (MBB) 집합**: 에이전트 i에 대해, 그의 가성비 비율을 최대화하는 객체 집합이다(가격 벡터 p가 주어졌을 때).
* **MBB 할당**: 각 에이전트가 자신의 MBB 집합에서만 객체를 받는 할당이다. MBB 할당에서 각 에이전트는 자신의 예산을 고려하여 효용을 최대화한다(그러나 MBB 할당은 더 강력한 조건이다). 제1복지정리는 MBB 할당이 부분 파레토 최적임을 의미한다.
***가격-비선점 (pEF) 할당**: Xi의 가격("i의 소득"이라고 함)이 Xj의 가격보다 크거나 같은 할당 X이다. 이는 모든 소득이 동일하다는 것을 의미한다. 더욱이, MBB와 pEF를 모두 만족하는 할당은 비선점적이다. 왜냐하면 각 에이전트가 자신의 소득을 고려하여 효용을 최대화하고, 다른 모든 에이전트가 동일한 소득을 가지기 때문이다.
***가격-비선점-예외-하나 (pEF1) 할당**: 두 에이전트 i.j에 대해, p(Xi)의 가격이 Xj에서 가장 비싼 항목을 제외한 가격보다 크거나 같은 할당이다. 이는 소득이 동일하다는 것을 의미하지는 않는다. 그러나 MBB와 pEF1을 모두 만족하는 할당은 EF1이기도 하다.
***e''-pEF1 할당**, 일부 상수 *e* > 0: 두 에이전트 *i*.*j*에 대해, (1+*e*)·p(*X<sub>i</sub>*)의 곱이 Xj에서 가장 비싼 항목을 제외한 p(Xj)보다 크거나 같은 할당이다. *e*가 클수록 *e*-pEF1 조건이 약해진다는 점에 유의한다. 특히, pEF1 할당은 모든 *e* > 0에 대해 *e*-pEF1이지만, 그 반대는 사실이 아니다. MBB와 *e*-pEF1을 모두 만족하는 할당은 또한 **e-EF1**이다.
***최소 지출자**: 할당 및 가격 벡터가 주어졌을 때, p(Xi)가 가장 작은 에이전트 i이다(동점은 미리 지정된 에이전트 순서에 따라 결정된다). 할당이 e-pEF1인 것은 e-pEF1 조건이 최소 지출자(에이전트 i로서)에 대해 만족될 때만이다.
***MBB 계층** 에이전트 i (할당 X 및 가격 벡터 p가 주어졌을 때): 다음과 같은 방식으로 구축된 트리 구조이다.
** 에이전트 i를 루트에 놓는다(레벨 0).
** 현재 가격 벡터 p가 주어졌을 때 에이전트 i의 MBB 집합에 있는 모든 객체를 에이전트 i에 연결한다.
** 각 객체 o에 대해, 트리에 아직 없는 경우 X에서 해당 객체를 소유한 에이전트를 연결한다(레벨 1).
** 레벨 1에 있는 각 에이전트에 대해, 트리에 아직 없는 그의 MBB 집합에 있는 모든 객체를 연결한다.
** 유사한 방식으로 에이전트와 객체를 번갈아 추가하는 것을 계속한다. 각 에이전트에 대해, 그의 MBB 객체를 추가한다. 각 항목에 대해, 그 항목을 소유한 에이전트를 추가한다.
***위반자** (할당 X 및 가격 벡터 p가 주어졌을 때): 최소 지출자 i에 대해 pEF1 조건을 위반하는 에이전트 h이다. 따라서 Xh의 가격은 가장 비싼 항목이 제거되었을 때에도 p(Xi)보다 높다. 유사하게, **e''-위반자**는 최소 지출자에 대해 *e*-pEF1 조건을 위반하는 에이전트이다.
***경로 위반자** (할당 *X*와 가격 벡터 *p*, 그리고 MBB 계층이 주어졌을 때): 최소 지출자 *i*의 MBB 계층에 나타나고, *i*에 대해 pEF1 조건을 부분적으로 위반하는 에이전트 *h*이다. 더 자세히 말하면: MBB 계층의 모서리를 따라 최소 지출자 *i*에서 객체 *o*로 가는 경로가 있고, 그 다음 객체 *o*에서 에이전트 *h*로 가는 모서리가 있다고 가정한다(이는 *X<sub>h</sub>*가 *o*를 포함한다는 것을 의미한다). 만약 p (*X<sub>h</sub>* \ {*o*}) > *p*(*X<sub>i</sub>*)라면, *h*는 경로 위반자이다. 모든 위반자는 경로 위반자이지만, 그 반대는 사실이 아니다. 유사하게, 만약 p (*X<sub>h</sub>* \ {*o*}) > (1+*e*)·*p*(*X<sub>i</sub>*)라면, *h*는 **e-경로 위반자**이다.

#### 알고리즘
매개변수 e가 주어지면, 이 알고리즘은 fPO와 3e-pEF1을 모두 만족하는 할당을 찾는 것을 목표로 한다. 여러 단계로 진행된다.

**1단계: 초기 MBB 할당+가격 (X, p) 구성**

* 한 가지 방법은 각 객체 o를 그것을 가장 높게 평가하는 에이전트 i에게 주는 것(동점은 임의로 해소)이고, o의 가격을 vi,o로 설정하는 것이다. 이는 각 에이전트에 대해 그의 묶음에 있는 모든 객체의 가성비가 정확히 1이고, 다른 묶음에 있는 모든 객체의 가성비가 최대 1임을 보장한다. 따라서 이 할당은 MBB이므로 fPO이기도 하다.
* 할당이 3e-pEF1이면 반환하고, 그렇지 않으면 2단계로 진행한다.

**2단계:** **MBB 계층 내 가격 비선점 제거**:

* 현재 (X, p)가 주어졌을 때, 최소 지출자의 MBB 계층을 구성한다.
* L = 1,2,...에 대해:
** 트리의 레벨 L에 있는 각 에이전트 h에 대해:
***h가 i → ... → h' → o → h 경로를 따라 e-경로 위반자이면, 객체 o를 에이전트 h에서 에이전트 h'로 전송한다(할당은 MBB로 유지된다). 2단계를 다시 시작한다.
* 더 이상 e-경로 위반자가 없으면:
** 할당이 3e-pEF1이면 반환하고, 그렇지 않으면 3단계로 진행한다.

**3단계:** **가격 인상**. 다음 세 가지 중 하나가 발생할 때까지 MBB 계층의 모든 객체 가격을 동일한 배율로 인상한다.

# 최소 지출자의 신원이 변경된다. 이는 계층 외부에 있는 에이전트(항목 가격이 오르지 않음)가 최소 지출자가 될 경우 발생할 수 있다. 이 경우 2단계에서 다시 시작한다.
# 새로운 객체가 MBB 계층에 추가된다. 이는 계층 내 객체의 가격이 r 요인으로 증가할 때, 계층 내 객체의 BB 비율은 r만큼 감소하는 반면, 계층 외부 객체의 BB 비율은 동일하게 유지되기 때문에 발생할 수 있다. 따라서 r이 충분히 크면 일부 외부 객체가 일부 계층 에이전트에게 MBB가 될 것이다. 이 경우에도 2단계에서 다시 시작한다.
# 현재 할당 X가 3e-pEF1이 된다. 이는 계층 내 객체 가격이 증가함에 따라 최소 지출자의 소득이 증가하고, 계층 외부 에이전트의 소득은 일정하게 유지되기 때문에 발생할 수 있다. 따라서 r이 충분히 크면, 최소 지출자에 대해 3e-pEF1 조건이 만족될 수 있다. 이 경우, 할당 X와 새로운 가격 p를 반환한다.

#### 정확성 증명
먼저, 위 알고리즘이 고정된 e>0에 대해 모든 값이 (1+e)의 거듭제곱인 인스턴스에서 실행된다고 가정한다.

* 첫 번째 과제는 알고리즘이 종료됨을 증명하는 것이다. 모든 평가가 (1+e)의 거듭제곱일 때, 알고리즘은 O(poly(m, n, 1/e, ln(Vmax)) 시간에 종료됨을 증명할 수 있다. 여기서 Vmax는 에이전트에 대한 객체의 가장 큰 값이다.
* 초기 할당은 MBB 할당이며, 모든 연산은 이 조건을 유지한다. 따라서 반환된 할당은 MBB이며, fPO이기도 하다.
* 종료 조건에 따라, 알고리즘이 종료될 때마다 반환된 할당은 3e-pEF1이며, 3e-EF1이기도 하다.

이제, 일반적인 가치 평가를 가진 인스턴스가 있다고 가정한다. 우리는 각 가치 평가를 (1+e)의 가장 가까운 거듭제곱으로 반올림한 반올림된 인스턴스에서 위 알고리즘을 실행한다. 각 에이전트 i와 객체 o에 대해, 반올림된 값 Vi'(o)는 Vi(o)와 (1+e)Vi(o) 사이에 있다는 점에 유의한다.

* 이전 단락에 따라, 결과 할당은 반올림된 인스턴스에 대해 fPO이며 3e-EF1이다.
* 모든 e가 충분히 작을 때(특히, 1 / 6 m3 Vmax4 미만일 때), 반올림된 인스턴스에 대해 fPO인 할당은 원래 인스턴스에 대해 PO이다.
*반올림된 인스턴스에 대한 3e-EF1 보장과 반올림에 대한 경계를 결합하면, 반환된 할당이 다음 근사 EF1 조건을 만족함을 얻는다.
**\forall i,j: ~~~ \exists C\subseteq X_j: ~~~|C|\leq 1, ~~~(1+e)\cdot (1+3e)\cdot V_i(X_i) \geq V_i(X_j\setminus C)
*충분히 작은 e에 대해, 곱 (1+e)(1+3e)는 최대 (1+7e)이다. 따라서 반올림된 인스턴스에 대해 3e-EF1인 할당은 원래 인스턴스에 대해 7e-EF1이다.
*원래 가치 평가가 정수이므로, e가 충분히 작을 때, 7e-EF1 할당은 EF1이기도 하다.
*따라서 결과 할당은 원래 인스턴스에 대해 PO+EF1이다.

### 일반화 조정 승자
**아지즈, 카라기아니스, 이가라시, 월시**는 혼합 가치 평가(객체가 양수 및 음수 유틸리티를 모두 가질 수 있음)에 EF1 조건을 확장했다. 그들은 두 에이전트에 대해 O(m2) 시간에 PO+EF1 할당을 찾는 조정 승자 절차의 일반화를 제시했다.

## 효율적인 대략적인 비례 할당
객체 할당은 모든 에이전트가 자신의 몫의 가치를 모든 항목 가치의 최소 1/n로 평가하는 경우 **[[비례 항목 할당|비례적]] (PROP)**이라고 불린다. 에이전트 i에 대해, 그의 묶음에 최대 하나의 항목이 추가되면 i가 묶음을 전체 가치의 최소 1/n로 평가하는 경우 **항목 하나까지의 비례적 (PROP1)**이라고 불린다. 공식적으로, 모든 i에 대해 (M은 모든 재화의 집합):

*\exists Y\subseteq M \setminus X_i: ~~~|Y|\leq 1, ~~~V_i(X_i \cup Y) \geq V_i(M)/n.

PROP1 조건은 **코니처, 프리먼, 샤**가 공정한 공공 의사 결정의 맥락에서 도입했다. 그들은 이 경우 PE+PROP1 할당이 항상 존재한다고 증명했다.

모든 EF1 할당은 PROP1이므로, 비분할 항목 할당에서도 PE+PROP1 할당이 존재한다. 문제는 그러한 할당이 PE+EF1 알고리즘보다 빠른 알고리즘으로 찾아질 수 있는지 여부이다.

**바르만과 크리슈나무르티**는 재화(양의 효용을 가진 객체)에 대한 PE+PROP1 할당을 찾는  알고리즘을 제시했다.

**브란제이와 산도미르스키**는 PROP1 조건을 잡일(음의 효용을 가진 객체)로 확장했다. 공식적으로, 모든 i에 대해:

* \exists Y\subseteq X_i: ~~~|Y|\leq 1, ~~~V_i(X_i \setminus Y) \geq V_i(M)/n.

그들은 잡일에 대한 PE+PROP1 할당을 찾는 알고리즘을 제시했다. 객체의 수 또는 에이전트의 수(또는 둘 다)가 고정되어 있다면 이 알고리즘은 강력한 다항 시간이다.

**아지즈, 카라기아니스, 이가라시, 월시**는 PROP1 조건을 혼합 가치 평가(객체가 양수 및 음수 효용을 모두 가질 수 있음)로 확장했다. 이 설정에서 할당은 각 에이전트 i에 대해, i의 묶음에서 음수 항목 하나를 제거하거나 i의 묶음에 양수 항목 하나를 추가하면, i의 효용이 총량의 최소 1/n인 경우 PROP1이라고 불린다. 그들의 일반화 조정 승자 알고리즘은 두 에이전트에 대한 PE+EF1 할당을 찾으며, 이러한 할당은 PROP1이기도 하다.

**아지즈, 물랑, 산도미르스키**는 에이전트나 객체의 수가 고정되지 않고, 에이전트들이 다른 권리를 가지고 있더라도, 일반적인 혼합 가치 평가를 가진 분수적으로 PE(PE보다 강력함)이며 PROP1인 할당을 찾는 강력한 다항 시간 알고리즘을 제시했다.

## 효율적인 대략적인 공평한 할당
객체 할당은 모든 에이전트의 주관적 가치가 동일할 때 '''공평적''' **(EQ)**이라고 불린다. 이 개념을 연구하는 동기는 인간 피험자들이 비선점 할당보다 공평한 할당을 선호한다는 실험 결과에서 비롯된다. 할당은 두 에이전트 i와 j에 대해, j의 묶음에서 최대 하나의 항목이 제거되면 i의 주관적 가치가 j의 가치만큼 높을 때 **항목 하나까지 공평적 (EQ1)**이라고 불린다. 공식적으로, 모든 i, j에 대해:

*\exists Y\subseteq X_j: ~~~|Y|\leq 1, ~~~V_i(X_i) \geq V_j(X_j\setminus Y).
더 강력한 개념은 **어떤 항목까지도 공평적 (EQx)**이다. 두 에이전트 i와 j에 대해, j의 묶음에서 어떤 단일 항목이 제거되든 i의 주관적 가치는 j의 가치만큼 높다.
*\forall y\in X_j: ~~~V_i(X_i) \geq V_j(X_j\setminus \{y\}).
EQx 할당은 **구르베, 모노, 틀리란**이 "거의 질투 없음"이라는 다른 용어를 사용하여 처음 연구했다. 그들은 할당된 모든 재화의 합집합이 주어진 매트로이드의 기저라는 추가 요구 사항이 있더라도 부분 EQx 할당이 항상 존재함을 증명했다. 그들은 비선점 그래프 절차와 유사한 알고리즘을 사용했다. **숙솜퐁**은 모든 할당이 한 선의 연속적인 부분집합이어야 한다는 추가 요구 사항이 있더라도 EQ1 할당이 존재함을 증명했다.

**프리먼, 시카르, 바이스, 시아**는 다음과 같은 더 강력한 결과를 증명했다.

* 모든 가치 평가가 엄격히 양수일 때, PE+EQx 할당은 항상 존재하며, PE+EQ1 할당을 찾는 의사 다항 시간 알고리즘이 있다.
* 일부 가치 평가가 0일 수 있을 때, PE+EQ1 할당조차 존재하지 않을 수 있으며, PE+EQ/EQ1/EQx의 존재 여부를 결정하는 것은 강력 NP-난해이다.
* PE+EQ1+EF1 할당은 존재하지 않을 수 있다. 존재 여부를 결정하는 것은 일반적으로 강력 NP-난해이지만, 이진(0 또는 1) 가치 평가에서는 다항 시간으로 해결 가능하다.
*

## 소수의 에이전트를 위한 알고리즘
**브레더렉, 카치마르키크, 크놉, [[롤프 니더마이어|니더마이어]]**는 에이전트가 적고(작은 n) 항목 유형이 적으며(작은 m), 항목 유형당 효용이 상한선(V)으로 제한되지만, 각 유형의 항목이 많을 수 있는 설정을 연구한다. 이 설정에 대해 그들은 다음 메타 정리를 증명한다(정리 2): 효율성 기준 E와 공정성 기준 F가 주어졌을 때, 만약 n+u_{\max}+m이 고정되어 있다면, E와 F가 다음 속성을 만족하는 한, E-효율적이면서 F-공정한 할당이 존재하는지 여부를 다항 시간에 결정할 수 있다.

* **공정성**: F-공정한 할당이 존재하는지 여부의 문제는 고정된 차원의 정수 선형 계획법으로 모델링할 수 있다.
* **효율성**: 주어진 할당을 E-지배하는 다른 할당이 존재하는지 여부의 문제는 듀얼 정수 계획법의 트리 깊이와 가장 큰 계수의 절대값이 f(n,u_{\max}) 함수에 의해 상한되는 정수 계획법으로 모델링할 수 있다.

그런 다음, 그들은 여러 일반적인 공정성 및 효율성 기준이 이러한 속성을 만족함을 증명한다. 여기에는 다음이 포함된다.

* **공정성 개념**: 비선점성, EF1, EFx, 그래프-EF(에이전트가 고정된 그래프에서 이웃만을 선점하는 경우), 평등주의, 최대최소몫, 평균-그룹-비선점성(각 에이전트 그룹이 자신의 몫을 구성원 효용의 산술 평균으로 평가하는 경우).
* **효율성 개념**: 파레토 효율성, 그래프 파레토 효율성(파레토 지배가 고정된 그래프에서 이웃 간의 교환만 고려하는 경우), 그룹-파레토 효율성. 할당 X는 k-그룹-파레토 효율적(GPEk)이라면, 크기 k의 모든 그룹에 대해 최소한 동일하게 좋고(효용의 산술 평균에 의해), 크기 k의 최소 한 그룹에 대해 엄격하게 더 좋은 다른 할당 Y가 존재하지 않는 경우이다. GPE1은 파레토 효율성과 동등하다는 점에 유의한다. GPEn은 공리주의-최대화 할당과 동등하다. 왜냐하면 크기 n의 대그룹 G의 경우, 산술 평균 효용은 모든 에이전트 효용의 합과 동등하기 때문이다. 모든 k에 대해 GPEk+1은 GPEk를 의미한다.
그들의 알고리즘의 실행 시간은 입력 크기(비트 단위)에 d^{2.5 d}를 곱한 값이며, 여기서 d는 결과 ILP의 변수 수로 d = m(n+1) + m(n+1)\cdot(4\cdot (4n\cdot V+1)^n)^{m(n+1)}이다.

그들은 나중에 이러한 문제들 중 일부에 대해 더 실용적인 알고리즘을 개발했다.

## 같이 보기
* 부분 파레토 효율성#공정하고 fPO 할당 찾기

## 각주

## 같이 보기
* 효율적인 비선점 분할 - 분할 가능한 자원에 대해. 정확한 공정성이 가능하므로 근사치가 필요하지 않다.
* 항목 할당의 비선점성 - PE 요구 사항이 없다.
* 임대 조화 - 각 에이전트가 단일 항목을 받아야 한다는 추가 제약 조건이 있다.

분류:공평한 분할