기술 요약: 다중 에이전트 밴딧에서의 절차적 공정성 (Procedural Fairness in Multi-Agent Bandits)

문제 정의

다중 에이전트 다중 팔 밴딧(Multi-Agent Multi-Armed Bandits, MA-MAB)에서 공정성은 전통적으로 공리주의적 복지 극대화, 불평등 최소화, 또는 내쉬 사회적 복지(Nash Social Welfare, NSW)와 같은 **결과 기반 지표(outcome-based metrics)**를 통해 정의되어 왔습니다. 이러한 접근 방식은 결정의 집계된 결과(예: 총 효용 또는 보상의 분포)에 초점을 맞춥니다. 그러나 저자들은 이러한 관점이 절차적 공정성(procedural fairness), 즉 **동등한 목소리(equal voice)**와 **대표성(representation)**에 관한 의사결정 과정 자체의 본질적인 원칙을 간과한다고 주장합니다.

기존 문헌은 공정성을 시스템에 부과되는 외부 기준(결과주의)으로 취급하여 참여자의 주체성을 무시하는 경우가 많습니다. 반면, 절차적 공정성은 그 영향력이 반드시 최적의 결과로 이어지는지 여부와 관계없이, 각 에이전트가 정책에 대해 동등한 수준의 영향력을 가질 수 있어야만 결정이 정당하다는 원칙을 제시합니다.

방법론

절차적 공정성의 공식화

본 논문은 에이전트의 대표성(equal representation) 내에 기반한 MA-MAB를 위한 절차적 공정성의 엄격한 정의를 도입합니다.

• 의사결정 점유율(Decision Share): 에이전트 $i$에 대하여, 의사결정 점유율 $\beta_i(P)$는 해당 에이전트가 가장 선호하는 팔(가장 높은 평균 보상 $\mu^*_{i,k}$를 가진 팔들)에 할당된 총 확률 질량입니다.
• 절차적 공정성 정의: 정책 $P$가 절차적으로 공정하다는 것은, 확률 분포가 $N$개의 동등한 점유율($1/N$)로 분해될 수 있으며, 각 에이전트의 점유율이 오직 그들의 선호하는 팔에만 배타적으로 할당될 수 있음을 의미합니다.
• 절차적 공정성 점수(PF): 저자들은 주어진 정책이 얼마나 절차적으로 공정한지를 측정하기 위해 최적화 문제를 공식화합니다. 이 점수는 정책의 총 확률 제약 조건을 위반하지 않으면서 각 에이전트의 선호하는 팔에 할당할 수 있는 $1/N$ 의사결정 점유율의 최대 비율을 나타냅니다. 점수가 1이면 완벽한 절차적 공정성을 의미합니다.

알고리즘적 접근 방식

보상 평균을 알 수 없는 온라인 환경에서 절차적으로 공정한 정책을 학습하기 위해 다음을 수행합니다:

1. 목적 함수: 저자들은 에이전트들의 의사결정 점유율의 곱인 **의사결정 점유율 기반 내쉬 복지(Decision-Share-Based Nash Welfare, $NW_\beta$)**를 극대화합니다: $\prod_{i=1}^N \beta_i(P)$.
2. 이론적 보장: 그들은 $NW_\beta$를 극대화하는 것이 절차적으로 공정한 정책(즉, **절차적 코어(Procedural Core)**에 속하는 정책)을 생성함을 증명합니다 (정리 1).
3. 학습 알고리즘 (Algorithm 1):
   • 선호하는 팔의 집합($\hat{F}_i$)을 추정하기 위해 상한 신뢰 구간(Upper Confidence Bound, UCB) 스타일의 집중 경계(concentration bounds)를 사용합니다.
   • 모든 팔이 충분히 샘플링되어 신뢰 구간을 줄이고 실제 선호 집합을 회복할 수 있도록 무작위 탐색(randomized exploration) 메커니즘(확률 $t^{-(1-\gamma)}$로 무작위 팔을 선택)을 포함합니다.
   • 매 단계마다, 알고리즘은 추정된 선호 집합에 대해 $NW_\beta$ 최적화 문제를 풀어 정책 $P_t$를 결정합니다.
4. 후회 분석(Regret Analysis): 논문은 추정된 선호 집합이 실제 집합과 일치하지 않는 라운드 수를 기준으로 **절차적 공정성 후회(Procedural Fairness Regret, $R_{PF}$)**를 정의합니다. 저자들은 알고리즘이 절차적으로 공정한 정책으로 수렴함을 보여주는 하위 선형 후회 경계(sublinear regret bound) $O(K + T^\gamma/\gamma + (\dots)^{1/\gamma})$를 증명합니다.

주요 기여

1. 공식적 정의: 결과(효용)와 대표성(목소리)을 구분하여 MA-MAB를 위한 절차적 공정성에 대한 엄격한 정의를 제공합니다.
2. 불가능성 결과: 절차적 공정성이 결과 기반의 공정성 개념과 근본적으로 양립할 수 없음을 증명합니다.
   • 명제 2 & 3: 완벽한 절차적 공정성과 완벽한 불평등 최소화 또는 완벽한 공리주의를 동시에 달성할 수 없는 보상 구조가 존재함을 입증합니다.
   • 정리 6: 효용 기반 내쉬 복지 최적 정책과 절차적으로 공정한 정책은 서로 파레토 우위(Pareto dominate)를 점한다는 보장이 없으며, 서로 충돌하는 다른 가치들을 우선시합니다.
3. 코어 안정성(Core Stability): 의사결정 점유율 기반 내쉬 복지를 극대화하는 정책이 절차적 코어에 속함을 확립합니다. 이는 어떤 에이전트 연합도 자신들의 비례적 의사결정 권한을 사용하여 모든 구성원의 대표성을 (최소 한 명의 엄격한 개선을 동반하여) 개선할 수 없음을 의미하며, 이를 통해 '목소리'에 기반한 이탈에 대한 안정성을 보장합니다.
4. 알고리즘 및 후회 경계: 에이전트들의 목소리가 학습되는 동안 보장되는 하위 선형 후회 보장을 가진 절차적 공정성 정책 학습 알고리즘을 제시합니다.

실험 결과

저자들은 다양한 환경에서 결과 기반 벤치마크(공리주의, 불평등 최소화, 평등 복지, 내쉬 사회적 복지, 일반화된 지니 계수)를 대상으로 자신들의 접근 방식을 평가했습니다:

• 합성 데이터: 에이전트, 팔, 선호 분포(Uniform, Single-Peaked, Impartial Culture, Mallows)를 달리한 7,764개의 인스턴스.
• 실제 데이터: 50명의 투표자와 4명의 후보자가 포함된 Mechanical Turk(PrefLib) 데이터셋.

주요 결과:

• 트레이드오프(Trade-offs): 결과 기반 지표(공리주의, NSW)에 최적화된 정책들은 일관되게 낮은 절차적 공정성 점수(종종 0.8 미만)를 기록했으며, 이는 결과 최적화가 동등한 목소리를 보존하지 못할 수 있음을 나타냅니다.
• 균형: 절차적으로 공정한 정책은 높은 불평등 최소화 및 공리주의 점수(종종 0.9 이상)를 유지하면서도 완벽한 절차적 공정성 점수(1.0)를 달ように 했습니다. 이는 세 가지 차원 모두에서 탁월한 균형을 보여줍니다.
• 강건성(Robustness): 에이전트 간의 이견(예: 높은 분산을 가진 Mallows 모델)이 증가함에 따라 결과 기반 정책의 절차적 공정성은 크게 약화된 반면, 절차적 공정 정책은 대표성 보장을 유지했습니다.
• 수렴: 실제 데이터 실험에서 학습 알고리즘은 높은 평등과 효용을 유지하면서도 동등한 대표성을 보장하는 정책으로 수렴하며, 다른 모든 벤치마크보다 절차적 지표에서 우수한 성능을 보였습니다.

의의 및 주장

본 논문은 절차적 공정성이 효율성이나 평등과는 별개인, 다중 에이전트 시스템에서 필수적이고 구별되는 목적임을 주장합니다.

• 규범적 선택: 저자들은 공정성이 단일한 수학적 해답이 아니라 경쟁하는 가치들의 집합임을 강조합니다. 공정성 목표를 선택하는 것은 규범적인 결정입니다. 효율성(공리주의)을 우선시하는 것은 필연적으로 동등한 목소리를 희생하며, 절차적 공정성을 우선시하는 것은 정당성을 확보하기 위해 잠재적 비효율성을 수용하는 것입니다.
• 최적화보다 정당성: 롤스(Rawls), 스캔론(Scanlon)의 정치 철학과 린드 & 타일러(Lind & Tyler)의 심리학을 인용하여, 시스템이 참여의 존엄성(dignity of participation)을 존중할 때 에이전트들에게 더 정당하고 수용 가능하게 인식될 수 있다고 주장합니다.
• 설계 원칙: 절차적 공정성은 단순한 이론적 개념이 아니라, 안정적(코어 안정성)이고 강건하며, "동등한 목소리"로서의 공정성에 대한 인간의 가치를 반영하는 실질적인 설계 원칙으로 제시됩니다.

결론적으로, 본 논문은 결과 기반 지표들이 우아하고 다루기 쉽지만 외부에서 가치를 강요한다는 점을 지적합니다. 절차적 공정성은 "누구의 선호가 결정을 형성했는가"로 초점을 전환함으로써, 단순히 지능적일 뿐만 아니라 정당한 다중 에이전트 시스템을 구축하기 위한 프레임워크를 제공합니다.