東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

New Separations and Beyond-Worst-Cas...

Zhao, Junyao,

Linked to FindBook

Google Book

Amazon

博客來

New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization /

Record Type:	Electronic resources : Monograph/item
Title/Author:	New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization // Junyao Zhao.
Author:	Zhao, Junyao,
Description:	1 electronic resource (277 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 86-04, Section: B.
Contained By:	Dissertations Abstracts International86-04B.
Subject:	Auctions. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31591794
ISBN:	9798342138512

New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization /
Zhao, Junyao,

New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization /Junyao Zhao. - 1 electronic resource (277 pages)

Source: Dissertations Abstracts International, Volume: 86-04, Section: B.

In algorithmic game theory, we analyze games and design mechanisms through computational lens. We prefer mechanisms that are simple, deterministic and incentive compatible because of their practicability. However, such mechanisms might obtain suboptimal value or require heavier computation compared to their counterparts without those restrictions. Part I of this thesis advances our understanding of the trade-off between simplicity/determinism/incentive compatibility and economic/computational efficiency by proving several near-tight separation results for central problems in algorithmic game theory such as optimal auction, contract design and social choice problem.In Part II of this thesis, we study various problems in algorithmic game theory and submodular optimization, such as cardinality-constrained submodular maximization, budget-feasible mechanism design and repeated first-price auction, under beyond-worst-case assumptions that model problem structure and user behavior in real-world applications; we investigate whether we can design algorithms/mechanisms/strategies with provably better performance than the best we can hope for in worst-case analysis.

English

ISBN: 9798342138512Subjects--Topical Terms:

778937
Auctions.

New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization /
LDR:02516nmm a22003853i 4500 001 2432447
005 20250707081504.5
006 m o d
007 cr|nu||||||||
008 261011s2024 miu||||||m |||||||eng d
020 $a 9798342138512
035 $a (MiAaPQD)AAI31591794
035 $a (MiAaPQD)Stanfordxv055zk4111
035 $a AAI31591794
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Zhao, Junyao, $e author. $3 3821671
245 1 0 $a New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization / $c Junyao Zhao.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2024
300 $a 1 electronic resource (277 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: Dissertations Abstracts International, Volume: 86-04, Section: B.
500 $a Advisors: Rubinstein, Aviad Committee members: Anari, Nima; Vondrák, Jan; Bent, Stacey F.
502 $b Ph.D. $c Stanford University $d 2024.
520 $a In algorithmic game theory, we analyze games and design mechanisms through computational lens. We prefer mechanisms that are simple, deterministic and incentive compatible because of their practicability. However, such mechanisms might obtain suboptimal value or require heavier computation compared to their counterparts without those restrictions. Part I of this thesis advances our understanding of the trade-off between simplicity/determinism/incentive compatibility and economic/computational efficiency by proving several near-tight separation results for central problems in algorithmic game theory such as optimal auction, contract design and social choice problem.In Part II of this thesis, we study various problems in algorithmic game theory and submodular optimization, such as cardinality-constrained submodular maximization, budget-feasible mechanism design and repeated first-price auction, under beyond-worst-case assumptions that model problem structure and user behavior in real-world applications; we investigate whether we can design algorithms/mechanisms/strategies with provably better performance than the best we can hope for in worst-case analysis.
546 $a English
590 $a School code: 0212
650 4 $a Auctions. $3 778937
650 4 $a Protocol. $3 3564384
650 4 $a Communication. $3 524709
650 4 $a Power. $3 518736
650 4 $a Game theory. $3 532607
650 4 $a Design. $3 518875
650 4 $a Determinism. $3 3561000
650 4 $a Neighborhoods. $3 993475
650 4 $a Theoretical mathematics. $3 3173530
690 $a 0389
690 $a 0459
690 $a 0642
710 2 $a Stanford University. $e degree granting institution. $3 3765820
720 1 $a Rubinstein, Aviad $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-04B.
790 $a 0212
791 $a Ph.D.
792 $a 2024
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31591794