평등주의 아이템 할당

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 주제를 잘 모르는 사람들에게 불충분한 맥락을 제공한다. 독자에게 더 많은 맥락을 제공하여 기사를 개선할 수 있도록 도와주십시오.(2020년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다. 기술 세부 정보를 삭제하지 않고 비전문가가 이해할 수 있도록 개선하십시오.(2020년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

최대-최소 항목배분이라고도 불리는 평등주의 항목배분은 공정성 기준이 평등주의 규정을 따르는 공정성 항목배분 문제다.목표는 에이전트의 최소값을 최대화하는 것이다.즉, 가능한 모든 할당 중에서 에이전트의 가장 작은 값이 가능한 한 큰 할당을 찾는 것이 목표다.동일한 최소값을 가진 할당량이 둘 이상일 경우, 목표는 이러한 할당 중에서 두 번째로 작은 값이 가능한 한 큰 값을 선택하는 것, 즉 렉시민 순서에 의해.따라서 평등주의적 품목 배분을 렉시민 품목배분이라고 부르기도 한다.

각각의 대리인에 대한 각 항목 j의 가치가 0이거나 일정한_j v가 되는 특별한 경우를 산타클로스 문제라 부른다: 산타클로스는 정해진 선물 세트를 가지고 있고, 가장 행복하지 않은 아이가 가능한 한 행복하지 않은 아이가 행복할 수 있도록 아이들에게 그것들을 산타클로스 문제라고 한다.

관련된 몇 가지 문제는 다음과 같다.

• 최대 최소 목표를 가진 다방향 번호 분할은 모든 에이전트가 동일한 가치를 갖는 특별한 경우에 해당한다.더욱 특별한 경우는 칸막이 문제인데, 이는 두 에이전트의 경우에 해당된다.이 특별한 경우조차 일반적으로 NP-hard이다.
• 관련 없는 기계 스케줄링은 최대값을 최소화하는 것이 목표인 이중 문제다.
• 맥시민 주식항목 할당은 다른 문제인데, 최적의 솔루션을 얻는 것이 아니라 각 대리점이 일정 임계값을 초과하는 가치를 받는 솔루션을 찾는 것이 목표다.

정확한 알고리즘

일반적인 문제는 NP-hard이지만, 작은 인스턴스들은 제약 프로그래밍 기법에 의해 정확하게 해결될 수 있다.Bouveret와 Lemaître는 별개의 제약조건 만족 문제에 대한 렉시민-최적 해결책을 찾기 위한 다섯 가지 다른 알고리즘을 제시한다.^[1]그들은 특별 케이스로 최대 항목 할당량을 제시한다.

근사 알고리즘

아래 n은 에이전트 수, m은 항목 수입니다.

산타클로스 문제의 특별한 경우:

• Vansal과 Sviridenko는^[2] 선형 프로그램을 반올림하여 $($ ${\displaystyle n}$/ ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ log logn / 로그 ${\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle n}$) {\$displaystyle$ O$(\log{n}/\log$ {\$log {\log}}}}}})$ - 약사$$ 알고리즘을 부여했다.
• Feige는^[3] 다항식 시간 상수 인자 근사 알고리즘이 존재한다는 것을 증명했지만, 그 증명은 Lovász 로컬 보조정리법을 사용했고 비구축적이었다.
• 아사드푸어, 페이지, 사베리는^[4] 하이퍼그래프 매칭을 사용하여 실제 상수 인자 근사 알고리즘을 제공했다.그들은 그것이 한정된 수의 단계로 수렴된다는 것을 증명할 수 없었다.
• 안나말라이, 칼라리츠, 스벤손은^[5] 다항 시간 13 근사 알고리즘을 부여했다.

일반적인 경우, 부가 가치가 있는 에이전트의 경우:

• 베자코바와 다니엘은^[6]${\displaystyle }$(${\displaystyle \mathrm{m}}$- ${\displaystyle n}$+ 1${\displaystyle }$) ${\displaystyle (m-n+1)}$ 근사$$ 알고리즘을 부여했다.
• 아사드푸어와 사베리는^[7] $O{\displaystyle (n\sqrt{}}$ ${\displaystyle \cdot }$ ${\displaystyle {\log }^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle$ O$({\sqrt{n}}\cdot \log ^{3}n)}$ 근사$$ 알고리즘을 부여했다.그들의 알고리즘은 나무에서 부분 일치를 반올림하기 위해 반복적인 방법을 사용한다.그들은 또한 그 문제에서 소수의 사람들을 제외하는 것이 허용될 때 더 나은 한계를 제공한다.

• Chakrabarty박사, Chuzoy과 Khanna[8]O(m1/ε){O(m^{1/\varepsilon})\displaystyle}의 런타임과,(로그⁡ 로그 ⁡ m로그 ⁡ m){\displaystyle \varepsilon \in \Omega \left({\frac{\log \log m}{\log m}}\right)}Ω 어떤ε ∈에 대한 O(mε){O(m^{\varepsilon})\displaystyle}-approximation 알고리즘을 주었다. .모든 품목에 0이 아닌 효용이 있는 특수 사례에 대해, 그들은 2-요인 근사 알고리즘을 제공했고, 더 나은 요인에 근사치하는 것이 어렵다는 것을 증명했다.
• Golovin[9]. 이는 문제의 적절한 선형 프로그래밍 이완 라운딩에서는 최고의 가능한 재산 획득에 있는, 모든 정수 k에{k\displaystyle}대행의(1− 1/k){\displaystyle(1-1/k)}일부 유틸리티 적어도 OPT/k{OPT/k\displaystyle} 받는 알고리즘을 주었다.ult이 선형 프로그램에 대해.그는 또한 두 종류의 상품이 있는 특수 케이스에 대해 $O{\displaystyle }$($){\displaystyle$O$({\sqrt{n}}})$ 근사$$ 알고리즘을 부여했다.
• Dall'Aglio와 Mosca는^[10] 조정 우승자 절차의 적응에 기초하여 두 에이전트에 대해 정확한 지점 및 바인딩 알고리즘을 제공했다.

하위 모듈 유틸리티 기능이 있는 에이전트의 경우:

• Golovin은^[9]${\displaystyle }$(${\displaystyle m\mathrm{-n}}$+${\displaystyle }$1$$) {\$displaystyle (m-n+1)}$ 근사치$$ 알고리즘과 일반 효용 함수에 대한 유사성 결과를 제공했다.
• 괴만, 하비, 이와타, 미르코니는^[11] $($ 1${\displaystyle {}^{}}$/ ${\displaystyle {4\mathrm{}}^{}}$ ${\displaystyle {}^{}}$ 로그 ${\displaystyle {\log }^{}}$ n${\displaystyle {2\mathrm{}}^{}}$ log ${\displaystyle {3\mathrm{}}^{}}$ / 2 ${\displaystyle {}^{}}$ ${\displaystyle m}$)를 부여한다. ${\displaystyle$ O$({\sqrt {m}}\cdot n^{1/4}\cdot \cdlog n\cdot ^{3/2}m$).
• Nguyen, Roos, Rothe는^[12][13] 더 강한 경도 결과를 제시한다.

정규화

평등주의 원칙에는 두 가지 변종이 있다.^[14]

• 절대 평등주의(또는 절대 렉시민), 최대화가 대리인의 명목 값을 사용하는 경우.
• 최대화가 정규화된 값을 사용하는 상대적 평등주의(또는 상대적 렉시민) - 번들 값을 모든 항목의 값으로 나눈 값.

두 규칙은 대리점의 평가가 이미 정상화되었을 때, 즉 모든 대리점이 모든 항목 집합에 동일한 가치를 부여할 때 동등하다.그러나 비정상화 가치에 따라 다를 수 있다.예를 들어, 4개의 항목이 있다면, 앨리스는 1,1,1,1로, 조지는 3,3,3,3으로, 절대 렉시민 룰은 앨리스에게는 3개의 항목을, 조지에게는 1개의 항목을 주는데, 이는 이 경우의 효용 프로필이 (3,3)이 최적이기 때문이다.반대로, 상대-leximin 규칙은 두 에이전트의 총 값이 1로 정규화된 경우 이 경우 정규화된 효용 프로파일이 최적(0.5,0.5)이기 때문에 각 에이전트에 두 개의 항목을 부여한다.

기타 공정성 기준과의 비교

비례성

비례적 할당이 존재할 때마다 상대적-완화적 할당은 비례한다.비례 배분에서 에이전트의 상대적 가치가 최소 1/n이므로 가장 작은 상대적 가치를 최대화할 때 동일성이 유지되어야 하기 때문이다.그러나 위의 예와 같이 절대 렉시민 배분이 비례하지 않을 수도 있다.

부러움-자유

1. 모든 대리점이 0이 아닌 한계 효용과 동일한 가치를 갖는 경우, 상대적-독소적 할당은 PO와 EFX이다.

• 렉시민++라 불리는 렉시민의 개선은 일반적으로 동일한 가치로 EFX(PO는 아님)를 보장한다.^[15]

2. 부가 가치 평가가 있는 두 에이전트의 경우, 상대적 렉시민 할당은 EF1이다.^{[15]: Thm.5.5} 그러나:

• 절대 렉시민 할당은 부가 가치가 있는 두 개의 에이전트에도 EF1이 아닐 수 있다.예를 들어 {0,1,1,1} 및 {3,3,3,3}(으)로 가치를 두는 4개의 상품과 2개의 에이전트가 있다고 가정해 보십시오.고유한 절대 렉시민 할당은 첫 번째 에이전트에 {1,1,1}을(를) 주고 두 번째 에이전트에 {3}을(를) 주지만, 두 번째 에이전트는 부러워한다.^{[16]: 32}
• 상대적 렉시민 할당은 3명 이상의 에이전트에 대한 EF1이 아닐 수 있다.예를 들어 {30,0,0,0,0} {20,5,0} 및 {0,12,12,6}(으)로 가치를 두는 4개의 상품과 3개의 에이전트가 있다고 가정해 보십시오.가치평가가 정규화됨(총가치는 30)에 유의한다.렉시민 할당에서 첫 번째 재화는 에이전트 1에 할당되어야 한다.그런 다음 두 번째와 세 번째 상품을 에이전트 2에 할당해야 하고, 에이전트 3에 대한 선은 남아 있다.그러나 에이전트 3은 아이템을 제거한 후에도 에이전트 2를 부러워한다.^{[17]: 22}

3. 모든 대리인이 매트로이드 순위 함수(즉, 이항 여백이 있는 하위 모델)인 값을 갖는 경우, 절대 leximin 할당 집합은 최대 제품 할당 집합과 동일하며, 그러한 할당은 모두 max-sum과 EF1이다.^[16]

4. 가사(부정적 효용성이 있는 항목)의 분할할 수 없는 할당과 관련하여, 부가 가치 평가를 받는 3, 4명의 에이전트와 함께, 모든 렉시민-최적 배분은 PROP1과 PO이며, 일반적으로 동일한 가치를 가진 에이전트 n명에게는 모든 렉시민-최적 배분이 EFX이다.^[18]

맥시민 주식

모든 대리인이 동일한 가치를 갖는 경우, 정의상 평등주의 배분은 각 대리인에게 최소한 자신의 최대 몫을 부여한다.

그러나 에이전트들의 평가가 다르면 문제는 다르다.최대주주 할당은 만족도 문제인데, 목표는 각 대리인이 동일한 가치 임계값을 초과하는 값을 받도록 보장하는 것이다.이와는 대조적으로, 평등주의 배분은 최적화 문제인데, 목표는 각 대리인에게 가능한 한 높은 가치를 부여하는 것이다.어떤 경우에는 결과적인 할당이 매우 다를 수 있다.예를 들어 {3,0,0,0,0}, {3-2ε,195,0} 및 {1-2ε,1,2ε}(여기서 ε은 작은 양의 상수)로 평가하는 4개의 상품과 3개의 에이전트가 있다고 가정하자.가치평가는 정규화되므로(총가치는 3이다), 절대 렉시민과 상대 렉시민이 동등하다는 점에 유의한다.

• 렉시민 할당은 유틸리티프로파일을 산출한다(3,2,, 2ε).첫 번째. 그렇지 않으면 최소 효용이 0이다 에이전트 1로이동해야 한다 항목은.그런 다음 두 번째와 세 번째 항목은 에이전트 2로이동해야 한다. 그렇지 않으면 다음으로 작은 효용이 ε 이하이므로 에이전트 3은 마지막항목만 얻는다.
• 에이전트의 최대 공유 값은 0, ε, 1이다.따라서 최대 공유 할당량은 에이전트 3에게 첫 번째 세 가지 항목 중 하나를 제공해야 한다. 이 경우 가능한 유틸리티 프로파일은 (0, 2 2, 1) 또는 (3, ε, 1+2ε)이다.

예시는 k>3에 대해 1-of-k MMS로 확장할 수 있다.k+1 상품과 이를 {k, 0, ..., 0}, {k-(k-1),, ,, ,, ,, ,, 0}, {1-k,, 1, ..., kε}.에이전트 3의 1-of-k MMS가 1인 반면 렉시민 유틸리티 프로파일은 (k, kε, kε)이어야 한다.

실제 애플리케이션

렉시민 규칙은 공립학교의 사용하지 않는 교실을 전세학교에 공정하게 할당하는 데 사용되어 왔다.^[19]

참고 항목

수요 감소 절차는 순서적 의미에서 평등주의적인 할당을 반환한다. 즉, 다발의 선형 순위, 최하위 순위를 가진 에이전트의 순위를 최대화한다.그것은 번들을 주문하는 모든 수의 에이전트에서 작동한다.

참조