서브메뉴
검색
New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization
New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211152944
- ISBN
- 9798342138512
- DDC
- 300
- 저자명
- Zhao, Junyao.
- 서명/저자
- New Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization
- 발행사항
- [Sl] : Stanford University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 277 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-04, Section: B.
- 주기사항
- Advisor: Rubinstein, Aviad.
- 학위논문주기
- Thesis (Ph.D.)--Stanford University, 2024.
- 초록/해제
- 요약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.
- 일반주제명
- Auctions
- 일반주제명
- Protocol
- 일반주제명
- Communication
- 일반주제명
- Power
- 일반주제명
- Game theory
- 일반주제명
- Design
- 일반주제명
- Determinism
- 일반주제명
- Neighborhoods
- 일반주제명
- Theoretical mathematics
- 기타저자
- Stanford University.
- 기본자료저록
- Dissertations Abstracts International. 86-04B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017164290
■00520250211152944
■006m o d
■007cr#unu||||||||
■020 ▼a9798342138512
■035 ▼a(MiAaPQ)AAI31591794
■035 ▼a(MiAaPQ)Stanfordxv055zk4111
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a300
■1001 ▼aZhao, Junyao.
■24510▼aNew Separations and Beyond-Worst-Case Analysis in Algorithmic Game Theory and Submodular Optimization
■260 ▼a[Sl]▼bStanford University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a277 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-04, Section: B.
■500 ▼aAdvisor: Rubinstein, Aviad.
■5021 ▼aThesis (Ph.D.)--Stanford University, 2024.
■520 ▼aIn 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.
■590 ▼aSchool code: 0212.
■650 4▼aAuctions
■650 4▼aProtocol
■650 4▼aCommunication
■650 4▼aPower
■650 4▼aGame theory
■650 4▼aDesign
■650 4▼aDeterminism
■650 4▼aNeighborhoods
■650 4▼aTheoretical mathematics
■690 ▼a0389
■690 ▼a0459
■690 ▼a0642
■71020▼aStanford University.
■7730 ▼tDissertations Abstracts International▼g86-04B.
■790 ▼a0212
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17164290▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
