curiositech/shoham-leyton-brown-2009-mas-foundations

Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations

Metadata

• Source: Shoham & Leyton-Brown (2009)
• Applies to: Distributed systems design, mechanism design, protocol design, API economics, coordination problems
• Triggers: "multiple agents", "coordination", "incentive design", "distributed constraint", "equilibrium", "mechanism design", "voting system", "auction design", "strategic behavior", "Nash equilibrium"

Decision Points

Primary Branching: Problem Type Identification

Coordination Problem
├─ Strategic agents (may misreport)?
│  ├─ YES → Mechanism Design Path
│  │  ├─ Need truthful reporting?
│  │  │  ├─ YES + efficiency required → Use VCG (accept budget imbalance)
│  │  │  └─ YES + budget balance required → Check Myerson-Satterthwaite impossibility
│  │  ├─ Computational constraints on agents?
│  │  │  ├─ YES → Avoid revelation principle; use simplified mechanisms
│  │  │  └─ NO → Direct truthful mechanism feasible
│  │  └─ Requirements contradictory? → Identify which impossibility applies
│  │
│  └─ NO → Distributed Algorithm Path
│     ├─ Interdependent constraints?
│     │  ├─ YES → Distributed CSP (asynchronous backtracking)
│     │  └─ NO → Standard distributed coordination
│     └─ Global consistency required? → Use priority-based conflict resolution
│
├─ Equilibrium computation required?
│  ├─ YES → Representation Choice
│  │  ├─ Perfect information → Backward induction (linear time)
│  │  ├─ Imperfect info + perfect recall → Sequence form (polynomial)
│  │  ├─ Normal form small → Support enumeration
│  │  └─ Normal form large → Use correlated equilibrium (LP)
│  │
│  └─ NO → Check existence only
│
└─ Agents computationally bounded?
   ├─ YES → Bounded Rationality Model
   │  ├─ Repeated interaction → Use finite automata analysis
   │  ├─ Memory < game length → Cooperation may emerge
   │  └─ Simple heuristics → Myopic best response, tit-for-tat
   │
   └─ NO → Full game-theoretic analysis

Information Structure Decision Tree

IF agents have private information AND strategic
THEN choose information revelation mechanism:
├─ Perfect information possible → Design full revelation protocol
├─ Imperfect information + perfect recall → Use sequence form representation
├─ Imperfect recall unavoidable → Accept mixed ≠ behavioral strategies
└─ Common knowledge achievable → Enable coordination on superior equilibria

Computational Feasibility Gates

IF mechanism requires Nash computation
THEN check problem size:
├─ Small normal form (< 10 strategies) → Support enumeration acceptable
├─ Large normal form OR imperfect information → Switch to sequence form
├─ Still intractable → Use correlated equilibrium (linear program)
└─ Real-time constraints → Bounded rationality heuristics only

Failure Modes

1. Centralized Control Assumption

• Symptom: Designing "distributed" systems with required central coordinator
• Detection: If system fails when any single node has complete information/control
• Root Cause: Confusing distribution of computation with distribution of authority
• Fix: Design for truly autonomous agents with private state and strategic behavior

2. Computational Complexity Blindness

• Symptom: Proposing mechanisms requiring Nash equilibrium computation for large games
• Detection: If best-response computation or mechanism operation is exponential-time
• Root Cause: Treating existence theorems as constructive algorithms
• Fix: Check both mechanism and agent computational complexity; use correlated equilibrium or bounded rationality models

3. Revelation Principle Misapplication

• Symptom: Concluding "we only need direct truthful mechanisms" without implementation analysis
• Detection: If converted direct mechanism requires exponential communication or creates new equilibria
• Root Cause: Ignoring computational and implementation constraints of revelation principle conversion
• Fix: Treat as theoretical tool only; explicitly model feasibility constraints

4. Impossibility Denial

• Symptom: Attempting to achieve efficiency + budget balance + individual rationality in bilateral trade
• Detection: If requirements match known impossibility theorem conditions
• Root Cause: Unfamiliarity with fundamental impossibility results
• Fix: Identify applicable impossibility theorem; choose which property to relax before designing

5. Representation Lock-in

• Symptom: Declaring problems intractable after analyzing only normal form representation
• Detection: If computational analysis doesn't consider extensive form or sequence form alternatives
• Root Cause: Treating representation as given rather than design choice
• Fix: Exhaust representation alternatives before concluding intractability

Worked Examples

Example 1: API Rate Limiting with Strategic Users

Scenario: Design rate limiting for API where users may misreport resource needs to get better service.

Decision Process:

1. Problem Type: Strategic agents (users lie about needs) → Mechanism Design Path
2. Requirements: Efficiency (allocate to highest-value users) + Revenue generation
3. Impossibility Check: Not bilateral trade, so Myerson-Satterthwaite doesn't apply
4. Mechanism Choice: VCG auction for rate limits
   • Users bid value per request
   • Award to highest bidders up to capacity
   • Charge second-price (VCG payment)
5. Computational Check:
   • Mechanism: Sort bids (O(n log n)) ✓
   • Agents: Submit single bid (O(1)) ✓
6. Trade-off: Accepts budget imbalance (system profit) for truthful reporting

Expert vs Novice: Novice would use first-price auction (agents shade bids, lose efficiency). Expert recognizes VCG truthfulness requirement.

Example 2: Multi-tenant Resource Allocation with Correlated Equilibrium

Scenario: Multiple services sharing compute cluster; need coordination without central controller.

Decision Process:

1. Problem Type: Strategic agents + equilibrium computation needed
2. Representation Check: 100+ services → Normal form has 2^100 strategy combinations
3. Nash Computation: PPAD-complete, infeasible
4. Alternative: Correlated equilibrium via central randomization
   • Random oracle broadcasts resource allocation suggestions
   • Following suggestions forms correlated equilibrium (linear program solution)
   • Often higher welfare than Nash equilibrium
5. Implementation: Blockchain oracle or trusted scheduler

Key Insight: Central randomization ≠ central control. Oracle can't force compliance, only coordinate expectations.

Example 3: Distributed Sensor Network with Bounded Rationality

Scenario: Sensor nodes with limited memory must coordinate measurements without central control.

Decision Process:

1. Constraints: 4-bit memory per node, 10-round coordination game
2. Rationality Bound: Cannot perform backward induction (requires 10 states, have 16 total)
3. Equilibrium Analysis: Perfect rationality would mandate defection; bounded rationality enables cooperation
4. Strategy: Tit-for-tat automata (3 states: cooperate, defect-once, defect-always)
5. Result: Cooperation emerges because backward induction is computationally impossible

Trade-off Analysis: Accept suboptimal individual decisions for superior collective outcomes.

Quality Gates

• [ ] Problem classified as strategic vs non-strategic agents
• [ ] Information structure explicitly specified (perfect/imperfect info, perfect/imperfect recall)
• [ ] Computational complexity verified for both mechanism and agent best-response
• [ ] Representation choice justified (normal/extensive/sequence form) based on tractability
• [ ] Applicable impossibility theorems identified and constraints relaxed accordingly
• [ ] Equilibrium existence proven OR bounded rationality model justified
• [ ] Budget balance vs efficiency vs truthfulness trade-offs explicitly stated
• [ ] Communication complexity bounded by practical constraints
• [ ] Incentive compatibility verified under specified rationality assumptions
• [ ] Failure modes for misaligned incentives identified with detection mechanisms

NOT-FOR Boundaries

This skill should NOT be used for:

• Single-agent optimization problems → Use algorithmic-optimization instead
• Pure algorithm design without strategic considerations → Use computational-complexity instead
• Systems with complete central control → Use distributed-algorithms instead
• Cooperative multi-agent systems where agents don't act strategically → Use consensus-protocols instead
• Machine learning coordination where agents adapt rather than optimize → Use multi-agent-reinforcement-learning instead

Delegation Rules:

• For consensus with Byzantine faults but non-strategic agents → Use byzantine-fault-tolerance
• For auction design with known valuations → Use combinatorial-optimization
• For voting without strategic manipulation → Use social-choice-theory
• For distributed optimization with truthful agents → Use distributed-constraint-optimization