Proportionality Degree in Participatory Budgeting

이 논문은 참여 예산 배분에서 '동등 분배법 (MES)'과 '프라그멘의 순차적 규칙'의 비례성 정도를 이론적으로 분석하고 실험적으로 검증하여, 공리적 보장이 더 강한 MES 도 두 규칙이 정량적 관점에서는 동일한 비례성 정도를 가진다는 사실을 규명했습니다.

핵심

이 논문은 **'참여예산제 (Participatory Budgeting)'**라는 민주적 시스템에서, **"어떤 규칙을 써야 시민들의 의견을 가장 공정하게 반영할 수 있을까?"**라는 질문에 답하기 위해 쓰인 연구입니다.

비유하자면, 이 논문은 **"학교 급식비 (예산) 를 어떻게 나누어 먹어야 모든 반 (시민 집단) 이 불만 없이 배부르게 먹을 수 있을까?"**를 수학적으로 분석한 보고서라고 볼 수 있습니다.

주인공은 두 가지 유명한 '나눔 규칙'입니다.

1. 평등 분배법 (MES): "우리 다 같이 돈을 모아서, 내가 원하는 메뉴를 사자. 내 돈이 부족하면 다른 친구가 보태주자."
2. 프라그멘 규칙 (Phragmén): "시간이 지날수록 내 계좌에 돈이 쌓여. 내가 원하는 메뉴 값이 모이면 바로 사자."

이 두 규칙이 과연 얼마나 '공정하게' (Proportionality) 돈을 나누어 주는지를 연구한 내용입니다.

---

🍕 핵심 내용: "공정한 나만의 피자"

1. 문제 상황: 왜 '공정함'을 숫자로 재야 할까?

과거에는 "이 규칙은 정의로운가? (예/아니오)"라고만 따졌습니다. 하지만 현실은 더 복잡합니다.

• 비유: "100 명 중 30 명이 피자 10 판을 원하는데, 규칙 A 는 8 판을 사주고 규칙 B 는 9 판을 사준다면, 둘 다 '정의'를 실현한 걸까요?"
• 연구의 목적: 단순히 '예/아니오'가 아니라, **"집단 크기에 비례해서 얼마나 만족스러운 결과를 얻었는지"**를 숫자 (비례성 지수) 로 정확히 측정해 보자는 것입니다.

2. 두 규칙의 대결: "규칙은 다르지만, 결과는 비슷하다"

연구자들은 두 가지 규칙을 수학적으로 분석했습니다.

• 평등 분배법 (MES): 이론적으로 아주 강력한 '공정함의 원칙' (EJR) 을 따릅니다. 마치 "누구도 소외되지 않게 완벽하게 계산한다"는 철학을 가집니다.
• 프라그멘 규칙: 이론적으로는 MES 보다 약한 원칙 (PJR) 을 따릅니다. "누군가 조금 더 기다려야 할 수도 있다"는 식의 유연함을 가집니다.

🎉 놀라운 발견:
이론적으로 MES 가 더 강력한 원칙을 따르는데도, 실제로 '공정함의 수치 (비례성 지수)'를 계산해 보면 두 규칙은 거의 똑같은 성능을 냅니다!

• 비유: 한 명은 "완벽한 수학자"처럼 계산하고, 다른 한 명은 "현실적인 장인"처럼 계산하지만, 최종적으로 배달된 피자 판 수는 거의 같다는 뜻입니다.
• 결론: 두 규칙 모두 매우 훌륭하며, 이론적으로도 최적에 가까운 성능을 보입니다.

3. 실험 결과: "현실 세계에서도 똑같다"

이론만 믿기엔 부족해서, 실제 전 세계 참여예산제 데이터 100 개를拿来서 컴퓨터로 시뮬레이션했습니다.

• 실험 내용: 두 규칙에 '남은 예산까지 다 쓰게 하는 (Exhaustion)' 기능을 추가하거나, 단순히 '인기 많은 것부터 사는 (Greedy)' 규칙과 비교했습니다.
• 결과:
  • 두 규칙 (MES, Phragmén): 거의 동점! (약간의 차이만 있음). 둘 다 시민들의 의견을 매우 잘 반영했습니다.
  • 단순 인기 투표 (Greedy): "가장 인기 있는 것만 사자"는 규칙은 소수 집단의 의견을 무시해서, 공정성 점수가 현저히 낮았습니다.
  • 비유: 인기 투표는 "피자 10 판 중 9 판이 페퍼로니라면 페퍼로니만 10 판 다 사는 것"이라면, MES 와 Phragmén 은 "페퍼로니 8 판, 치즈 2 판"처럼 집단의 크기에 맞춰 골고루 배분해 줍니다.

4. 결론: 무엇을 선택해야 할까?

• 두 규칙 모두 추천: 이론과 실험 모두에서 두 규칙은 매우 훌륭합니다. 어느 것을 써도 시민들의 목소리가 예산에 잘 반영됩니다.
• 단순 인기 투표는 NO: 단순히 '좋아요'가 많은 것만 고르는 방식은 소수 의견을 배제하므로 공정하지 않습니다.
• 미래의 과제: 두 규칙이 이미 '최고'에 가까운지, 혹은 그보다 더 완벽한 규칙이 있을지 연구가 더 필요하다는 점을 남겼습니다.

---

💡 한 줄 요약

"참여예산제를 운영할 때, '평등 분배법'이나 '프라그멘 규칙' 중 하나를 쓰면, 이론과 현실 모두에서 시민들의 의견을 가장 공정하게 반영할 수 있습니다. 단순히 인기 많은 것만 고르는 방식은 피하세요!"

이 논문은 복잡한 수학적 증명과 실험을 통해, **"어떤 규칙을 써도 결국 같은 좋은 결과를 얻을 수 있다"**는 위안과 확신을 주었습니다.

기술 요약

1. 연구 배경 및 문제 정의 (Problem)

• 참여예산제 (Participatory Budgeting, PB): 시민들이 공적 자금의 배분에 직접 참여하여 프로젝트를 제안하고 투표하는 민주적 절차입니다.
• 핵심 문제: 기존의 PB 규칙 (규칙) 들은 '공정성'과 '대표성'을 보장하는 이산적 공리 (Axioms) (예: 정당화된 대표성 JR, 확장된 정당화된 대표성 EJR 등) 를 만족하는지 여부에 초점을 맞추어 왔습니다. 그러나 이러한 공리적 접근은 "만족한다/안 한다"는 이분법적 (Binary) 인 특성을 가지며, 규칙이 실제로 얼마나 정량적으로 비례성을 달성하는지에 대한 세부적인 척도가 부족했습니다.
• 연구 목표: 본 논문은 PB 규칙의 비례성 정도 (Proportionality Degree) 를 체계적으로 연구하는 것을 목표로 합니다. 이는 결집된 유권자 그룹 (cohesive group) 이 자신의 규모에 비례하여 예산의 얼마만큼을 확보할 수 있는지를 정량화하는 지표입니다.
• 주요 대상 규칙:
  1. Method of Equal Shares (MES): 강력한 공리 (EJR) 를 만족하는 것으로 알려진 규칙.
  2. Phragm´en's Sequential Rule: 약한 공리 (PJR) 만 만족하고 EJR 은 만족하지 않는 규칙.
  • 가설: MES 가 더 강력한 공리적 보장을 가지므로, MES 의 비례성 정도가 Phragm´en 규칙보다 높을 것이라고 예상할 수 있었으나, 본 논문은 이를 반증하고 두 규칙이 정량적으로 동일한 비례성 정도를 가진다는 것을 증명합니다.

2. 방법론 (Methodology)

본 논문은 이론적 분석과 실증적 실험을 결합한 하이브리드 접근법을 사용합니다.

A. 이론적 분석 (Theoretical Analysis)

• 정의:
  • T-결집 그룹 (T-Cohesive Group): 특정 프로젝트 집합 $T$를 모두 지지하며, 그룹의 크기가 예산 대비 $T$의 비용 비율 이상인 유권자 그룹.
  • 비례성 정도 ($d_f(T)$): 특정 규칙 $f$가 결집 그룹 $V$에 대해 보장하는 평균 만족도 (평균 승인된 프로젝트 수) 의 하한선.
• 증명 기법:
  • MES 에 대한 하한 및 상한: MES 의 실행 과정에서 결집 그룹 내 유권자들이 지불하는 비용의 상한을 추정하는 보조 정리 (Lemma) 를 도출하고, 이를 통해 평균 만족도의 하한을 증명합니다. 또한, 최악의 경우를 구성하여 상한을 도출합니다.
  • Phragm´en 규칙에 대한 하한 및 상한: 잠재 함수 (Potential Function) 논증을 사용하여 Phragm´en 규칙의 비례성 하한을 증명합니다. 이는 다수결 투표 (Multi-winner voting) 문헌의 기법을 PB 설정에 적용한 것입니다.
  • 일반적 상한: EJR 을 만족하는 모든 규칙에 대한 일반적인 상한을 유도하여, MES 와 Phragm´en 규칙이 이 상한에 근접함을 보여줍니다.

B. 실증적 실험 (Experimental Evaluation)

• 데이터셋: Pabulib 라이브러리의 실제 세계 참여예산 데이터 100 개를 사용.
• 비교 규칙:
  1. Method of Equal Shares (MES)
  2. Sequential Phragm´en
  3. MES with Exhaustion (잔여 예산을 탐욕적 방식으로 배분하는 변형)
  4. Phragm´en with Exhaustion
  5. Greedy Approval (승인 점수 순으로 탐욕적으로 선택하는 기준선)
• 측정 방법:
  • 모든 부분집합을 계산하는 것은 불가능하므로, 프로젝트 부분집합 크기에 따라 무작위 샘플링 (각 크기당 5000 개) 을 수행.
  • 각 샘플에 대해 T-결집 그룹을 식별하고, 해당 그룹의 평균 만족도를 계산하여 비례성 정도를 산출.
  • 100 개 데이터셋 전체에 대한 평균 비례성 정도를 비교.

3. 주요 기여 및 결과 (Key Contributions & Results)

A. 이론적 결과

1. 동일한 비례성 정도: 놀랍게도, 강력한 공리 (EJR) 를 만족하는 MES와 약한 공리 (PJR) 만 만족하는 Phragm´en 규칙은 정량적으로 동일한 비례성 정도를 가집니다.
   • 두 규칙 모두 비례성 정도 하한이 $\frac{1}{2} \left( \frac{\text{cost}(T)}{\max_{t \in T} \text{cost}(t)} - 1 \right)$ 로 동일하게 증명되었습니다.
   • 이는 공리적 강도와 정량적 성능 사이에 항상 비례 관계가 성립하지 않을 수 있음을 시사합니다.
2. tight bounds (tight 한 경계): 두 규칙에 대해 소수 상수 인자만큼의 오차 범위 내에서 tight 한 하한과 상한을 도출했습니다.
3. 일반적 상한: EJR 을 만족하는 임의의 규칙에 대해 $\frac{\text{cost}(T)}{\max \text{cost}(t)} - 1$ 정도의 상한이 존재함을 보였으며, 이는 두 규칙이 거의 최적 (optimal) 에 가깝다는 것을 암시합니다.

B. 실험적 결과

1. 탐욕적 규칙 (Greedy) 의 열세: 모든 규칙 (MES, Phragm´en 및 그 변형) 은 탐욕적 규칙 (Greedy Approval) 보다 비례성 정도 측면에서 현저히 우수했습니다.
2. MES vs Phragm´en:
   • 이론과 달리 실험에서는 Phragm´en (잔여 예산 포함 시) 이 MES 보다 약간 더 나은 성능을 보이는 경우가 많았습니다.
   • 잔여 예산 처리 (Exhaustion) 가 적용된 경우 두 규칙 모두 매우 높은 성능을 보였으며, Phragm´en-Exh 가 MES-Exh 보다 미세하게 우세한 경향을 보였습니다.
   • 100 개 데이터셋 중 98 개에서 MES 와 Phragm´en (및 그 변형) 이 탐욕적 규칙보다 우월하거나 동등한 성능을 보였습니다.
3. 실제 적용성: 이론적 분석이 실제 데이터에서도 잘 반영됨을 확인했습니다.

4. 의의 및 결론 (Significance & Conclusion)

• 공리 vs 정량적 성능의 격차 해소: 기존 연구가 공리 만족 여부에만 집중했다면, 본 논문은 정량적 비례성 정도라는 새로운 지표를 도입하여 PB 규칙들의 실제 성능을 정밀하게 비교했습니다.
• 규칙 선택의 기준: MES 가 EJR 을 만족한다는 이론적 우위가 반드시 더 높은 비례성 정도를 의미하지는 않으며, Phragm´en 규칙도 동등한 수준의 비례성 보장을 제공함을 증명했습니다. 이는 실제 PB 시스템 설계 시 Phragm´en 규칙도 강력한 대안이 될 수 있음을 시사합니다.
• 실무적 함의: 단순한 탐욕적 알고리즘 (Greedy) 은 비례성을 보장하지 못하므로, MES 나 Phragm´en 과 같은 공리 기반 규칙을 사용하는 것이 공정성 측면에서 필수적임을 실험을 통해 입증했습니다.
• 미래 과제: 두 규칙이 비례성 정도 측면에서 최적 (Optimal) 일 것이라는 가설을 세웠으며, 이를 엄밀하게 증명하는 것이 향후 연구 과제로 남았습니다.

요약하자면, 이 논문은 참여예산제에서 MES 와 Phragm´en 규칙이 강력한 공리적 차이는 있으나 정량적 비례성 성능은 동일하며, 둘 다 탐욕적 규칙보다 월등히 우수함을 이론과 실험을 통해 입증한 획기적인 연구입니다.