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