東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

Learning Equilibria of Simulation-Ba...

Brown University., Department of Computer Science.

FindBook

Google Book

Amazon

博客來

Learning Equilibria of Simulation-Based Games: Applications to Empirical Mechanism Design.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Learning Equilibria of Simulation-Based Games: Applications to Empirical Mechanism Design./
作者:	Areyan Viqueira, Enrique.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
面頁冊數:	133 p.
附註:	Source: Dissertations Abstracts International, Volume: 83-01, Section: B.
Contained By:	Dissertations Abstracts International83-01B.
標題:	Game theory. -
電子資源:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28727129
ISBN:	9798534694246

Learning Equilibria of Simulation-Based Games: Applications to Empirical Mechanism Design.
Areyan Viqueira, Enrique.

Learning Equilibria of Simulation-Based Games: Applications to Empirical Mechanism Design. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 133 p.

Source: Dissertations Abstracts International, Volume: 83-01, Section: B.

Thesis (Ph.D.)--Brown University, 2021.

This item must not be sold to any third party vendors.

In this thesis, we first contribute to the empirical-game theoretic analysis (EGTA) literature both from a theoretical and a computational perspective. Theoretically, we present a mathematical framework to precisely describe simulation-based games and analyze their properties. In a simulation-based game, one only gets to observe samples of utility functions but never a complete analytical description. We provide results that complement and strengthen previous results on guarantees of the approximate Nash equilibria learned from samples. Computationally, we find and thoroughly evaluate Probably Approximate Correct (PAC) learning algorithms, which we show make frugal use of data to provably solve simulation-based games, up to a user's given error tolerance. Next, we turn our attention to mechanism design. When mechanism design depends on EGTA, it is called empirical mechanism design (EMD). Equipped with our EGTA framework, we further present contributions to EMD, in particular to parametric EMD. In parametric EMD, there is an overall (parameterized) mechanism (e.g., a second price auction with reserve prices as parameters). The choice of parameters then determines a mechanism (e.g., the reserve price being $10 instead of $100). Our EMD contributions are again two-fold. From a theoretical point of view, we formulate the problem of finding the optimal parameters of a mechanism as a black-box optimization problem. For the special case where the parameter space is finite, we present an algorithm that, with high probability, provably finds an approximate global optimal. For more general cases, we present a Bayesian optimization algorithm and empirically show its effectiveness. EMD is only as effective as the set of heuristic strategies used to optimize a mechanism's parameters. To demonstrate our methodology's effectiveness, we developed rich bidding heuristics in one specific domain: electronic advertisement auctions. These auctions are an instance of combinatorial auctions, a vastly important auction format used in practice to allocate many goods of interest (e.g., electromagnetic spectra). Our work on designing heuristics for electronic advertisement led us to contribute heuristics for the computation of approximate competitive (or Walrasian) equilibrium, work of interest in its own right.

ISBN: 9798534694246Subjects--Topical Terms:

532607
Game theory.
Subjects--Index Terms:

Game theory

Learning Equilibria of Simulation-Based Games: Applications to Empirical Mechanism Design.
LDR:03442nmm a2200349 4500 001 2283515
005 20211029101505.5
008 220723s2021 ||||||||||||||||| ||eng d
020 $a 9798534694246
035 $a (MiAaPQ)AAI28727129
035 $a (MiAaPQ)Brown_bdr_zhchjga9
035 $a AAI28727129
040 $a MiAaPQ $c MiAaPQ
100 1 $a Areyan Viqueira, Enrique. $3 3562485
245 1 0 $a Learning Equilibria of Simulation-Based Games: Applications to Empirical Mechanism Design.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 133 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-01, Section: B.
500 $a Advisor: Greenwald, Amy.
502 $a Thesis (Ph.D.)--Brown University, 2021.
506 $a This item must not be sold to any third party vendors.
520 $a In this thesis, we first contribute to the empirical-game theoretic analysis (EGTA) literature both from a theoretical and a computational perspective. Theoretically, we present a mathematical framework to precisely describe simulation-based games and analyze their properties. In a simulation-based game, one only gets to observe samples of utility functions but never a complete analytical description. We provide results that complement and strengthen previous results on guarantees of the approximate Nash equilibria learned from samples. Computationally, we find and thoroughly evaluate Probably Approximate Correct (PAC) learning algorithms, which we show make frugal use of data to provably solve simulation-based games, up to a user's given error tolerance. Next, we turn our attention to mechanism design. When mechanism design depends on EGTA, it is called empirical mechanism design (EMD). Equipped with our EGTA framework, we further present contributions to EMD, in particular to parametric EMD. In parametric EMD, there is an overall (parameterized) mechanism (e.g., a second price auction with reserve prices as parameters). The choice of parameters then determines a mechanism (e.g., the reserve price being $10 instead of $100). Our EMD contributions are again two-fold. From a theoretical point of view, we formulate the problem of finding the optimal parameters of a mechanism as a black-box optimization problem. For the special case where the parameter space is finite, we present an algorithm that, with high probability, provably finds an approximate global optimal. For more general cases, we present a Bayesian optimization algorithm and empirically show its effectiveness. EMD is only as effective as the set of heuristic strategies used to optimize a mechanism's parameters. To demonstrate our methodology's effectiveness, we developed rich bidding heuristics in one specific domain: electronic advertisement auctions. These auctions are an instance of combinatorial auctions, a vastly important auction format used in practice to allocate many goods of interest (e.g., electromagnetic spectra). Our work on designing heuristics for electronic advertisement led us to contribute heuristics for the computation of approximate competitive (or Walrasian) equilibrium, work of interest in its own right.
590 $a School code: 0024.
650 4 $a Game theory. $3 532607
650 4 $a Approximation. $3 3560410
650 4 $a Design. $3 518875
650 4 $a Algorithms. $3 536374
650 4 $a Heuristic. $3 568476
650 4 $a Applied mathematics. $3 2122814
650 4 $a Computer science. $3 523869
650 4 $a Auctions. $3 778937
650 4 $a Experiments. $3 525909
650 4 $a Equilibrium. $3 668417
650 4 $a Methods. $3 3560391
650 4 $a Libraries. $3 525303
650 4 $a Friendship. $3 611043
650 4 $a Simulation. $3 644748
650 4 $a Optimization. $3 891104
653 $a Game theory
653 $a Simulation-based games
690 $a 0389
690 $a 0984
690 $a 0364
710 2 $a Brown University. $b Department of Computer Science. $3 3562486
773 0 $t Dissertations Abstracts International $g 83-01B.
790 $a 0024
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28727129