임의우선순위항목할당

Random priority item allocation

Random priority(RP;랜덤시리얼독재)[2]라고도 불리는 Random priority([1]RP;랜덤시리얼독재)는 분할할 수 없는 항목을 사람들 간에 공평하게 나누는 절차입니다.

예를 들어 그 이하의 파트너가 서로 다른 항목을해야 한다고 합니다.아이템은 분리할 수 없기 때문에 일부 파트너는 반드시 선호도가 낮은 아이템(또는 아이템이 전혀 없음)을 얻을 수 있습니다.RSD는 다음과 같은 방법으로 이 상황에 공정성을 도입하려고 합니다.균일한 분포에서 에이전트의 랜덤 순열을 그립니다.그런 다음 순서대로 개체를 선택합니다(순서의 첫 번째 에이전트가 먼저 선택됨).

특성.

RSD는 아이템의 수가 최대 에이전트 수일 때 진실한 메커니즘입니다.이는 아이템을 선택할 기회가1번밖에 없기 때문입니다.이 기회에서 가장 우세한 전략은 사용 가능한 아이템을 선택하는 것입니다.

RSD는 ex-ante envy-free(EF)입니다.이것은, 각 에이전트가 주문의 각 포지션에 표시할 기회가 같기 때문입니다.랜덤 치환에서 마지막에 나온 에이전트가 먼저 나타난 에이전트를 부러워할 수 있기 때문에 확실히 사후 부러움이 없는 것은 아닙니다.

RSD는 항상 Pareto Efficient(PE; 파레토 효율화) 이후 결과를 산출합니다.그러나 에이전트가 무작위 할당에 대해 Von Neumann-Morgenstern 유틸리티를 가지고 있는 경우, 즉 오브젝트에 대한 복권(ex-ante envy-freeness는 ex-post envy-freeness보다 약하지만 ex-ante pare-to-효율성은 ex-post pare-efficiencyfficiency보다 강하다).예를 들어 에이전트, 항목, VNM 유틸리티가 3개 있다고 가정합니다.

아이템 x 아이템 y 아이템 z
앨리스야. 1 0.8 0
밥. 1 0.2 0
칼 1 0.2 0

RSD는 (특정 오브젝트보다 우선순위가 일치하기 때문에) 각 에이전트에 각 오브젝트의 1/3 확률과 예상되는 유틸리티 벡터(0.6, 0.4, 0.4)의 프로파일을 제공합니다.그러나 항목 y를 Alice에 할당하고 Bob과 Carl 사이에 항목 x,z를 랜덤으로 할당하면 기대되는 효용 벡터(0.8, 0.5, 0.5)가 생성됩니다.원래의 효용 벡터는 파레토 [1]효율이 아닙니다.

오브젝트에 대한 에이전트의 랭킹이 랜덤으로 균일하게 작성되면 에이전트의 수가 [3]증가함에 따라 RSD에 의해 부여되는 할당이 ex-ante PE일 확률은 0에 가까워집니다.

대안 규칙인 확률-직렬규칙은 ex-ante PE(ex-post PE를 의미함)와 ex-ante EF이지만 진실하지는 않다.대칭적이고 진실하며 이전의 [4]PE인 메커니즘은 입증할 수 없다.

일반화

에이전트보다 많은 객체

의 오브젝트가 있는 경우 일부 에이전트는 여러 오브젝트를 얻을 수 있습니다.RSD를 이 케이스로 확장하는 방법은 여러 가지가 있습니다.

  • 한 가지 방법은 각 에이전트에 할당량을 정의하고(할당량의 합계가 개체 수와 같도록), 각 에이전트에 할당량까지 항목을 선택하도록 하는 것입니다.이 절차는 여전히 전략적으로 유효하지만 매우 불공정합니다.
  • 다른 방법은 각 에이전트가 단일 개체를 선택한 후 모든 개체를 가져올 때까지 각 에이전트가 단일 개체를 선택하는 다른 라운드를 수행하는 것입니다. 그러면 라운드 로빈 항목 할당 절차가 수행됩니다.이 절차가 더 공정하기는 하지만 전략적으로 입증되지는 않습니다.
  • 두 절차 모두 피킹 시퀀스의 특수한 경우입니다.

일반적인 의사결정

RSD는 그룹이 일련의 대안에서 단일 대안을 선택해야 하는 보다 일반적인 설정에 대해 정의할 수 있습니다.이 설정에서는 RSD는 다음과 같이 동작합니다.먼저 에이전트를 임의로 허가합니다.모든 선택지 세트부터 순서대로 나머지 선택지 중에서 원하는 선택지를 선택하도록 각 담당자에게 의뢰합니다.모든 에이전트의 프리퍼런스를 고려한 후에도 여러 가지 대안이 남아 있는 경우 RSD는 이러한 대안보다 균일하게 랜덤화됩니다.앞서 말한 항목 분할 설정에서는 대체 항목이 에이전트에 할당되어 있습니다.각 에이전트는 동일한 항목을 가져오는 모든 할당 간에 무관심하기 때문에 선호도에 큰 동등성 클래스를 가집니다.

이 일반적인 설정에서는 모든 에이전트가 대체 에이전트보다 엄격하게 우선하는 경우 RSD는 랜덤에이전트를 그려 에이전트에 가장 적합한 대체 에이전트를 선택하는 것으로 줄어듭니다.이 절차는 랜덤독재(RD)라고 불리며,[5] 선호도가 엄격할 때 효율적이고 전략적인 고유한 절차입니다.그러나 에이전트가 약한 선호도를 가질 수 있는 경우 RD(RSD 포함)를 확장하는 절차는 효율성과 전략성을 [6]모두 충족시키지 못합니다.

「 」를 참조해 주세요.

  • 공정한 무작위 할당 페이지는 RSD를 확률론적 연속 규칙과 같은 동일한 문제를 해결하기 위한 다른 절차와 비교한다.
  • 독재 메커니즘의 페이지에는 RSD는 사회적 선택을 위한 일반적인 규칙이지 반드시 항목 할당을 위한 것은 아니라고 기술되어 있습니다.

레퍼런스

  1. ^ a b Bogomolnaia, Anna; Moulin, Hervé (2001). "A New Solution to the Random Assignment Problem". Journal of Economic Theory. 100 (2): 295. doi:10.1006/jeth.2000.2710.
  2. ^ Abdulkadiroglu, Atila; Sonmez, Tayfun (1998). "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems". Econometrica. 66 (3): 689. doi:10.2307/2998580. JSTOR 2998580.
  3. ^ Manea, Mihai (2009). "Asymptotic ordinal inefficiency of random serial dictatorship". Theoretical Economics. 4 (2): 165–197. hdl:10419/150127.
  4. ^ Zhou, Lin (1990). "On a conjecture by gale about one-sided matching problems". Journal of Economic Theory. 52: 123–135. doi:10.1016/0022-0531(90)90070-Z.
  5. ^ Gibbard, Allan (1977). "Manipulation of schemes that mix voting with chance" (PDF). Econometrica. 45 (3): 665–681. doi:10.2307/1911681. JSTOR 1911681.
  6. ^ Brandl, Florian; Brandt, Felix; Suksompong, Warut (2016). "The impossibility of extending random dictatorship to weak preferences". Economics Letters. 141: 44–47. arXiv:1510.07424. doi:10.1016/j.econlet.2016.01.028. S2CID 4917725.