Repeated Games and Reputation — excluding the Folk Theorem proof TODO
Concept
In a one-shot game, defection is a dominant strategy, so cooperation can't be sustained as an equilibrium — but when the same players repeat the game, current gains and future retaliation are weighed together, and cooperation can be sustained as an equilibrium. The key variable is the discount factor, representing how much future payoffs are valued (or, equivalently, the probability the game continues); once this value is large enough, the loss from future punishment outweighs the one-time gain from defecting. Strategies like grim trigger and tit-for-tat turn this comparison into an executable rule, and the condition for sustaining cooperation reduces to the inequality 'gain from defecting ≤ discounted loss from future punishment.' The folk theorem states that as the discount factor approaches 1, essentially any payoff combination satisfying individual rationality can be supported as an equilibrium (we won't cover the proof). The practical takeaway is that reputation isn't a matter of morality — it's an equilibrium phenomenon produced by three conditions: repeated interaction, observability of behavior, and the value of the future relationship.
The honesty of continuously participating actors — validators, oracle providers, market makers — is something you design through the possibility of punishment and the size of future earnings, not something you can count on out of good faith. The moment a relationship becomes one-shot, that equilibrium disappears.
Code & Formula
# 반복게임과 평판(grim trigger) — 할인인자가 임계치 이상이면 "영원한 보복" 위협만으로
# 무한반복 죄수의 딜레마에서 협력이 균형으로 유지됨을 수치로 확인한다.
# 표준 PD payoff: R(둘다 협력) < T(배신 유혹) 이고 P(둘다 배신) 는 그 사이 어딘가
T, R, P, S = 5, 3, 1, 0 # Temptation, Reward, Punishment, Sucker
# grim trigger: 상대가 한 번이라도 배신하면 그 뒤로 영원히 배신으로 응징
# 협력 유지 조건(이탈 무이익): R/(1-δ) >= T + δ*P/(1-δ) => δ >= (T-R)/(T-P)
threshold = (T - R) / (T - P)
print(f"협력 유지를 위한 할인인자 임계값 δ* = (T-R)/(T-P) = {threshold:.3f}")
def value_of_cooperating(delta: float) -> float:
# 계속 협력 → 매 라운드 R을 무한히 할인합산
return R / (1 - delta)
def value_of_deviating_once(delta: float) -> float:
# 이번 라운드만 배신(T 획득) 후 상대의 grim trigger로 영원히 P
return T + delta * P / (1 - delta)
for delta in (0.3, threshold, 0.7):
coop = value_of_cooperating(delta)
dev = value_of_deviating_once(delta)
verdict = "협력 우세 → 협력이 균형으로 유지" if coop >= dev else "이탈 우세 → 협력 붕괴"
print(f"δ={delta:.3f}: V(협력)={coop:8.3f} V(1회 이탈+영구응징)={dev:8.3f} → {verdict}")
Exercise
Fix a payoff table for the repeated prisoner's dilemma, compute by hand the minimum discount factor under which grim trigger sustains cooperation, then check how that threshold moves as you increase the gain from defecting.
Practical Connection
In prediction markets, the incentive for an oracle reporting outcomes or a dispute participant to stay honest ultimately comes down to whether the size of the stake and future fee income outweigh the one-time gain from manipulation.
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/.