Research map / Multi-agent systems and games / Games and equilibria
Learning to Recommend in Unknown Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies how a moderator who issues correlated-equilibrium-style recommendations can learn agents' unknown normal-form game utilities from best-response or quantal-response action feedback, giving learnability results and an online low-regret cutting-plane algorithm.
Problem
Platforms issuing action recommendations to strategic agents with unknown utilities must learn utilities (or enough of them) and keep recommendations compliant, given only observed follow/deviate actions.
Approach
Treats recommendations as active probes: under quantal-response feedback the sign of incentive-to-deviate reveals utility-difference vectors up to scale, enabling identifiability up to positive affine equivalence with binary search; under best-response feedback the indistinguishable set is characterized via normal fans of polarized utility polytopes; a cutting-plane method with center-of-gravity q
Key results
- Under quantal-response feedback, utilities are learnable up to positive affine equivalence with O(mnM log(1/epsilon)) recommendations.
- Under best-response feedback, a two-player counterexample shows non-learnability; the indistinguishable set is fully characterized via normal fans of polarized polytopes.
- Online cutting-plane algorithm achieves O(nM log T) cumulative incentive-to-deviate regret under both feedback models.
Surprising findings
- Best-response feedback cannot identify utilities even for generic games without weakly dominated actions, because distinct games induce identical best-response regions.
Limitations
- Learnability and regret analysis assume generic games with no weakly dominated actions and bounded utility differences.
- No empirical experiments are reported; results are purely theoretical.
- Quantal-response learning assumes sampling until deviations are observed, with sample cost scaling with exp(beta*C).
Experimental setup
Metrics: regret sample complexity
Builds on: correlated equilibrium contextual search quantal response equilibrium
Closest papers by meaning
- Multi-Agent Imitation Learning: Value is Easy, Regret is Hard (NeurIPS 2024 · similarity 0.87)
- Strategic Linear Contextual Bandits (NeurIPS 2024 · similarity 0.87)
- UNEX-RL: Reinforcing Long-Term Rewards in Multi-Stage Recommender Systems with UNidirectional EXecution (AAAI 2024 · similarity 0.87)
- Learning in Online Principal-Agent Interactions: The Power of Menus (AAAI 2024 · similarity 0.86)
- Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation (ICLR 2024 · similarity 0.86)
- Impact of Decentralized Learning on Player Utilities in Stackelberg Games (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.