공정품목할당

공정항목 배분은 공정분할의 일종으로, 분할할 품목이 연속성이 아니라 분리되어 있는 공정분할할할 품목이 분리되어 있다.품목을 서로 다르게 평가하는 여러 파트너에게 나누어 주어야 하며, 각 품목을 한 사람에게 통째로 주어야 한다.이러한 상황은 다양한 현실 시나리오에서 발생한다.

• 상속인 몇 명이 상속재산을 분할하기를 원하는데, 여기에는 집, 자동차, 피아노, 그림 등이 포함된다.
• 몇몇 강사들이 교수진에게 주어진 과목을 나누기를 원한다.각 강사는 하나 이상의 전체 과정을 가르칠 수 있다.
• 흰코끼리 선물 교환 파티

항목들의 불분명한 점은 공정한 분배가 불가능할 수 있다는 것을 의미한다.극단적인 예로서, 단품(예: 집)만 있는 경우에는 반드시 단품(예: 집)에게 주어야 하지만, 이것은 다른 파트너에게 공평하지 않다.배당금이 분할되고 공평한 분할이 항상 존재하는 공정 케이크 커팅 문제와 대조적이다.화폐 지급이나 시간제 순환을 도입하거나 일부 항목을 폐기함으로써 불분명한 문제를 완화할 수 있는 경우도 있다.^{[1]: 285} 그러나 그러한 해결책이 항상 이용 가능한 것은 아니다.

품목 할당 문제에는 몇 가지 성분이 있다.

1. 파트너들은 서로 다른 아이템 분들에 대한 선호도를 표현해야 한다.
2. 그 단체는 공정성 기준을 결정해야 한다.
3. 선호도와 공정성 기준에 기초해 공정분할을 산정하기 위해 공정분할 알고리즘을 실행해야 한다.

이 성분들은 아래에 자세히 설명되어 있다.

우선권

조합 기본 설정

선호도를 결정하는 순진한 방법은 각 파트너에게 가능한 각 번들에 대해 숫자 값을 제공하도록 요청하는 것이다.예를 들어, 나눌 항목이 자동차와 자전거인 경우, 파트너는 자동차를 800으로, 자전거는 200으로, 묶음 {car, 자전거}을(를) 900으로 평가할 수 있다(자세한 예는 분리할 수 없는 물품에 대한 유틸리티 기능 참조).이 접근법에는 두 가지 문제가 있다.

1. 사람이 번들에 대한 정확한 숫자 값을 계산하는 것은 어려울 수 있다.
2. 가능한 번들의 수는 엄청날 수 있다. $만약{\displaystyle }$ m ${\displaystyle m}$ 항목이$$ 있다면 ${\displaystyle {2m}^{}}$ ${\$개의$$ 가능한 번들이 있다.예를 들어, 16개의 항목이 있는 경우 각 파트너는 65536개의 숫자를 사용하여 선호도를 표시해야 한다.

첫 번째 문제는 기본적인 효용보다는 서수 효용의 사용에 동기를 부여한다.순서형 모델에서 각 파트너는 $(\$ 2$^{m})$의 서로 다른 번들 위에 순위를 표시해야 한다. 즉, 어떤 번들이 가장 좋은지, 차선인지 등을 말한다.이것은 정확한 숫자를 계산하는 것보다 쉬울 수 있지만, 항목 수가 많으면 여전히 어렵다.

두 번째 문제는 종종 번들이 아닌 개별 항목으로 처리된다.

• 기본 접근방식에서 각 파트너는 각 항목에 대한 수치 평가를 보고해야 한다.
• 순서형 접근법에서 각 파트너는 품목에 대한 순위를 보고해야 한다. 즉, 어떤 품목이 가장 좋은지, 즉 차선인지 등을 말해야 한다.

적절한 가정 하에서, 품목의 선호도를 번들의 선호도로 끌어올릴 수 있다.^{[2]: 44–48} 그런 다음, 대리인은 개별 항목에 대한 평가/순위를 보고하고, 알고리즘은 해당 대리점에 대한 평가/순위를 계산한다.

가법 선호도

항목 할당 문제를 간단히 하기 위해, 모든 항목이 독립적인 재화라고 가정하는 것이 일반적이다(따라서 대체재화나 보완재가 아니다).^[3] 다음:

• 기본 접근법에서 각 작용제는 부가 효용 함수(모듈 효용 함수라고도 함)를 가지고 있다.에이전트가 개별 항목별로 값을 보고하면 항목 값을 합산해 각 번들의 값을 계산하기 쉽다.
• 서수적 접근법에서, 부가성은 우리가 묶음 사이의 몇 가지 순위를 유추할 수 있게 해준다.예를 들어, 어떤 사람이 z보다 w를 더 선호한다면, 반드시 {w,x}을(를) {w,y}보다 {w,x}을(를) 더 선호하거나 {x}보다 {x,y}을(를) 더 선호한다.이러한 추론은 부분적으로만 추론할 수 있으며, 예를 들어 에이전트가 {x,y}보다 {w}을(를) 선호하는지 또는 {w,z}을(를) {x,y}^[4][5]보다 선호하는지 알 수 없다.

추가성은 각 파트너가 테이블의 항목 집합에서 항상 "선호 가능한 항목"을 선택할 수 있다는 것을 의미하며, 이러한 선택은 파트너가 가질 수 있는 다른 항목과 무관하다.이 속성은 다음에 설명될 몇몇 공정한 할당 알고리즘에 의해 사용된다.^{[1]: 287–288}

콤팩트한 환경설정 표현 언어

콤팩트한 선호 표현 언어는 조합 선호의 완전한 표현성과 첨가 선호의 단순성 사이의 절충으로서 개발되었다.그것들은 적층 효용보다 더 일반적이지만 조합 효용처럼 일반적이지 않은 일부 자연 등급의 효용 함수에 간결한 표현을 제공한다.몇 가지 예는 다음과 같다.^{[1]: 289–294}

• 2단계 기본 설정: 각 파트너는 최대 2개의 크기 묶음에 대한 값을 보고한다.번들의 값은 번들의 개별 항목에 대한 값을 합산하고 번들의 쌍 값을 추가하여 계산한다.전형적으로 대체 항목이 있을 때는 쌍의 값이 음수가 되고, 보완 항목이 있을 때는 쌍의 값이 양수가 된다.이 아이디어는 모든 양의 정수 k에 대한 k-addiction 선호도로 일반화될 수 있다.
• 그래픽 모델: 각 파트너에 대해 서로 다른 항목 간의 종속성을 나타내는 그래프가 있다.기본 접근법에서 공통 도구는 GAI 네트(일반화된 적층 독립성)이다.순서형 접근법에서 공통 도구는 CP 네트(조건형 선호도)이며 그 확장: TCP 네트, UCP 네트, CP 이론, CI 네트(조건적 중요도), SCI 네트(CI Net의 단순화)이다.
• 논리 기반 언어: 각 파트너는 첫 번째 순서 논리 공식을 사용하여 일부 번들을 설명하며, 각 공식에 값을 할당할 수 있다.예를 들어, 파트너는 "(x 또는 (y와 z)의 경우, 내 값은 5"라고 말할 수 있다.즉, 에이전트에서 x, xy, xz, yz, xyz 번들 중 하나에 대해 값이 5인 경우
• 입찰 언어: 조합 선호도를 나타내기 위한 많은 언어가 조합 경매의 맥락에서 연구되었다.이러한 언어 중 일부는 항목 할당 설정에 적응할 수 있다.

공정성 기준

개별보증기준

개별 보증 기준은 파트너가 자신의 선호도를 진실하게 보고하는 한 개별 파트너별로 보유해야 하는 기준이다.그러한 다섯 가지 기준이 아래에 제시되어 있다.가장 약한 것부터 가장 강한 것까지 주문한다(가치가 부가적이라고 가정할 때).^[6]

맥시민 주식

대리인의 최대주주(maximin-min-fair-share 보증이라고도 함)는 그가 분열과 적대적 반대자에 대한 선택에서 자신이 분배자임을 보증할 수 있는 가장 선호되는 묶음이다.모든 에이전트가 자신의 MMS보다 약하게 선호하는 보따리를 받는다면 할당을 MMS-fair라고 부른다.^[7]

비례적 공정점유율(PFS)

대리인의 비례적 공정 점유율은 전체 항목 집합에서 그의 효용성의 1/n이다.모든 대리인이 최소한 그의 비례-공정지분만큼의 보따리를 받는다면 할당을 비례라고 부른다.

최소-최대 공정점유율(mFS)

에이전트의 최소-최대-공정 공유는 그녀가 항상 최고의 공유를 받을 때, 다른 모든 에이전트들이 그녀와 동일한 선호도를 가지고 있다면 할당으로부터 얻을 수 있는 최소한의 효용이다.할당 게임 '누군가 잘라, 내가 먼저 고른다'에서 에이전트가 확실하게 얻을 수 있는 최소한의 효용이기도 하다.모든 에이전트가 자신의 mFS보다 약하게 선호하는 번들을 받는 경우, 할당은 mFS-fair이다.^[6] mFS-fair는 다음과 같은 협상 과정의 결과로 설명될 수 있다.일정한 할당을 제안한다.각 에이전트는 다른 에이전트에 의해 다른 할당을 요구하여 그가 먼저 선택하도록 함으로써 그것에 반대할 수 있다.따라서 에이전트는 모든 파티션에 현재 번들보다 강력하게 선호하는 번들이 있는 경우에만 할당에 반대할 것이다.에이전트 개체가 없는 경우(즉, 모든 에이전트에 대해 현재 자신의 공유보다 모든 번들이 약하게 더 나쁜 파티션이 존재하는 경우) 할당은 mFS-fair이다.

하위 추가 유틸리티를 사용하는 모든 에이전트의 경우 mFS는 최소 ${\displaystyle 1}$/ n ${\displaystyle 1/n}$의 가치가 있으므로 모든 mFS-fair 할당은 비례한다$.$초첨가 유틸리티를 가진 모든 에이전트의 MMSis 값은 최대 $1{\displaystyle \mathrm{}}$/ ${\displaystyle n}$ ${\displaystyle 1/n$이므로 모든 비례 할당은 MMS-fair이다.모든 에이전트가 첨가 효용성을 가질 때 조차도 두 가지 포함은 엄격하다.이는 다음 예에 설명되어 있다.^[6]

에이전트 3개 및 항목 3개:

• 앨리스는 그 아이템들을 2,2,2로 소중히 여긴다.그녀에게는 MMS=PFS=mFS=2.
• 밥은 그 품목들을 3,2,1로 평가한다.그에게는 MMS=1, PFS=2, mFS=3이 있다.
• 칼은 그 품목들을 3,2,1로 중시한다.그에게는 MMS=1, PFS=2, mFS=3이 있다.

가능한 할당은 다음과 같다.

• 각 에이전트에게 항목을 제공하는 모든 할당은 MMS-fair이다.
• 밥과 칼에게 첫 번째와 두 번째, 앨리스에게 세 번째 항목을 주는 모든 할당은 비례한다.
• 어떤 할당도 mFS-fair가 아니다.

위와 같은 의미는 대리점의 가치가 하위/초고화적이지 않을 때는 유지되지 않는다.^[8]

질투-자유(EF)

모든 요원은 다른 어떤 보따리보다 자신의 보따리를 약하게 선호한다.모든 품목에 대한 부러움 없는 배분은 mFS-fair이다. 이는 서수적 정의에서 직접 따르며 추가성에 의존하지 않는다.평가액이 부가적인 경우, EF 할당도 비례적이며 MMS 공정하다.그렇지 않으면 EF 할당은 비례적이지 않을 수도 있고 MMS도 아닐 ^[8]수도 있다. 자세한 내용은 질투 없는 항목 할당을 참조하십시오.

동일소득으로부터의 경쟁균형(CEEI)

이 기준은 다음과 같은 주장에 근거한다: 할당과정은 공급(객체 집합, 각 공시가격)과 수요(대리인의 욕망, 각 대리인이 물건을 사는 데 동일한 예산을 갖는 것) 사이의 평형을 찾는 것으로 간주되어야 한다.공급이 수요와 일치할 때 경쟁적 균형에 도달한다.공정성 주장은 간단하다. 가격과 예산은 누구에게나 동일하다.CEEI는 긍정과 상관없이 EF를 암시한다.에이전트들의 선호도가 가미되고 엄격할 때(각 번들마다 다른 값을 갖는 경우), CEEI는 파레토 효율을 암시한다.^[6]

최근에 제안된 몇 가지 공정성 기준은 다음과 같다.^[9]

질투-자유-1(EF1)

각 두 에이전트 A와 B에 대해, 우리가 B의 묶음에서 A에게 가장 가치 있는 아이템을 제거하면, A는 B를 부러워하지 않는다(즉, B에서 A의 "envy level"은 기껏해야 하나의 아이템의 값이다).단조로운 상태에서는 EF1 할당이 항상 존재한다.

질투-자유-제외-셰이페스트(EFX)

두 에이전트 각각 A와 B에 대해 A에게 가장 가치 없는 아이템을 B의 묶음에서 제거하면 A는 B를 부러워하지 않는다. EFx는 EF1보다 엄격히 강하다.EFx 할당이 항상 존재하는지 여부는 알려지지 않았다.

글로벌 최적화 기준

글로벌 최적화 기준은 주어진 사회복지 기능을 기준으로 분과를 평가한다.

• 평등주의 사회 복지는 단일 대리인의 최소한의 효용이다.항목 배정은 가능한 최대의 평등주의 복지를 달성하는 경우 평등주의-최적이라 불린다. 즉, 그것은 가장 가난한 대리인의 효용을 극대화한다.가장 작은 효용성을 최대화하는 몇 가지 다른 할당이 있을 수 있기 때문에 평등주의 최적성은 종종 렉시민 최적성으로 정제된다: 가장 작은 효용성을 최대화하는 할당 부분집합에서 두 번째로 작은 효용, 그 다음 세 번째로 작은 효용 등을 최대화하는 할당을 선택한다.
• 나시 사회복지는 대리인들의 효용의 산물이다.전력회사의 생산량을 최대화할 경우 Nash-최적화 또는 Maximum-Nash-Welfare라는 과제.나시-최적 배분은 공정성 특성이 좋다.^[9]

개별 기준보다 글로벌 최적화 기준의 장점은 복지를 극대화하는 할당이 파레토 효율적이라는 점이다.

할당 알고리즘

공정성 항목 배분을 위한 다양한 알고리즘을 특정 공정성 기준에 대한 페이지에서 조사한다.

• 최대 공유 항목 할당.
• 비례적 품목 할당;
• Minimax 공유 항목 할당:에이전트의 mFS 계산 문제는 coNP-완전성이다.mFS 할당의 존재 여부를 결정하는 문제는 N ${\displaystyle {}^{}}$ ${\displaystyle N^{}}$ ${\displaystyle P^{}}$ ${\$에 있지만, 정확한 계산 복잡성은 여전히 알려져 있지 않다.^[6]
• 부러움 없는 아이템 할당.
• 평등주의 품목 할당.
• 내시-최적 할당: 공리-최적 및 내시-최적 할당 계산의 경도를 입증한다^[10].^[12] 내시 최적 배분에 대한 근사 절차를 제시한다.

• 선택 시퀀스: 미리 지정된 턴 순서에 따라 에이전트가 교대로 항목을 선택하는 간단한 프로토콜.목표는 사회복지 기능의 기대 가치(예: 평등주의 또는 공리주의)를 대리인의 가치평가에 대한 일부 확률론적 가정 하에 최대화하는 방식으로 선정 순서를 설계하는 것이다.
• 경쟁 평형: CE 할당을 찾기 위한 다양한 알고리즘이 피셔 시장에 관한 기사에 설명되어 있다.

변형 및 확장형

다른 자격

이 변종에서, 다른 작용제는 자원의 다른 분수를 가질 권리가 있다.공통적으로 내각부처를 연립 정당으로 나누는 경우가 있다.각 당이 국회 의석수에 따라 각 부처를 받아야 한다고 보는 게 일반적이다.다양한 공정성 개념은 그에 맞게 수정되어야 한다.이 문제와 몇 가지 솔루션에 대한 자세한 내용은 및 를 참조하십시오.

그룹에 할당

이 변종에서 번들은 개별 에이전트가 아닌 에이전트 그룹에 주어진다.일반적인 사용 사례는 가족 간에 상속을 나누거나 대학 내 학과 간에 시설을 나누는 것이다.동일한 그룹의 모든 에이전트는 동일한 번들을 사용하지만, 다른 가치로 평가할 수 있다.고전적 항목 할당 설정은 모든 그룹이 단골격인 특수한 경우에 해당한다.

단체로는 만장일치 공정성(각 단체 소속 모든 대리인의 눈에 공정성)을 보장할 수 없기 때문에 민주적 공정성(각 단체 소속 대리인의 절반 이상 보는 공정성)으로 완화된 경우가 많다.^[16]

공공의사

이 변종에서, 몇몇 대리인은 몇 가지 문제에 대한 결정을 받아들여야 한다.일반적인 사용 사례는 매일 어떤 활동을 할지 결정해야 하는 가족이다(여기서 각 이슈는 하루).각 에이전트는 각 이슈의 다양한 옵션에 서로 다른 유틸리티를 할당한다.고전적인 항목 할당 설정은 각 이슈가 항목에 해당하고, 각 결정 옵션이 특정 에이전트에 해당 항목을 제공하는 것과 일치하며, 대리점의 유틸리티는 항목이 다른 사람에게 주어지는 모든 옵션에 대해 0이다.이 경우 비례성은 각 대리점의 효용이 적어도 그의 "독재 효용"의 1/n, 즉 각 이슈에서 최선의 옵션을 선택하여 얻을 수 있는 효용성을 의미한다.비례 migh는 달성할 수 없지만, PROP1은 라운드 로빈 품목 할당을 통해 달성할 수 있다.^[17]

참고 항목

• 빈 커버링 문제와 빈 패킹 문제 - 각각 분리할 수 없는 물품 할당과 분리할 수 없는 집안일 할당에 대한 특별한 사례로 볼 수 있는 잘 연구된 두 가지 최적화 문제.이러한 문제에 사용되는 많은 기법들은 공정한 항목 배분의 경우에도 유용하다.
• 공정 분할 실험 - 공정 항목 할당과 관련된 일부 사례 연구 및 실험실 실험 포함.
• 임대차 화합 - 분리할 수 없는 품목과 고정된 총 비용을 동시에 분할해야 하는 공정한 분할 문제.
• 공정한 무작위 배정 - 돈이 없는 공정한 분배 문제, 즉 무작위화를 통해 공정성이 확보된다.
• 주택 할당 문제 - 각 대리인이 정확히 하나의 대상을 얻어야 하며, 통화 이체나 임의화가 없어야 하는 공정한 분할 문제.
• 공정성 가격 - 공정성과 효율성 사이의 절충에 대한 일반적인 척도로서 항목 할당 설정에 대한 일부 결과가 있다.
• 공정 부분집합 문제

참조