Mechanism Design: The VCG Concept TODO
Concept
Mechanism design is the field of designing the rules themselves so that a desired outcome emerges in equilibrium, under the premise that participants hold private information (preferences, values) and act strategically. One core goal is incentive compatibility, and the strongest form is dominant-strategy incentive compatibility, where truthful reporting is optimal for a participant regardless of what everyone else does. The VCG mechanism chooses the allocation that maximizes the sum of reported values, and charges each participant a payment equal to "the welfare their participation cost every other participant" — this aligns each participant's own net gain with the social surplus they create, making truthful reporting a dominant strategy. Applying VCG to a single-item auction gives exactly the second-price (Vickrey) auction, where the winner pays not their own bid but the runner-up's bid. That said, VCG can break budget balance, is vulnerable to collusion and Sybil (fake-identity) bidding, and the allocation problem itself can be computationally hard — so in practice it's often used as a design reference rather than deployed as-is.
Every place a protocol prices something — block-space auctions, MEV distribution, fee markets, oracle rewards — is a mechanism, and misaligned incentives inevitably surface as participants gaming the rules.
Code & Formula
# 메커니즘 디자인(VCG 개념) — 단일 물품 경매에 VCG를 적용하면 2위가격(비크리) 경매가 됨을
# 직접 계산으로 확인: 지불액 = "내가 없었다면 다른 참가자들이 얻었을 후생" = 차순위 입찰가.
def vcg_payment(bids: dict, winner: str) -> float:
# 배분: 신고된 가치 합(단일 물품이므로 = 최고 입찰자)을 최대화.
# 지불액: 위너가 참여하지 않았을 때 다른 참가자들이 얻는 최적 후생(=차순위 최고가)
# 에서, 위너 참여 시 다른 참가자들이 얻는 후생(=0, 물품을 못 받으므로)을 뺀 값.
others = {b: v for b, v in bids.items() if b != winner}
welfare_without_winner = max(others.values()) if others else 0.0
welfare_of_others_with_winner = 0.0 # 물품이 하나뿐이라 위너가 다 가져가면 남에게 후생 0
return welfare_without_winner - welfare_of_others_with_winner
bids = {"alice": 90, "bob": 70, "carol": 55}
winner = max(bids, key=bids.get)
payment = vcg_payment(bids, winner)
second_highest = sorted(bids.values(), reverse=True)[1]
print("입찰:", bids)
print(f"낙찰자(신고 가치 합 최대화): {winner} (가치={bids[winner]})")
print(f"VCG 지불액: {payment}")
print(f"차순위 입찰가(2위가격): {second_highest}")
print("VCG 지불액 == 2위가격?", payment == second_highest)
# 유인합치성 확인: 낙찰자가 진실보다 낮게 신고해도 지불액(payment)은 안 바뀌므로
# (payment 는 '남의' 입찰가에만 의존) 거짓 신고로 순이익을 늘릴 수 없음을 수치로 보인다.
true_value = bids["alice"]
for reported in (95, 90, 75, 60): # alice 가 진실(90) 대신 다르게 신고해봄
trial_bids = dict(bids)
trial_bids["alice"] = reported
trial_winner = max(trial_bids, key=trial_bids.get)
if trial_winner == "alice":
pay = vcg_payment(trial_bids, "alice")
surplus = true_value - pay # 실제 가치 기준 순이익
else:
surplus = 0.0
print(f"alice 신고={reported:3} -> 낙찰자={trial_winner:6} 순이익(진짜가치 기준)={surplus}")
Exercise
For a single-item auction with three bidders of different values, directly compute the payment and each participant's optimal strategy under first-price and second-price rules, and compare.
Practical Connection
When Verex sets rewards and penalties for oracle reporters or dispute participants, structuring payments so truthful reporting is also individually optimal is exactly an incentive-compatibility design problem.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.