Learning Stackelberg Equilibria from Preferences over Unknown Multi-Objective Trade-offs

Interactions among self-interested agents often lead to socially inefficient outcomes. A central authority can counteract this by introducing incentives that steer agents toward more desirable outcomes, a setting naturally captured by a Stackelberg game in which the authority acts as the leader, the agents as followers, and the Stackelberg equilibrium characterizes the desired outcome. Defining what is “desirable”, however, typically requires trading off multiple, possibly competing objectives. While each objective may be easy to evaluate on its own, assigning numerical weights that reflect their relative importance and combine them into a single scalar cost is often difficult. Existing methods for solving Stackelberg games typically assume the leader observes this scalar cost directly. We instead consider a leader who does not know the trade-off parameter, but observes each objective's value at an approximate follower equilibrium and receives a pairwise preference between consecutive realizations. We jointly estimate the equilibrium-induced objective maps via kernel ridge regression and the trade-off parameter via logistic maximum likelihood, combining their confidence bounds in an optimistic action-selection rule. This yields a high-probability regret bound that captures the objective and trade-off estimation errors together with the inexactness of the followers' response. We establish conditions under which the resulting policy achieves no regret and further translate these guarantees into a finite-time criterion for extracting an $ϵ$-Stackelberg policy-response pair from the interaction history. The framework is validated in a carbon-tax design study, showing that the leader can recover a socially desirable policy despite inexactness in the followers' responses.