Game Theory
Strategic interaction between rational agents — equilibria, mechanism design, and algorithmic aspects.
Nash equilibria, mechanism design, auctions, and the algorithmic and computational side of strategic interaction.
Notes
- Basic Solution Concepts and the Complexity of Nash Equilibria
- Cascading Behavior in Networks: Algorithmic and Economic Issues Stub. Networked coordination games as a model of social contagion, more general contagion models, finding influential sets of nodes (influence maximization), and empirical studies of online cascades. (AGT ch. 24)
- Combinatorial Auctions and Approximation Mechanisms Stub. Combinatorial auction design (single-minded bidders, Walrasian equilibrium, bidding languages, iterative/ascending auctions, communication complexity) and computationally efficient approximation mechanisms for single- and multi-dimensional domains. (AGT ch. 11-12)
- Computational Evolutionary Game Theory Stub. Evolutionarily stable strategies and the complexity of computing them, evolutionary dynamics applied to selfish routing, and evolutionary game theory played over graphs. (AGT ch. 29)
- Computing Market Equilibria Stub. Combinatorial primal-dual algorithms and convex-programming approaches to Fisher and Arrow-Debreu market equilibria; the Eisenberg-Gale program, tight sets, balanced flows, WGS exchange economies. (AGT ch. 5-6)
- Cost Sharing Stub. Cooperative cost-sharing games, the core, group-strategyproof cross-monotonic cost-sharing schemes, the primal-dual schema for constructing them, their limitations, and the Shapley value / Nash bargaining solution. (AGT ch. 15)
- Cryptography and Game Theory Stub. 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)
- Distributed Algorithmic Mechanism Design Stub. Mechanism design where the mechanism itself must run as a distributed algorithm over a network with strategic nodes, with interdomain (BGP) routing as the driving example. (AGT ch. 14)
- Graphical Games Stub. 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)
- Incentives and Information Security Stub. Misaligned incentives as a root cause of security failures, informational asymmetries (lemons markets for security), the economics of censorship resistance, and how network topology shapes security economics. (AGT ch. 25)
- Incentives in Peer-to-Peer Systems Stub. The p2p file-sharing game and free-riding, reputation, barter-based systems like BitTorrent's tit-for-tat, currency-based systems, and hidden actions (moral hazard) in p2p systems. (AGT ch. 23)
- Incentives and Pricing in Communication Networks Stub. Competitive (large-network) models and game-theoretic pricing/resource-allocation models for communication networks, plus alternative pricing and incentive schemes. (AGT ch. 22)
- Introduction to the Inefficiency of Equilibria Stub. Opens Part III: the price-of-anarchy framework for quantifying how much selfish behavior degrades social welfare, with the canonical network examples (Pigou, Braess) and inefficiency as a mechanism-design metric. (AGT ch. 17)
- Introduction to Mechanism Design Stub. Social choice functions, mechanisms with and without money, dominant-strategy implementation, revelation principle, Gibbard-Satterthwaite and Myerson-Satterthwaite-style characterizations, Bayesian-Nash implementation. (AGT ch. 9)
- Learning, Regret Minimization, and Equilibria External, 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
- Mechanism Design without Money Stub. Strategyproof mechanisms when transfers aren't allowed: single-peaked preferences over policies, the house allocation problem, and stable matching. (AGT ch. 10)
- Network Formation Games and the Potential Function Method Stub. Games where players build a network rather than route on a fixed one: local connection games, global connection games as potential games, and facility location, all analyzed via potential functions. (AGT ch. 19)
- Online Mechanisms Stub. Mechanism design in dynamic environments where agents and information arrive over time: single-valued online domains and Bayesian implementation online. (AGT ch. 16)
- Computational Aspects of Prediction Markets Stub. What prediction markets are, combinatorial prediction markets, automated market makers, and using markets as a distributed computation device. (AGT ch. 26)
- The Price of Anarchy and the Design of Scalable Resource Allocation Mechanisms Stub. Designing simple, scalable (no full-VCG) resource-allocation mechanisms with bounded price of anarchy, via the proportional allocation mechanism and a characterization theorem, contrasted with the VCG approach. (AGT ch. 21)
- Profit Maximization in Mechanism Design Stub. Revenue/profit-maximizing mechanism design: Bayesian optimal auctions (Myerson), prior-free approximation and optimal mechanisms, and frugality of procurement mechanisms. (AGT ch. 13)
- Manipulation-Resistant Reputation Systems Stub. Why reputation systems matter, effects of reputations on behavior, whitewashing (identity-reset attacks), eliciting effort and honest feedback, and reputation based on transitive trust. (AGT ch. 27)
- Routing Games Stub. Selfish routing models, existence/uniqueness of equilibrium flows via potential functions, the price of anarchy of selfish routing (including for nonlinear latencies), and mechanisms for reducing it (e.g. tolls, Braess-edge removal). (AGT ch. 18)
- Selfish Load Balancing Stub. Price of anarchy for scheduling jobs on selfish machines: pure and mixed equilibria on identical and uniformly related machines. (AGT ch. 20)
- Sponsored Search Auctions Stub. Existing sponsored-search mechanisms (GSP vs. VCG), a static equilibrium model of ad-slot auctions, and dynamic aspects (budgets, repeated play). (AGT ch. 28)
- Algorithmic game theory My annotations of the book "Algorithmic game theory"