Game Theory
Bayesian Games and Incomplete Information
Google and Facebook auctions are Bayesian games. Every second ~100,000 sealed-bid auctions with private valuations. Advertisers know how much a click is worth to them, competitors don't. $200M per day in bids - and the optimal strategy is computed through BNE: bid exactly (n-1)/n of true valuation.
- **Google Ads (GSP auction):** ~100K auctions per second. Equilibrium bid depends on beliefs about the distribution of competitors' valuations. Revenue Equivalence: theoretically Google could use any standard format.
- **Adverse selection in medicine:** the ACA (Obamacare) mandated accepting all comers - a deliberate violation of BNE to achieve a social optimum.
- **Credit scoring:** FICO score, bank underwriting models - algorithms for reducing adverse selection by refining the borrower's type.
Предварительные знания
Google Auctions: $200M in Bids Per Day
Every time a Google page loads, it runs a sealed-bid auction for ad placement. ~8.5 billion page loads per day. Each advertiser knows how much a click is worth to them - but not the valuations of competitors. This is a classic Bayesian game with private values.
Incomplete information differs from imperfect information. **Imperfect**: players cannot see some **moves** in the current game (cards in poker). **Incomplete**: players do not know fundamental **characteristics** of opponents - their type: preferences, valuations, costs.
**Why did the used car market not fully collapse (as in Akerlof's model)?** Three mechanisms: 1) signaling (seller's warranty, service history), 2) screening (independent mechanic check), 3) reputation mechanisms (CarHistory, CARFAX). Incomplete information destroys markets - but markets invent tools to fight back.
A used car seller knows its quality q; the buyer does not. Is this 'incomplete' or 'imperfect' information, and how does Harsanyi's transformation model it?
Incomplete information concerns fundamental characteristics (types) - the buyer doesn't know the car's quality before purchase. Imperfect information concerns hidden moves within the game. Harsanyi's transformation: Nature randomly assigns type q before the game starts. Each player sees only their own type. This converts incomplete information into imperfect information (Nature's private move).
Bayesian Game: Formal Model
A Bayesian game (Bayesian game) is a formal description of a game with incomplete information. The key difference from a standard game: a strategy is not a single action, but a **function of the type** (a contingency plan for all possible types).
**Revenue Equivalence Theorem:** with symmetric risk-neutral bidders with independent valuations, all standard auction formats (first-price, second-price, English, Dutch) yield the same expected revenue to the seller. This is one of the most surprising theorems in auction theory.
In a first-price auction BNE, why doesn't a player bid their true valuation v?
At bid b = v: profit when winning = v − b = 0, so winning gives no benefit. Optimal bid b* maximizes expected profit: E[π] = P(win)·(v − b) = b·(v − b) for two bidders with Uniform[0,1] valuations. Setting d/db[b(v−b)] = v − 2b = 0 gives b* = v/2. With n bidders: b*(v) = v·(n−1)/n.
BNE and Revenue Equivalence
Bayesian Nash Equilibrium (BNE) is a generalization of Nash Equilibrium. Every type of every player maximizes expected payoff given others' strategies and beliefs about types.
**Google uses a modified Generalized Second-Price (GSP) auction**, not a pure Vickrey auction. GSP has no dominant strategy - equilibrium depends on beliefs about others. The exact BNE of GSP is an open research problem with direct application at $200M per day.
The Vickrey auction has a dominant strategy of bidding true valuation. Why doesn't Google use it instead of GSP?
Several reasons: (1) Ad slots are multiple heterogeneous items - VCG for multiple slots (Vickrey-Clarke-Groves) is complex to implement and explain. (2) GSP emerged earlier and the advertiser ecosystem is built around it. (3) Revenue Equivalence may not hold for GSP in practice. (4) Strategic considerations: with VCG, advertisers might collude more easily since the dominant strategy is obvious.
Adverse Selection and Moral Hazard
Incomplete information produces two classic market failures. **Adverse selection** (before the contract): bad types drive out good ones. **Moral hazard** (after the contract): the insured party behaves more recklessly.
**Moral hazard:** a bank extends a loan - the borrower knows that in bankruptcy, they lose less than the bank (limited liability). Incentive to take risk: privatize profits while socializing losses. Solution: loan covenants, collateral, monitoring. All of bank regulation is built around moral hazard.
**Too Big to Fail as extreme moral hazard:** banks knew in 2008 that the government would bail them out. This created an incentive for excessive risk-taking. Akerlof, Spence, and Stiglitz received the Nobel Prize (2001) precisely for analyzing markets with asymmetric information.
The insurance market under adverse selection leads to a 'death spiral'. Why does risk-grouping restore market efficiency, and what ethical problems does it create?
Risk grouping: the insurer assesses individual risk and sets premium ≈ E[claimᵢ]. This eliminates adverse selection - no cross-subsidization means no death spiral. Ethical problems: (1) high-risk individuals (elderly, ill) pay more or are denied coverage; (2) insurers require medical data (privacy); (3) pre-existing conditions - the ACA in the US banned denial of coverage, deliberately departing from an efficient market in favor of fairness.
Key Ideas
- **Incomplete information**: players don't know opponents' types (θᵢ). Harsanyi: Nature randomly assigns types.
- **BNE**: s*ᵢ(θᵢ) = best response for each type θᵢ given beliefs p(θ₋ᵢ|θᵢ) and others' strategies.
- **First-price auction**: BNE bid(v) = v·(n-1)/n. Second-price (Vickrey): bid(v) = v (dominant strategy).
- **Revenue Equivalence**: all standard formats yield the same E[revenue] for symmetric rn-bidders with iid valuations.
- **Adverse selection**: pre-contract (bad types drive out good). **Moral hazard**: post-contract (behavior changes).
Related Topics
Bayesian games are the foundation of auction theory and mechanism design:
- Signaling Games — Signaling is a way to reveal type through a costly action. Direct continuation of Bayesian games with dynamic belief updating.
- Repeated Games — Reputation mechanisms in repeated games solve adverse selection through signaling type via action history
Вопросы для размышления
- Google uses GSP instead of the theoretically optimal VCG (Vickrey-Clarke-Groves). Revenue Equivalence says they should give the same revenue. What violations of Revenue Equivalence's assumptions explain why Google chooses GSP?
- Adverse selection in insurance creates a death spiral. How does mandatory insurance (like auto liability) mathematically change BNE and eliminate adverse selection? What new distortions does it create?
- ML algorithms for credit scoring (LightGBM, neural networks) more accurately predict default risk. From a game theory perspective: how does improving information about borrower type change the equilibrium in the credit market?