Decoupling a Resource Constraint Through Fictitious Play in Multi-Agent Sequential Decision Making
Frits de Nijs, Matthijs T. J. Spaan, Mathijs M. De Weerdt · Frontiers in artificial intelligence and applications · 2016
When multiple independent agents use a limited shared resource, they need to coordinate and thereby their planning problems become coupled. We present a resource assignment strategy that decouples agents using marginal utility cost, allowing them to plan individually. We show that agents converge to an expected cost curve by keeping a history of plans, inspired by fictitious play. This performs slightly better than a state-of-the-art best-response approach and is significantly more scalable than a preallocation Mixed-Integer Linear Programming formulation, providing a good trade-off between performance and quality.