東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Myopic Best-Response Learning in Lar...

Swenson, Brian Woodbury.

Linked to FindBook

Google Book

Amazon

博客來

Myopic Best-Response Learning in Large-Scale Games.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Myopic Best-Response Learning in Large-Scale Games./
Author:	Swenson, Brian Woodbury.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2017,
Description:	250 p.
Notes:	Source: Dissertation Abstracts International, Volume: 78-10(E), Section: B.
Contained By:	Dissertation Abstracts International78-10B(E).
Subject:	Engineering. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10282381
ISBN:	9781369778267

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

Myopic Best-Response Learning in Large-Scale Games. - Ann Arbor : ProQuest Dissertations & Theses, 2017 - 250 p.

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

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

This item is not available from ProQuest Dissertations & Theses.

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.

ISBN: 9781369778267Subjects--Topical Terms:

586835
Engineering.

Myopic Best-Response Learning in Large-Scale Games.
LDR:03438nmm a2200325 4500 001 2164279
005 20181106104111.5
008 190424s2017 ||||||||||||||||| ||eng d
020 $a 9781369778267
035 $a (MiAaPQ)AAI10282381
035 $a (MiAaPQ)cmu:10104
035 $a AAI10282381
040 $a MiAaPQ $c MiAaPQ
100 1 $a Swenson, Brian Woodbury. $3 3352324
245 1 0 $a Myopic Best-Response Learning in Large-Scale Games.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2017
300 $a 250 p.
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.
506 $a This item is not available from ProQuest Dissertations & Theses.
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.
590 $a School code: 0041.
650 4 $a Engineering. $3 586835
650 4 $a Applied mathematics. $3 2122814
690 $a 0537
690 $a 0364
710 2 $a Carnegie Mellon University. $b Electrical and Computer Engineering. $3 2094139
773 0 $t Dissertation Abstracts International $g 78-10B(E).
790 $a 0041
791 $a Ph.D.
792 $a 2017
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10282381