In many economic and strategic interactions, a "principal" (such as a seller or an employer) must learn the hidden preferences or "type" of an "agent" (such as a buyer or a new hire) through repeated interactions. Traditionally, this is modeled as an online learning problem where the principal offers a single strategy per round and observes the agent's response. However, this approach can be prohibitively slow, sometimes requiring a number of interactions that scales linearly or even exponentially with the number of possible agent types.
This paper introduces a paradigm shift: by offering a menu of options instead of a single take-it-or-leave-it offer, the principal can learn the agent's private information dramatically faster—often in just a single round.
The Core Challenge: Asymmetric Information
The principal-agent problem under asymmetric information is a cornerstone of mechanism design. Whether it is a defender in a security game trying to identify an attacker's values or a platform trying to understand a user's utility function, the bottleneck is always the speed of learning. Previous research suggested that in complex scenarios, such as certain Stackelberg games, identifying the agent's type was fundamentally "hard."
The authors ask a simple but powerful question: If the principal can offer a menu of choices (e.g., different price-quantity bundles), can they force the agent to reveal their type more efficiently?
Methodology: Geometric Identification and Binary Search
The authors extend the standard framework to allow for menus of strategies. Their approach varies based on the dimensionality of the strategy space:
- Geometric Identification (High-Dimensional Spaces): If the strategy space has more than one dimension ($m > 1$), the principal can construct a small, local "spherical" menu. Because the agent's choice from this menu must satisfy first-order optimality conditions (KKT conditions), their selection essentially reveals the gradient of their utility function. Under a non-degeneracy assumption, this gradient uniquely identifies the agent's type in a single round.
- Binary Search (1D Spaces): In one-dimensional spaces (like a simple price), a single round is insufficient. The authors developed a "Learning-via-Menu" algorithm that uses a binary search-like approach to eliminate half of the possible agent types each round, achieving $O(\log |\Theta|)$ complexity.
Key Insights: The Blessing of Dimensionality
A counter-intuitive finding of this work is that higher-dimensional strategy spaces actually make learning easier rather than harder. More dimensions provide more "directions" to differentiate agent types, allowing the principal to design menus that force unique responses from different types. This allows the principal to overcome the exponential hardness previously associated with single-strategy learning in Stackelberg games.
Results and Performance
The theoretical results demonstrate that menus consistently match or outperform single-strategy approaches across all settings. For finite types in higher dimensions, the complexity drops from $O(|\Theta|)$ to $O(1)$. For infinite types, the authors provide an algorithm that identifies the type within $O(n^2 L)$ rounds, an improvement over the previous state-of-the-art $O(n^3 L)$.
Conclusion and Future Directions
By leveraging the optimization behavior of agents, principals can use menus to "read" hidden preferences with unprecedented speed. While this paper focuses on identification with potentially large menus, future work remains to explore the trade-offs involved when menu sizes are restricted or when agents are strategic (non-myopic) and attempt to hide their types to secure better future offers.
Summary updated