| license | Apache-2.0 |
| name | nisan-et-al-2007-algorithmic-game-theory |
| description | Comprehensive treatment of algorithmic game theory covering mechanism design, auctions, and equilibrium computation |
| category | Research & Academic |
| tags | ["game-theory","mechanism-design","auctions","algorithmic","equilibria"] |
| io-contract | {"kind":"none","covers":["mechanism design","auction theory","Nash equilibrium computation","price of anarchy","VCG mechanisms","incentive compatibility","multi-agent learning convergence","sybil attack prevention","information aggregation","strategic behavior in computational systems"]} |
Algorithmic Game Theory
Name: Algorithmic Game Theory
Author: Noam Nisan, Tim Roughgarden, Éva Tardos, Vijay V. Vazirani (editors)
Maintainer: Claude Code Skill Library
Version: 1.0
Tags: #game-theory #mechanism-design #multi-agent-systems #incentive-design #computational-complexity
Description
This skill provides frameworks for designing computational systems where self-interested agents make strategic decisions. It integrates game theory and algorithm design to solve the dual challenge: creating systems that are both computationally efficient and strategically robust. Use when building systems with multiple decision-makers whose incentives may not naturally align with system goals.
Decision Points
1. Centralized vs Decentralized Architecture Choice
Calculate Price of Anarchy (PoA) for your domain:
├── PoA ≤ 2
│ ├── System loses <50% efficiency from strategic behavior
│ └── → Allow decentralized control
├── 2 < PoA ≤ 10
│ ├── Moderate inefficiency, check implementation costs
│ └── → Consider mechanism intervention (taxes, tolls)
└── PoA > 10 or unbounded
├── Strategic behavior destroys system value
└── → Require centralized allocation or strong mechanisms
2. Mechanism Selection for Truthful Information Elicitation
Can you compute optimal allocation efficiently?
├── YES: Optimal allocation is polynomial-time
│ ├── Budget deficits acceptable?
│ │ ├── YES → Use VCG mechanism (dominant strategy truthful)
│ │ └── NO → Use proportional allocation (4/3-approximation + budget balance)
│ └── Private information has structure?
│ ├── Gross substitutes → Use ascending auction
│ └── General valuations → Check approximation algorithms
└── NO: Optimal allocation is NP-hard
├── Good approximation algorithm exists?
│ ├── YES + algorithm preserves monotonicity → Approximate VCG
│ └── NO → Use Bayesian mechanisms with known priors
└── Need budget balance → Relax to ex-post individually rational
3. Convergence Analysis for Multi-Agent Learning
What learning algorithm do agents use?
├── Regret minimization (multiplicative weights, follow-the-leader)
│ └── → Converges to correlated equilibrium in O(log n / ε²) rounds
├── Best response dynamics
│ ├── Game has potential function?
│ │ ├── YES → Converges to pure Nash
│ │ └── NO → May cycle indefinitely
│ └── Game is zero-sum → Converges to mixed Nash
├── Gradient-based learning
│ ├── Payoffs are concave?
│ │ ├── YES → Converges to Nash
│ │ └── NO → Check if game is stable (eigenvalues)
│ └── Network topology matters
│ ├── Tree structure → TreeNash algorithm (polynomial time)
│ └── General graph → PPAD-hard
└── No learning structure specified
└── → Nash computation is PPAD-complete, use approximate equilibrium
4. Sybil Attack Prevention Strategy
Identify attack vector:
├── Cheap identity creation possible?
│ ├── YES: Require costly signaling
│ │ ├── Proof-of-stake (economic cost)
│ │ ├── Proof-of-work (computational cost)
│ │ └── Identity verification (administrative cost)
│ └── NO: Can rely on natural identity scarcity
├── Trust is transitive (friend-of-friend)?
│ ├── YES → Use graph-based reputation (PageRank, hitting time)
│ └── NO → Use direct interaction history only
└── Whitewashing possible (restart with clean identity)?
├── YES → Require long-term identity investment
└── NO → Standard reputation accumulation works
5. Information Aggregation Function Choice
What type of information are you aggregating?
├── Probability estimates
│ ├── Single event → Use proper scoring rules (logarithmic, quadratic)
│ └── Conditional probabilities → Market scoring rules (LMSR)
├── Binary signals (yes/no votes)
│ ├── Simple majority needed → Always market-computable
│ └── Complex threshold → Check if market-computable
│ ├── Weighted majority → Market-computable
│ └── XOR, parity → NOT market-computable
├── Expert predictions with different quality
│ ├── Track record available → Weight by historical accuracy
│ └── No history → Sequential reporting (experts condition on previous)
└── Strategic experts may coordinate
└── → Use scoring rules + randomization to prevent manipulation
Failure Modes
1. Equilibrium Existence Fallacy
Symptom: "Nash theorem guarantees equilibrium exists, so our multi-agent system will find it"
Diagnosis: Confusing existence with computability
Detection Rule: If you're assuming agents will "find" Nash equilibrium without specifying a polynomial-time algorithm
Fix: Use correlated equilibrium (polynomial-time via regret minimization) or approximate Nash with convergence guarantees
2. Incentive-Blind Optimization
Symptom: System computes optimal allocation but agents lie about preferences, causing poor outcomes
Diagnosis: Ignoring strategic behavior when designing algorithms
Detection Rule: If your mechanism asks for private information but doesn't specify why truth-telling is optimal
Fix: Use VCG payments (charge externality) or design allocation rule to be monotone + incentive-compatible
3. Budget Balance Blindness
Symptom: VCG mechanism runs budget deficits; system financially unsustainable
Diagnosis: Assuming theoretical mechanisms work without resource constraints
Detection Rule: If mechanism payments sum to negative (subsidizing participants)
Fix: Use proportional allocation, core-based mechanisms, or accept approximate efficiency for budget balance
4. Topology Neutrality Mistake
Symptom: Network performance degrades unexpectedly; agents find exploits through graph structure
Diagnosis: Treating network topology as purely technical choice, ignoring strategic implications
Detection Rule: If equilibrium analysis doesn't account for graph structure effects on agent payoffs
Fix: Design topology jointly with incentives; use bounded-degree graphs for tractability, tree structure for exact solutions
5. Sybil-Vulnerable Reputation
Symptom: Reputation system overwhelmed by fake accounts; honest users' influence diluted
Diagnosis: Building reputation without identity costs
Detection Rule: If reputation system has no barriers to creating new identities
Fix: Require proof-of-stake, proof-of-work, or administrative identity verification; make identity persistent and costly
Worked Examples
Example 1: API Rate Limiting Mechanism Design
Scenario: Design rate limiting for an API where users have different urgency levels for requests, but you can't directly observe urgency.
Step 1 - Decision Point Navigation: Can we compute optimal allocation efficiently?
- YES: Assigning requests to users is a matching problem (polynomial)
- Budget balance needed? YES: Can't subsidize API usage
- → Use proportional allocation variant
Step 2 - Mechanism Design:
- Ask users to bid their "urgency value" for each request
- Allocate capacity proportionally: user i gets (bid_i / total_bids) × capacity
- Charge each user their bid (truthful in expectation)
Step 3 - Failure Mode Check:
- Sybil attack possible? YES: Users could split across multiple accounts
- Fix: Require account creation cost or tie to authenticated identity
- Budget balance achieved? YES: Payments exactly equal bids
Expert vs Novice:
- Novice would: Set fixed rate limits or simple priority queues
- Expert catches: Need to elicit private urgency info; must prevent account multiplication; proportional allocation achieves truthfulness + budget balance
Example 2: Distributed Cache Cost Allocation
Scenario: Multiple services share a distributed cache. Cache hits reduce database load (shared benefit), but cache maintenance has costs. How do we allocate costs fairly?
Step 1 - Convergence Analysis: Will cost-sharing reach equilibrium?
- Services choose cache usage levels based on allocated costs
- Game has negative externalities (my usage increases everyone's costs)
- Check: Is this a potential game? NO: Cost-sharing games typically don't have potential
- → Use Shapley cost-sharing to bound inefficiency
Step 2 - Mechanism Selection:
- VCG would be optimal but computationally expensive for cost-sharing
- Shapley cost-sharing: each service pays average marginal cost
- Price of Anarchy ≤ O(log n) for Shapley cost-sharing
Step 3 - Implementation Reality Check:
- Can services manipulate by splitting workloads? Need to define "service" carefully
- Will services truthfully report cache benefit? Use revealed preference (actual usage) rather than stated preference
Expert vs Novice:
- Novice would: Split costs equally or by usage percentage
- Expert catches: Equal splitting creates free-rider problem; usage-based creates gaming incentives; Shapley cost-sharing balances fairness and incentives with known approximation bounds
Quality Gates
NOT-FOR Boundaries
Do NOT use this skill for:
- Pure optimization problems where all agents are under your direct control → Use standard algorithms and operations research instead
- Cooperative scenarios where all parties share aligned incentives → Use collaborative planning and coordination mechanisms
- Single-agent decision problems even with uncertainty → Use decision theory, reinforcement learning, or stochastic optimization
- Non-interactive systems where agents don't affect each other's payoffs → Use independent optimization for each agent
- Legal/regulatory compliance where behavior is enforced externally → Use audit mechanisms and compliance frameworks
- Physical constraints that prevent strategic behavior → Use engineering solutions and capacity planning
Delegate to other skills:
- For cryptographic protocol security → Use formal verification and cryptographic analysis
- For system performance optimization → Use distributed systems and performance engineering
- For user experience design → Use human-computer interaction and behavioral design
- For data privacy protection → Use privacy-preserving computation and differential privacy
- For fault tolerance → Use reliability engineering and distributed consensus protocols
This skill applies when agents are strategic AND their choices affect system outcomes AND you cannot simply command compliance.
Bundle Inventory
Deep-dive reference chapters bundled with this skill:
- references/mechanism-design-with-money.md — VCG mechanisms, auctions, incentive-compatible payment rules.
- references/equilibrium-computation-and-convergence.md — computing Nash equilibria, complexity (PPAD), learning dynamics and when they converge.
- references/price-of-anarchy-and-network-design.md — bounding efficiency loss from selfish behavior; routing and network-formation games.
- references/reputation-systems-and-trust.md — reputation as an incentive instrument; whitewashing, Sybil attacks, and trust aggregation.
- references/information-aggregation-and-prediction.md — prediction markets, scoring rules, and eliciting honest beliefs.
(_book_identity.json and _raw_response.md are book-skill generation artifacts, consistent with the other imported-literature bundles.)
