A computationally efficient implementation of fictitious play in a distributed setting

Brian Swenson; Soummya Kar; Joao Xavier

doi:10.1109/EUSIPCO.2015.7362542

A computationally efficient implementation of fictitious play in a distributed setting

Brian Swenson, Soummya Kar, Joao Xavier

Applied Research Laboratory (ARL)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

Abstract

The paper deals with distributed learning of Nash equilibria in games with a large number of players. The classical fictitious play (FP) algorithm is impractical in large games due to demanding communication requirements and high computational complexity. A variant of FP is presented that aims to mitigate both issues. Complexity is mitigated by use of a computationally efficient Monte-Carlo based best response rule. Demanding communication problems are mitigated by implementing the algorithm in a network-based distributed setting, in which player-to-player communication is restricted to local subsets of neighboring players as determined by a (possibly sparse, but connected) preassigned communication graph. Results are demonstrated via a simulation example.

Original language	English (US)
Title of host publication	2015 23rd European Signal Processing Conference, EUSIPCO 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1043-1047
Number of pages	5
ISBN (Electronic)	9780992862633
DOIs	https://doi.org/10.1109/EUSIPCO.2015.7362542
State	Published - Dec 22 2015
Event	23rd European Signal Processing Conference, EUSIPCO 2015 - Nice, France Duration: Aug 31 2015 → Sep 4 2015

Publication series

Name	2015 23rd European Signal Processing Conference, EUSIPCO 2015

Conference

Conference	23rd European Signal Processing Conference, EUSIPCO 2015
Country/Territory	France
City	Nice
Period	8/31/15 → 9/4/15

All Science Journal Classification (ASJC) codes

Media Technology
Computer Vision and Pattern Recognition
Signal Processing

Access to Document

10.1109/EUSIPCO.2015.7362542

Cite this

Swenson, B., Kar, S., & Xavier, J. (2015). A computationally efficient implementation of fictitious play in a distributed setting. In 2015 23rd European Signal Processing Conference, EUSIPCO 2015 (pp. 1043-1047). Article 7362542 (2015 23rd European Signal Processing Conference, EUSIPCO 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/EUSIPCO.2015.7362542

@inproceedings{90e6754b9d6d4ecc87ca1449feed9619,

title = "A computationally efficient implementation of fictitious play in a distributed setting",

abstract = "The paper deals with distributed learning of Nash equilibria in games with a large number of players. The classical fictitious play (FP) algorithm is impractical in large games due to demanding communication requirements and high computational complexity. A variant of FP is presented that aims to mitigate both issues. Complexity is mitigated by use of a computationally efficient Monte-Carlo based best response rule. Demanding communication problems are mitigated by implementing the algorithm in a network-based distributed setting, in which player-to-player communication is restricted to local subsets of neighboring players as determined by a (possibly sparse, but connected) preassigned communication graph. Results are demonstrated via a simulation example.",

author = "Brian Swenson and Soummya Kar and Joao Xavier",

note = "Publisher Copyright: {\textcopyright} 2015 EURASIP.; 23rd European Signal Processing Conference, EUSIPCO 2015 ; Conference date: 31-08-2015 Through 04-09-2015",

year = "2015",

month = dec,

day = "22",

doi = "10.1109/EUSIPCO.2015.7362542",

language = "English (US)",

series = "2015 23rd European Signal Processing Conference, EUSIPCO 2015",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "1043--1047",

booktitle = "2015 23rd European Signal Processing Conference, EUSIPCO 2015",

address = "United States",

}

Swenson, B, Kar, S & Xavier, J 2015, A computationally efficient implementation of fictitious play in a distributed setting. in 2015 23rd European Signal Processing Conference, EUSIPCO 2015., 7362542, 2015 23rd European Signal Processing Conference, EUSIPCO 2015, Institute of Electrical and Electronics Engineers Inc., pp. 1043-1047, 23rd European Signal Processing Conference, EUSIPCO 2015, Nice, France, 8/31/15. https://doi.org/10.1109/EUSIPCO.2015.7362542

A computationally efficient implementation of fictitious play in a distributed setting. / Swenson, Brian; Kar, Soummya; Xavier, Joao.
2015 23rd European Signal Processing Conference, EUSIPCO 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 1043-1047 7362542 (2015 23rd European Signal Processing Conference, EUSIPCO 2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A computationally efficient implementation of fictitious play in a distributed setting

AU - Swenson, Brian

AU - Kar, Soummya

AU - Xavier, Joao

PY - 2015/12/22

Y1 - 2015/12/22

N2 - The paper deals with distributed learning of Nash equilibria in games with a large number of players. The classical fictitious play (FP) algorithm is impractical in large games due to demanding communication requirements and high computational complexity. A variant of FP is presented that aims to mitigate both issues. Complexity is mitigated by use of a computationally efficient Monte-Carlo based best response rule. Demanding communication problems are mitigated by implementing the algorithm in a network-based distributed setting, in which player-to-player communication is restricted to local subsets of neighboring players as determined by a (possibly sparse, but connected) preassigned communication graph. Results are demonstrated via a simulation example.

AB - The paper deals with distributed learning of Nash equilibria in games with a large number of players. The classical fictitious play (FP) algorithm is impractical in large games due to demanding communication requirements and high computational complexity. A variant of FP is presented that aims to mitigate both issues. Complexity is mitigated by use of a computationally efficient Monte-Carlo based best response rule. Demanding communication problems are mitigated by implementing the algorithm in a network-based distributed setting, in which player-to-player communication is restricted to local subsets of neighboring players as determined by a (possibly sparse, but connected) preassigned communication graph. Results are demonstrated via a simulation example.

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

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

U2 - 10.1109/EUSIPCO.2015.7362542

DO - 10.1109/EUSIPCO.2015.7362542

M3 - Conference contribution

AN - SCOPUS:84963959053

T3 - 2015 23rd European Signal Processing Conference, EUSIPCO 2015

SP - 1043

EP - 1047

BT - 2015 23rd European Signal Processing Conference, EUSIPCO 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 23rd European Signal Processing Conference, EUSIPCO 2015

Y2 - 31 August 2015 through 4 September 2015

ER -

A computationally efficient implementation of fictitious play in a distributed setting

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this