정당한 대표성

Justified representation

정당대표(JR)는 다승자 승인 투표의 공정성 기준입니다.비례대표 기준을 찬성 투표에 적용한 것으로 볼 수 있습니다.

배경

비례대표제(PR)는 선거제도를 설계할 때 중요한 고려사항입니다.인구의 다양한 집단과 부문을 그 규모에 비례하여 의회에서 대표해야 한다는 뜻입니다.비례대표를 보장하기 위한 가장 일반적인 제도는 정당명부제입니다.이 시스템에서는 후보자들이 정당으로 나뉘고, 각 시민들은 단일 정당에 투표합니다.각 정당은 투표한 시민의 수에 비례하여 의석수를 받습니다.예를 들어, 10석의 의회에서 시민의 정확히 50%가 A당에, 정확히 30%가 B당에, 정확히 20%가 C당에 투표한다면, 비례대표는 의회가 A당에 정확히 5명, 정확히 3명, 정확히 2명의 후보가 있어야 합니다.현실적으로 분수가 정확하지 않기 때문에 반올림법을 사용해야 하는데, 이는 다양한 배분법으로 할 수 있습니다.

최근 몇 년간 당 제도에 대한 불만이 커지고 있습니다.[1]정당명부제의 가능한 대안은 시민들이 승인 투표를 사용하여 후보자에게 직접 투표할 수 있도록 하는 것입니다.이것은 새로운 도전을 제기합니다: 비례대표를 받을 자격이 있는 미리 지정된 그룹(정당)이 없는데 어떻게 비례대표를 정의할 수 있을까요?예를 들어, 한 유권자가 후보 1,2,3을 승인하고, 다른 유권자가 후보 2,4,5를 승인하고, 세 번째 유권자가 후보 1,4를 승인한다고 가정합니다.이 경우 "비례대표"의 합리적 정의는 무엇입니까?[2]몇 가지 답변이 제안되었으며, 이를 통칭하여 정당한 표현이라고 합니다.

기본개념

아래는 의석수를 k, 유권자수를 n으로 표시합니다.Hare 할당량은 n/k - 단일 좌석을 정당화하는 최소 지지자 수입니다.PR 정당 목록 시스템에서, 최소 L개의 쿼터로 구성된 각 유권자 그룹은 같은 정당에 투표하는 L개의 정당 대표에게 자격이 주어집니다.

이 아이디어를 자연스럽게 일반화하는 것이 L개 이상의 할당량을 가진 유권자 그룹으로 정의되며, 최소 L개 이상의 후보를 공통적으로 승인하는 L-cohesive 그룹입니다.

정당화된 표현 속성

이상적으로, 우리는 모든 L-cohesive 그룹에 대해 모든 구성원이 L개 이상의 대표자를 가져야 한다고 요구하고 싶습니다.강력한 정당화 표현(SJR)이라고 불리는 이 조건은 다음 예에서 볼 수 있듯이 달성할 수 없을 수 있습니다.[3]

예 1.k=3명의 좌석과 4명의 후보자 {a,b,c,d}가 있습니다.승인 세트를 가진 n=12명의 유권자가 있습니다: ab, b, b, bc, c, c, cd, d, d, d, d, a. Hare 할당량은 4입니다.{ab,b,b,b,bc} 그룹은 1개의 할당량을 포함하고 모든 구성원이 후보 b를 승인하므로 1-cohesive입니다.Strong-JR은 후보자 b가 당선되어야 함을 의미합니다.마찬가지로 {bc,c,cd} 그룹은 후보 c를 선택해야 하는 1-cohesive입니다.마찬가지로 {cd,d,d,d,da} 그룹은 선택해야 하고 {da,a,a,ab} 그룹은 a를 선택해야 합니다.그래서 후보를 4명 뽑아야 하는데 위원회 규모가 3명밖에 안 됩니다.따라서 강한 JR을 만족시키는 위원회는 없습니다.

스트롱-JR의 개념을 완화하는 몇 가지 방법이 있습니다.

만장일치 그룹

한 가지 방법은 최소 L개의 할당량을 가진 유권자 그룹으로 정의된 L개의 단일 그룹에만 대표성을 보장하는 것입니다. 그들은 최소 L개의 후보로 정확히 동일한 집합을 승인합니다.이 조건을 만장일치 정당 대표(UJR)라고 합니다.그러나 L-유니버스 그룹은 승인 투표 제도에서 상당히 드물기 때문에 만장일치-JR은 그다지 유용한 보증서가 될 수 없습니다.

응집군

L-cohesive 그룹에 남아 다음과 같이 대표성 보증을 완화할 수 있습니다.유권자의 만족도를 해당 유권자가 승인한 당선자 수로 정의합니다.Strong-JR은 모든 L-cohesive 그룹에서 그룹 구성원의 최소 만족도가 L 이상이어야 합니다.대신, 우리는 그룹 구성원의 평균 만족도가 L 이상이어야 한다고 요구할 수 있습니다.이렇게 더 약한 조건을 평균 정당화 표현(AJR)이라고 합니다.[4]불행히도 이 상태는 여전히 달성할 수 없을 수 있습니다.위의 예 1에서도 스트롱-JR과 마찬가지로 평균-JR은 4명의 후보를 모두 선출하도록 되어 있지만, 3석밖에 없습니다.규모 3의 모든 위원회에서 일부 1-cohesive 그룹의 평균 만족도는 1/2에 불과합니다.

  • 비례 승인 투표는 각 L-cohesive 그룹을 보장하며, 평균 만족도는 L-1보다 큽니다.L-1보다 큰 평균 만족도를 보장하는 다항식 시간 내에 실행되는 Local-Search-PAV라는 변형이 있습니다.[5]: Thm.1,Prop.1 이 보증은 최적입니다. 모든 상수 c>0에 대해 L-1+c 이상의 평균 만족도를 보장하는 규칙은 없습니다.[5]: Prop.2
  • AJR은 위원들이 임기의 일부를 수행할 수 있는 위원회인 소수 위원회에 의해 충족될 수 있습니다.특히 내쉬 규칙은 AJR을 만족합니다.[6]부분적인 사회적 선택도 참조하십시오.

우리는 그룹 구성원의 최대 만족도가 L 이상이어야 함을 요구함으로써 요구사항을 더욱 약화시킬 수 있습니다.즉, 모든 L-cohesive 그룹에서 최소 한 명의 구성원이 L개의 승인된 대표자를 가져야 합니다.이 조건을 EJR(Extended Profided Representation)이라고 하며, Aziz, Brill, Conitzer, Elkind, Freeman 및 Walsh가 도입하고 분석했습니다.[3]더 약한 조건이 있는데, EJR은 L=1(1 cohes 그룹에만 해당)에 대해서만 보유해야 합니다. 이를 JR이라고 합니다.몇 가지 알려진 방법이 EJR을 만족합니다.

  • 평균 만족도가 L-1보다 큰 모든 위원회는 (비둘기 구멍 원칙에 의해) EJR을 만족합니다.[5]따라서 PAV 및 Local-Search-PAV는 EJR을 만족합니다.PAV는 EJR을 만족하는 유일한 가중치 기반 승인 투표 규칙입니다.[3]
  • 동일한[7] 공유의 방법은 EJR을 만족시키는 또 다른 다항식 시간 계산 가능 규칙입니다.
  • EJR을 보장하는 또 다른 폴리타임 알고리즘은 EJR-Exact입니다.[5]
  • EJR 할당을 찾는 간단한 알고리즘은 "Greedy EJR"입니다.이 알고리즘은 L을 k에서 1로 하향 조정하여 유권자의 L-cohesive 부분 집합이 있는지 여부를 확인합니다.그렇다면 가장 큰 L-cohesive 부분 집합을 선택하고, 이들 모두가 승인한 일부 L 후보를 추가합니다.[8]: Algorithm 1
  • 순차적 PAV는 1-코히어군에 대해서만 EJR을 만족하며, k ≤ 5인 경우에만 EJR을 만족합니다. k ≥ 6의 경우 1-코히어군에 대해서도 EJR에 실패합니다.
  • 먼로의 규칙은 EJR에 실패합니다.
  • 주어진 위원회가 EJR을 만족하는지 확인하는 것은 co-NP-complete입니다.

EJR의 또 다른 약화를 PJR(Proportional Profided Representation)이라고 합니다.즉, 모든 L ≥ 1에 대해, 모든 L-cohesive 유권자 그룹에서, 그들의 승인 집합의 연합은 일부 L개의 승자를 포함합니다.산체스-페르난데스, 엘킨트, 라크너, 페르난데스, 피스테우스, 발, 스코우론 등이 도입해 분석했습니다.[4]

  • PAV는 EJR을 만족하므로 PJR도 만족하며, PJR을 만족하는 유일한 중량제 승인 투표 규칙이기도 합니다.그러나 Sequential-PAV는 PJR을 위반합니다.
  • Phragmen의 투표 규칙 중 일부는 PJR, 즉 NP 계산이 어려운 Leximax Phragmen과 폴리타임 계산이 가능한 순차적 Phragmen을 충족하며 또한 위원회 단조성을 충족합니다.
  • k가 n을 나눌 때 먼로와 그리디 먼로는 PJR을 만족시킵니다.그러나 k가 분할되지 않을 때 먼로와 그리디 먼로는 L=1인 경우를 제외하고 모두 PJR을 위반할 수 있습니다.
  • PJR과 폴리타임 모두 계산 가능한 또 다른 규칙은 맥심 지원 규칙입니다.[10]
  • 주어진 위원회가 PJR을 만족하는지 확인하는 것은 co-NP-complete입니다.[5]

부분적으로 응집력이 있는 그룹

위의 조건은 L-cohesive 그룹에 대해서만 무는 것입니다.그러나 L-cohesive 그룹은 실제로는 매우 드물 수 있습니다.[11]위의 조건들은 "거의" 응집력이 있는 그룹들에게는 전혀 보장되지 않습니다.이는 부분적으로 응집력이 있는 그룹에도 무언가를 보장하는 JR의 보다 강력한 개념을 찾는 동기를 부여합니다.

협동 게임 이론에서 매우 일반적인 그러한 개념 중 하나는 코어 안정성(CS)입니다.[3]즉, L석을 가진 유권자 그룹(반드시 응집력이 있는 것은 아님)의 경우, 이 그룹이 L석을 가진 소규모 위원회를 이탈하여 구성할 경우, 적어도 한 명의 유권자의 경우, 그가 승인하는 위원회 구성원의 수가 원래 위원회보다 많지 않다는 것을 의미합니다.EJR은 L-cohesive group만이 이탈이 허용되는 CS의 약한 변형으로 볼 수 있습니다.EJR은 L-cohesive 그룹에 대해 최소 한 명의 구성원이 이탈하지 않도록 요구합니다. 그의 현재 만족도는 이미 L이고, 이는 L 대표자에게 가능한 최대 만족도입니다.

  • 2023년 현재 CS 위원회가 항상 존재하는지는 미결 문제입니다.

Peters, Pierczynski 및 Skowron은[12] 응집력의 다른 약화를 나타냅니다.두 개의 정수 L과 B≤L이 주어졌을 때, 유권자 그룹 S는 최소 L개의 쿼터를 포함할 경우 (L,B)-약-집약이라고 불리고, 최소 L개의 후보로 구성된 집합 C가 있으므로 S의 각 구성원은 최소 B개의 후보를 승인합니다.(L,L)-약-응집성은 L-응집성과 동등하다는 것에 유의하십시오.위원회는 모든 (L,B)-약-집착 그룹에서 일부 B 수상자를 승인하는 구성원이 한 명 이상 있는 경우 FJR(Full Profided Representation)을 만족합니다.분명히 FJR은 EJR을 의미합니다.

  • FJR은 항상 Greed Cohesive Rule(폴리타임이 아닌)에 의해 충족될 수 있습니다. FJR을 만족하는 폴리타임 알고리즘이 있는지 여부는 열려 있습니다.

브릴과 피터스는[13] 다른 응집력 약화를 보여줍니다.선출된 위원회가 주어진 경우, L개 이상의 할당량이 포함된 그룹을 L-drived로 정의하고, 또한 선출되지 않은 후보 중 한 명 이상이 모든 구성원의 승인을 받습니다.위원회는 모든 L-낙선 유권자 그룹에 대해 최대 만족도가 L 이상이면 EJR+를 만족하고, 모든 L-낙선 유권자 그룹에 대해 승인 집합의 조합이 일부 L-낙선자를 포함하면 PJR+를 만족합니다.분명히 EJR+는 EJR과 PJR+를 의미하고, PJR+는 PJR을 의미합니다.

  • PAV, local-search-PAV 및 MES는 EJR+를 만족합니다. 원래 증명은 응집력을 사용하지 않기 때문에 원래 증명과 동일합니다. 모든 그룹 구성원이 승인한 한 후보가 선택되지 않았다는 사실만 사용합니다.
  • EJR+ 위원회를 찾는 폴리타임 그리디 알고리즘인 그리디 정당한 후보 규칙도 있습니다.
  • PJR+는 검증하기 어려운 PJR과 대조적으로 서브모듈 최적화로의 축소에 의해 다항식 시간 내에 검증될 수 있습니다.
  • EJR+는 다음과 같은 간단한 알고리즘으로 다항식 시간 내에 확인할 수 있습니다.1에서 k 사이의 모든 L에 대하여, 그리고 선택되지 않은 모든 후보 c에 대하여: c를 찬성하는 유권자의 수를 세고, L보다 적은 수의 당선자를 찬성합니다.이러한 유권자 수가 최소 L명 이상이면 위원회는 EJR+를 위반합니다.
  • EJR+는 약한 형태의 위원회 단조성을 만족합니다: 모든 k에 대해 크기 k의 EJR+ 위원회 W가 있고 선택되지 않은 후보 c가 있으므로 W에 c를 더하면 (크기 k+1의) EJR+ 위원회가 생성됩니다.

완벽한 표현

관련 없는 다른 속성은 완벽 표현(PER)입니다.즉, 각 유권자가 자신이 승인한 단일 유권자에 대한 매핑이 있으므로 각 유권자는 정확히 n/k 유권자를 대표합니다.완벽한 대리인이 존재하지 않을 수도 있지만, 존재한다면 투표 규칙에 의해 선출될 것으로 예상합니다.[4]

  • PER는 PJR 및 JR과 호환됩니다. 완벽한 대표성을 인정하는 모든 경우에 PJR을 만족시키는 위원회가 존재합니다.그러나 PER은 EJR과 호환되지 않습니다. 완벽한 표현이 존재하지만 EJR을 만족하는 경우가 없습니다. PER은 먼로 규칙에 의해 충족되지만 Greed Monroe, Sequential PAV 및 PAV에 의해 위반됩니다.[4]PER은 또한 Phragmen의 규칙에 의해 충족되므로 이 규칙은 PJR과 PER을 모두 달성하는 데 사용될 수 있습니다.[9]

시사점

SJR은 AJR을 의미하고, CS는 FJR을 의미하며, EJR은 EJR을 의미하며, EJR+는 EJR과 PJR+를 의미합니다.EJR은 UJR과 JR을 모두 의미하는 PJR을 의미합니다.UJR과 JR은 서로를 암시하지 않습니다.

SJR → AJR → EJR → PJR → UJR
↑ ↑ → JR
CS → FJR → ↑ ↑
↑ ↑
EJR+ → ↑ → PJR+

EJR+는 CS 및 FJR과 비교할 수 없습니다.[13]: Rem.2

PER은 완벽한 표현이 존재하는 경우만 고려합니다.따라서 PER은 다른 공리를 암시하거나 암시하지 않습니다.

검증

유권자들의 선호도와 특정 위원회를 고려할 때, 이들 공리 중 어느 하나라도 충족하는지 효율적으로 점검할 수 있을까요?[5]

  • JR은 다항식 시간으로 확인할 수 있습니다.
  • PJR과 EJR은 확인하기 위해 coNP-complete입니다.
  • PER은 NP-검증하기 어렵습니다(완벽한 표현이 존재하는지 여부를 결정하는 것은 NP-완전입니다).

평균만족도

특정 위원회가 주어진 유권자의 만족도는 해당 유권자가 승인한 위원 수로 정의됩니다.유권자 그룹의 평균 만족도는 만족도를 그룹 크기로 나눈 값입니다.유권자 그룹이 L-cohesive(즉, 그들의 크기가 최소 L*n/k이고 최소 L개의 후보를 공통적으로 승인하는 경우):

  • 모든 JR 위원회의 평균 만족도는 1 - 1/L + 1/(Ln) 이상입니다.모든 PJR 위원회도 마찬가지입니다.
  • 모든 EJR 위원회는 최소 (L-1)/2의 평균 만족도를 가지고 있습니다.그래서 EJR은 PJR보다 훨씬 강력한 최악의 만족 보장을 제공합니다.[4]
  • 평균 만족도가 L-1 이상인 모든 위원회는 EJR을 만족합니다.

비례 승인 투표는 L-1보다 큰 평균 만족도를 보장합니다.L-1보다 큰 평균 만족도(따라서 EJR)를 보장하는 Local-Search-PAV라는 변형이 있습니다.[5]: Thm.1,Prop.1 이 보증은 최적입니다. 모든 상수 c>0에 대해 L-1+c 이상의 평균 만족도를 보장하는 규칙은 없습니다.[5]: Prop.2

Skowron은[14] 일정한 크기의 모든 그룹의 평균 만족도에 대한 하한인 다승자 투표 규칙의 비례성 정도를 연구합니다.

변동승수

Freeman, Khang, Pennock은[15] 평균 만족도 개념을 다양한 수의 당첨자가 있는 다당첨자 투표에 적용합니다.그들은 다른 JR 공리들이 다양한 수의 수상자들로 매력적이지 않은 반면, 평균 만족도는 더 강력한 개념이라고 주장합니다.적응에는 다음과 같은 변경 사항이 포함됩니다.

  • 각 유권자는 자신이 승인하는 선출된 후보자뿐만 아니라 자신이 승인하지 않는 비선출 후보자로부터도 만족감을 얻습니다(이로 인해 문제는 각 후보자가 이진 문제인 다중 이슈 투표와 유사합니다).
  • L*n/m 이상의 유권자(여기서 m은 총 후보 수)를 포함하는 경우 그룹은 L-대수이고, 또한 그룹 구성원들이 L 이상의 후보 배치에 동의하는 경우 L-대수입니다(즉i, A의 교집합과 Ci\A의 교집합을 더한 교집합이 L 이상).
  • 모든 L-cohesive 그룹에 대해 구성원의 만족도 평균이 r*L 이상이면 위원회는 r-AS(r-평균-만족도)입니다.JR, PJR 및 EJR 조건도 유사한 방식으로 일반화됩니다.
  • PAV 규칙은 Harmonic(sati)의 합을 최대화하는 위원회를 선택합니다. 여기서 sat는i 유권자 i의 만족도입니다.순차적 프라그멘 규칙과 균등분할방법은 선출된 각 후보자의 부담을 승인하는 유권자들 사이에서 나누고, 승인하지 않는 유권자들 사이에서 선출되지 않은 각 후보자의 부담을 나눈다.이 모든 규칙은 PJR을 만족합니다.MES는 EJR을 위반합니다. 나머지 2개가 EJR을 만족하는지 여부는 알 수 없습니다.
  • 결정론적 규칙은 r = (m-1)/m+엡실론, 임의의 엡실론>0에 대한 r-AS를 보장할 수 없습니다.PAV, Phragmen 및 MES는 r = 1/2+epsilon에 대해 r-AS를 보장할 수 없습니다.그러나 (29/32)-AS를 만족하는 무작위 규칙이 있습니다.

정당대표가격

정당한 대표성의 대가란 정당한 대표성을 가져야 한다는 요건으로 인하여 평균적인 만족도가 상실되는 것을 말합니다.그것은 공정의 대가와 비슷합니다.[8]

경험적 연구

브레데렉, Faliszewski, Kaczmarczyk, Niedermeier는[11] 얼마나 많은 위원회가 다양한 정당화된 대표성 공리를 만족하는지 확인하기 위한 실험 연구를 수행했습니다.그들은 응집력 있는 그룹이 드물고, 따라서 무작위로 선정된 JR 위원회의 많은 부분이 PJR과 EJR을 만족시킨다는 것을 발견했습니다.

번안

정당화된 대표성 공리는 단순한 위원회 투표를 넘어 다양한 환경에 적응되어 왔습니다.

정당승인투표

브릴, 골츠, 피터스, 슈미트-크래플린, 윌커는 JR 원칙을 정당 승인 투표에 적용했습니다.이런 상황에서 유권자들은 개별 후보를 승인하기보다는 정당 전체를 승인해야 합니다.이 설정은 유권자들이 단일 정당을 선택해야 하는 정당명부식 선거와 유권자들이 어떤 후보든 선택할 수 있는 표준승인투표의 중간지대입니다.정당 승인 투표에서 유권자들은 어떤 정당이든 선택할 수 있지만, 정당 내에서 개별 후보를 선택할 수는 없습니다.일부 JR 공리는 다음과 같이 이 설정에 적용됩니다.[16]

유권자 그룹은 L-대규모일 경우 L-cohesive라고 불리며, 모든 그룹 구성원은 최소 한 정당을 공통적으로 승인합니다(이전 설정과 달리 각 정당에는 최소 L명의 후보가 포함되어 있고 정당을 승인하는 모든 유권자는 이 모든 후보를 자동으로 승인한다고 가정하므로 L 정당을 승인할 필요가 없습니다).즉, L-cohesive 그룹은 적어도 한 정당에 동의하는 유권자의 L 할당량을 포함합니다.

비례 정당 대표(PJR)는 모든 L ≥ 1에 대해, 모든 L-cohesive 유권자 그룹에서, 그들의 지지 집합의 연합에 있는 정당들이 적어도 L석을 할당받는 것을 의미합니다.

EJR(Extended Profided Representation)은 모든 정수 L ≥ 1에 대해, 모든 L-cohesive 유권자 그룹에서 적어도 한 명의 유권자에 의해 승인된 정당이 최소 L석을 할당받는 것을 의미합니다.

핵심 안정성(CS)은 L*n/k 크기의 유권자 그룹(반드시 응집력이 있는 것은 아님)에 대해, 이 그룹이 L석을 가진 더 작은 위원회를 이탈하여 구성한다면, 적어도 한 명의 유권자의 경우, 그가 승인하는 정당의 위원 수가 원래 위원회보다 많지 않다는 것을 의미합니다.

다음 예는[16] CS와 EJR의 차이를 보여줍니다.5명의 정당 {a, b, c, d, e}, k=16석, n=16명의 유권자가 있다고 가정해보자: 4*ab, 3*bc, 1*c, 4*ad, 3*de, 1*e.a당 8석, c당 4석, e당 4석의 위원회를 생각해 보세요.유권자의 대표 수는 8, 4, 4, 8, 4, 4입니다.CS가 아닙니다. ab, bc, ad, de를 찬성하는 14명의 유권자 그룹을 생각해 보세요.a당 4석, b당 5석, d당 5석으로 위원회를 구성할 수 있습니다.자, 대표의 수는 9, 5, [0], 9, 5, [0] 이므로 이탈 연합의 모든 구성원들은 엄격히 행복합니다.그러나 원 위원회는 EJR을 만족합니다.할당량은 1입니다.L-cohesive 그룹이 존재하는 가장 큰 L은 L=8(광고 투표자)이며, 이 그룹에는 8석이 할당됩니다.

순위제 선거

JR의 개념은 마이클 덤멧(Michael Dummett)이 순위제 선거를 위해 도입한 이전 개념에서 비롯되었습니다.그의 조건은 모든 정수 L ≥ 1에 대하여 최소 L*n/k 크기의 모든 그룹에 대하여 동일한 L 후보를 맨 위에 올린다면 이 L 후보를 선택해야 한다는 것입니다.

트리코토머스 투표용지

Talmon과 Page는[18] JR의 일부 공리를 승인 투표에서 삼차 투표로 확장하여 각 유권자가 각 후보에 대해 긍정적, 부정적 또는 중립적인 감정을 표현할 수 있도록 합니다.그들은 두 가지 등급의 일반화를 제시합니다: 강한 ("클래스 I")과 약한 ("클래스 II").

그들은 삼차 투표에 맞춘 몇 가지 투표 규칙을 제안하고 시뮬레이션을 통해 그들의 규칙이 채택된 JR 공리를 충족하는 정도를 보여줍니다.

기타적응

  • Bulteau, Hazon, Page, Rosenfeld 및 Talmon은[19] JR 공리를 다중 이슈 투표(영구 투표, 공개 의사 결정 또는 순차 의사 결정이라고도 함)에 적용했습니다.그들의 작업은 후에 찬닥, 샤쉬왓, 피터스에 의해 확장되었습니다.[20]
  • Aziz, Lee, Talmon은[21] JR 원칙을 참여형 예산 편성에 적용했습니다.
  • Brill, Laslier, Skowron은[22] JR을 퇴행적 비례에 적응시켜 소수자에게 더 많은 비중을 부여했습니다.
  • Mavrov, Munagala, Shen은[23] 위원회에 제약이 있을 때 핵심과 JR 공리를 연구합니다.
  • Munagala, Shen, Wang 및 Wang은[24] 에이전트가 비첨가 만족 함수를 가질 수 있는 경우 코어의 곱셈 근사를 연구합니다.

참고 항목

참고문헌

  1. ^ https://www.nytimes.com/2023/09/21/us/politics/politics-discontent.html
  2. ^ Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Nimrod Talmon (2017-10-26). "Multiwinner Voting: A New Challenge for Social Choice Theory". In Endriss, Ulle (ed.). Trends in Computational Social Choice. Lulu.com. ISBN 978-1-326-91209-3.{{cite book}}: CS1 maint: 다중 이름: 저자 목록 (링크)
  3. ^ a b c d e Aziz, Haris; Brill, Markus; Conitzer, Vincent; Elkind, Edith; Freeman, Rupert; Walsh, Toby (2017). "Justified representation in approval-based committee voting". Social Choice and Welfare. 48 (2): 461–485. doi:10.1007/s00355-016-1019-3. S2CID 8564247.
  4. ^ a b c d e f Sánchez-Fernández, Luis; Elkind, Edith; Lackner, Martin; Fernández, Norberto; Fisteus, Jesús; Val, Pablo Basanta; Skowron, Piotr (2017-02-10). "Proportional Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 31 (1). doi:10.1609/aaai.v31i1.10611. ISSN 2374-3468. S2CID 17538641.
  5. ^ a b c d e f g h Aziz, Haris; Elkind, Edith; Huang, Shenwei; Lackner, Martin; Sanchez-Fernandez, Luis; Skowron, Piotr (2018-04-25). "On the Complexity of Extended and Proportional Justified Representation". Proceedings of the AAAI Conference on Artificial Intelligence. 32 (1). doi:10.1609/aaai.v32i1.11478. ISSN 2374-3468. S2CID 19124729.
  6. ^ Aziz, Haris; Bogomolnaia, Anna; Moulin, Hervé (2019-06-17). "Fair Mixing: The Case of Dichotomous Preferences" (PDF). Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19. New York, NY, USA: Association for Computing Machinery. pp. 753–781. doi:10.1145/3328526.3329552. ISBN 978-1-4503-6792-9. S2CID 7436482.
  7. ^ Grzegorz, Pierczyński; Piotr, Skowron; Dominik, Peters (2021-12-06). "Proportional Participatory Budgeting with Additive Utilities". Advances in Neural Information Processing Systems. 34. arXiv:2008.13276.
  8. ^ a b 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].
  9. ^ a b Brill, Markus; Freeman, Rupert; Janson, Svante; Lackner, Martin (2023-03-06). "Phragmén's voting methods and justified representation". Mathematical Programming. doi:10.1007/s10107-023-01926-8. ISSN 1436-4646.
  10. ^ Sánchez-Fernández, Luis; Fernández, Norberto; Fisteus, Jesús A.; Brill, Markus (2018-09-05). "The Maximin Support Method: An Extension of the D'Hondt Method to Approval-Based Multiwinner Elections". arXiv:1609.05370 [cs.GT].
  11. ^ a b Bredereck, Robert; Faliszewski, Piotr; Kaczmarczyk, Andrzej; Niedermeier, Rolf (2019-08-10). "An experimental view on committees providing justified representation". Proceedings of the 28th International Joint Conference on Artificial Intelligence. IJCAI'19. Macao, China: AAAI Press: 109–115. ISBN 978-0-9992411-4-1.
  12. ^ Peters, Dominik; Pierczyński, Grzegorz; Skowron, Piotr (2021). "Proportional Participatory Budgeting with Additive Utilities". Advances in Neural Information Processing Systems. Curran Associates, Inc. 34: 12726–12737.
  13. ^ a b Brill, Markus; Peters, Jannik (2023). "Robust and Verifiable Proportionality Axioms for Multiwinner Voting". arXiv:2302.01989 [cs.GT].
  14. ^ Skowron, Piotr (2021-07-18). "Proportionality Degree of Multiwinner Rules". Proceedings of the 22nd ACM Conference on Economics and Computation. EC '21. New York, NY, USA: Association for Computing Machinery. pp. 820–840. arXiv:1810.08799. doi:10.1145/3465456.3467641. ISBN 978-1-4503-8554-1. S2CID 53046800.
  15. ^ Freeman, Rupert; Kahng, Anson; Pennock, David M. (2021-01-07). "Proportionality in approval-based elections with a variable number of winners". Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI'20. Yokohama, Yokohama, Japan: 132–138. ISBN 978-0-9992411-6-5.
  16. ^ a b Brill, Markus; Gölz, Paul; Peters, Dominik; Schmidt-Kraepelin, Ulrike; Wilker, Kai (2020-04-03). "Approval-Based Apportionment". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (2): 1854–1861. arXiv:1911.08365. doi:10.1609/aaai.v34i02.5553. ISSN 2374-3468. S2CID 208158445.
  17. ^ Dummett, Michael (1984). Voting Procedures. Oxford University Press UK.
  18. ^ Talmon, Nimrod; Page, Rutvik (2021). "Proportionality in Committee Selection with Negative Feelings". arXiv:2101.01435 [cs.GT].
  19. ^ Bulteau, Laurent; Hazon, Noam; Page, Rutvik; Rosenfeld, Ariel; Talmon, Nimrod (2021). "Justified Representation for Perpetual Voting". IEEE Access. 9: 96598–96612. Bibcode:2021IEEEA...996598B. doi:10.1109/ACCESS.2021.3095087. ISSN 2169-3536. S2CID 235966019.
  20. ^ Chandak, Nikhil; Goel, Shashwat; Peters, Dominik (2023-06-26). "Proportional Aggregation of Preferences for Sequential Decision Making". arXiv:2306.14858 [cs.GT].
  21. ^ Aziz, Haris; Lee, Barton E.; Talmon, Nimrod (2018-07-09). "Proportionally Representative Participatory Budgeting: Axioms and Algorithms". Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. AAMAS '18. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems: 23–31. arXiv:1711.08226.
  22. ^ Brill, Markus; Laslier, Jean-François; Skowron, Piotr (2018-07-01). "Multiwinner approval rules as apportionment methods". Journal of Theoretical Politics. 30 (3): 358–382. arXiv:1611.08691. doi:10.1177/0951629818775518. ISSN 0951-6298. S2CID 10535322.
  23. ^ Mavrov, Ivan-Aleksandar; Munagala, Kamesh; Shen, Yiheng (2023). "Fair Multiwinner Elections with Allocation Constraints". arXiv:2305.02868 [cs.GT].
  24. ^ Munagala, Kamesh; Shen, Yiheng; Wang, Kangning; Wang, Zhiyi (2021). "Approximate Core for Committee Selection via Multilinear Extension and Market Clearing". arXiv:2110.12499 [cs.GT].