curiositech/nisan-et-al-2007-algorithmic-game-theory

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.