~vaibhav

Algorithmic game theory

My annotations of the book "Algorithmic game theory"

· 1 min read · 0 words
Open document ↗

Reading order

  1. 1Basic Solution Concepts and the Complexity of Nash Equilibria
  2. 2Learning, Regret Minimization, and EquilibriaExternal, internal and swap regret; greedy, randomized greedy, RWM and Polynomial Weights; the minimax theorem from regret; convergence to correlated equilibrium; the external-to-swap reduction; the bandit reduction; and Wardrop routing
  3. 3Computing Market EquilibriaFisher and Arrow–Debreu models; the Eisenberg–Gale program; tight sets, balanced flows and the primal-dual algorithm; auction-based Arrow–Debreu; Kelly's resource allocation markets; convex programs for WGS, linear and CES economies; production; and PPAD-hardness for Leontief
  4. 4Graphical GamesStub. Representing games compactly via an interaction graph; computing Nash equilibria on tree graphical games; connections to correlated equilibria and graphical exchange economies. (AGT ch. 7)
  5. 5Cryptography and Game TheoryStub. Contrasting secure multiparty computation with game-theoretic solution concepts, and the two-way influence between crypto and game theory (rational secret sharing, etc.). (AGT ch. 8)
  6. 6Introduction to Mechanism DesignSocial choice, Arrow and Gibbard–Satterthwaite; VCG and the Clarke pivot rule; the revelation principle; weak monotonicity, Roberts' theorem and single-parameter domains; Bayesian–Nash and revenue equivalence; and design without money — single-peaked preferences, house allocation, stable matching
  7. 7Combinatorial Auctions and Approximation MechanismsSingle-minded bidders and the greedy mechanism; Walrasian equilibrium and the LP relaxation; bidding languages and OR* bids; demand queries; communication lower bounds; ascending auctions; monotone scheduling; the decomposition technique; Roberts-style impossibilities; and algorithmic implementation
  8. 8Profit Maximization in Mechanism DesignMyerson's optimal auction and virtual valuations; regularity and ironing; prior-free competitive analysis against F(2); random sampling and RSOP; the decision problem and consensus estimates; digital goods and multicast pricing; and frugality with the ν bound
  9. 9Distributed Algorithmic Mechanism DesignWhy DAMD differs from AMD (computational manipulation, network complexity); distributed VCG via replication and ex-post Nash equilibrium; multicast cost sharing with the marginal-cost (MC) and Shapley-value (SH) mechanisms; the Omega(|P|) lower bound for SH and the two-pass tree algorithm for MC; interdomain routing, BGP and path-vector protocols; BGP oscillation, dispute wheels and robust convergence; distributed mechanisms, ex-post Nash and collusion-proof ex-post Nash; Gao–Rexford constraints; policy consistency; Lemma 14.8 (local optimality) and Theorem 14.7 (BGP is welfare-maximizing and incentive-compatible without payments)
  10. 10Cost SharingTU and NTU cooperative games; the facility location game; the core, Bondareva–Shapley theorem via LP duality, the gamma-approximate core and its equality with the integrality gap (Corollary 15.9); the facility location dual LP as the core LP (Proposition 15.10); Scarf's theorem for NTU cores; NPT/VP/CS and group-strategyproof cost-sharing mechanisms; cross-monotonic cost-sharing schemes and Moulin's mechanism (Theorem 15.16); primal-dual cost shares for submodular games (Dutta–Ray, Theorem 15.20); ghost duals and the 1/3-budget-balanced FLCostShare (Pál–Tardos, Theorem 15.21); the probabilistic-method upper bound of 1/3 for facility location (Theorem 15.23); the Shapley value and its axiomatization; the Nash bargaining solution and collective utility functions
  11. 11Online MechanismsOnline mechanism design with arrivals, departures and uncertain supply; direct-revelation online mechanisms, limited misreports (no early arrival, no late departure), DSIC, strong truthfulness and BNIC; failure of the revelation principle and the heartbeat fix; single-valued domains, critical value, monotonic and monotonic-late policies (Theorems 16.13, 16.15, Lemma 16.14); the greedy expiring-items auction, 2-competitive and tight (Theorems 16.17–16.19); the secretary problem and an adaptive limited-supply auction, e- and e^2-competitive (Theorems 16.21, 16.23); ex-post IC vs DSIC with feedback; price-schedule auctions; stochastic monotonicity (Theorem 16.25); MDPs and the dynamic VCG mechanism, BNIC under stalling (Theorem 16.28)
  12. 12The Inefficiency Of EquilibriaPareto inefficiency vs quantitative inefficiency; utilitarian and egalitarian objectives; the five modeling choices behind any inefficiency measure; price of anarchy and price of stability; Pigou's example (PoA 4/3); Shapley network design games, the PoA-k example and the H_k price-of- stability example; load-balancing games, mixed equilibria and balls into bins (Theta(log m / log log m)); expected makespan vs maximum expected load; resource allocation games, Kelly's proportional sharing mechanism and the Johari–Tsitsiklis 3/4 example; price of anarchy as a design metric and the optimality of proportional sharing among single-price mechanisms
  13. 13Routing GamesNonatomic and atomic selfish routing; equilibrium (Wardrop) flows; nonlinear Pigou example and Braess's Paradox; the AAE example (PoA 5/2) and nonexistence in weighted atomic instances; marginal cost functions and the equivalence of optimal and equilibrium flows (Corollary 18.10); the Beckmann potential and existence/essential uniqueness (Theorem 18.8); Rosenthal's potential and existence for unweighted instances (Theorem 18.12); potential-function PoA bound (p+1 for degree-p polynomials); the Pigou bound, variational inequality and its tightness (Theorem 18.21, 4/3 affine, about p/ln p polynomial); bounds on Braess's Paradox; atomic affine PoA (3+sqrt5)/2 via Cauchy–Schwarz (Theorem 18.23); marginal cost (Pigouvian) taxes; capacity augmentation, equilibrium beats optimum at double traffic (Theorem 18.29), M/M/1 capacity doubling
  14. 14Network Formation Games And The Potential Function MethodThe local connection game (Fabrikant et al.) — optimal networks (star vs clique at alpha = 2), stable networks (alpha = 1), price of stability at most 4/3, diameter-based PoA bounds O(sqrt alpha) and O(1 + alpha/sqrt n); the global connection game with Shapley (fair) cost sharing, PoA k, the harmonic potential and PoS H_k; exact potential games, existence of pure equilibria, best-response convergence, Rosenthal and Monderer–Shapley congestion-game equivalence; the potential function method (PoS at most AB); PLS-completeness of pure equilibria via weighted MAX-SAT; cost-sharing games, Prim-simulating nonoblivious scheme with PoA 2 and optimality of Shapley among oblivious schemes; Vetta's competitive facility location game, welfare as potential, utility games (submodular, basic, monotone), PoA 2, and a (1/2 - eps) guarantee after O(n) random best responses
  15. 15Selfish Load BalancingLoad balancing games on identical and uniformly related machines with makespan as (nonutilitarian) social cost; expected cost formula for mixed profiles (20.1); existence of pure equilibria via lexicographically decreasing load vectors; PoA 2 - 2/(m+1) for pure equilibria on identical machines (tight); max-weight best response converges in n steps; PoA Theta(log m / log log m) for pure equilibria on related machines via the inverse gamma function and the layered lower-bound construction; LPT computes a pure equilibrium, PTAS plus Nashification; fully mixed equilibria and balls into bins (Proposition 20.11); the fully mixed Nash equilibrium conjecture is false; PoA Theta(log m / log log m) for mixed equilibria on identical machines via a weighted Chernoff bound; PoA Theta(log m / log log log m) for mixed equilibria on related machines
  16. 16The Price Of Anarchy And Scalable Resource Allocation MechanismsAllocating a divisible resource (link capacity C) among R users with concave utilities; the SYSTEM problem; Kelly's proportional allocation mechanism as market clearing; price-taking users and efficient competitive equilibrium (Theorem 21.1); price-anticipating users, unique Nash equilibrium as the solution of GAME with modified utilities U-hat (Theorem 21.2) and its variational inequality (Corollary 21.3); tight 3/4 price of anarchy via the constant beta (Theorem 21.4); smooth market-clearing mechanisms, the class D, every mechanism in D allocates proportionally to bids and differs only in price, proportional allocation uniquely minimizes worst-case loss (Theorem 21.10, G(Psi) and price elasticity); VCG and scalar-strategy VCG (SSVCG) with one price per user, Nash characterization (Lemma 21.11), efficient equilibrium with local truthfulness (Corollary 21.12), bluff equilibria, and full efficiency when marginal utility at zero is infinite (Proposition 21.14)
  17. 17Incentives And Pricing In Communication NetworksKelly's network utility maximization (NUM) with routing matrix and link capacities; KKT conditions and link prices as Lagrange multipliers; price-taking users; weighted proportionally fair allocation via bids; primal–dual congestion control (link price ODE, rate = bid / route price) and its Lyapunov convergence proof; myopic bid updates recover the social optimum; architectural decomposition into congestion control, congestion indication and feedback; wireless extension with schedules and max-weight scheduling (queue lengths as prices); profit-maximizing providers on parallel links with Wardrop equilibrium and reservation utility; monopoly markup equals the Pigouvian tax, so monopoly is efficient; duopoly and oligopoly equilibrium prices with an extra competitive markup; tight 5/6 efficiency bound for oligopoly (Theorem 22.3), 2/3 for elastic traffic (Theorem 22.4), 1/2 for parallel–serial networks under strict equilibria with double marginalization (Theorem 22.5); smart markets, Paris Metro Pricing, first-best tolls, flat-fee marginal-user pricing, P2P and wireless cooperation incentives
  18. 18Incentives In Peer-To-Peer SystemsFree-riding in p2p (Gnutella: two thirds free riders); the p2p file-sharing game as a Prisoner's Dilemma; direct vs indirect reciprocity and why reciprocative strategies fail to scale under random matching; treating strangers and whitewashers; reputation systems (KaZaA, EigenTrust, Credence) and collusion, Sybil and whitewashing attacks; a minimalist generosity-type model with contribution cost 1/x, fixpoint dynamics, tipping point and collapse for theta_m < 4 (Claim 23.1); reputation-based service differentiation, threat vs reduced cost, and full cooperation when p >= 1/alpha (Claim 23.2); BitTorrent barter, opportunistic unchoking and its rational manipulations; FOX and non-credible grim triggers; currency systems (Golle et al., threshold equilibria and optimal money supply); hidden actions as moral hazard, principal–agent model with AND/OR read-once technologies, marginal contribution and optimal contracts c/Delta_i, price of unaccountability, single 0-to-n transition and unbounded POU for AND (Theorem 23.8), all transitions and POU at most 5/2 for OR (Theorem 23.9), #P-hardness of optimal contracts on read-once networks (Theorem 23.10)
  19. 19Cascading Behavior In NetworksDiffusion of innovations as network contagion; networked coordination games (Morris) and the threshold rule d_B >= q d; contagion threshold, progressive vs nonprogressive dynamics and their equivalence (Theorem 24.1); no graph has contagion threshold above 1/2 via a decreasing cut-size potential (Theorem 24.2); Linear Threshold, General Threshold and Cascade models, and the translation between threshold functions g_v and incremental functions p_v; k-threshold (critical mass) vs diminishing returns vs Independent Cascade; time-layered reduction from nonprogressive to progressive; influence maximization (Domingos–Richardson), NP-hardness and n^(1-eps) inapproximability; submodularity and the Nemhauser–Wolsey–Fisher (1 - 1/e) greedy guarantee; diminishing returns implies submodular influence (Kempe–Kleinberg–Tardos, Theorem 24.4); live-edge proof for Independent Cascade (Theorem 24.5); Mossel–Roch (Theorem 24.6); recommendation incentives; LiveJournal community joining P(k), logarithmic diminishing returns, and the effect of friend connectedness
  20. 20Incentives And Information SecuritySecurity failures from misaligned incentives (UK vs US bank liability, antivirus and DDoS externalities, medical privacy); Varian's total-effort, weakest-link and best-shot security games; Kunreuther–Heal interdependent security and multiple equilibria; network effects and bootstrapping of security protocols (SSH, IPsec, DNS, routing); hidden-action attacks and the observability window; clubs and social topologies to raise observability; hidden information and Akerlof's market for lemons applied to software; vulnerability markets and software security derivatives; cyber-insurance and physically vs logically interdependent, globally correlated risk; censorship resistance, the Danezis–Anderson Red–Blue utility model, discretionary vs random (DHT) content placement, optimal defense budgets and why discretionary systems cost more to censor; scale-free robustness vs targeted attack; dynamic attack–defense simulations (vertex-order and centrality attacks vs random, ring, clique and delegation defenses) explaining why revolutionaries use cells
  21. 21Computational Aspects Of Prediction MarketsThe information aggregation problem; partition model of knowledge, common prior, omniscient forecast; market mechanisms (call market, continuous double auction, market maker, parimutuel) and empirical record (IEM, marginal traders, HP); rational expectations equilibrium, fully revealing equilibria, efficient market hypothesis and no-trade theorems; combinatorial markets over 2^|E| states, complete markets, combined vs compound orders, conditional securities S_(phi|psi), order payoff vectors and the matching problem; divisible matching polynomial (LP) for O(log n) events and co-NP-complete in general (Theorem 26.6), indivisible NP- and Sigma_2^p-complete (Theorem 26.7); Bayesian-network-structured markets and operational completeness; automated market makers, the thin-market problem, market scoring rules and the logarithmic cost function with loss b ln|Omega|, quadratic cost function, sequential shared scoring rules; dynamic parimutuel markets with the share-ratio cost function; the Boolean market model, price formation, myopic truthful Bayesian traders, common knowledge of aggregates (Theorem 26.9), XOR non-convergence, weighted threshold functions as exactly the computable aggregates (Theorems 26.12–26.13), and convergence within n rounds (Theorems 26.14–26.15)
  22. 22Manipulation-Resistant Reputation SystemsWhy reputation matters (ability revelation, moral hazard, adverse selection); the reputation-system pipeline and aggregation across users, time, and transitive trust; three threats (whitewashing, dishonest or missing feedback, phantom/sybil feedback); repeated Prisoner's Dilemma, discounted average payoff, Grim SPNE for delta >= 1/2, reputational vs personalized Grim; whitewashing, entry fees f >= 1/delta, the pay-your-dues (PYD) strategy and its social cost, noisy dynamic model and unavoidable mistrust of newcomers; peer-prediction method (Miller–Resnick– Zeckhauser) with common prior, signals, reference raters and the log scoring rule, truthful strict Nash equilibrium (Proposition 1), worked H/L example, non-truthful equilibria and extensions; transitive trust graphs, PageRank, max-flow (Advogato), Pathrank; monotonicity, symmetry, rank-strategyproofness impossibility; sybil strategies, value- vs rank-sybilproofness, no symmetric rank-sybilproof function (Theorems 27.5, 27.7), max-flow value-sybilproof but not rank-sybilproof (Theorem 27.8), Pathrank value- and rank-sybilproof (Theorem 27.9)
  23. 23Sponsored Search AuctionsSponsored search (per-click pricing, per-query continuous auctions, slots, impressions vs clicks); click-through rates alpha_ij, weights and scores, rank-by-bid vs rank-by-revenue, the generalized second price (GSP) and generalized first price (GFP) auctions; the static model and its four strong assumptions; Myerson revenue-optimal auction as VCG on virtual values; efficient allocation as a maximum-weight assignment LP with VCG prices from the minimal optimal dual; assortative (Northwest corner) assignment; why multi-slot VCG differs from GSP (worked two-slot example); ranking auctions and the truthful payment rule; GFP symmetric Bayes-Nash efficiency and bid fluctuation; locally envy-free assignments = optimal assignments (Theorem 28.1); GSP full-information equilibrium implementing VCG (Theorem 28.2); condominium auctions; bid rotation and vindictive bidding; online budgeted allocation, LP with budget shadow prices, greedy 1/2-competitive, budget smoothing with phi(x) = 1 - e^(x-1), optimal 1 - 1/e competitive ratio (Theorem 28.3, Lemma 28.4); open issues (soft budgets, pay per action, competing search engines, syndication, CTR learning)
  24. 24Computational Evolutionary Game TheoryThe classical infinite-population model, replication and imitation dynamics; evolutionarily stable strategies (ESS) and the equivalent Nash-refinement characterization (Theorem 29.2); Hawks and Doves with pure ESS H for V > C and mixed ESS V/C otherwise; the clique reduction showing ESS existence is NP-hard and coNP-hard (Theorem 29.8) and ESS recognition is coNP-hard (Theorem 29.9), with the Motzkin–Straus-style Lemma 29.3 and Lemmas 29.4–29.7; imitative/replicator dynamics for nonatomic selfish routing, x_p' = lambda x_p (l-bar - l_p); Lyapunov convergence to Nash (Wardrop) flow; epsilon-approximate equilibria and why Euclidean distance is the wrong metric; the Beckmann potential plus l* and convergence in O(eps^-3 ln(l_max/l*)) time (Theorem 29.12); ESS on graphs (contracting mutant sets, eps-linear families, Definition 29.15); classical ESS are exactly the ESS of dense Erdos–Renyi random graphs against adversarial mutants (Theorem 29.16, Lemma 29.17, Bollobas's Theorem 29.18, converse via cliques); future work on finite-population convergence times

← All notes