Computationally efficient learning in large-scale games: Sampled fictitious play revisited

Brian Swenson; Soummya Kar; Joao Xavier

doi:10.1109/ACSSC.2016.7869565

Computationally efficient learning in large-scale games: Sampled fictitious play revisited

Brian Swenson, Soummya Kar, Joao Xavier

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

Abstract

Fictitious Play (FP) is a popular algorithm known to achieve Nash equilibrium learning in certain large-scale games. However, for games with many players, the computational demands of the FP algorithm can be prohibitive. Sampled FP (SFP) is a variant of FP that mitigates computational demands via a Monte Carlo approach. While SFP does mitigate the complexity of FP, it can be shown that SFP still uses information in an inefficient manner. The paper generalizes the SFP convergence result and studies a stochastic-approximation-based variant that significantly reduces the complexity of SFP.

Original language	English (US)
Title of host publication	Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Editors	Michael B. Matthews
Publisher	IEEE Computer Society
Pages	1212-1215
Number of pages	4
ISBN (Electronic)	9781538639542
DOIs	https://doi.org/10.1109/ACSSC.2016.7869565
State	Published - Mar 1 2017
Event	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 - Pacific Grove, United States Duration: Nov 6 2016 → Nov 9 2016

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Other

Other	50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016
Country/Territory	United States
City	Pacific Grove
Period	11/6/16 → 11/9/16

All Science Journal Classification (ASJC) codes

Signal Processing
Computer Networks and Communications

Access to Document

10.1109/ACSSC.2016.7869565

Cite this

Swenson, B., Kar, S., & Xavier, J. (2017). Computationally efficient learning in large-scale games: Sampled fictitious play revisited. In M. B. Matthews (Ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 (pp. 1212-1215). Article 7869565 (Conference Record - Asilomar Conference on Signals, Systems and Computers). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2016.7869565

Swenson, Brian ; Kar, Soummya ; Xavier, Joao. / Computationally efficient learning in large-scale games : Sampled fictitious play revisited. Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. editor / Michael B. Matthews. IEEE Computer Society, 2017. pp. 1212-1215 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

@inproceedings{74860097a9b44abcb09c9b549d352ccd,

title = "Computationally efficient learning in large-scale games: Sampled fictitious play revisited",

abstract = "Fictitious Play (FP) is a popular algorithm known to achieve Nash equilibrium learning in certain large-scale games. However, for games with many players, the computational demands of the FP algorithm can be prohibitive. Sampled FP (SFP) is a variant of FP that mitigates computational demands via a Monte Carlo approach. While SFP does mitigate the complexity of FP, it can be shown that SFP still uses information in an inefficient manner. The paper generalizes the SFP convergence result and studies a stochastic-approximation-based variant that significantly reduces the complexity of SFP.",

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

note = "Funding Information: The work was partially supported by the FCT project FCT [UID/EEA/50009/2013] through the Carnegie-Mellon/Portugal Program managed by ICTI from FCT, and was partially supported by NSF grant CIF-1513936 Publisher Copyright: {\textcopyright} 2016 IEEE.; 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016 ; Conference date: 06-11-2016 Through 09-11-2016",

year = "2017",

month = mar,

day = "1",

doi = "10.1109/ACSSC.2016.7869565",

language = "English (US)",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

publisher = "IEEE Computer Society",

pages = "1212--1215",

editor = "Matthews, \{Michael B.\}",

booktitle = "Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016",

address = "United States",

}

Swenson, B, Kar, S & Xavier, J 2017, Computationally efficient learning in large-scale games: Sampled fictitious play revisited. in MB Matthews (ed.), Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016., 7869565, Conference Record - Asilomar Conference on Signals, Systems and Computers, IEEE Computer Society, pp. 1212-1215, 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016, Pacific Grove, United States, 11/6/16. https://doi.org/10.1109/ACSSC.2016.7869565

Computationally efficient learning in large-scale games: Sampled fictitious play revisited. / Swenson, Brian; Kar, Soummya; Xavier, Joao.
Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. ed. / Michael B. Matthews. IEEE Computer Society, 2017. p. 1212-1215 7869565 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

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

TY - GEN

T1 - Computationally efficient learning in large-scale games

T2 - 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

AU - Swenson, Brian

AU - Kar, Soummya

AU - Xavier, Joao

N1 - Funding Information: The work was partially supported by the FCT project FCT [UID/EEA/50009/2013] through the Carnegie-Mellon/Portugal Program managed by ICTI from FCT, and was partially supported by NSF grant CIF-1513936 Publisher Copyright: © 2016 IEEE.

PY - 2017/3/1

Y1 - 2017/3/1

N2 - Fictitious Play (FP) is a popular algorithm known to achieve Nash equilibrium learning in certain large-scale games. However, for games with many players, the computational demands of the FP algorithm can be prohibitive. Sampled FP (SFP) is a variant of FP that mitigates computational demands via a Monte Carlo approach. While SFP does mitigate the complexity of FP, it can be shown that SFP still uses information in an inefficient manner. The paper generalizes the SFP convergence result and studies a stochastic-approximation-based variant that significantly reduces the complexity of SFP.

AB - Fictitious Play (FP) is a popular algorithm known to achieve Nash equilibrium learning in certain large-scale games. However, for games with many players, the computational demands of the FP algorithm can be prohibitive. Sampled FP (SFP) is a variant of FP that mitigates computational demands via a Monte Carlo approach. While SFP does mitigate the complexity of FP, it can be shown that SFP still uses information in an inefficient manner. The paper generalizes the SFP convergence result and studies a stochastic-approximation-based variant that significantly reduces the complexity of SFP.

UR - https://www.scopus.com/pages/publications/85016297573

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

U2 - 10.1109/ACSSC.2016.7869565

DO - 10.1109/ACSSC.2016.7869565

M3 - Conference contribution

AN - SCOPUS:85016297573

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1212

EP - 1215

BT - Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016

A2 - Matthews, Michael B.

PB - IEEE Computer Society

Y2 - 6 November 2016 through 9 November 2016

ER -

Swenson B, Kar S, Xavier J. Computationally efficient learning in large-scale games: Sampled fictitious play revisited. In Matthews MB, editor, Conference Record of the 50th Asilomar Conference on Signals, Systems and Computers, ACSSC 2016. IEEE Computer Society. 2017. p. 1212-1215. 7869565. (Conference Record - Asilomar Conference on Signals, Systems and Computers). doi: 10.1109/ACSSC.2016.7869565

Computationally efficient learning in large-scale games: Sampled fictitious play revisited

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this