Coordination via predictive assistants from a game-theoretic view

Philipp Geiger, Justus Winkelmann, Claudius Proissl, Michel Besserve, Bernhard Schölkopf

Abstract

We study data-driven assistants that provide congestion forecasts to users of shared facilities (roads, cafeterias, etc.), to support coordination between them and increase the efficiency of such collective systems. Key questions are: (1) when and how much can accurate predictions help for coordination, and (2) which assistant algorithms reach optimal predictions? We establish conditions under which "self-fulfilling prophecies"—perfect probabilistic predictions—solve the coordination problem by selecting a Bayesian Nash equilibrium (BNE). We prove these prophecies exist even in large-scale settings with aggregate statistics and propose the "Expodamp" algorithm to sequentially learn these states. Our findings are validated through a real-world experiment in a campus cafeteria.

Introduction

In modern smart cities, predictive apps guide our decisions on when to visit the gym, commute, or eat. However, these forecasts create a feedback loop: if an app predicts a facility will be quiet, many users may react by going at that time, making the prediction false. This "flapping" behavior can lead to systemic inefficiency. This research provides a rigorous game-theoretic framework to understand how predictive assistants can act as coordination mechanisms to reach stable, accurate outcomes.

The Coordination Problem and System Model

The core challenge in social systems is that a forecast acts as an intervention. Unlike weather forecasting, where the prediction does not change the outcome, a congestion forecast influences user behavior. We model this as a congestion game where users are "assistant-best-responding," meaning they trust the forecast and choose time slots that maximize their utility based on that information.

The system model illustrates the feedback loop between the assistant's forecast (A) and the users' private actions (B), which ultimately determine the public outcome (Y).

We define a Self-Fulfilling Prophecy (SFP) as a state where the forecast $A$ perfectly matches the resulting distribution of outcomes $Y$. Mathematically, reaching an SFP is equivalent to selecting a Bayesian Nash Equilibrium (BNE) for the system. Using fixed-point theorems, we demonstrate that such equilibria exist even in large-scale "nonatomic" games where only aggregate population statistics are available.

Learning Stable Forecasts: The Expodamp Algorithm

To reach these stable states without knowing users' private preferences, we propose the Expodamp algorithm. Traditional algorithms often fail because they overreact to recent data, causing oscillations. Expodamp uses a dampened update rule:

$A^t := A^{t-1} + \alpha(Y^{t-1} - A^{t-1})$

By updating the forecast incrementally (using a small dampening factor $\alpha$), the assistant prevents user overreaction and allows the system to converge toward a stable fixed point. This approach shows that being "slow" to update can actually lead to faster convergence in interactive environments.

Experimental Results

We validated our framework through a 70-day interventional study at a campus cafeteria with approximately 400 daily users. The experiment compared the Expodamp algorithm against a standard historical "Average" baseline.

The Expodamp algorithm achieved a lower Mean Squared Error (MSE) compared to the historical average baseline during the real-world cafeteria experiment.

As shown in the results, Expodamp significantly outperformed the baseline, achieving a Mean Squared Error (MSE) of 69.56 compared to 74.25. This empirical evidence supports the theoretical claim that dampened learning rules can effectively navigate the feedback loops of human-in-the-loop systems.

Conclusion

This work demonstrates that predictive assistants are not merely passive observers but active coordination mechanisms. By framing forecasting as equilibrium selection, we can design algorithms that stabilize social systems. Future research will explore the dynamics of user trust—modeling how users react when forecasts are inaccurate—and how assistants can steer crowds toward socially optimal outcomes rather than just stable ones.

Summary updated

Abstract

We study data-driven assistants that provide congestion forecasts to users of shared facilities (roads, cafeterias, etc.), to support coordination between them, and increase efficiency of such collective systems. Key questions are: (1) when and how much can (accurate) predictions help for coordination, and (2) which assistant algorithms reach optimal predictions? First we lay conceptual ground for this setting where user preferences are a priori unknown and predictions influence outcomes. Addressing (1), we establish conditions under which self-fulfilling prophecies, i.e., "perfect" (probabilistic) predictions of what will happen, solve the coordination problem in the game-theoretic sense of selecting a Bayesian Nash equilibrium (BNE). Next we prove that such prophecies exist even in large-scale settings where only aggregated statistics about users are available. This entails a new (nonatomic) BNE existence result. Addressing (2), we propose two assistant algorithms that sequentially learn from users' reactions, together with optimality/convergence guarantees. We validate one of them in a large real-world experiment.
BibTeX
@inproceedings{geiger2019coordination,
  author = {Philipp Geiger and Justus Winkelmann and Claudius Proissl and Michel Besserve and Bernhard Schölkopf},
  title = {{Coordination via predictive assistants from a game-theoretic view}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=5CX-hEwOBv},
}
Figure