Game Theory
An academic computer science course on strategic interaction, Nash equilibrium, equilibrium computation, regret minimization, and mechanism design.
Game theory models strategies of multiple decision makers whose outcomes depend on one another. The course develops computational problems through pure and mixed equilibria, algorithms for equilibrium, online learning, network games, and incentive mechanisms. Individual rationality and system efficiency are distinct objectives.
Unit 1: Mathematical Representation of Games and Strategic Decisions
1.1. Players, Strategies, and Payoff Functions
A strategic game specifies a player set, strategy set for each player, and payoffs dependent on the joint strategy profile. An individual choice is not an independent optimization because its payoff depends on other choices. Normal-form and extensive-form representations describe interactions with different information structures.
1.2. Distributed Resource-Sharing Models
In distributed resource allocation, an action may select a server or channel while payoff depends on latency and resource cost. The construction of payoffs from measurements must be specified. Infinite strategy sets cannot always be represented by finite payoff matrices.
G = (N, (Sᵢ)ᵢ∈N, (uᵢ)ᵢ∈N); uᵢ : ∏[j] Sⱼ → ℝ1.3. Consistency of Payoff Representations
Before computing equilibrium, validate payoff and feasibility for every relevant profile. Distinguish positive affine changes in individual utility from transformations that can alter equilibrium.
1.4. Numerical and Algorithmic Example
In a two-player resource-sharing game, actions select resources A or B. Congestion from simultaneous selection of A may make switching to B profitable. This is not a centralized assignment optimum because players need not share the same objective.
1.5. Elements of a Strategic Model
A finite normal-form game specifies players, action sets and payoff functions over joint action profiles. Payoffs need not be monetary; latency, computing cost and access quality can be transformed into utilities. The scale of utility and whether transformations preserve the relevant preferences influence equilibrium interpretations. In routing games, aggregate system cost need not equal a simple sum of individual utilities.
G = (N, (Sᵢ)ᵢ∈N, (uᵢ)ᵢ∈N)1.6. Central Optimization Versus Strategic Interaction
Single-agent optimization searches for a best value of one objective. In a strategic model, each player optimizes its own payoff while other players change its environment. The aggregate system objective may conflict with individual incentives. A two-resource example with independent user decisions can illustrate why centralized optimal allocation need not emerge spontaneously.
1.7. Validation of Payoff Matrices
Each cell of a two-player payoff table holds an ordered payoff pair. Unstable row and column ordering can cause best-response calculations to use the wrong player's incentives. Generated games should be tested for agreement between payoff-function evaluation and table entries. For many players, the explicit normal form grows as the product of action-set sizes and may require compressed representations.
1.8. Computational Example and Calculation
Let two users independently choose resource A or B, with resource cost equal to the number of users choosing it. If both select A, each incurs cost 2; splitting across resources yields cost 1 each, illustrating strategic externality.
C(A,A)=4; C(A,B)=21.9. Independent Verification and Implementation Constraints
Payoff matrices must distinguish cost minimization from utility maximization to avoid reversing best responses.
Unit 2: Normal-Form Games and Best-Response Analysis
2.1. The Best-Response Correspondence
A best-response correspondence contains actions maximizing an agent’s payoff for fixed strategies of others. Strict and weak dominance differ: removing weakly dominated strategies may depend on elimination order. Rationality is an assumption of the model, not a property inferred automatically from a payoff matrix.
2.2. Dominance and Strategy Elimination Algorithms
Best responses in finite games can be computed by enumerating each player’s actions. The number of joint profiles grows multiplicatively, making exhaustive enumeration exponential in the number of players. Compact payoff representations can reduce memory demand.
BRᵢ(s₋ᵢ) = arg max[a∈Sᵢ] uᵢ(a, s₋ᵢ)2.3. Computational Cost of Finite Games
When iterated elimination is used, record removed actions and the comparison criterion. Best responses found without mixing apply only to the pure-strategy space.
2.4. Numerical and Algorithmic Example
A two-action game with two players has four pure strategy profiles. At each profile, check both players’ gains from deviating to the other action. Pure Nash equilibria are precisely those with no strictly profitable unilateral deviation.
2.4.1. Illustrative Pseudocode
for profile in cartesian_product(strategy_sets):
deviations = []
for player in players:
deviations += profitable_unilateral_deviations(player, profile)
if deviations == []: report_pure_equilibrium(profile)2.5. Strict and Weak Dominance
An action is strictly dominated if another action gives a strictly higher payoff against every opposing strategy. It cannot be a best response in a finite game. Weak dominance allows equality in some profiles, making elimination order and modeling assumptions important. Iterated elimination can simplify equilibrium analysis, but indiscriminately removing weakly dominated actions may discard equilibria.
uᵢ(aᵢ,s₋ᵢ) > uᵢ(bᵢ,s₋ᵢ) ∀s₋ᵢ2.6. Computing Best Responses
A best response is the set of actions maximizing a player's utility against fixed opposing strategies. Tied actions produce a correspondence rather than one unique response. A pure Nash equilibrium requires consistency with every player's best-response set. Small matrices can be enumerated, but computational cost grows rapidly for many players or implicit payoff functions.
2.7. Pure-Equilibrium Search and Verification
A pure strategy profile can be verified by checking all unilateral deviations for every player. Failure to find a pure equilibrium does not imply that the game has no solution: finite games admit mixed-strategy equilibria. Exhaustive enumeration is a useful small-case oracle but is not a scalable algorithm for very large games.
2.8. Computational Example and Calculation
Two players obtain payoff 2 each when choosing the same action and zero when choosing different actions. (A,A) and (B,B) are pure Nash equilibria; mismatched profiles admit profitable unilateral deviations.
uᵢ(A,A)=uᵢ(B,B)=2; uᵢ(A,B)=uᵢ(B,A)=02.9. Independent Verification and Implementation Constraints
Multiple pure equilibria provide a test of nonunique equilibrium selection. Every available deviation must be reconsidered when adding strategies.
Unit 3: Zero-Sum Games and the Minimax Theorem
3.1. Zero-Sum Payoff Matrices
In a two-player zero-sum game, one player’s gain equals the other’s loss. A mixed strategy is a probability distribution with nonnegative entries summing to one. Finite two-player zero-sum games possess a minimax value.
3.2. Minimax Computation by Linear Programming
The maximal guaranteed payoff is representable as a linear program. Its dual expresses the opponent’s optimal mixture. Linear-program equilibrium computation applies to this special class and does not extend unchanged to arbitrary general-sum games.
max[p∈Δₘ] min[j] ∑[i] pᵢAᵢⱼ = min[q∈Δₙ] max[i] ∑[j] Aᵢⱼqⱼ3.3. Primal–Dual Strategy Validation
For a small payoff matrix, compute both primal and dual mixed strategies and compare expected values. Validate worst-case guarantees and probability normalization separately.
3.4. Numerical and Algorithmic Example
In matching pennies, one player prefers matching and the other mismatching actions. There is no pure equilibrium; both players mix each action with probability ½. Under symmetric zero-sum payoffs the value is zero.
3.5. Linear Programming Form of a Zero-Sum Game
In a finite two-player zero-sum game, the row player maximizes the minimum guaranteed expected payoff. Mixed-strategy probabilities are nonnegative and sum to one. Every column strategy imposes a lower bound on expected payoff, and the opponent's optimization forms the dual linear program. Minimax equality gives a common game value, but this construction must not be generalized uncritically to arbitrary general-sum games.
max v; Aᵀp ≥ v·1; ∑ᵢpᵢ=1; pᵢ≥03.6. Saddle Points and Mixed Equilibria
A pure saddle point exists when maximin equals minimax over pure actions. Otherwise, mixed-strategy probabilities may be needed. In two-action examples, mixture probabilities follow from indifference equations over the opponent's support. Every candidate must satisfy probability bounds and must be checked against profitable deviations to unused opponent actions.
3.7. Complexity and Numerical Sensitivity
Linear programming for zero-sum games differs fundamentally from general-sum Nash computation. Enumerating every strategy in a large implicit game may be prohibitive, motivating best-response oracle methods. Small payoff perturbations can change equilibrium supports, so approximate solutions require residual checks against expected-payoff improvement.
3.8. Computational Example and Calculation
For matching pennies, take the row payoff matrix [[1,−1],[−1,1]]. Uniform mixing by both players leaves each opponent indifferent, producing value zero.
p=(½,½); q=(½,½); value=03.9. Independent Verification and Implementation Constraints
Verify expected guaranteed payoffs against each pure opponent action and compare primal and dual optimum values.
Unit 4: Nash Equilibrium and Mixed Strategies
4.1. Unilateral Deviations and Equilibrium
A Nash equilibrium is a profile from which no player can profit through unilateral deviation. Pure equilibria need not exist, whereas finite games have a mixed-strategy equilibrium. Every action assigned positive probability in a mixed equilibrium must yield the same maximum expected payoff.
4.2. Computing Mixed-Strategy Supports
For small bimatrix games, support enumeration generates candidate equilibria. Actions outside the support must then be checked for profitable deviations. Approximate equilibria are characterized by a maximum deviation gain, not merely by equal displayed payoffs.
uᵢ(sᵢ*, s₋ᵢ*) ≥ uᵢ(sᵢ, s₋ᵢ*) ∀i, sᵢ ∈ Sᵢ4.3. Approximate Equilibrium and Deviation Gain
Because multiple equilibria may exist, returning one does not enumerate the whole equilibrium set. A consistent tolerance is required when interpreting probabilities close to zero.
4.4. Numerical and Algorithmic Example
In a two-action game, solve for mixture p by equalizing the opponent’s expected payoffs from actions within its proposed support. If p∉[0,1], that support is invalid and boundary strategies must be examined.
4.4.1. Illustrative Pseudocode
for support_1 in nonempty_subsets(Actions1):
for support_2 in nonempty_subsets(Actions2):
candidate = solve_indifference_equations(support_1, support_2)
if valid_probabilities(candidate) and no_profitable_deviation(candidate):
report_equilibrium(candidate)4.5. Support Enumeration for Equilibrium
Every action played with positive probability in a mixed Nash equilibrium must give the same expected payoff. Unused actions cannot have a higher payoff. Support enumeration chooses candidate positive-action sets, solves the corresponding indifference equations and checks all deviation inequalities. The number of supports grows exponentially with available actions, limiting scalability.
uᵢ(a,s₋ᵢ*) = vᵢ (a ∈ supp(sᵢ*)); uᵢ(b,s₋ᵢ*) ≤ vᵢ4.6. Approximation Error and Deviation Gain
Distance from equilibrium can be measured by the largest payoff improvement available through unilateral deviation. A small maximal ε-regret characterizes an ε-Nash equilibrium. Payoff scales should be normalized before comparing epsilon across games. Statistical uncertainty must also be reported when expected payoffs are estimated from finite samples.
4.7. Equilibrium Selection with Multiple Solutions
Nash equilibrium need not uniquely determine an outcome. Several equilibria can differ in efficiency, fairness and robustness. The first equilibrium returned by an algorithm is not automatically a social optimum. Equilibrium selection criteria, deviation residuals and aggregate objectives should be reported separately.
4.8. Computational Example and Calculation
In the coordination game with payoff 2 for matching actions and 0 otherwise, two pure equilibria coexist with a mixed equilibrium where both players choose A and B with probability one half.
P(A)=P(B)=½; E[u(A)]=E[u(B)]=14.9. Independent Verification and Implementation Constraints
Verification checks equality of expected support payoffs and absence of unused better actions.
Unit 5: Equilibrium Algorithms and Computational Complexity
5.1. PPAD and the Complexity of Equilibrium
Equilibrium computation in general-sum bimatrix games differs from the zero-sum case. Lemke–Howson traces complementary pivots on labeled polytopes and does not guarantee polynomial-time execution for all games. The general equilibrium problem is associated with PPAD complexity.
5.2. Lemke–Howson and Graphical Games
Large games may be represented by graphical or factored payoffs instead of explicit payoff tables. Without structural assumptions, compact representation does not remove worst-case computational difficulty. Approximate solutions require explicit deviation-regret reports.
ε(s) = max[i] max[a∈Sᵢ] [uᵢ(a, s₋ᵢ) − uᵢ(s)]5.3. Approximation Error and Numerical Degeneracy
Test algorithms under different starting labels and degeneracy conditions. Reaching a computational budget limit does not prove that an equilibrium is absent.
5.4. Numerical and Algorithmic Example
Lemke–Howson seeks an equilibrium of a bimatrix game by tracing complementary labels. Different missing-label choices can return distinct equilibria. Verify each result independently through normalized probabilities and deviation incentives.
5.5. PPAD and Computational Limits of Equilibrium
Existence of a mixed Nash equilibrium in a finite general-sum two-player game does not imply a general polynomial-time algorithm for computing one. Exact equilibrium computation is associated with PPAD-completeness results. Special game families may nevertheless admit efficient algorithms. Worst-case complexity, observed runtime and approximation quality are distinct evaluation dimensions.
ε(s) = maxᵢ maxₐ [uᵢ(a,s₋ᵢ) − uᵢ(s)]5.6. Lemke–Howson and Labeled Polytopes
Nash equilibria in bimatrix games can be represented by complementarity labels on two polytopes. Lemke–Howson traverses adjacent vertices after dropping an initial label. The algorithm depends on starting labels and degeneracy handling; it neither enumerates every equilibrium nor guarantees polynomial time. Small instances can be cross-checked using support enumeration.
5.7. Error Budgets for Approximate Solvers
Numerical linear algebra tolerances, finite iterations and sampling error can all contribute to equilibrium residuals. When payoffs are estimated, the error in deviation gains must be bounded before treating a reported ε as reliable. Outputs should include strategy probabilities, expected utilities, best deviations by player and maximal ε. Failure to compute a profile differs from failure to meet a target approximation threshold.
5.8. Computational Example and Calculation
If the two players have maximal unilateral improvement opportunities of 0.03 and 0.05, the profile is an ε-Nash equilibrium for ε=0.05. Its interpretation requires the payoff scale.
ε = max(0.03,0.05)=0.055.9. Independent Verification and Implementation Constraints
Small changes in successive strategy probabilities are not sufficient evidence; actual deviation gains need evaluation.
Unit 6: Sequential Games and Subgame-Perfect Equilibrium
6.1. Game Trees and Information Sets
Sequential games are represented by extensive-form trees with decision nodes, actions, information sets, and terminal payoffs. Information sets describe which nodes an agent cannot distinguish. Backward induction computes subgame-perfect equilibria in finite perfect-information games.
6.2. Backward Induction and Sequence Form
Explicit normal-form conversion is often impractical for large game trees because pure-strategy counts can grow exponentially in decision points. The sequence form uses realization plans and flow constraints for compact representation in certain two-player games.
a*(v) ∈ arg max[a∈A(v)] u[player(v)](a | v)6.3. Validation of Proper Subgames
Validate ties and the precise definition of proper subgames, especially where information sets intervene. Misrepresenting observations may produce a spurious equilibrium.
6.4. Numerical and Algorithmic Example
In a sequential game tree, work backward from terminal decisions and choose the branch maximizing the acting player’s payoff. Collapsing all agents’ objectives to one score can distort the game. Subgame perfection requires rational continuation in every proper subgame.
6.5. Game Trees and Information Sets
In extensive-form games, nodes represent decision points, edges actions and terminal nodes payoffs. Decision nodes a player cannot distinguish belong to information sets, and a strategy specifies behavior at each information set. Backward induction that falsely assumes every node is observed can fail under imperfect information. Information sets must preserve player identity and available-action consistency.
V(h) = maxₐ V(h·a) (tek oyunculu karar düğümü)6.6. Backward Induction and Subgames
Backward induction in finite perfect-information games computes optimal actions from terminal decisions toward the root. Subgame-perfect Nash equilibrium must be an equilibrium in every proper subgame, excluding noncredible threats. A subtree crossing an information set is not an independent subgame. Runtime depends on explicit tree size, so long-horizon games often need compressed state representations.
6.7. Strategy Representation and Memory
A behavioral strategy assigns a distribution over actions at each information set; a mixed strategy distributes probability over complete pure strategies. Their equivalence depends on conditions such as perfect recall. Implementations need collision-free information-set keys, consistently ordered payoff vectors and deterministic traversal for reproducible testing.
6.8. Computational Example and Calculation
The first player chooses entry or staying out; the second responds after entry. If a threatened response would harm the second player relative to its alternative, backward induction eliminates the noncredible threat.
SPNE: optimal action at every proper subgame6.9. Independent Verification and Implementation Constraints
Proper subgames require correctly represented node ownership and information sets.
Unit 7: Bayesian Games and Incomplete Information
7.1. Type Spaces and Beliefs
Bayesian games incorporate privately known types and prior beliefs about those types. A strategy maps each possible type to an action. In a Bayes–Nash equilibrium, no type of any player can gain by unilaterally changing its action under the specified beliefs.
7.2. Conditional Expected Utility
Expected utilities weight opponents’ types by the relevant conditional probabilities. Type independence cannot be assumed without specifying it. Estimated beliefs may be biased by missing or nonrepresentative observations.
E[uᵢ | tᵢ,aᵢ] = ∑[t₋ᵢ] P(t₋ᵢ | tᵢ)uᵢ(aᵢ, s₋ᵢ(t₋ᵢ), t)7.3. Sensitivity to Prior Distributions
Sensitivity tests compare strategies and potential equilibrium changes across alternative priors. Model assumptions about information must not be equated with directly observed player behavior.
7.4. Numerical and Algorithmic Example
Suppose one agent believes an opponent has type t₁ with probability .7 and t₂ with .3. Action values use 0.7u(a,t₁)+0.3u(a,t₂). Where types are correlated, these probabilities must be conditioned appropriately.
7.5. Types, Priors and Payoff Functions
In a Bayesian game, a player's type describes preferences or private information not directly observed by opponents. The Harsanyi transformation models an initial chance move selecting types under a common prior. Common-prior assumptions are not universally valid and must be stated. Confusing type, observation and action spaces leads to incorrectly conditioned posterior beliefs.
P(t₋ᵢ | tᵢ) = P(t₋ᵢ,tᵢ) / P(tᵢ)7.6. Bayes–Nash Equilibrium
A strategy maps each type to an action or action distribution. In Bayes–Nash equilibrium, each type with positive prior probability maximizes expected utility given its information and other players' strategies. Checking only the overall expected payoff is insufficient: unilateral deviations must be evaluated type by type. Conditional beliefs for zero-probability types require special handling.
7.7. Scenario Count in Bayesian Computation
As type spaces increase, their Cartesian product rapidly becomes large. Factored probability models or sampling can replace full enumeration, but sampled expected utilities require uncertainty intervals. Estimating type distributions from data is a statistical problem separate from equilibrium computation. Leakage or misspecified priors can produce misleadingly precise strategic predictions.
7.8. Computational Example and Calculation
Let private types t₁ and t₂ occur with probabilities 0.7 and 0.3. If action a pays 4 and −2 respectively, expected payoff is 2.2. An alternative action must be evaluated under the same information structure.
E[u(a)] = 0.7·4 + 0.3·(−2) = 2.27.9. Independent Verification and Implementation Constraints
Prior expectations and posterior-conditioned expectations must not be interchanged.
Unit 8: Regret Minimization and Strategy Learning
8.1. External and Internal Regret
Online strategic decisions select actions sequentially and may observe losses afterwards. External regret is cumulative excess loss relative to the best fixed action in hindsight. Low external regret does not imply that every iterate is a Nash equilibrium.
8.2. Multiplicative-Weight Algorithms
Multiplicative-weight and probability-update methods attain sublinear regret under bounded-loss assumptions. When all players have vanishing external regret, the empirical joint distribution approaches coarse correlated equilibrium; correlated equilibrium requires the stronger internal/swap-regret guarantees.
R(T) = ∑[t=1..T] ℓₜ(aₜ) − min[a] ∑[t=1..T] ℓₜ(a)8.3. Cumulative Loss and Convergence
Experiments report cumulative loss, comparator loss, and normalized regret separately. Adaptive opponents must not be silently modeled as a fixed environment.
8.4. Numerical and Algorithmic Example
If the best fixed action incurs total loss 20 and the online strategy incurs 24, external regret equals four. Over 100 rounds, average regret equals .04. This does not show that every intermediate strategy profile is a Nash equilibrium.
8.4.1. Illustrative Pseudocode
weights = uniform_distribution(actions)
for round in horizon:
action = sample(weights)
observe_loss_vector_when_available()
weights = normalize(weights * exp(-eta * losses))
report_cumulative_regret()8.5. External Regret and Online Learning
External regret compares the learner's realized sequence of decisions with the best fixed action in hindsight. Sublinear cumulative regret implies vanishing average regret. It does not imply that the strategy used at every single iteration is close to Nash equilibrium. The loss convention and learning-rate schedule must be specified.
Rₜ = ∑ₜ ℓₜ(aₜ) − minₐ ∑ₜ ℓₜ(a)8.6. Weighted Majority and Exponential Weights
Hedge exponentially reweights actions based on observed losses. Full-information feedback reveals every action's loss, while bandit feedback reveals only the chosen action's loss. Bandit learning requires importance-weighted estimates or explicit exploration; applying a full-information update to missing losses is incorrect. An overly large learning rate can make the policy unstable.
8.7. Regret and Correlated Equilibrium
Time-averaged play can approach correlated-equilibrium families under appropriate regret guarantees. Vanishing external regret supports coarse correlated equilibrium, whereas stronger internal or swap-regret guarantees support correlated equilibrium. Neither should be conflated with Nash equilibrium. Experiments must distinguish the empirical joint-play distribution from a single-round strategy profile.
8.8. Computational Example and Calculation
Across 100 rounds, suppose the learner incurs loss 70 and the best fixed action in hindsight incurs 60. Total external regret is 10 and mean per-round regret 0.1.
R₁₀₀=70−60=10; R₁₀₀/100=0.18.9. Independent Verification and Implementation Constraints
This metric does not certify Nash equilibrium on any single round. Record random repetitions and the feedback model.
Unit 9: Graphical and Potential Games
9.1. Local Interaction and Graphical Representation
Graphical games permit a player’s payoff to depend only on neighboring strategies. The dependency graph reduces representation size, although graph density and treewidth affect computation. Potential games admit a scalar potential function that tracks unilateral payoff changes.
9.2. Best Responses via Potential Functions
In finite exact-potential games, strict unilateral improvement terminates at a pure equilibrium; general-sum games need not share this property. Tree-structured graphical games may permit dynamic-programming algorithms under suitable restrictions.
Φ(aᵢ, s₋ᵢ) − Φ(s) = uᵢ(aᵢ, s₋ᵢ) − uᵢ(s)9.3. Finite Improvement Property
Validate local payoff dependencies and potential changes on sample deviations. Asynchronous and simultaneous updates do not necessarily enjoy the same convergence guarantees.
9.4. Numerical and Algorithmic Example
If each unilateral rerouting changes a scalar network-cost potential by exactly the acting user’s cost change, the game is an exact potential game. In a finite such game, asynchronous strict improvement steps terminate.
9.5. Potential Functions and Finite Improvement
In an exact potential game, the payoff change caused by a unilateral deviation equals the change in a scalar potential function. In finite strategy spaces, strict-improvement dynamics change the potential monotonically and must terminate. The required number of steps can nonetheless be exponential. Approximate potential games should not be confused with exact potential games.
Φ(aᵢ,s₋ᵢ) − Φ(s) = uᵢ(aᵢ,s₋ᵢ) − uᵢ(s)9.6. Local Dependencies in Graphical Games
In graphical games, each player's payoff depends on actions of its graph neighbors. Local factors may avoid storing the full joint-action payoff table. Local structure alone, however, does not guarantee easy Nash computation. Graph treewidth and action-set sizes influence the cost of message passing and dynamic programming.
9.7. Asynchronous Best-Response Updates
Sequential best-response updates and simultaneous player updates can generate different load-balancing dynamics. Potential-function guarantees typically rely on unilateral improvement, which simultaneous changes need not preserve. Experiments should fix update schedules, tie-breaking and stopping criteria. A simulated final profile still requires an independent deviation test.
9.8. Computational Example and Calculation
Three users choose between two identical resources, each charging cost equal to its occupancy. At distribution (2,1), moving a user from the crowded side yields (1,2) with the moving player cost still 2, so there is no strict improvement.
load=(2,1); moving cost: 2→29.9. Independent Verification and Implementation Constraints
If updates require strict improvements, indifference moves should not be inadvertently treated as improvements.
Unit 10: Network Games and Price of Anarchy
10.1. Congestion Costs and Social Objectives
Congestion games assign a resource cost based on the number of users or aggregate load. Individually optimal actions need not minimize total system latency. Price of anarchy compares equilibrium social cost to the optimal achievable social cost.
10.2. Wardrop Equilibrium and Network Flows
In routing, Wardrop equilibrium states that used paths offer no individually cheaper available route. Atomicity and the shape of latency functions change price-of-anarchy bounds.
PoA = max[s∈NE] C(s) / min[s∈ℱ] C(s)10.3. Price-of-Anarchy Measure
Total routing cost aggregates edge flow multiplied by edge latency. Compute system optimum and selfish equilibrium independently on the same instance; their cost ratio is at least one when the denominator is positive.
10.4. Numerical and Algorithmic Example
For parallel links with latency ℓ₁(x)=x and ℓ₂(x)=1 under unit flow, selfish equilibrium can differ from the assignment minimizing xℓ₁(x)+(1−x)ℓ₂(1−x). Compute both solutions before reporting price of anarchy.
10.5. Latency Models in Congestion Games
In congestion games, resource latency depends on the number of users or continuous flow volume. Players minimize their own route delay, which need not minimize total network delay. Assumptions such as nondecreasing resource latency are essential for particular existence and efficiency results. Path-based player strategies must be consistent with edge-based cost evaluation.
C(f) = ∑ₑ fₑℓₑ(fₑ)10.6. Price of Anarchy and Worst-Case Equilibrium
Price of anarchy compares the worst equilibrium's social cost with the centralized optimum for the stated game family. For cost minimization, the ratio is typically at least one; degenerate zero-optimum cases need special definitions. The price of stability instead considers the best equilibrium. Bounds proved for affine latency functions must not be generalized to arbitrary latency models.
10.7. Wardrop Equilibrium and Nonatomic Flow
In atomic games individual players select routes; nonatomic flow assumes any single user's effect is negligible. At Wardrop equilibrium, all used routes have minimum available path cost. A potential optimization formulation can compute equilibria for suitable separable latency models. Equilibrium and system-optimal first-order conditions differ because users do not internalize congestion externalities.
10.8. Computational Example and Calculation
In Pigou routing, one link has latency x and another latency 1, with demand 1. Wardrop equilibrium can route all flow onto the variable-delay link, giving cost 1; system optimum sends x=½ there for cost ¾.
PoA = 1/(¾) = 4/310.9. Independent Verification and Implementation Constraints
Price-of-anarchy calculations must compare equilibrium and optimum under identical demand and feasible routes.
Unit 11: Mechanism Design and Auction Algorithms
11.1. Incentive Compatibility and Allocation Rules
Mechanism design selects allocation and payment rules while accounting for privately known information and incentives. Incentive compatibility requires truthful reporting to be a best response under the stated strategic model.
11.2. VCG and Computational Auctions
In single-parameter environments, monotone allocation rules and appropriate payments are central. VCG can achieve efficiency and truthfulness under quasilinear utility and transfer assumptions, but neither computational tractability nor budget balance follows automatically.
uᵢ = vᵢ(x) − pᵢ; x ∈ arg max[x∈ℱ] ∑[j] v̂ⱼ(x)11.3. Auditing Truthful Reporting
Verify allocation feasibility for every tested bid profile. Check truthfulness by comparing deviation utilities; document payment signs and transfer direction explicitly.
11.4. Numerical and Algorithmic Example
When allocating one resource to one of two bidders, a payment rule may depend on the competing value rather than the winner’s bid. Allocation and payment must be defined together; awarding to the largest bid alone does not prove truthfulness.
11.5. Direct Revelation and Incentive Compatibility
Mechanism design studies rules mapping private value reports to allocations and payments. Dominant-strategy truthfulness means no player benefits from misreporting regardless of others' reports. This condition is distinct from social-welfare maximization. Allocation, payment and outside-option utilities must be modeled together.
uᵢ(vᵢ; bᵢ,b₋ᵢ) ≥ uᵢ(vᵢ; b′ᵢ,b₋ᵢ)11.6. VCG Payments and Externalities
Vickrey–Clarke–Groves mechanisms maximize reported aggregate value, with payments based on each agent's externality on others. Truthful revelation is a dominant strategy under the relevant assumptions. VCG does not automatically guarantee budget balance, collusion resistance or computational tractability. Allocating distributed resources may require additional optimization runs to compute payments.
11.7. Monotonicity in Single-Parameter Auctions
In single-parameter allocation, monotonicity means increasing a bid does not reduce the agent's allocation. Suitable threshold payments can then implement incentive compatibility. This characterization does not extend directly to unrestricted multidimensional mechanisms. Simulations should vary each reported bid to test allocation monotonicity and utility incentives independently.
11.8. Computational Example and Calculation
In a single-item second-price auction with bids 9, 6 and 4, the top bidder receives the item and pays the second-highest bid of 6. If the winner values the item at 9, its utility is 3.
payment=6; utility=9−6=311.9. Independent Verification and Implementation Constraints
Truthfulness claims depend on the single-parameter private-value assumptions and auction payment rules.
Unit 12: Multi-Agent Decision Algorithms and Equilibrium Verification
12.1. Stochastic Games and Shared States
Multi-agent systems consist of software agents sharing resources or affecting one another through their actions. Running a single-agent MDP solver for each participant does not eliminate strategic interactions. Joint state, simultaneous actions, and transition distributions must be specified.
12.2. Multi-Agent Learning Architectures
Stochastic games separate each agent’s reward from the shared state-transition model. Learning agents can invalidate stationarity when they adapt policies simultaneously. Centralized training and decentralized execution must be distinguished when analyzing coordination.
Qᵢ⁽π⁾(s,a) = rᵢ(s,a) + γ∑[s′] P(s′ | s,a)Vᵢ⁽π⁾(s′)12.3. Policy Evaluation and Equilibrium Error
Estimated deviation gains should be accompanied by uncertainty intervals. Improved training reward is not a proof of Nash equilibrium or Pareto optimality.
12.4. Numerical and Algorithmic Example
When two learning agents update simultaneously, each changes the other’s environment. Single-agent convergence proofs need not apply. Approximate unilateral-deviation gain is measured to assess policy stability.
12.5. States and Joint Actions in Stochastic Games
A stochastic game includes multiple agents whose joint actions affect transition probabilities. Players may have different reward functions. Single-agent Bellman optimality does not replace multi-agent Nash conditions. State-space size combined with Cartesian joint-action spaces drives computational complexity.
Qᵢ(s,a) = rᵢ(s,a) + γ∑ₛ′P(s′|s,a)Vᵢ(s′)12.6. Nonstationarity in Multi-Agent Learning
When independently learning agents update policies in the same environment, each agent experiences a changing effective transition distribution. Assumptions used by stationary single-agent algorithms may fail. Centralized training with decentralized execution uses richer information during training while deploying local observations. Strong training returns do not establish a stable strategy or Nash-equilibrium guarantee without additional analysis.
12.7. Strategic Robustness Under Opponent Changes
Success against one opponent policy does not imply robustness against alternatives. Evaluation may use a fixed opponent pool, out-of-distribution strategies, exploitability through best responses, and multiple random seeds. Mean return, worst-case utility and unilateral deviation gains should be reported separately. Observation delays in simulation must also match the modeled simultaneous or sequential action protocol.
12.8. Computational Example and Calculation
In a two-state stochastic game, the joint action determines both immediate payoff and transition probabilities. An action optimized against one fixed opponent policy can change value when the opponent adapts.
Vᵢ(s) = E[∑ₜ≥0 γᵗrᵢ,t | s]12.9. Independent Verification and Implementation Constraints
Record opponent policy versions, discount factor and state-transition sample sizes.
References
- Nisan, Noam; Roughgarden, Tim; Tardos, Éva; Vazirani, Vijay V. (eds.). Algorithmic Game Theory. Cambridge University Press, 2007. ISBN 9780521872829.
