Economics and Computation Boot Camp 2015
2015-08-24..2015-08-27
Berkeley, United States
who it's for
algorithmic game theorists, market design researchers, mechanism designers, theoretical computer scientists, learning theorists, complexity theorists
topics
Walrasian price-adjustment dynamics; gross substitutes condition; Scarf's lemma applications; PPAD-completeness of equilibria; lambda-mu smoothness inequalities; no-regret learning in games; multiplicative weights replicator dynamics; multi-dimensional mechanism design; marginal revenue mechanisms; fictitious play stochastic approximation; complexity of Nash equilibria; interim feasibility Border inequalities
| title | author | length |
|---|---|---|
| Approximating Competitive Equilibria: A History | Kenneth J. Arrow | 47m |
A clear, historical account of how Walrasian tâtonnement is modeled as a price-adjustment differential equation, proving global convergence under two explicit… | ||
| On Algorithmic Game Theory I | Christos Papadimitriou | 52m |
A brisk history of algorithmic game theory traces pre-’95 links to TCS and Herbert Simon’s bounded rationality, then shifts to concrete complexity results… | ||
| Scarf's Lemma and Applications I | Rakesh Vohra | 01h 01m |
Scarf’s Lemma is stated as: every feasible polyhedron built from a nonnegative matrix has an dominant extreme point that “dominates every column,” and that… | ||
| Near-Optimal Equilibria I | Tim Roughgarden | 01h 14m |
Gives a concrete toolbox that proves worst-case equilibrium efficiency via a lambda–mu smoothness inequality, then uses simple algebra and edge- or bidder-wise… | ||
| On Algorithmic Game Theory II | Christos Papadimitriou | 01h 10m |
Survey of current problems: internet research concentrates on ad auctions, BGP and net neutrality, and cloud economics with no neat theoretical consensus; a… | ||
| Scarf's Lemma and Applications II | Rakesh Vohra | 55m |
Outlines a constructive use of Scarf’s lemma on an LP for doctor–hospital matching with couples: variables x_dh and x_c,hh′, non‑negative A and positive b… | ||
| Near-Optimal Equilibria II | Tim Roughgarden | 01h 11m |
Proves a smoothness inequality showing a single-item first-price auction achieves lambda=1/2 (improvable to ~0.63), uses a composition theorem so composition… | ||
| Multi-Dimensional and Non-Linear Mechanism Design and Approximation I | Jason Hartline | 01h 07m |
Claims a modular route from single-agent solutions to multi-agent auctions using a ex-ante reduction (solve best single-player mechanism for each… | ||
| Learning in Games I | Drew Fudenberg | 01h 09m |
Argues that repeated play with simple belief updates — fictitious play — is analyzed by replacing discontinuous best responses with smooth ones and applying… | ||
| Complexity and Algorithmic Game Theory I | Constantinos Daskalakis | 01h 01m |
Surveys computational status of equilibrium concepts and gives concrete results: two‑player zero‑sum games are solvable by linear program / ellipsoid, while… | ||
| Multi-Dimensional and Non-Linear Mechanism Design and Approximation II | Jason Hartline | 01h 10m |
A reduction maximizes the sum of single-agent revenues subject to interim feasibility constraints (Border-style inequalities) and shows an ex ante relaxation… | ||
| Learning in Games II | Drew Fudenberg | 01h 06m |
Analyzes learning in extensive form games where players observe only terminal nodes and shows repeated play can converge to outcomes that are self‑confirming… | ||
| Complexity and Algorithmic Game Theory II | Constantinos Daskalakis | 01h 10m |
Second part of the tutorial presents concrete positive and negative results: deterministic mechanisms that make only value queries need exponentially many… | ||
| nothing matches | ||