Research map / Multi-agent systems and games / Games and equilibria
Learning in Online Principal-Agent Interactions: The Power of Menus
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.
Shows that letting the principal post a menu of strategies, rather than a single strategy per round, lets it learn an agent's private type in one round in many principal-agent settings, and gives log|Θ| and O(n²L) algorithms for the single-strategy-limited cases.
Problem
Online learning of an agent's private type in principal-agent problems (pricing, Stackelberg/security games, contract design, information design) when the principal learns from revealed preferences and can only post a single strategy per round.
Approach
Allow the principal to post a menu of strategies per round and learn from the agent's selection, giving sample complexities that are a single round under nondegeneracy when the strategy space has dimension at least 2, and log|Θ| rounds in the one-dimensional case with menus of two strategies.
Key results
- With menus and a nondegeneracy assumption, the agent's type can be learned in a single round when the principal's strategy space has effective dimension at least 2.
- For one-dimensional strategy spaces with menus, an algorithm learns the type in log|Θ| rounds; with single strategies under extra assumptions, also log|Θ| rounds.
- With an action-informed oracle and infinite type space, O(n^2 L) rounds suffice, improving the single-strategy O(n^3 L) bound by a factor of n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Offer a menu instead of a single strategy | Stackelberg games with m>2 and finite types · Stackelberg games, m>2 | rounds to learn type: |Θ| -> O(1) | Helped |
| Offer a menu instead of a single strategy | Stackelberg games with m=2 and finite types · Stackelberg games, m=2 | rounds to learn type: log |Θ| -> log |Θ| | No clear effect |
| Use menus to identify the type from the agent's selection | General principal-agent problems satisfying Assumption 1 · Finite type set | rounds to learn type | Helped |
| Use a menu-based algorithm instead of the single-strategy state of the art | Infinite-type principal-agent learning · Infinite type space | rounds to learn type: O(n^3L) -> O(n^2L) | Helped |
| Offer a menu of leader strategies | Stackelberg hardness example · Stackelberg hardness example | samples to learn type: 2^{Ω(m)} -> single round | Helped |
| Use a menu-based algorithm rather than a single-strategy algorithm | One-dimensional principal strategy with finite types · Finite type set | rounds to learn type: log |Θ| -> log |Θ| | No clear effect |
Surprising findings
- In the two-action Stackelberg case the menu-based single-round learning is impossible for more than two types, because the utility is piecewise linear convex and only the endpoints can be argmax.
Limitations
- Single-round results rely on a nondegeneracy assumption and fail in the one-dimensional strategy space case.
- Assumes unbounded menu sizes; finite menu size characterization left open.
- Infinite-type result requires an agent action-informed oracle assumption.
Experimental setup
Metrics: sample complexity (number of rounds)
Baselines: single-strategy online learning in Stackelberg games O(n^3 L) single-strategy algorithm
Builds on: Stackelberg game online learning hardness example (Balcan et al.) menus in contract design
Closest papers by meaning
- Generalized Principal-Agent Problem with a Learning Agent (ICLR 2025 · similarity 0.89)
- Contracting with a Learning Agent (NeurIPS 2024 · similarity 0.88)
- Learning Optimal Contracts: How to Exploit Small Action Spaces (ICLR 2024 · similarity 0.88)
- Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning (ICML 2024 · similarity 0.88)
- Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.87)
- Contract Design Under Approximate Best Responses (ICML 2025 · similarity 0.87)
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.