Mathematics
Core mathematics underpinning computer science and research work.
Mathematical foundations — algebra, analysis, probability, and beyond. Browse the subtopics below.
Subtopics
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)
- Maximum Entropy The maximum entropy distribution under moment constraints, worked examples, the anomalous ε-achievable case, spectrum estimation, and Burg's maximum entropy theorem
- Information Theory and Statistics The method of types, universal source coding, Sanov's theorem and large deviations, the conditional limit theorem, hypothesis testing, Chernoff–Stein and Chernoff information, and Fisher information
- Rate Distortion Theory Lossy compression — quantization, the rate distortion function for binary and Gaussian sources, reverse water-filling, the converse and achievability proofs, and the Blahut–Arimoto algorithm
- The Gaussian Channel Capacity of the additive white Gaussian noise channel, sphere packing, bandlimited channels and the Shannon–Hartley formula, water-filling over parallel and colored channels, and how little feedback buys
- Differential Entropy Entropy of continuous random variables, the continuous AEP and volume of the typical set, the quantization relation, the Gaussian as maximum-entropy distribution, and the estimation counterpart to Fano
- Channel Capacity The information capacity of a discrete memoryless channel, worked examples, jointly typical sequences, Shannon's second theorem and its converse, Hamming codes, feedback, and source–channel separation
- Entropy Rates of a Stochastic Process Stationarity, Markov chains, the entropy rate and its two definitions, random walks on graphs, the second law, and functions of Markov chains
- The Asymptotic Equipartition Property The information-theoretic law of large numbers, the typical set, the source code it yields, and its optimality among high-probability sets
- Information Theory Inequalities Jensen's Inequality, Log Sum Inequality, Data Processing Inequality and Sufficient Statistics, and Fano's Inequality
- Elements of Information Theory My annotations of the book "Elements of Information Theory" (Cover & Thomas).
- Data Compression and Source Coding Kraft inequality, Huffman codes, and Shannon-Fano-Elias coding bounds.
- Information, Entropy, Relative Entropy, and Mutual Information Fundamental definitions, Relationships between them, and Chain rules
- Kolmogorov Complexity Incompressible sequences, Occam's Razor, and the Minimum Description Length principle.
- Network Information Theory Multiple-access channels, Slepian-Wolf encoding, and broadcast/relay channels.
- Information Theory in Gambling and Portfolios Side information, log-optimal portfolios, Kelly criterion, and universal portfolios.
- Universal Source Coding Arithmetic coding, Lempel-Ziv algorithms, and optimality proofs.
- Algorithmic game theory My annotations of the book "Algorithmic game theory"
- Optimization for data analysis My annotations of the book "Optimization for data analysis"