Learning Incentives, Not Utilities: Certified Selection and Steering in Extensive-Form Games

We study how a principal can steer no-regret learning agents in a repeated extensive-form game without knowing their utility functions. Left alone, such agents can settle on outcomes that are poor for the principal. The principal knows the game tree and its own payoff, observes play, and can privately recommend actions and pay the agents at its own cost. Given a class of candidate rules for doing so, it must decide which are robust: under the true utilities, every agent loses by deviating from their recommendations. A large enough bonus for following recommendations is robust without any learning, but it is paid in every round. Whether a cheaper rule is also robust depends on utilities the principal cannot see. We show that the principal never needs the utility functions themselves. Learning only the agents' incentives, it can check every candidate at once, and choosing the highest-value certified candidate is safe. Steering to it then earns its value, net of payments, up to the agents' regret and the rounds spent learning. This is possible because in extensive form, incentives depend on the utilities only up to one constant per information set. Every relevant deviation gain is linear in what remains, the incentive-relevant part of the utilities. As in recent work on normal-form games, this part can be learned by a zero-sum payment game against one agent at a time. The proof is a modular reduction whose steps each have a concrete construction, and we report diagnostics on small games. For bonus-based rules, all steps can be carried out together under extra assumptions on observation and learning; steering a cheaper certified rule is left open. In short, learning buys value rather than feasibility: it lets the principal trust cheaper rules.