Coordinating users of shared facilities via data-driven predictive assistants and game theory

Philipp Geiger, Michel Besserve, Justus Winkelmann, Claudius Proissl, 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 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. 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.

Introduction: The Challenge of Interactive Forecasting

Imagine a popular campus cafeteria. If a mobile app tells everyone that 12:00 PM will be quiet, everyone might decide to show up at exactly 12:00 PM, creating the very crowd they were trying to avoid. This is known as the "flapping" or oscillation problem: the forecast itself changes the outcome.

Most standard forecasting tools assume the future is independent of the prediction. In social and economic systems, this is rarely true. This paper addresses how to design assistants that can reach stable, accurate predictions even when the system is constantly reacting to the assistant’s own output.

Theoretical Framework: Self-Fulfilling Prophecies

The authors combine Game Theory with Control Theory to model the interaction between the assistant and the users. They define a "perfect" probabilistic forecast as a self-fulfilling prophecy: a state where the predicted distribution of outcomes matches the actual distribution resulting from users reacting to that forecast.

The interaction loop between the predictive assistant and users.

The paper proves that reaching such a prophecy is equivalent to selecting a Bayesian Nash Equilibrium (BNE). Using fixed-point theorems, they establish that these prophecies exist even in large-scale "nonatomic" games where the assistant only observes aggregate data (like total headcounts) rather than individual choices.

The Expodamp Algorithm

To reach these stable states in practice, the authors propose Expodamp, a dampened exponential smoothing algorithm. Instead of naively predicting that tomorrow will look exactly like today, Expodamp updates its forecast by only a fraction (a "dampening" factor) of the observed error. This prevents the system from overshooting and oscillating, allowing the population to converge toward a stable behavior.

Empirical Validation: The Campus Cafeteria Experiment

The researchers conducted a real-world interventional experiment at a university cafeteria with approximately 400 daily users. Over several months, they provided daily forecasts via a web app. The experiment compared two 35-day periods: one using a simple "Average" baseline and one using the Expodamp algorithm.

Key Results

The study found that the Expodamp algorithm significantly outperformed the baseline in terms of predictive accuracy. By accounting for the feedback loop between the forecast and user behavior, Expodamp achieved a lower Mean Squared Error (MSE), indicating a more stable and reliable coordination mechanism.

Comparison of Mean Squared Error (MSE) between Expodamp and the Average baseline.

Beyond the numbers, the algorithm successfully avoided the wild oscillations that often plague interactive social systems, effectively acting as a coordinator that "solved" the congestion game for the users.

Discussion and Future Directions

While the results are promising, the model currently assumes users are "assistant-best-responding"—meaning they trust and act rationally based on the forecast. Future work could explore scenarios where users are skeptical or attempt to "game" the system. Additionally, while the assistant reaches a Nash Equilibrium, this is not always the most socially efficient outcome. Future research may investigate how to steer users toward outcomes that maximize overall social welfare rather than just individual stability.

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{geiger2019coordinating,
  author = {Philipp Geiger and Michel Besserve and Justus Winkelmann and Claudius Proissl and Bernhard Schölkopf},
  title = {{Coordinating users of shared facilities via data-driven predictive assistants and game theory}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=5CX-hEwOBv},
}
Figure