Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making

Frits de Nijs; Matthijs T. J. Spaan; M.M. de Weerdt

doi:10.3233/978-1-61499-672-9-1724

Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making

Frits de Nijs, Matthijs T. J. Spaan, M.M. de Weerdt

Algorithmics

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

25 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	Proceedings - 22nd European Conference on Artificial Intelligence, ECAI 2016
Publisher	IOS Press
Pages	1724-1725
Number of pages	2
Volume	285
ISBN (Electronic)	978-1-61499-672-9
ISBN (Print)	978-1-61499-671-2
DOIs	https://doi.org/10.3233/978-1-61499-672-9-1724
Publication status	Published - 2016
Event	ECAI 2016: 22nd European Conference on Artificial Intelligence 2016 - World Forum, The Hague, Netherlands Duration: 29 Aug 2016 → 2 Sept 2016 Conference number: 22 http://www.ecai2016.org/

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Publisher	IOS Press

Conference

Conference	ECAI 2016
Abbreviated title	ECAI 2016
Country/Territory	Netherlands
City	The Hague
Period	29/08/16 → 2/09/16
Other	Including Prestigious Applications of Artificial Intelligence, PAIS 2016
Internet address	http://www.ecai2016.org/

Access to Document

10.3233/978-1-61499-672-9-1724

FAIA285-1724Final published version, 187 KBLicence: CC BY-NC

Cite this

Nijs, F. D., Spaan, M. T. J., & de Weerdt, M. M. (2016). Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making. In Proceedings - 22nd European Conference on Artificial Intelligence, ECAI 2016 (Vol. 285, pp. 1724-1725). (Frontiers in Artificial Intelligence and Applications). IOS Press. https://doi.org/10.3233/978-1-61499-672-9-1724

@inproceedings{8553119bc3634a739cf6d69446d548fb,

title = "Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making",

abstract = "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.",

author = "Nijs, {Frits de} and Spaan, {Matthijs T. J.} and {de Weerdt}, M.M.",

year = "2016",

doi = "10.3233/978-1-61499-672-9-1724",

language = "English",

isbn = "978-1-61499-671-2",

volume = "285",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "1724--1725",

booktitle = "Proceedings - 22nd European Conference on Artificial Intelligence, ECAI 2016",

address = "Netherlands",

note = "ECAI 2016 : 22nd European Conference on Artificial Intelligence 2016, ECAI 2016 ; Conference date: 29-08-2016 Through 02-09-2016",

url = "http://www.ecai2016.org/",

}

Nijs, FD, Spaan, MTJ & de Weerdt, MM 2016, Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making. in Proceedings - 22nd European Conference on Artificial Intelligence, ECAI 2016. vol. 285, Frontiers in Artificial Intelligence and Applications, IOS Press, pp. 1724-1725, ECAI 2016, The Hague, Netherlands, 29/08/16. https://doi.org/10.3233/978-1-61499-672-9-1724

Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making. / Nijs, Frits de; Spaan, Matthijs T. J.; de Weerdt, M.M.
Proceedings - 22nd European Conference on Artificial Intelligence, ECAI 2016. Vol. 285 IOS Press, 2016. p. 1724-1725 (Frontiers in Artificial Intelligence and Applications).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making

AU - Nijs, Frits de

AU - Spaan, Matthijs T. J.

AU - de Weerdt, M.M.

N1 - Conference code: 22

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.3233/978-1-61499-672-9-1724

DO - 10.3233/978-1-61499-672-9-1724

M3 - Conference contribution

SN - 978-1-61499-671-2

VL - 285

T3 - Frontiers in Artificial Intelligence and Applications

SP - 1724

EP - 1725

BT - Proceedings - 22nd European Conference on Artificial Intelligence, ECAI 2016

PB - IOS Press

T2 - ECAI 2016

Y2 - 29 August 2016 through 2 September 2016

ER -

Decoupling a Resource Constraint through Fictitious Play in Multi-agent Sequential Decision Making

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this