Combinatorial Game Theory (Zero-sum vs Non-zero-sum) TODO
Concept
The most basic axis for classifying games is whether the sum of participants' payoffs is constant. Zero-sum games are purely adversarial, since one side's gain is exactly the other side's loss; for finite two-player zero-sum games there's a theorem that a unique minimax value exists once mixed strategies are allowed. In non-zero-sum games, the total payoff varies with strategy, so cooperation can leave everyone better off or everyone worse off, and the relevant solution concept shifts to Nash equilibrium — a point where no one has a unilateral incentive to deviate given others' strategies. In finite games, a mixed-strategy Nash equilibrium always exists but there can be more than one, and, as in the prisoner's dilemma, the equilibrium can be worse than the jointly optimal outcome. Separately, combinatorial games with perfect information and no element of chance have their own theory — most notably Sprague-Grundy theory, which reduces positions to Grundy numbers so that the sum of games can be computed.
Protocol design ultimately comes down to predicting what participants will do within the rules, and if a situation you assumed was zero-sum is actually non-zero-sum — where collusion pays off — the whole incentive design breaks down. It's also important to separate 'an equilibrium exists' from 'that equilibrium is desirable.'
Code & Formula
# 조합 게임이론(제로섬 vs 비제로섬) — 제로섬(Matching Pennies)의 minimax=maximin 값을
# 그리드서치로 확인하고, 비제로섬(죄수의 딜레마)의 순수전략 내시균형을 직접 탐색한다.
import numpy as np
# --- 제로섬: Matching Pennies. Row 이득 행렬 (Column 이득은 정확히 -Row) ---
A = np.array([[1, -1],
[-1, 1]], dtype=float)
ps = np.linspace(0, 1, 2001) # Row가 action0을 고를 확률 p
# Row(최대화)가 p를 고르면, Column(최소화)은 자신에게 최선인(=Row에게 최악인) 열을 선택
maximin = max(min(p * A[0, 0] + (1 - p) * A[1, 0], p * A[0, 1] + (1 - p) * A[1, 1]) for p in ps)
# Column(최소화)이 q를 고르면, Row(최대화)는 자신에게 최선인 행을 선택
minimax = min(max(q * A[0, 0] + (1 - q) * A[0, 1], q * A[1, 0] + (1 - q) * A[1, 1]) for q in ps)
print("Matching Pennies (제로섬) — payoff 행렬:")
print(A)
print(f"maximin(row가 확보 가능한 최소 기대이득의 최대치) = {maximin:.4f}")
print(f"minimax(column이 허용하는 최대 기대손실의 최소치) = {minimax:.4f}")
print("→ 두 값이 (거의) 같다 = minimax 정리: 혼합전략 하에서 게임의 값이 유일하게 존재\n")
# --- 비제로섬: 죄수의 딜레마. Row/Col 각자의 payoff 행렬이 따로 있고 합이 일정하지 않음 ---
# 행/열: 0=협력, 1=배신
R = np.array([[3, 0], [5, 1]]) # Row의 payoff
C = np.array([[3, 5], [0, 1]]) # Column의 payoff
nash = []
for i in range(2):
for j in range(2):
row_best = max(R[:, j]) == R[i, j] # Row가 j 고정 시 i가 최선인가
col_best = max(C[i, :]) == C[i, j] # Column이 i 고정 시 j가 최선인가
if row_best and col_best:
nash.append((i, j))
labels = ["협력", "배신"]
print("죄수의 딜레마 (비제로섬) — 순수전략 내시균형:")
for i, j in nash:
print(f" - (Row={labels[i]}, Col={labels[j]}) payoff=({R[i,j]}, {C[i,j]})")
print("→ payoff 합이 칸마다 다르다(3+3=6 vs 5+0=5 vs 1+1=2): 제로섬이 아니라서 협력이 상호 이득이지만,")
print(" 각자의 지배전략은 배신이라 균형은 (배신, 배신)뿐 — 파레토 열등한 결과가 균형이 된다.")
Exercise
Construct a few 2x2 payoff matrices; for the zero-sum cases, solve via minimax, and for the non-zero-sum cases, find pure and mixed Nash equilibria by hand and verify them in code.
Practical Connection
In prediction markets, trader P&L is roughly zero-sum once fees are removed, but the dispute game around challenging an oracle's result is non-zero-sum because of bonds and rewards, so parameters need to be set such that honest reporting is itself the equilibrium.
Where it lands in Jayverse
- Verex: write the oracle-dispute payoff matrix before setting bond sizes. Model challenger/reporter payoffs explicitly and solve for the equilibrium, instead of assuming the non-zero-sum bond-and-reward game behaves like the (roughly zero-sum) trading side.
- OFA: check whether solver competition is actually zero-sum. If solvers can coordinate on the price they bid in the intent auction, the mechanism has quietly become non-zero-sum, and collusion-resistance has to be designed for, not assumed away.
- Auditor: log that an equilibrium exists separately from whether it's desirable. Any mechanism write-up (slashing, dispute bonds) should say which equilibrium was found and note if it's a prisoner's-dilemma-shaped one, worse than the cooperative outcome.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| pay off | 득이 되다, 이익으로 돌아오다 · 담합이 이득일 때. "collusion pays off" |
| unilateral | 일방적인(한쪽만의) · 균형 상태에서 벗어날 유인이 없음을 말할 때. "no unilateral incentive to deviate" |
| deviate | (합의·전략에서) 벗어나다, 이탈하다 · 균형 개념을 정의할 때. "no one has a unilateral incentive to deviate" |
| break down | (설계가) 무너지다, 붕괴하다 · 전제가 틀리면 인센티브 설계 전체가 실패할 때. "the whole incentive design breaks down" |
| jointly optimal | 공동으로 최적인(다 같이 가장 나은) · 균형이 최선이 아닐 수 있음을 말할 때. "worse than the jointly optimal outcome" |
| separate X from Y | X와 Y를 구별하다 · 존재와 바람직함을 구분할 때. "separate 'an equilibrium exists' from 'that equilibrium is desirable'" |
| bond (noun) | 보증금, 공탁금 · 오라클 이의제기 게임의 유인 구조를 설명할 때. "non-zero-sum because of bonds and rewards" |
| minimax | 미니맥스 · 유한 2인 제로섬 게임에서 혼합전략을 허용하면 유일하게 존재하는 값. "a unique minimax value exists once mixed strategies are allowed" |
| Nash equilibrium | 내쉬균형 · 상대 전략이 주어졌을 때 아무도 이탈할 유인이 없는 지점, 비제로섬 게임의 해 개념. "the relevant solution concept shifts to Nash equilibrium" |
| Sprague-Grundy theory | 스프라그-그런디 이론 · 완전정보·비확률 조합게임의 위치를 그런디 수로 환원해 게임들의 합을 계산하는 이론. "most notably Sprague-Grundy theory, which reduces positions to Grundy numbers" |
| Grundy number | 그런디 수 · 조합게임의 각 위치를 나타내는 수, 게임 합산 계산의 단위. "so that the sum of games can be computed" |
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/.