2025-11-11T19:07:10.076722

Quantifying Inefficiency

Gonczarowski, Segev

We axiomatically define a cardinal social inefficiency function, which, given a set of alternatives and individuals' vNM preferences over the alternatives, assigns a unique number -- the social inefficiency -- to each alternative. These numbers -- and not only their order -- are uniquely defined by our axioms despite no exogenously given interpersonal comparison, outside option, or disagreement point. We interpret these numbers as per-capita losses in endogenously normalized utility. We apply our social inefficiency function to a setting in which interpersonal comparison is notoriously hard to justify -- object allocation without money -- leveraging techniques from computer science to prove an approximate-efficiency result for the Random Serial Dictatorship mechanism.

academic

비효율성의 정량화

기본 정보

논문ID: 2412.11984
제목: Quantifying Inefficiency (비효율성의 정량화)
저자: Yannai A. Gonczarowski (하버드 대학교), Ella Segev (예루살렘 히브리 대학교)
분류: econ.TH (경제이론), cs.GT (컴퓨터과학 및 게임이론)
발표일: 2025년 11월 6일 (arXiv v2)
논문 링크: https://arxiv.org/abs/2412.11984

요약

본 논문은 기수 사회 비효율성 함수(cardinal social inefficiency function)를 공리적으로 정의하며, 이는 개인의 폰 노이만-모르겐슈테른(vNM) 선호도에 기반하여 각 대안에 고유한 수치값(사회 비효율성)을 부여한다. 이러한 수치값들(단순히 그들의 순서 관계가 아닌)은 공리에 의해 유일하게 결정되며, 외생적 개인 간 효용 비교, 외부 선택, 또는 분쟁점이 필요하지 않다. 저자들은 이러한 수치값들을 내생적으로 표준화된 효용의 1인당 손실로 해석한다. 본 논문은 개인 간 비교가 극도로 어려운 시나리오인 무화폐 물품 분배 문제에 이 함수를 적용하며, 컴퓨터과학 기법을 활용하여 무작위 순차 독재(Random Serial Dictatorship, RSD) 메커니즘의 근사 효율성 결과를 증명한다.

연구 배경 및 동기

핵심 문제

사회선택이론의 핵심 문제는 대안에 대한 개인의 선호도를 사회 선호도로 어떻게 집계할 것인가이다. 전통적인 순서 집계(ordinal aggregation)는 두 대안의 사회적 효율성을 비교할 수 있지만, 한 방안이 다른 방안보다 얼마나 더 효율적인지를 정량화할 수 없다.

문제의 중요성

이론적 의의: Arrow(1951)와 Harsanyi(1955)가 사회선택이론의 기초를 수립했지만, 전통 이론은 순서 비교에만 초점을 맞추고 기수 비교는 할 수 없다
실무적 가치: 비효율성을 정량화할 수 없으면 정책 평가, 메커니즘 설계, 상황 간 비교에 정확한 근거가 부족하다
학제 간 수요: 컴퓨터과학의 "비효율성 경계"(inefficiency-bounding theorems)는 비교 가능한 기수 척도를 필요로 한다

기존 방법의 한계

vNM 효용의 비유일성: 개인의 vNM 효용함수는 단조 아핀 변환 하에서만 유일하여 개인 간 비교가 어렵다
외생적 표준화의 문제:
- Nash 사회복지함수(Kaneko & Nakamura, 1979)는 외생적 "최악의 경우"를 참조점으로 필요로 한다
- 컴퓨터과학의 "무정부 대가"(Price of Anarchy)는 외생적으로 표준화된 효용함수에 의존한다
상황 간 비교 가능성 부족: 기존 사회복지함수는 일반적으로 단일 상황 내에서만 비교 가능하며 상황 간 기수 비교는 불가능하다

연구 동기

본 논문은 다음 세 가지 핵심 속성을 만족하는 기수 사회 비효율성 함수를 구축하고자 한다:

순서 집계(Ordinal Aggregation): 개인의 순서 선호도에 기반한 집계
상황 내 기수 비교 가능성(Intra-context Cardinal Comparability): 동일 상황 내 다양한 대안의 비효율성 차이를 정량 비교
상황 간 기수 비교 가능성(Inter-context Cardinal Comparability): 서로 다른 상황 간 비효율성을 정량 비교

핵심 기여

공리적 기수 사회 비효율성 함수: 일곱 개의 공리를 제시하여 개인의 순서 vNM 선호도에 기반한 기수 사회 비효율성 함수를 유일하게 특성화(전역 곱셈 상수를 제외하고)
내생적 표준화 방법: 파레토 전선 상의 효용 범위를 통한 표준화로 외생적 개인 간 비교나 참조점이 필요 없음
이론적 특성화: 특성화된 사회 비효율성 함수가 자연스러운 해석을 가짐을 증명: 1인당 가산 복지 손실. 여기서 각 개인의 효용함수는 파레토 전선 상의 분배 갈등 폭에 따라 내생적으로 표준화됨
물품 분배에 적용:
- RSD 메커니즘의 사회 비효율성 보장 증명
- 모든 진실 보고 순서 메커니즘의 사회 비효율성 보장이 RSD를 28% 이상 개선할 수 없음을 증명
- 사회 비효율성을 계산하는 다항식 시간 알고리즘 제공
경제이론과 컴퓨터과학의 다리 구축: 컴퓨터과학의 근사 정리에 경제학적 미시 기초를 제공하여 외생적 표준화가 없는 상황에 적용 가능하게 함

방법론 상세 설명

작업 정의

상황(Context): $C = (X, (\succeq_i)_{i=1}^n)$ . 여기서:

$X$ : 유한 대안 집합
$n$ : 개인 수
$\succeq_i$ : 개인 $i$ 의 $\Delta(X)$ ( $X$ 상의 복권 공간) 상 vNM 공리를 만족하는 선호도

사회 비효율성 함수(Social Inefficiency Function): $I: \text{Contexts} \times \text{Alternatives} \to \mathbb{R}_{\geq 0} \cup \{\infty\}$

각 상황 $C$ 와 대안 $x \in \Delta(X)$ 에 대해 음이 아닌 실수 $I(C, x)$ (무한대일 수 있음)를 부여하여 상황 $C$ 에서 $x$ 의 사회 비효율성을 나타낸다.

공리 체계

논문은 사회 비효율성 함수를 특성화하기 위해 일곱 개의 공리를 제시한다:

공리 1: 파레토 단조성(Pareto Monotonicity)

$x$ 가 $y$ 에 파레토 우월하면 $I(C, x) \leq I(C, y)$ ; $x$ 가 $y$ 에 엄격히 파레토 우월하면 $I(C, x) < I(C, y)$ 이거나 둘 다 무한대(단, 유한 비효율성을 가진 더 나은 방안이 존재).

공리 2: 익명성(Anonymity)

개인 순서의 배열이 사회 비효율성을 변경하지 않음: 임의의 배열 $\pi$ 에 대해, $I((X, (\succeq_{\pi(i)})_{i=1}^n), x) = I((X, (\succeq_i)_{i=1}^n), x)$

공리 3: 기댓값 비효율성(Expected Inefficiency)

사회 비효율성은 복권에 대해 선형: $I(C, \alpha \cdot x + (1-\alpha) \cdot y) = \alpha \cdot I(C, x) + (1-\alpha) \cdot I(C, y)$

이는 사회 집계가 위험 중립적임을 보장한다.

공리 4: 무관한 대안 독립성(IIA)

두 상황 $C$ 와 $C'$ 이 동일한 이상점(각 개인의 최적 방안)과 최소 기댓값점(각 개인의 파레토 전선 상 최악 방안)을 가지면, 상대 비효율성은 유지됨: $I(C', x) - I(C', y) = I(C, x) - I(C, y)$

이는 Nash(1953)의 IIA를 Roth(1977)가 정의한 내생적 참조점으로 일반화한 것이다.

공리 5: 무관한 선호도 독립성(IIP)

결합 상황 $C \oplus D$ 에서, 두 대안 $(x, y)$ 와 $(x', y)$ 가 부분 상황 $C$ 에서만 다르면, 그들의 상대 비효율성은 부분 상황 $D$ 의 선호도와 무관함.

공리 6: 인구 규모 안정성(Population-Size Stability)

자기 결합(self-composition)이 상대 비효율성을 변경하지 않음: $I(\oplus_{j=1}^k C, (x, \ldots, x)) - I(\oplus_{j=1}^k C, (x', \ldots, x')) = I(C, x) - I(C, x')$

이는 사회 비효율성이 1인당 특성을 갖도록 한다.

공리 7: 실행 가능성(Feasibility)

각 상황에서 어떤 방안의 사회 비효율성은 0(즉, 가장 효율적인 방안).

특성화된 사회 비효율성 함수

명시적 구성:

상황 $C = (X, (\succeq_i)_{i=1}^n)$ 과 대안 $x \in \Delta(X)$ 에 대해:

표준화 효용: 각 개인 $i$ $i$ 에 대해 vNM 효용 표현 $u_i$ $u_{i}$ 를 선택하고 계산:
- $u_i^{\max} = \max_{x \in F_C} u_i(x)$ (파레토 전선 상의 최대 효용)
- $u_i^{\min} = \min_{x \in F_C} u_i(x)$ (파레토 전선 상의 최소 효용)
사회복지함수: $V(C, x) = \frac{1}{n} \sum_{i=1}^n \frac{u_i(x) - u_i^{\min}}{u_i^{\max} - u_i^{\min}}$
분모가 0일 때(개인이 파레토 전선 상에서 무차별), 관례 사용: 음수를 0으로 나누면 음의 무한대, 0을 0으로 나누면 0.
사회 비효율성: $\hat{I}(C, x) = \max_{x' \in X} V(C, x') - V(C, x)$

주요 정리(Theorem 1): 사회 비효율성 함수 $I$ 가 일곱 개의 공리를 만족할 필요충분조건은 상수 $0 < c < \infty$ 가 존재하여 모든 상황과 방안에 대해: $I(C, x) = c \cdot \hat{I}(C, x)$

즉, 일곱 개의 공리는 $\hat{I}$ 를 유일하게 특성화함(전역 곱셈 상수를 제외하고).

기술적 혁신점

내생적 표준화의 영리함:
- 파레토 전선의 효용 범위를 통한 표준화로 각 개인의 효용 단위를 "분배 갈등 폭"으로 설정
- 이러한 표준화는 선호도에 의해 완전히 내생적으로 결정되며 외부 정보 불필요
- 수학적으로 각 개인의 파레토 전선 상 효용 범위를 $[0, 1]$ 로 표준화하는 것과 동등
전선 무차별 개인 처리:
- 파레토 전선 상에서 완전히 무차별한 개인(frontier-indifferent)의 경우, 표준화는 0으로 나누기 포함
- 혁신적으로 무한 비효율성을 허용하고 Lemma 1을 통해 이것이 필요함을 증명
- 파레토 전선보다 열등하다고 전선 무차별 개인이 판단하는 방안에서만 무한 비효율성 부여
공리의 시너지 효과:
- IIA와 IIP가 함께 상황 간 비교 가능성 실현
- 인구 규모 안정성이 1인당 해석 보장
- 기댓값 비효율성이 파레토 단조성과 결합하여 가산 구조 보장
컴퓨터과학과의 연결:
- 무정부 대가(Price of Anarchy)의 경제학적 대안 제공
- 외생적 표준화 없이 근사 정리 진술 가능
- 기술적으로 컴퓨터과학의 증명 기법을 직접 개조 가능

실험 설정

응용 시나리오: 물품 분배 문제

문제 정의:

$n$ 명의 개인과 $n$ 개의 물품
각 개인이 물품에 대해 엄격한 vNM 선호도 보유
$X = X(n)$ : 모든 완벽한 매칭의 집합
순서 메커니즘 $\mu$ : 순위 프로필 $R^n$ 에서 $\Delta(X)$ 로의 매핑

연구 메커니즘:

RSD(무작위 순차 독재): 무작위 순서로 개인들이 차례로 가장 선호하는 미분배 물품을 선택
RSD는 사전에 효율적이지 않은 것으로 알려짐(Zhou, 1990; Bogomolnaia & Moulin, 2001)

평가 지표

견고한 사회 비효율성 보장(Robust Social Inefficiency Guarantee): $\sup_{(X, \succeq) \in \mathcal{M}} \hat{I}((X, \succeq), \mu(\succeq))$

즉, 모든 가능한 물품 분배 문제에서 진실 보고 균형 하의 메커니즘 출력의 최악 사회 비효율성.

비교 방법

논문은 RSD와 모든 가능한 진실 보고 순서 메커니즘의 사회 비효율성 보장을 비교한다.

기술 도구

Filos-Ratsikas et al. (2014)의 증명 개조:
- 원문: 무정부 대가(비율) 분석
- 본 논문: 사회 비효율성(차이) 분석으로 개조
주요 기술 차이:
- 원문: 외생적으로 효용을 $[0, 1]$ 로 표준화, $\frac{U_u(\mu(u))}{\max_{x} U_u(x)}$ 분석
- 본 논문: 파레토 전선으로 내생적 표준화, $\max_x V(C, x) - V(C, x)$ 분석

실험 결과

주요 이론 결과

정리 2(주요 결과): 순서 메커니즘 $\mu$ 가 존재하여 $\sup_{(X,\succeq)\in\mathcal{M}} \hat{I}((X,\succeq), \mu(\succeq)) < \frac{1}{2\ln 2} \sup_{(X,\succeq)\in\mathcal{M}} \hat{I}((X,\succeq), \text{RSD}(\succeq))$ 를 만족할 수 없다.

수치 해석: $\frac{1}{2\ln 2} \approx 0.721$ , 즉:

모든 순서 메커니즘의 견고한 사회 비효율성 보장은 최소한 RSD의 72.1%
RSD의 사회 비효율성 보장은 28% 이상 개선될 수 없음

상세 경계

정리 3(하한): 모든 순서 메커니즘 $\mu$ 와 임의의 $n$ 에 대해: $\sup_{\succeq \in P^n} \hat{I}((X, \succeq), \mu(\succeq)) \geq \frac{1}{2} - \frac{1}{2n}$

$n \to \infty$ 일 때 $\frac{1}{2}$ 로 수렴.

정리 4(RSD 상한): 임의의 $n$ 에 대해: $\sup_{\succeq \in P^n} \hat{I}((X, \succeq), \text{RSD}(\succeq)) \leq \ln 2 \approx 0.693$

계산 복잡성 결과

명제 1(다항식 시간 알고리즘): 주어진 물품 분배 문제의 사회 비효율성을 계산하는 다항식 시간 알고리즘(Algorithm 1)이 존재한다.

핵심 기술:

각 개인의 파레토 전선 상 최소 효용 계산은 해당 개인이 사후 파레토 효율적 매칭에서 가장 선호하지 않는 물품 찾기와 동등
최대 기수 매칭(Hopcroft & Karp, 1973)을 통해 다항식 시간 내 계산 가능

실험 발견

근사 효율성: RSD가 사전에 효율적이지 않음에도 불구하고, 그 사회 비효율성은 유계( $\leq \ln 2$ )이며 근사 효율성을 증명함
메커니즘 간 차이 제한: 모든 진실 보고 메커니즘의 성능 차이는 28%를 초과하지 않으며, 견고한 보장 의미에서 메커니즘 선택의 공간이 제한됨을 나타냄
계산 실행 가능성: 사회 비효율성의 계산이 실행 가능하여 실제 메커니즘 평가에 사용 가능

결론 및 논의

주요 결론

이론적 기여:
- 일곱 개의 공리가 기수 사회 비효율성 함수를 유일하게 특성화(전역 단위 제외)
- 해당 함수는 자연스러운 해석을 가짐: 내생적으로 표준화된 1인당 효용 손실
- 외생적 개인 간 비교나 참조점 불필요
응용 결과:
- RSD의 사회 비효율성 보장 $\leq \ln 2 \approx 0.693$
- 모든 진실 보고 메커니즘이 RSD를 28% 이상 개선할 수 없음
- 사회 비효율성을 다항식 시간 내 계산 가능
방법론적 기여:
- 컴퓨터과학의 근사 정리에 경제학적 미시 기초 제공
- 학제 간 방법의 잠재력 시연

한계

무한 비효율성 처리:
- 무한 비효율성 허용이 필요(Lemma 1)하지만, 일부 응용에서는 충분히 정교하지 않을 수 있음
- 전선 무차별 개인이 존재할 때만 발생하며, 실무에서는 드문 경우
공리 선택의 논쟁성:
- 저자들이 언급했듯이, 모든 공리화는 의문의 여지가 있을 수 있음
- 특히 IIA의 약화 형태(두 개의 내생적 참조점에 상대적)는 추가 논증이 필요할 수 있음
응용 범위:
- 물품 분배 응용은 진실 보고 메커니즘만 고려
- 비진실 보고 메커니즘의 경우 전략적 행동의 영향 고려 필요
계산 복잡성:
- 다항식 시간 알고리즘을 제공하지만, 대규모 문제의 경우 여전히 계산 비용이 클 수 있음
- 알고리즘 복잡도는 $O(n^3)$ (최대 매칭 알고리즘 기반)

향후 방향

다른 목표로 확장:
- 기수 사회 부공평성 함수의 공리화
- 기수 사회 불평등 함수의 공리화
- 이러한 목표에 대한 근사 보장 증명
다른 분야로의 응용:
- 투표 이론
- 매칭 시장(학교 선택, 신장 교환 등)
- 경매 설계
경계 개선:
- RSD의 사회 비효율성 보장을 추가로 개선 가능
- 특정 선호도 구조 하의 더 나은 경계 탐색
메커니즘 설계:
- 사회 비효율성을 명시적으로 최적화하는 메커니즘 설계
- 사회 비효율성과 다른 목표(공평성 등)의 권형 연구

심층 평가

장점

이론적 엄밀성:
- 완전한 공리화 특성화, 상세한 증명(주요 결과 및 모든 보조정리)
- 공리의 논리적 독립성(Section 4.2)이 특성화의 신뢰성 강화
- 수학적 증명 기법 우수, 특히 무한 비효율성 처리 방식
혁신성:
- 최초로 순서 선호도에 기반한 기수 상황 간 비교 가능 사회복지함수 실현
- 내생적 표준화 방법(파레토 전선을 통한)이 극도로 혁신적
- 경제이론과 컴퓨터과학의 융합으로 새로운 방향 개척
실용적 가치:
- 계산 가능한 알고리즘(다항식 시간) 제공
- 실제 문제(물품 분배)에 적용하여 의미 있는 결과 도출
- 방법의 보편성으로 다양한 경제 시나리오에 적용 가능
작문 품질:
- 구조 명확, 동기에서 공리를 거쳐 특성화에서 응용까지 단계적 진행
- 도표(Figure 1, 2)가 이해 보조
- 관련 연구 종합이 포괄적이고 본 논문의 기여를 정확히 위치
학제 간 기여:
- 경제학자에게 정량화 도구 제공
- 컴퓨터과학자에게 경제학적 기초 제공
- EconCS 교차 연구의 잠재력 시연

부족한 점

공리의 직관성:
- IIP(무관한 선호도 독립성)의 경제적 직관이 다른 공리만큼 명확하지 않음
- 인구 규모 안정성이 수학적으로는 우아하지만, 경제적 필요성의 논증이 충분하지 않을 수 있음
응용의 깊이:
- 물품 분배 응용이 주로 기존 증명(Filos-Ratsikas et al. 2014) 개조로, 기술적 혁신 제한적
- 수치 실험이나 실제 데이터 응용 미제공
- 28%의 개선 여지가 실무에서 의미 있는지 충분히 논의되지 않음
비교 기준:
- 다른 가능한 사회복지함수(예: Nash 사회복지)와의 실증 비교 부재
- 다양한 공리 선택이 초래하는 서로 다른 사회 비효율성 함수의 체계적 비교 부족
전선 무차별 경우:
- 무한 비효율성의 필요성은 증명되었으나, 이 경우의 실제 의미와 빈도가 충분히 논의되지 않음
- 실제 응용에서 이 경우를 처리하거나 회피하는 방법에 대한 지침 부족
계산 복잡성:
- 다항식 시간이지만 $O(n^3)$ 은 대규모 문제에 충분히 효율적이지 않을 수 있음
- 근사 계산이나 휴리스틱 알고리즘의 가능성 미논의

영향력

분야에 대한 기여:
- 중대한 이론적 기여: 사회선택이론의 오래된 문제(기수 집계) 해결
- 새로운 연구 방향 촉발 가능: 기수 사회선택이론
- 메커니즘 설계에 새로운 평가 도구 제공
실용적 가치:
- 정책 평가 및 메커니즘 비교에 사용 가능
- 무화폐 거래 자원 분배(물품 분배, 장기 교환) 설계에 정량화 도구 제공
- 광범위한 응용 가능성(투표, 매칭, 자원 분배 등)
재현 가능성:
- 이론 결과 완전히 재현 가능(증명 완전)
- 알고리즘 설명 명확(Algorithm 1)
- 코드 미제공이나 알고리즘 구현 직접적
잠재적 영향:
- 높은 인용 가능성(경제학과 컴퓨터과학 교차)
- 기수 사회선택이론의 기초 논문이 될 가능성
- 다수의 컴퓨터과학 근사 정리에 경제학적 설명 제공

적용 시나리오

이상적 시나리오:
- 무화폐 거래 자원 분배(물품 분배, 장기 교환)
- 효율성 손실을 정량화해야 하는 메커니즘 설계
- 상황 간 비교가 필요한 정책 평가
- 명확한 파레토 전선이 있는 의사결정 문제
부적절한 시나리오:
- 자연 화폐 척도가 있는 시장(이 경우 전통 방법이 더 간단)
- 파레토 전선이 정의하기 어려운 복잡한 환경
- 동적 또는 불완전 정보를 고려해야 하는 문제
- 전선 무차별 개인이 지배적인 경우
잠재적 확장 시나리오:
- 투표 시스템의 효율성 평가
- 양측 매칭 시장(결혼 시장, 노동 시장)
- 공공재 공급 결정
- 다목표 최적화에서 효율성-공평성 권형

핵심 참고문헌

Arrow, K. J. (1951). Social Choice and Individual Values. Yale University Press.
- 사회선택이론의 기초 저작
Harsanyi, J. C. (1955). Cardinal welfare, individualistic ethics, and interpersonal comparisons of utility. Journal of Political Economy, 63(4):309-321.
- 공리주의의 공리적 기초
Dhillon, A. and Mertens, J.-F. (1999). Relative utilitarianism. Econometrica, 67(3):471-498.
- 본 논문에 가장 근접한 선행 연구
Filos-Ratsikas, A., Frederiksen, S. K. S., and Zhang, J. (2014). Social welfare in one-sided matchings: Random priority and beyond. SAGT.
- 물품 분배 응용의 기술적 기초
Koutsoupias, E. and Papadimitriou, C. (1999). Worst-case equilibria. STACS.
- 무정부 대가의 개척적 저작

종합 평가: 이것은 탁월한 이론 논문으로, 사회선택이론에서 중대한 돌파구를 이루었다. 영리한 내생적 표준화 방법과 엄밀한 공리화 특성화를 통해 오래 지속된 기수 집계 문제를 해결했다. 논문은 이론적 기여가 현저할 뿐 아니라 물품 분배 응용을 통해 실용적 가치를 시연하며, 경제이론과 컴퓨터과학의 융합을 위한 새로운 방향을 개척했다. 응용의 깊이와 실증 검증 측면에서 개선 여지가 있지만, 이론적 혁신성과 잠재적 영향력으로 인해 해당 분야의 중요한 기여가 된다. 상위 경제학 및 컴퓨터과학 저널에 게재될 것으로 예상되며, 후속 연구의 물결을 촉발할 것으로 기대된다.