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

다양한 선호를 가진 사람들 사이에 물건을 할당할 때, 두 가지 주요 목표는 파레토 효율성과 공정성이다. 물건이 분할 불가능하기 때문에 공정한 할당이 존재하지 않을 수 있다. 예를 들어, 단 하나의 집과 두 사람이 있을 때, 집의 모든 할당은 한 사람에게는 불공평할 것이다. 따라서 최소최대몫 공정성(MMS), 항목 하나까지의 비선점성(EF1), 항목 하나까지의 비례성(PROP1), 항목 하나까지의 공평성(EQ1)과 같은 몇 가지 일반적인 근사치들이 연구되어 왔다. **효율적인 대략 공정한 항목 할당**(Efficient approximately fair item allocation) 문제는 파레토 효율적(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 할당을 반환한다.chapter=On approximately fair allocations of indivisible goods 둘 다 비선점 사이클이 없는 할당을 반환하도록 보장된다. 그러나 할당이 파레토 효율적이라고 보장되지는 않는다. * 대략적인 CEEI 메커니즘은 임의의 선호 관계에 대한 부분적인 EF1 할당을 반환한다. 할당된 객체에 대해서는 PE이지만 모든 객체에 대해서는 PE가 아니다 (일부 객체는 할당되지 않을 수 있으므로).s2cid=154703357 이는 PE와 EF1을 모두 만족하는 할당을 찾는 문제로 이어졌다.
## 최대 내쉬 복지 규칙
**카라기아니스, 쿠로카와, 물랑, 프로카치아, 샤, 왕**doi-access=free는 PE+EF1 할당의 존재를 처음으로 증명했다. 그들은 모든 에이전트가 양의 가산 유틸리티를 가질 때, 유틸리티 곱을 최대화하는 모든 할당(내쉬 복지라고도 함)이 EF1임을 증명했다. 최대화 할당이 PE임은 명백하므로, PE+EF1 할당의 존재가 뒤따른다. 최대 곱 할당은 바람직한 속성을 가지고 있지만, 다항 시간 내에 계산할 수 없다. 최대 곱 할당을 찾는 것은 NP-난해이며issn=1573-7454 심지어 APX-hard이다.issn=0020-0190 이로 인해 최대 곱을 근사하려는 다양한 연구가 이루어졌으며, 근사 계수는 다음과 같이 개선되었다. * 콜과 가첼리스s2cid=52817863는 2.89배 근사를 제시했다. * 아나리, 가란, 사베리, 싱s2cid=2076238는 e배 근사를 제시했다. * 콜, 데바누어, 가텔리스, 제인, 마이, 바지라니, 야즈단보드isbn= 978-1-4503-4527-9는 2배 근사를 제시했다. 그러나 이러한 근사치는 EF1을 보장하지 않는다. 최근의 일부 알고리즘은 대략적인 최대 곱과 공정성을 모두 보장한다. * 바르만, 크리슈나무르티, 바이스는 의사다항 시간(아래 증가 가격 알고리즘 참조)에 PE, (1+epsilon)-EF1, 최대 곱에 대한 1.45 근사를 보장하는 알고리즘을 제시한다. * 가그와 맥글로플린doi-access=free은 강력한 다항 시간 내에 PE, PROP1, 최대 곱에 대한 2-근사를 보장하는 알고리즘을 제시한다. * 카라기아니스, 그라빈, 황s2cid=60441171은 일부 상품을 폐기함으로써 EFX, PROP1, 최대 곱에 대한 2.9-근사를 보장하는 알고리즘을 제시한다(2-근사 할당의 존재도 보여준다). 최대 곱 해법은 가치 평가가 이진일 때(각 항목의 가치가 0 또는 1) 특히 매력적이다. * 아마나티디스, 비르파스, 필로스-라치카스, 홀렌더, 부두리스arxiv=2001.09838는 이진 가치 평가에서 최대 곱 해법이 EF1뿐만 아니라 EFX(어떤 재화까지도 비선점)라는 것을 증명했다. 이는 각 항목의 가치가 두 가지 값 중 하나를 가질 수 있을 때마다(반드시 0 또는 1일 필요는 없음) 성립한다. 일반적인 가산 가치 평가에서는 최대 곱이 EFX를 의미하지 않지만, 그것의 자연스러운 일반화를 의미한다. * 할페른, 프로카치아, 프소마스, 샤s2cid=220496489는 이진 가치 평가에서 사전순 우선순위가 있는 최대 곱 규칙이 다항 시간 내에 계산될 수 있으며, 그룹-전략-불능이라는 것을 증명했다.
### 비가산 가치 평가
에이전트의 효용이 가산적이지 않더라도, 최대 곱 해법이 반드시 EF1은 아니다. 그러나 에이전트의 효용이 적어도 준모듈러라면, 최대 곱 해법은 약한 속성인 항목 1을 제외한 한계 비선점성(MEF1)을 만족한다. 이는 각 에이전트 i가 자신의 묶음을 (j의 묶음에서 가장 좋은 항목을 제거한) 한계효용만큼 또는 그 이상으로 평가한다는 것을 의미한다. 공식적으로:isbn=9781450339360 *\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) 더 일반적인 효용 함수에 대해서도 비슷한 근사치가 발견되었다. * 베이, 가그, 호퍼, 멜혼isbn=978-3-319-66700-3과 아나리, 마이, 가란, 바지라니는 각 항목 종류의 여러 단위를 가진 시장을 연구하며, 가치 평가는 하고 조각별 선형 오목이다. 이는 다른 항목 종류를 가진 묶음의 효용이 각 단일 항목 종류에 대한 효용의 합이라는 것을 의미하지만("분리 가능"의 의미), 각 항목 종류에 대해서는 가치 평가가 한계 효용 체감을 가진다는 것을 의미한다("조각별 선형 오목"의 의미). 그들은 최대 곱에 대한 2-근사를 제시한다. * 오르테가s2cid=3479888는 이진 가치 평가를 가진 다단위 시장을 연구한다. 그는 평등주의 규칙이 로렌츠 우위적(렉시민-최적성보다 강한 속성), 효용에서 유일하며, 그룹 전략불능이라는 것을 증명한다. * 가그, 호퍼, 멜혼은 예산 가산 가치 평가를 연구한다. 이는 준모듈러 효용의 하위 클래스이다. 그들은 입력 크기와 1/ε에 대한 다항 시간 내에 최대 곱에 대한 (2.404 + ε)-근사를 제시한다. * 베나부, 차크라보르티, 이가라시, 지크s2cid=208328700는 이진 한계 이득을 가진 준모듈러 효용을 연구한다(즉, 각 항목은 각 묶음의 값에 0 또는 1을 더한다). 그들은 이러한 가치 평가에서 최대 곱 및 렉시민 할당 모두 EF1이며 공리주의 복지(효용의 합)를 최대화한다는 것을 증명한다. * 바바오프, 에즈라, 파이게eprint=2002.10704도 이진("이분법적") 한계 이득을 가진 준모듈러 효용을 연구한다. 그들은 로렌츠 우위적 할당을 출력하는 결정론적인 진실한 메커니즘을 제시한다. 이는 EFX이며 최대 곱이다.
### 혼합 가치 평가
마틴과 월시eprint=1911.11005는 "혼합 만나"(양수와 음수 모두를 가질 수 있는 가산 가치 평가)에서 효용의 곱을 최대화하는 것(또는 효용의 음수 곱을 최소화하는 것)이 EF1을 보장하지 않는다는 것을 보여준다. 그들은 또한 EFX3 할당이 동일한 효용을 가질 때도 존재하지 않을 수 있음을 증명한다. 그러나 삼차 효용을 가질 때, EFX와 PO 할당, 또는 EFX3과 PO 할당은 항상 존재한다. 그리고 동일한 효용을 가질 때, EFX와 PO 할당은 항상 존재한다. 이 경우 다항 시간 알고리즘이 있다.
## 가격 인상 알고리즘
**바르만, 크리슈나무르티, 바이스**isbn= 978-1-4503-5829-3는 양의 가산 가치 평가를 위한 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이기도 하다.Lem.4.1 ***e*-pEF1 할당**, 일부 상수 *e* > 0: 두 에이전트 *i*.*j*에 대해, (1+*e*)·p(*Xi*)의 곱이 Xj에서 가장 비싼 항목을 제외한 p(Xj)보다 크거나 같은 할당이다. *e*가 클수록 *e*-pEF1 조건이 약해진다는 점에 유의한다. 특히, pEF1 할당은 모든 *e* > 0에 대해 *e*-pEF1이지만, 그 반대는 사실이 아니다. MBB와 *e*-pEF1을 모두 만족하는 할당은 또한 **e-EF1**이다.Lem.4.1 ***최소 지출자**: 할당 및 가격 벡터가 주어졌을 때, 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*로 가는 모서리가 있다고 가정한다(이는 *Xh*가 *o*를 포함한다는 것을 의미한다). 만약 p (*Xh* \ {*o*}) > *p*(*Xi*)라면, *h*는 경로 위반자이다. 모든 위반자는 경로 위반자이지만, 그 반대는 사실이 아니다. 유사하게, 만약 p (*Xh* \ {*o*}) > (1+*e*)·*p*(*Xi*)라면, *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는 에이전트에 대한 객체의 가장 큰 값이다.eprint=1707.0473123–29 * 초기 할당은 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이다.29–34 *반올림된 인스턴스에 대한 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이다.
## 일반화 조정 승자
**아지즈, 카라기아니스, 이가라시, 월시**sec.4는 혼합 가치 평가(객체가 양수 및 음수 유틸리티를 모두 가질 수 있음)에 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 조건은 **코니처, 프리먼, 샤**isbn=978-1-4503-4527-9가 공정한 공공 의사 결정의 맥락에서 도입했다. 그들은 이 경우 PE+PROP1 할당이 항상 존재한다고 증명했다. 모든 EF1 할당은 PROP1이므로, 비분할 항목 할당에서도 PE+PROP1 할당이 존재한다. 문제는 그러한 할당이 PE+EF1 알고리즘보다 빠른 알고리즘으로 찾아질 수 있는지 여부이다. **바르만과 크리슈나무르티**doi-access=free는 재화(양의 효용을 가진 객체)에 대한 PE+PROP1 할당을 찾는 강력 다항 시간 알고리즘을 제시했다. **브란제이와 산도미르스키**eprint=1907.01766는 PROP1 조건을 잡일(음의 효용을 가진 객체)로 확장했다. 공식적으로, 모든 i에 대해: * \exists Y\subseteq X_i: ~~~|Y|\leq 1, ~~~V_i(X_i \setminus Y) \geq V_i(M)/n. 그들은 잡일에 대한 PE+PROP1 할당을 찾는 알고리즘을 제시했다. 객체의 수 또는 에이전트의 수(또는 둘 다)가 고정되어 있다면 이 알고리즘은 강력한 다항 시간이다. **아지즈, 카라기아니스, 이가라시, 월시**eprint=1811.08673는 PROP1 조건을 혼합 가치 평가(객체가 양수 및 음수 효용을 모두 가질 수 있음)로 확장했다. 이 설정에서 할당은 각 에이전트 i에 대해, i의 묶음에서 음수 항목 하나를 제거하거나 i의 묶음에 양수 항목 하나를 추가하면, i의 효용이 총량의 최소 1/n인 경우 PROP1이라고 불린다. 그들의 일반화 조정 승자 알고리즘은 두 에이전트에 대한 PE+EF1 할당을 찾으며, 이러한 할당은 PROP1이기도 하다. **아지즈, 물랑, 산도미르스키**eprint=1909.00740는 에이전트나 객체의 수가 고정되지 않고, 에이전트들이 다른 권리를 가지고 있더라도, 일반적인 혼합 가치 평가를 가진 분수적으로 PE(PE보다 강력함)이며 PROP1인 할당을 찾는 강력한 다항 시간 알고리즘을 제시했다.
# 효율적인 대략적인 공평한 할당
객체 할당은 모든 에이전트의 주관적 가치가 동일할 때 **공평적** **(EQ)**이라고 불린다. 이 개념을 연구하는 동기는 인간 피험자들이 비선점 할당보다 공평한 할당을 선호한다는 실험 결과에서 비롯된다.hdl-access=free 할당은 두 에이전트 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 할당은 **구르베, 모노, 틀리란**이 "거의 질투 없음"이라는 다른 용어를 사용하여 처음 연구했다.isbn=978-1-61499-418-33 그들은 할당된 모든 재화의 합집합이 주어진 매트로이드의 기저라는 추가 요구 사항이 있더라도 부분 EQx 할당이 항상 존재함을 증명했다. 그들은 비선점 그래프 절차와 유사한 알고리즘을 사용했다. **숙솜퐁**issn=0166-218X은 모든 할당이 한 선의 연속적인 부분집합이어야 한다는 추가 요구 사항이 있더라도 EQ1 할당이 존재함을 증명했다. **프리먼, 시카르, 바이스, 시아**eprint=1905.10656는 다음과 같은 더 강력한 결과를 증명했다. * 모든 가치 평가가 엄격히 양수일 때, PE+EQx 할당은 항상 존재하며, PE+EQ1 할당을 찾는 의사 다항 시간 알고리즘이 있다. * 일부 가치 평가가 0일 수 있을 때, PE+EQ1 할당조차 존재하지 않을 수 있으며, PE+EQ/EQ1/EQx의 존재 여부를 결정하는 것은 강력 NP-난해이다. * PE+EQ1+EF1 할당은 존재하지 않을 수 있다. 존재 여부를 결정하는 것은 일반적으로 강력 NP-난해이지만, 이진(0 또는 1) 가치 평가에서는 다항 시간으로 해결 가능하다. *
# 소수의 에이전트를 위한 알고리즘
**브레더렉, 카치마르키크, 크놉, 니더마이어**s2cid=195298520는 에이전트가 적고(작은 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)}이다.sub.4.3 그들은 나중에 이러한 문제들 중 일부에 대해 더 실용적인 알고리즘을 개발했다.first1 = Frank