On gradient-based methods for finding game-theoretic equilibria

on YouTube ↗04m

" summary

Matches a learning multi-armed bandit problem to a matching market where choices are exclusive so only one agent wins each arm, models agents exploring unknown preferences on both sides, and runs UCB-Gale Shapley by feeding upper confidence bounds into a Gale–Shapley matcher. The paper proves the algorithm achieves logarithmic regret (near-optimal) and quantifies agent interaction via a Δ^2 interaction term, presenting formal theorems and worked analysis rather than just examples.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 0:19Multi-Armed Bandits
3. 2:23Matching Markets Meet Learning
4. 3:25Regret-Minimizing Algorithm

" related talks

• 28mMultiplayer Bandit Learning - From Competition to CooperationSimina Branzei · Mathematics of Online Decision Making 2020
• 29mNash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-DebreuMojtaba Hosseini, Vijay V. Vazirani · ITCS 2022
• 22mOnline Learning and Bandits with Queried HintsAditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala · ITCS 2023
• 27mOn the Complexity of Best Arm Identification in Multi-Armed Bandit ModelsAurélien Garivier · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 12mLearning In The Presence Of Strategic Agents: Dynamics, Equilibria, And ConvergenceEric Mazumdar · Meet the Fellows Welcome Event
• 56mOf Moments and Matching: Trade-offs and Treatments in Imitation LearningSteven Wu · Adversarial Approaches in Machine Learning 2022
• 01h 11mA Theory of Multi-objective Machine LearningNika Haghtalab · Modern Paradigms in Generalization Boot Camp 2024
• Bandits and Agents: How to Incentivize Exploration?Aleksandrs Slivkins · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)