Mediator learns and guides decisions in games with limited feedback

Learning and Steering in Incomplete-Information Games

Computer Science and Game TheoryArtificial IntelligenceMachine Learning

Summary

This work studies how a mediator can influence the decisions of several players in a strategic game when they do not know the players' preferences but only see the final results of interactions. The mediator learns how the players value different outcomes by observing the outcomes of repeated plays and gradually adjusts payments and suggestions to steer the game to outcomes that benefit her. The authors develop algorithms that efficiently learn from limited feedback and use this to guide players toward equilibria that satisfy the mediator's objectives. These algorithms come with theoretical guarantees on how quickly they learn and steer outcomes over time.

What this means in practice

  • For mechanism designers: Create incentive schemes that learn player preferences through observed outcomes and steer interactions toward mediator-favorable results without knowing utilities upfront.
  • For game theory software developers: Build tools for computing equilibrium strategies in games with incomplete information and outcome-only feedback that help analyze strategic environments adaptively.

Authors

Asrın Efe Yorulmaz, Tamer Başar

Abstract

In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of $\widetilde O(\varepsilon^{-2})$ that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learning, equilibrium computation, and steering toward mediator-optimal extensive-form correlated equilibria (EFCE). With high probability, the Learn-Compute-Steer algorithm achieves a directness gap and an optimality gap of $\widetilde O(T^{-1/4})$, while time-average payments are of $\widetilde O(T^{-1/8})$.