--- 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 --- # 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 - [ ] **Incentive Compatibility Verified**: Mechanism specifies why truth-telling (or desired behavior) is optimal strategy for agents - [ ] **Computational Complexity Analyzed**: Either polynomial-time exact algorithm exists, or approximation factor and runtime bounds specified - [ ] **Budget Constraints Satisfied**: Payments sum to non-negative (no subsidies) OR explicit funding source identified - [ ] **Convergence Guaranteed**: Learning/adaptation process has polynomial-time convergence proof OR system uses pre-computed equilibrium - [ ] **Sybil Resistance Implemented**: Identity creation has meaningful cost OR system functions correctly under arbitrary identity multiplication - [ ] **Price of Anarchy Bounded**: Quantitative bound on efficiency loss from strategic behavior ≤ acceptable threshold - [ ] **Failure Modes Addressed**: Each failure mode has detection rule and mitigation strategy - [ ] **Network Effects Analyzed**: If system has network structure, topology's effect on equilibria and computation explicitly considered - [ ] **Private Information Handling**: Mechanism either doesn't require private info OR has dominant-strategy/Bayesian-Nash incentive compatibility proof - [ ] **Scalability Validated**: Mechanism performance (computational and economic) analyzed as number of agents grows ## 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.