國立虎尾科技大學 |

Myopic Best-Response Learning in Large-Scale Games.

紀錄類型:	書目-語言資料,手稿 : Monograph/item
正題名/作者:	Myopic Best-Response Learning in Large-Scale Games./
作者:	Swenson, Brian Woodbury.
面頁冊數:	1 online resource (250 pages)
附註:	Source: Dissertation Abstracts International, Volume: 78-10(E), Section: B.
Contained By:	Dissertation Abstracts International78-10B(E).
標題:	Engineering. -
電子資源:	click for full text (PQDT)
ISBN:	9781369778267

Myopic Best-Response Learning in Large-Scale Games.
Swenson, Brian Woodbury.

Myopic Best-Response Learning in Large-Scale Games. - 1 online resource (250 pages)

Source: Dissertation Abstracts International, Volume: 78-10(E), Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2017.

Includes bibliographical references

This dissertation studies multi-agent algorithms for learning Nash equilibrium strategies in games with many players. We focus our study on a set of learning dynamics in which agents seek to myopically optimize their next-stage utility given some forecast of opponent behavior; i.e., players act according to myopic best response dynamics. The prototypical algorithm in this class is the well-known fictitious play (FP) algorithm. FP dynamics are intuitively simple and can be seen as the "natural" learning dynamics associated with the Nash equilibrium concept. Accordingly, FP has received extensive study over the years and has been used in a variety of applications. Our contributions may be divided into two main research areas. First, we study fundamental properties of myopic best response (MBR) dynamics in large-scale games. We have three main contributions in this area. (i) We characterize the robustness of MBR dynamics to a class of perturbations common in real-world applications. (ii) We study FP dynamics in the important class of large-scale games known as potential games. We show that for almost all potential games and for almost all initial conditions, FP converges to a pure-strategy (deterministic) equilibrium. (iii) We develop tools to characterize the rate of convergence of MBR algorithms in potential games. In particular, we show that the rate of convergence of FP is "almost always" exponential in potential games.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9781369778267Subjects--Topical Terms:

561152
Engineering.
Index Terms--Genre/Form:

554714
Electronic books.

Myopic Best-Response Learning in Large-Scale Games.
LDR:03640ntm a2200349Ki 4500 001 918796
005 20181106104111.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9781369778267
035 $a (MiAaPQ)AAI10282381
035 $a (MiAaPQ)cmu:10104
035 $a AAI10282381
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Swenson, Brian Woodbury. $3 1193218
245 1 0 $a Myopic Best-Response Learning in Large-Scale Games.
264 0 $c 2017
300 $a 1 online resource (250 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 78-10(E), Section: B.
500 $a Adviser: Soummya Kar.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2017.
504 $a Includes bibliographical references
520 $a This dissertation studies multi-agent algorithms for learning Nash equilibrium strategies in games with many players. We focus our study on a set of learning dynamics in which agents seek to myopically optimize their next-stage utility given some forecast of opponent behavior; i.e., players act according to myopic best response dynamics. The prototypical algorithm in this class is the well-known fictitious play (FP) algorithm. FP dynamics are intuitively simple and can be seen as the "natural" learning dynamics associated with the Nash equilibrium concept. Accordingly, FP has received extensive study over the years and has been used in a variety of applications. Our contributions may be divided into two main research areas. First, we study fundamental properties of myopic best response (MBR) dynamics in large-scale games. We have three main contributions in this area. (i) We characterize the robustness of MBR dynamics to a class of perturbations common in real-world applications. (ii) We study FP dynamics in the important class of large-scale games known as potential games. We show that for almost all potential games and for almost all initial conditions, FP converges to a pure-strategy (deterministic) equilibrium. (iii) We develop tools to characterize the rate of convergence of MBR algorithms in potential games. In particular, we show that the rate of convergence of FP is "almost always" exponential in potential games.
520 $a Our second research focus concerns implementation of MBR learning dynamics in large-scale games. MBR dynamics can be shown, theoretically, to converge to equilibrium strategies in important classes of large-scale games (e.g., potential games). However, despite theoretical convergence guarantees, MBR dynamics can be extremely impractical to implement in large games due to demanding requirements in terms of computational capacity, information overhead, communication infrastructure, and global synchronization. Using the aforementioned robustness result, we study practical methods to mitigate each of these issues. We place a special emphasis on studying algorithms that may be implemented in a network-based setting, i.e., a setting in which inter-agent communication is restricted to a (possibly sparse) overlaid communication graph. Within the network-based setting, we also study the use of so-called "inertia" in MBR algorithms as a tool for learning pure-strategy NE.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Engineering. $3 561152
650 4 $a Applied mathematics. $3 1069907
655 7 $a Electronic books. $2 local $3 554714
690 $a 0537
690 $a 0364
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Carnegie Mellon University. $b Electrical and Computer Engineering. $3 1182305
773 0 $t Dissertation Abstracts International $g 78-10B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10282381 $z click for full text (PQDT)