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 gametheoretic 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{pmlr-v115-geiger20a,
title = {Coordinating Users of Shared Facilities via Data-driven Predictive Assistants and Game Theory},
author = {Geiger, Philipp and Besserve, Michel and Winkelmann, Justus and Proissl, Claudius and Sch{\"{o}}lkopf, Bernhard},
booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference},
pages = {207--216},
year = {2020},
editor = {Adams, Ryan P. and Gogate, Vibhav},
volume = {115},
series = {Proceedings of Machine Learning Research},
month = {22--25 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v115/geiger20a/geiger20a.pdf},
url = {https://proceedings.mlr.press/v115/geiger20a.html},
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 gametheoretic 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.}
}