공정성 가격

Price of fairness

공정분할 이론에서 공정가격(POF)은 공정분할이 달성할 수 있는 가장 큰 경제적 복지와 공정분할이 달성할 수 있는 경제적 복지의 비율이다.POF는 사회가 공정성을 보장하기 위해 취해야 할 복지 상실의 양적 척도이다.

일반적으로 POF는 다음 공식으로 정의됩니다.

정확한 가격은 우리가 관심 있는 분배의 종류, 공정성의 종류, 그리고 사회 복지의 종류에 따라 크게 달라진다.

가장 잘 연구된 사회복지 유형은 모든 에이전트의 (정규화된) 효용 합계로 정의되는 공리주의적 사회복지이다.또 다른 유형은 평등주의적 사회복지이며, 이는 에이전트당 최소(정규화된) 효용으로 정의된다.

수치 예시

이 예에서는 비례성의 공리적인 가격(UPOP)에 초점을 맞추고 있습니다.

100개의 파트너로 나눠야 하는 이기종 토지 소유지를 생각해 보십시오. 파트너들은 모두 100으로 평가합니다(또는 100으로 정규화됨).먼저 극단적인 경우를 살펴보겠습니다.

  • 가능한 최대 공리주의적 복지는 10000이다.이러한 복지는 각 파트너가 다른 지역을 원하는 매우 드문 경우에만 달성할 수 있습니다.
  • 비례분할에서는 각 파트너가 최소 1의 값을 받기 때문에 공리적 복지는 최소 100이다.

상한

위에서 설명한 극단적인 경우에서는 UPOP / 10000/100 = 100이라는 사소한 상한이 이미 부여되어 있습니다.하지만 상한선을 좀 더 좁힐 수 있어요

100명의 파트너에게 효율적인 토지분할을 실시하고, 공리주의적 복지를 U로 한다고 가정해 봅시다.비례분할로 전환하고 싶습니다.이를 위해 NAT은 파트너를 현재 가치에 따라 그룹화합니다.

  • 현재 값이 10 이상인 파트너는 fucky라고 불립니다.
  • 다른 파트너들은 불운하다고 불린다.

두 가지 경우가 있습니다.

  • 운이 좋은 파트너가 10개 미만인 경우, 현재의 분할을 포기하고 비례 분할을 새로 만듭니다(예: 마지막 감산자 프로토콜 사용).비례분할에서는 모든 파트너가 최소 1의 값을 받기 때문에 총값은 100 이상입니다.원래의 나눗셈의 값은 (10*100+90*10)=120보다 작기 때문에 UPOP는 최대 19입니다.
  • 10개 이상의 행운의 파트너가 있는 경우, 다음과 같은 마지막 체감자 프로토콜을 사용하여 비례 분할을 생성하십시오.
    • 운이 좋은 각 파트너는 자신의 점유율을 0.1씩 줄이고 다른 불행한 파트너에게 그 비율을 줄인다.본인 또는 불행한 파트너 중 한 명이 이 몫을 받게 됩니다.
    • 이는 (최대 90명의) 불행한 파트너가 각각 지분을 가질 때까지 계속됩니다.현재 10개 이상의 행운의 파트너는 각각 이전 가치의 0.1개 이상을 가지고 있으며, 불행한 파트너는 각각 이전 가치 이상을 가지고 있으므로 UPOP는 최대 10개입니다.

요약하면, 파트너의 가치 척도에 관계없이, UPOP는 항상 20 미만입니다.

하한

UPOP는 1까지 낮출 수 있습니다.예를 들어, 모든 파트너가 동일한 가치 척도를 가지고 있다면, 공정성에 관계없이 어느 부문에서도 공리주의적 복지는 100이다.따라서 UPOP=100/100=1이 됩니다.

그러나 우리는 최악의 경우 UPOP, 즉 UPOP가 큰 가치 측정의 조합에 관심이 있다.여기 그런 예가 있다.

파트너에는 다음 두 가지 유형이 있다고 가정합니다.

  • 전체 토지의 가치를 균일하게 평가하는 90명의 통일된 파트너(즉, 토지의 가치는 크기에 비례한다).
  • 10개의 집중적인 파트너, 각각 0.1개의 토지에 해당하는 단일 지역만을 중시합니다.

다음 두 개의 파티션을 고려합니다.

  • 공평한 분할:토지를 균일하게 분할하여 각 파트너에게 토지의 0.01을 부여합니다. 집중 파트너는 원하는 지역에서 각각 0.01을 받습니다.이 부문은 공평하다.획일적인 파트너의 가치는 1인 반면 집중적인 파트너의 가치는 10이므로 공리적인 복지는 190이다.
  • 효율적인 분할:모든 땅을 집중적인 파트너에게 나누어 각 파트너가 원하는 지역 전체를 제공합니다.공리적인 복지는 100*10=1000입니다.

이 예에서 UPOP는 1000/120=5.26입니다.따라서 5.26은 최악의 경우 UPOP(가치 측정의 가능한 모든 조합에 대해 "최악의 경우"가 취해진다)의 하한이다.

합쳐진

모든 결과를 종합하면 최악의 경우 UPOP가 5와 20 사이에 있다는 것을 알 수 있다.

이 예는 POF의 바인드에 사용되는 전형적인 인수입니다.하한을 증명하기 위해서는 하나의 예를 설명하는 것으로 충분하며, 상한을 증명하기 위해서는 알고리즘 또는 다른 정교한 인수를 제시해야 합니다.

일반 조각 케이크 커팅

비례의 실용적 가격

위에서 설명한 수치 예는 100에서n개의 파트너로 일반화할 수 있으며 최악의 경우 UPOP에 대해 다음 범위를 지정할 수 있습니다.

'n/2' 'UPOP' '2'n-1'
UPOP = θ√√√√√√√√√√n(n)

두 파트너의 경우 더 자세한 계산은 8-4*33 1 1.07의 [1]범위를 나타냅니다.

선망의 공리적인 가격

케이크 전체가 나눠질 때 부러움 없는 나눗셈은 항상 비례합니다.따라서 최악의 경우 UPOP의 하한('n/2)도 여기에 적용됩니다.한편, 상한으로서 n-1/[1]2의 약한 한계만 있습니다.이 때문에,

n/2 up UPOV n n-1/2
ω(nn) up UPOV o O(n)

두 파트너의 경우 더 자세한 계산은 8-4*33 1 1.07의 [1]범위를 나타냅니다.

공정성의 실용적 가격

두 파트너의 경우 더 자세한 계산을 통해 9/8=1.[1]125의 한계를 알 수 있습니다.

분리할 수 없는 재화의 할당

분할할 수 없는 항목의 경우, 비례성, 선망 없음 또는 공정성을 충족하는 할당이 항상 존재하는 것은 아닙니다(단순한 예로, 두 파트너가 하나의 가치 있는 항목을 나누려고 한다고 가정해 보십시오).공정한 항목 할당을 참조하십시오.따라서 공정성 계산에서는 관련 공정성 개념을 충족하는 양도가 없는 경우를 고려하지 않는다.결과의 [1]간단한 개요:

UPOP = n - 1 + 1/n, 2인용: 3/2.
(3n+7)/9-O(1/n) up UPOV n n-1/2 (2인용): 3/2
UPOQ=최종, 2인용: 2

일반 조각으로 잡무를 자르다

"케이크"가 바람직하지 않은 경우(예: 잔디 깎기) 케이크 절단 문제에 대해 다음과 같은 [1]결과를 얻었습니다.

(n+1)^2/4n up UPOP n n, 2인용: 9/8
(n+1)^2/4n up UPOV infinity 무한대, 2인용 : 9/8
UPOQ=n

분할할 수 없는 불량 할당

UPOP = n
UPOV = 무한대
UPOQ = 무한대

연결된 조각으로 케이크 커팅

공정하게 케이크를 자르는 문제는 조각들이 서로 연결되어야 하는 다양성이 있다.이 변동에서는 POF 공식의 지정자와 분모는 모두 작기 때문에(최대값이 작은 세트에 이어지므로), 우선 POF가 절단된 경우보다 작아야 하는지 커야 하는지 명확하지 않습니다.

공정성의 공리적인 가격

우리는 공리주의적 복지에 [2]대해 다음과 같은 결과를 얻었다.

UPOP = θ√√√√√√√√√√n(n)
UPOV = δ(140n)
n-1+1/n † EPOQ † n
EPOQ = δ(n)

평등주의적 공정성 가격

비례분할에서 각 파트너의 가치는 총액의 1/n 이상이다.특히, 최하위 대리인(사업부의 평등주의적 복지라고 불린다)의 가치는 1/n 이상이다.이것은 평등주의-최적 분할에서 평등주의 복지는 적어도 1/n이며, 따라서 평등주의-최적 분할은 항상 비례한다는 것을 의미합니다.따라서 평등적 비례 가격(EPOP)은 1이다.

EPOP=1

유사한 고려 사항 균평(EPOQ)의 평등 주의 가격에:적용된다.

EPOQ=1

envy-freeness의 평등 주의 가격이 훨씬:[2]더 크다.

EPOV)n/2

이것은 흥미로운 결과, 이 같은 상황들이 조건에 envy-freeness의 주장과 가장 불행한 시민들는 사회적 격차가 증가한다를 암시한다.비례의 기준 훨씬 덜 해롭다.

복지 극대화 가격

대신 복지의 손실 공정성 때문에 계산, 우리는 공정성의 손실 복지 최적화로 인해 계산할 수 있다.우리는 다음과 같은 결과를:[2].

proportional-price-of-egalitarianism 1=
envy-price-of-egalitarianism)n-1
proportional-price-of-utilitarianism)무한대
envy-price-of-egalitarianism)무한대

연결된 블록으로 분할할 수 없는 물품 할당

cake-cutting에 있어서, 불가분의 항목 과제가 항목을 끊지 말고 각 지정 작품은 라인에 있는 집단을 형성하야 한다 하고 있는 변화한다.결과의 간략하게:[3].

UPOP)n-1+1/n
UPOV = δ(140n)
UPOQ = 무한대, 2인용: 3/2
EPOP = 1
EPOV = n/2
EPOQ = 무한대, 2인용: 1

연결된 조각에 의한 잡무 절단

결과의 [4]간단한 개요:

n/2 up UPOP nn
UPOV = 무한대
UPOQ = n
EPOP = 1
EPOV = 무한대
EPOQ = 1

동종 자원 할당

공정성의 가격은 석유나 목재와 같은 균질한 분할 가능한 자원의 배분 경쟁에서도 연구되어 왔다.알려진 결과는 다음과 같습니다.[5][6]

UPOV = UPOP = δ(140n)

이는 동등한 소득에서 경쟁적 평형의 법칙이 선망 없는 배분을 낳으며, 그 공리적인 가격은 O(nn)이기 때문이다.

기타 컨텍스트

공정성 가격은 공정 부분집합 문제의 맥락에서 연구되었다.

정당 대표 가격은 승인 투표 [7]환경에서 정당 대표성을 보유해야 하는 요건에 따른 평균 만족도의 손실이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; Kyropoulou, M. (2011). "The Efficiency of Fair Division". Theory of Computing Systems. 50 (4): 589. CiteSeerX 10.1.1.475.9976. doi:10.1007/s00224-011-9359-y. S2CID 8755258.
  2. ^ a b c Aumann, Y.; Dombb, Y. (2010). "The Efficiency of Fair Division with Connected Pieces". Internet and Network Economics. Lecture Notes in Computer Science. Vol. 6484. pp. 26. CiteSeerX 10.1.1.391.9546. doi:10.1007/978-3-642-17572-5_3. ISBN 978-3-642-17571-8.
  3. ^ Suksompong, W. (2019). "Fairly Allocating Contiguous Blocks of Indivisible Items". Discrete Applied Mathematics. 260: 227–236. arXiv:1707.00345. doi:10.1016/j.dam.2019.01.036. S2CID 126658778.
  4. ^ Heydrich, S.; van Stee, R. (2015). "Dividing Connected Chores Fairly". Theoretical Computer Science. 593: 51–61. doi:10.1016/j.tcs.2015.05.041.
  5. ^ Bertsimas, D.; Farias, V. F.; Trichakis, N. (2011). "The Price of Fairness". Operations Research. 59: 17–31. doi:10.1287/opre.1100.0865. hdl:1721.1/69093.
  6. ^ Bertsimas, D.; Farias, V. F.; Trichakis, N. (2012). "On the Efficiency-Fairness Trade-off". Management Science. 58 (12): 2234. CiteSeerX 10.1.1.380.1461. doi:10.1287/mnsc.1120.1549.
  7. ^ Elkind, Edith; Faliszewski, Piotr; Igarashi, Ayumi; Manurangsi, Pasin; Schmidt-Kraepelin, Ulrike; Suksompong, Warut (2021-12-13). "The Price of Justified Representation". arXiv:2112.05994 [cs.GT].