Decoupling a resource constraint through fictitious play in multi-agent sequential decision making

Frits De Nijs; Matthijs T.J. Spaan; Mathijs 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, Mathijs M. De Weerdt

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review

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	ECAI 2016
Subtitle of host publication	22nd European Conference on Artificial Intelligence - 29 August-2 September 2016, The Hague, The Netherlands
Editors	Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hullermeier, Virgina Dignum, Frank Dignum, Frank van Harmelen
Place of Publication	Amsterdam Netherlands
Publisher	IOS Press
Pages	1724-1725
Number of pages	2
ISBN (Electronic)	9781614996729
ISBN (Print)	9781614996712
DOIs	https://doi.org/10.3233/978-1-61499-672-9-1724
Publication status	Published - 1 Jan 2016
Externally published	Yes
Event	European Conference on Artificial Intelligence 2016 - The Hague, Netherlands Duration: 29 Aug 2016 → 2 Sept 2016 Conference number: 22nd http://www.ecai2016.org/

Publication series

Name	Frontiers in Artificial Intelligence and Applications
Publisher	IOS Press
Volume	285
ISSN (Print)	0922-6389

Conference

Conference	European Conference on Artificial Intelligence 2016
Abbreviated title	ECAI 2016
Country/Territory	Netherlands
City	The Hague
Period	29/08/16 → 2/09/16
Internet address	http://www.ecai2016.org/

Access to Document

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

Cite this

De Nijs, F., Spaan, M. T. J., & De Weerdt, M. M. (2016). Decoupling a resource constraint through fictitious play in multi-agent sequential decision making. In G. A. Kaminka, M. Fox, P. Bouquet, E. Hullermeier, V. Dignum, F. Dignum, & F. van Harmelen (Eds.), ECAI 2016: 22nd European Conference on Artificial Intelligence - 29 August-2 September 2016, The Hague, The Netherlands (pp. 1724-1725). (Frontiers in Artificial Intelligence and Applications; Vol. 285). IOS Press. https://doi.org/10.3233/978-1-61499-672-9-1724

De Nijs, Frits ; Spaan, Matthijs T.J. ; De Weerdt, Mathijs M. / Decoupling a resource constraint through fictitious play in multi-agent sequential decision making. ECAI 2016: 22nd European Conference on Artificial Intelligence - 29 August-2 September 2016, The Hague, The Netherlands. editor / Gal A. Kaminka ; Maria Fox ; Paolo Bouquet ; Eyke Hullermeier ; Virgina Dignum ; Frank Dignum ; Frank van Harmelen. Amsterdam Netherlands : IOS Press, 2016. pp. 1724-1725 (Frontiers in Artificial Intelligence and Applications).

@inproceedings{1875ddc96e2c456e8fb1a3149ad968fa,

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 = "{De Nijs}, Frits and Spaan, {Matthijs T.J.} and {De Weerdt}, {Mathijs M.}",

year = "2016",

month = jan,

day = "1",

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

language = "English",

isbn = "9781614996712",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "1724--1725",

editor = "Kaminka, {Gal A.} and Maria Fox and Paolo Bouquet and Eyke Hullermeier and Virgina Dignum and Frank Dignum and {van Harmelen}, Frank",

booktitle = "ECAI 2016",

address = "Netherlands",

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

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

}

De Nijs, F, Spaan, MTJ & De Weerdt, MM 2016, Decoupling a resource constraint through fictitious play in multi-agent sequential decision making. in GA Kaminka, M Fox, P Bouquet, E Hullermeier, V Dignum, F Dignum & F van Harmelen (eds), ECAI 2016: 22nd European Conference on Artificial Intelligence - 29 August-2 September 2016, The Hague, The Netherlands. Frontiers in Artificial Intelligence and Applications, vol. 285, IOS Press, Amsterdam Netherlands, pp. 1724-1725, European Conference on Artificial Intelligence 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. / De Nijs, Frits; Spaan, Matthijs T.J.; De Weerdt, Mathijs M.
ECAI 2016: 22nd European Conference on Artificial Intelligence - 29 August-2 September 2016, The Hague, The Netherlands. ed. / Gal A. Kaminka; Maria Fox; Paolo Bouquet; Eyke Hullermeier; Virgina Dignum; Frank Dignum; Frank van Harmelen. Amsterdam Netherlands: IOS Press, 2016. p. 1724-1725 (Frontiers in Artificial Intelligence and Applications; Vol. 285).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other › peer-review

TY - GEN

T1 - Decoupling a resource constraint through fictitious play in multi-agent sequential decision making

AU - De Nijs, Frits

AU - Spaan, Matthijs T.J.

AU - De Weerdt, Mathijs M.

N1 - Conference code: 22nd

PY - 2016/1/1

Y1 - 2016/1/1

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.

UR - http://www.scopus.com/inward/record.url?scp=85013130628&partnerID=8YFLogxK

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

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

M3 - Conference Paper

AN - SCOPUS:85013130628

SN - 9781614996712

T3 - Frontiers in Artificial Intelligence and Applications

SP - 1724

EP - 1725

BT - ECAI 2016

A2 - Kaminka, Gal A.

A2 - Fox, Maria

A2 - Bouquet, Paolo

A2 - Hullermeier, Eyke

A2 - Dignum, Virgina

A2 - Dignum, Frank

A2 - van Harmelen, Frank

PB - IOS Press

CY - Amsterdam Netherlands

T2 - European Conference on Artificial Intelligence 2016

Y2 - 29 August 2016 through 2 September 2016

ER -

De Nijs F, Spaan MTJ, De Weerdt MM. Decoupling a resource constraint through fictitious play in multi-agent sequential decision making. In Kaminka GA, Fox M, Bouquet P, Hullermeier E, Dignum V, Dignum F, van Harmelen F, editors, ECAI 2016: 22nd European Conference on Artificial Intelligence - 29 August-2 September 2016, The Hague, The Netherlands. Amsterdam Netherlands: IOS Press. 2016. p. 1724-1725. (Frontiers in Artificial Intelligence and Applications). doi: 10.3233/978-1-61499-672-9-1724

Decoupling a resource constraint through fictitious play in multi-agent sequential decision making

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this