AGT and Machine Learning
summary
Three concrete results: strategic classification models data as a Stackelberg game and proves that with a separable cost (or min of few separable functions) a polynomial learner can get within ε of the full-information OPT with probability 1−δ, and shows experiments on spam data (uses K=2 separable terms). A mechanism for labeled-data elicitation pays workers with a dominant-strategy payment (VCG-style: regress on others) and attains the social-optimum effort and zero surplus. Finally, replicator dynamics behavior is summarized by Conley chain-recurrence sets forming a DAG, giving a computable performance prediction and several open complexity questions.
AI-written summary · about
chapters (25)
- 0:00Intro
- 0:16AGT'S three recent brushes with ML
- 0:59Classification when the data are strategic
- 1:53The data are strategic!
- 3:48But of course...
- 4:52Stackelberg!
- 5:59Our goal in classification
- 6:54Hard problem even with nonstrategic data
- 7:47Surprise: strategic data is "easier" to classify!
- 10:59Separable cost functions
- 16:11How come?
- 19:42Strategic Data Sources
- 20:51Meet the agents
- 22:48Social Optimum
- 24:36Surprise: It can be achieved!
- 28:11Caveat
- 29:22Solution Concepts from the Topology of Learning in Games
- 31:36Basic idea seems to work: matching pennies
- 32:03Basic idea seems to work (cont.): coordination
- 32:28Basic Idea does not work! The dynamics (of even two-player games) can be chaotic...
- 32:41Conley to the Rescue
- 33:43One CRS
- 34:23Five CRS's
- 36:51The CRS structure of a game
- 38:34Bottom line
related talks
36mWhat Does Machine Learning Offer Game Theory (And Vice Versa)?
01h 01mML for discrete optimization: Theoretical foundations
12mLearning In The Presence Of Strategic Agents: Dynamics, Equilibria, And Convergence
43mToward Human-Centered Machine Learning
46m(Improving) Muddled Information
01h 11mA Theory of Multi-objective Machine Learning
04mOn gradient-based methods for finding game-theoretic equilibria
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control