Learning in Online Principal-Agent Interactions: The Power of Menus

Minbiao Han, Michael Albert, Haifeng Xu

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?

The authors extend the standard framework to allow for menus of strategies. Their approach varies based on the dimensionality of the strategy space:

  1. 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.
  2. 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.
Figure 2: Different agent types (theta and theta-prime) result in distinct piecewise linear utility functions and best responses across the strategy space x.

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)$.

Figure 4: Comparison of sample complexity (number of rounds) between menu-based and single-strategy approaches across different dimensions.

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

Abstract

We study a ubiquitous learning challenge in online principal-agent problems during which the principal learns the agent's private information from the agent's revealed preferences in historical interactions. This paradigm includes important special cases such as pricing and contract design, which have been widely studied in recent literature. However, existing work considers the case where the principal can only choose a single strategy at every round to interact with the agent and then observe the agent's revealed preference through their actions. In this paper, we extend this line of study to allow the principal to offer a menu of strategies to the agent and learn additionally from observing the agent's selection from the menu. We provide a thorough investigation of several online principal-agent problem settings and characterize their sample complexities, accompanied by the corresponding algorithms we have developed. We instantiate this paradigm to several important design problems $-$ including Stackelberg (security) games, contract design, and information design. Finally, we also explore the connection between our findings and existing results about online learning in Stackelberg games, and we offer a solution that can overcome a key hard instance of Peng et al. (2019).
BibTeX
@inproceedings{han2024learning,
  author = {Minbiao Han and Michael Albert and Haifeng Xu},
  title = {{Learning in Online Principal-Agent Interactions: The Power of Menus}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i16.29691},
}
Figure