메커니즘·정직 보고·지급 설계

규칙 자체를 설계해야 하는 이유

연구실의 장비 한 대를 세 연구자에게 배정한다고 생각해 봅시다. 각자는 장비 사용이 자신에게 얼마나 가치 있는지 알지만 배정자는 모릅니다. 숫자를 제출하라고 하면 새로운 문제가 생깁니다. 실제 가치보다 높거나 낮은 숫자를 말해서 더 유리해질 수 있기 때문입니다. 누가 받는지뿐 아니라 얼마를 내는지도 함께 정해야 합니다.

게임이론이 주어진 규칙에서 사람들이 어떻게 행동하는지 묻는다면, 메커니즘 설계는 어떤 규칙이 바람직한 행동을 만드는지도 묻습니다. 여기서는 자신의 사적 가치를 숫자로 보고하는 직접 메커니즘부터 시작합니다. 직접 보고한다는 말은 메시지 형식에 관한 것이며 정직함이 자동으로 따라온다는 뜻은 아닙니다.

실습에는 식별자 0,1,2인 세 참가자가 있습니다. 실제 가치 v_i와 제출 보고 b_i는 각각 0부터 10까지 정수입니다. 효용은 받은 편익에서 지급액을 뺀 준선형 효용입니다. 예산 제약·위험 회피·담합·상호 의존 가치는 가정하지 않습니다. 실제 가치는 교육용 평가자가 아는 가상 참값이며 할당·지급 규칙에는 전달하지 않습니다.

이전 그림과 달리 무엇을 흐르게 하는가

첫 그림의 상자에는 실제 가치와 보고가 함께 보이지만 규칙으로 내려가는 화살표에는 보고 b만 흐릅니다. 규칙이 할당 x_i와 지급 p_i를 정한 다음, 실제 가치를 사용해 효용을 계산합니다.

$$u_i(v_i;b)=v_i x_i(b)-p_i(b).$$

여기서 u_i는 확률이 아니라 효용입니다. 값이 클수록 참가자에게 좋습니다. 경매에서는 낙찰자의 x_i만 1이고 나머지는 0입니다. 공공사업에서는 사업이 시행되면 모든 참가자의 x_i가 1입니다. 같은 사업에서 각자가 자기 편익을 받는 것이며 사적 물건 세 개를 파는 것과 다릅니다.

지급은 참가자에게서 운영자로 돈을 옮깁니다. 그 자체가 자원을 소모하지는 않습니다. 운영자 순수입은 지급 수입에서 실제 자원 비용을 뺀 값입니다. 따라서 다음 항등식이 성립합니다.

$$\sum_i u_i+\left(\sum_i p_i-\text{자원 비용}\right) =\sum_i v_i x_i-\text{자원 비용}=W.$$

W는 참 후생입니다. 한 참가자의 효용이 음수이거나 운영자가 적자를 보거나, 잘못된 보고로 나쁜 결정을 내렸더라도 이 회계 항등식은 유지됩니다. 지급액을 편익과 다시 더하면 돈의 이동을 중복 계산하게 됩니다.

같은 낙찰 규칙에 다른 가격을 붙이면

두 경매 모두 최저 보고 기준 r 이상인 최고 보고자에게 한 물건을 배정합니다. 동률에서는 작은 식별자가 우선합니다. 모두 r 미만이면 판매하지 않고 모든 지급은 0입니다. 보고 0도 실제 숫자입니다. r=0에서 세 보고가 모두 0이면 참가자 0이 낙찰받습니다.

1등 가격 경매는 낙찰자가 자신의 보고를 지급합니다. 2등 가격 경매는 낙찰자가 최저 보고 기준과 다른 사람의 최고 보고 중 큰 값을 지급합니다. 탈락자는 모두 0을 냅니다. 비교하는 동안 최저 보고 기준과 동률 우선순위는 바뀌지 않습니다.

실제 가치와 보고가 모두 (9,5,2), 기준이 0이라고 합시다. 두 경매 모두 참가자 0에게 물건을 줍니다. 1등 가격에서는 9를 내므로 효용은 9−9=0입니다. 보고를 5로 낮춰도 동률 우선권 때문에 낙찰되고, 효용은 9−5=4입니다. 현재 상대 보고를 고정하면 최적 보고는 5 하나입니다.

2등 가격에서는 보고 9로도 5를 내므로 효용은 4입니다. 보고 5부터 10까지는 모두 낙찰되고 지급은 계속 5입니다. 따라서 최적 보고가 여섯 개입니다. 정직한 보고가 최적이라고 해서 유일한 최적이라는 뜻은 아닙니다. 표와 그림은 동률인 최적 보고를 전부 남깁니다.

세 가지 정량화 범위를 구분한다

현재 상대 보고를 고정한 최적 반응은 다음 집합입니다.

$$B_i(b_{-i};v_i)=\arg\max_{z\in\{0,\ldots,10\}}u_i(v_i;z,b_{-i}).$$

파란 이산 곡선은 자기 보고 11개를 대조합니다. 주황 수평선은 같은 상대에게 정직하게 보고했을 때의 효용 수준입니다. 현재 보고점이 주황선 아래에 있을 수 있고, 정직 보고점 외의 다른 점도 최댓값일 수 있습니다. 가로축은 시간이 아니라 가능한 자기 보고입니다.

특정 실제 타입에서 정직 보고가 약하게 우월하려면 모든 상대 보고에 대해 다른 어떤 자기 보고보다 효용이 작지 않아야 합니다. 실습은 선택 참가자와 실제 가치를 고정한 뒤, 상대 보고 121개와 자기 보고 11개를 전부 검사합니다. 각 칸은 다음 위반량입니다.

$$\Delta_i(b_{-i};v_i)=\max_z u_i(v_i;z,b_{-i})-u_i(v_i;v_i,b_{-i})\ge0.$$

주황 칸은 정직보다 유리한 다른 보고가 있는 경우이고 파란 칸은 차이가 0인 경우입니다. 윤곽선은 현재 입력한 상대 보고를 표시합니다. 위반이 있으면 상대 보고와 유리한 자기 보고의 구체적 반례도 표시합니다. 표본추출한 통계량이 아니라 선택 타입에 대한 유한 전수 검사입니다.

DSIC, 즉 우월 전략 유인 적합성은 모든 참가자와 모든 실제 타입에서도 이 부등식을 요구합니다. 한 타입의 최대 위반이 0이라는 결과만으로 전체 메커니즘이 DSIC라고 할 수 없습니다. 예를 들어 1등 가격에서 실제 가치가 0이면 양의 가격으로 낙찰되어도 이득이 없어서 정직 보고가 약하게 우월할 수 있습니다. 아무도 도달하지 못하는 높은 최저 보고 기준에서는 모든 보고가 같은 결과를 낼 수도 있습니다. 두 경우 모두 1등 가격 전체의 DSIC를 뜻하지 않습니다.

Bayesian 유인 적합성은 다른 타입에 관한 명시적 확률분포를 놓고, 상대가 정직하게 행동하는 비교에서 기대 효용을 따집니다. 이 실습에는 사전분포가 없습니다. 한 상대 조합이나 선택 타입의 전수 그림을 BIC 계산으로 해석하지 않습니다.

2등 가격에서 정직 보고가 유리한 이유

상대 보고를 고정하고, 최저 보고 기준과 상대 최고 보고 중 큰 값을 t라고 합시다. 낙찰되면 자신의 보고 크기와 무관하게 t를 냅니다. v_i>t이면 낙찰 효용이 양수이고 정직 보고로 낙찰됩니다. v_i<t이면 낙찰 효용이 음수이므로 정직 보고로 피하는 것이 좋습니다. v_i=t이면 낙찰과 탈락의 효용이 모두 0이므로 고정된 동률 규칙이 약한 정직 유인을 깨지 않습니다.

이 논증은 명시한 사적 가치·준선형 효용 모형의 모든 가치와 상대 보고에 적용됩니다. 따라서 이 규칙의 2등 가격에는 전체 타입에 관한 성질을 증명합니다. 현재 입력한 보고가 정직하다거나, 낙찰되면 항상 이득이라거나, 임의의 다른 경매도 같은 성질을 갖는다는 뜻은 아닙니다.

실제 가치가 (4,5,2)인데 보고가 (9,5,2)이면 참가자 0은 5를 내고 가치 4의 물건을 받아 효용 −1을 얻습니다. 정직하게 4를 보고하면 탈락하여 효용 0입니다. 개별 합리성은 가정 아래 정직한 보고에 대한 보장이지 임의의 과대 보고를 손실에서 보호하는 장치가 아닙니다.

경매의 최저 보고 기준은 자원 비용이 아니다

이 경매 모형에서 판매자가 물건을 보유하는 실제 가치는 0입니다. 최저 보고 기준 r은 판매 정책이며 W에서 빼는 자원 비용이 아닙니다. 따라서 제한 없는 참 후생 최댓값은 max_i v_i입니다. 정직한 가치·보고가 (4,3,2)이고 기준이 5이면 2등 가격은 판매하지 않습니다. 실제 후생 0, 제한 없는 최적 4, 차이 4입니다.

이 기준에서도 정직 유인은 유지되지만 제한 없는 배정 효율성은 유지되지 않을 수 있습니다. 판매자에게 실제 기회 가치가 있는 다른 모형이라면 그 가치도 후생 목적에 일관되게 반영해야 합니다. 최저 보고 기준을 조용히 비용처럼 빼면 다른 질문을 계산하게 됩니다.

공공사업의 결정적 외부 효과를 지급한다

알려진 실제 비용 C로 공유 자원 하나를 만든다고 합시다. 시행하면 각자가 자기 편익을 받고 미시행이면 아무도 받지 않습니다. 제공자의 비용은 알려진 값이며 이 실습에서 전략적으로 보고받는 타입이 아닙니다. 보고 합이 비용 이상이면 시행하고 등호에서도 시행합니다.

$$x(b)=1\{\sum_i b_i\ge C\}.$$

참가자 i를 제외한 보고 합을 s_{-i}라고 합시다. i가 없을 때 나머지 사람과 제공자의 최적 보고 후생은 h_i=max(0,s_{-i}−C)입니다. 실제 선택에서는 (s_{-i}−C)x(b)입니다. 이 둘의 차이가 Clarke pivot 지급입니다.

$$p_i(b)=\max(0,s_{-i}-C)-(s_{-i}-C)x(b) =\begin{cases}\max(0,C-s_{-i}),&x(b)=1,\\0,&x(b)=0.\end{cases}$$

미시행일 때 지급이 0인 이유는 모든 보고가 음이 아니므로 전체 보고가 비용 미만이면 다른 사람 합도 비용 미만이기 때문입니다. 사람 하나를 제외한다고 실제 사업 비용까지 사라지지는 않습니다. ‘다른 사람의 후생’에 비용을 부담하는 제공자도 포함해야 지급식이 맞습니다.

상대 보고를 고정하면 자기 효용은 다음과 같습니다.

$$u_i=v_i x-p_i=(v_i+s_{-i}-C)x-h_i.$$

마지막 항은 자기 보고로 바꿀 수 없습니다. 정직하게 v_i를 보고하면 할당 규칙이 시행·미시행 중 첫 항을 최대화합니다. 따라서 다른 보고로 더 높은 효용을 만들 수 없습니다. 이는 두 결과에 대한 정확한 논증이며 학습 곡선에서 추정한 정리가 아닙니다.

정직 보고에서 결정적인 참가자의 필요 지급은 시행 조건 때문에 자신의 가치 이하입니다. 결정적이지 않은 사람은 0을 냅니다. 미시행 효용도 0이므로 정직한 개별 합리성을 얻습니다. 모두 정직하면 참 후생 max(0,sum_i v_i−C)를 최대화하는 결과를 고릅니다. 각 결론에는 명시한 가치·비용 가정이 필요합니다.

효율적인 선택과 운영자 적자는 함께 가능하다

세 번째 예제는 실제 가치·보고 (6,6,6), 비용 10입니다. 전체 편익 18이 비용을 넘으므로 시행합니다. 누구를 빼도 나머지 보고가 12이므로 사업은 여전히 시행됩니다. 아무도 결정적이지 않고 지급은 모두 0입니다.

효용은 각각 6, 수입은 0, 실제 자원 비용은 10, 운영자 순수입은 −10입니다. 참 후생은 18−10=8입니다. 참가자 효용 합 18과 운영자 순수입 −10을 더하면 다시 8이 됩니다. 지급 0은 이 결정에 결정적이지 않다는 뜻이지 편익이나 자원 소모가 없다는 뜻이 아닙니다.

이 사례는 정직 유인·효율적 선택·개별 합리성·비용 충당을 분리합니다. 모든 공공재 메커니즘에 대한 일반 불가능성 정리를 증명한 것은 아닙니다. 그런 정리에는 타입 영역과 제도에 대한 추가 가정이 있습니다.

경계 입력으로 화살표를 확인한다

비용을 0으로 두면 사업은 항상 시행되고 지급은 모두 0입니다. 비용 30과 보고 (10,10,10)에서는 등호로 시행되고 각 지급은 10입니다. 보고 하나를 9로 내리면 미시행으로 바뀝니다. 실제 가치가 모두 0인데 보고 (10,10,10)과 비용 30이면 보고 후생은 0이지만 참 후생은 −30입니다. 보고에 기초한 효율적 계산과 숨은 참값에 대한 효율성은 정직하지 않으면 다릅니다.

검사할 참가자를 바꾸면 효용 곡선·지급 분해·타입 검사는 바뀌어도 현재 할당과 지급은 같아야 합니다. 숨은 실제 가치를 바꾸면 효용·후생·정직 기준점은 바뀌지만 현재 보고에 따른 결정은 여전히 같아야 합니다. 이는 규칙이 실제 가치를 몰래 사용하지 않는지 점검하는 방법이기도 합니다.

연습 문제와 해설

1. 2등 가격, 실제 가치·보고 (5,5,0), 기준 0에서 참가자 1의 최적 보고는 무엇인가요? 보고 5에서는 참가자 0에게 동률로 집니다. 5 초과 보고는 5를 내고 낙찰되어 효용 0, 5 이하는 탈락하여 효용 0입니다. 따라서 0부터 10까지 모두 최적입니다. 정직 보고가 최적이어도 반드시 낙찰되는 것은 아닙니다.
2. 공공사업 가치·보고 (8,3,1), 비용 10에서 지급과 후생을 계산하세요. 지급은 (6,1,0), 효용은 (2,2,1), 수입 7, 운영자 순수입 −3, 참 후생 2입니다. 효용 합 5와 순수입 −3을 더하면 2입니다. 각자의 편익 전액을 청구하는 규칙과는 다릅니다.
3. 현재 보고를 바꾸면 효용이 개선된다는 결과는 정직 보고가 우월하지 않다는 뜻인가요? 아닙니다. 2등 가격에서 가치 4를 가진 사람이 상대 (5,2)에게 9를 보고하면 효용 −1이지만 정직 보고 4로 바꾸면 0입니다. 정직 유인은 유지되며 현재의 잘못된 보고가 문제입니다. 현재 보고의 개선량과 정직 보고의 최대 위반량은 다른 질문입니다.

AI 연구에 연결하기

데이터 기여자·모델 제공자·평가자는 보상 규칙에 맞춰 제출 메시지를 바꿀 수 있습니다. 숨은 품질이나 가치와 제출 점수를 분리하고, 가능한 결과 집합·지급 주체·실제 비용 부담자를 명시한 뒤 어떤 일탈을 정량화하는지 확인해야 합니다. 정확한 후생 최대화를 임의의 근사 알고리즘으로 바꾸면 같은 지급 논증이 자동으로 유지되는 것도 아닙니다.

이 실습의 인증 대상은 자신의 유한 할당·지급 구현입니다. 임의의 AI 보상 시스템, 담합 저항, 개인정보 보호나 거대한 결과 공간에서의 계산 가능성을 보장하지 않습니다. 각각 별도 모형과 근거가 필요합니다.

표준적인 사적 가치 효용과 2등 가격 유인은 Roughgarden 강의 2, 일반 보고 후생·외부 효과 지급의 틀은 강의 7을 참고하세요. 여기의 수치 예제·유한 영역 전수 그림·공공 비용 회계는 이 실습의 모형에서 별도로 유도했습니다.