Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019, Proceedings (Lecture Notes in Computer Science Book 11801)

This book constitutes the refereed proceedings of the 12th International Symposium on Algorithmic Game Theory, SAGT 2019, held in Athens, Greece, in September/October 2019. The 25 full papers presented together with 3 invited talks and one abstract paper were carefully reviewed and selected from 55 submissions. The papers are organized in topical sections named: Algorithmic Mechanism Design; Auctions and Markets; Computational Aspects of Games; Network Games and Congestion Games; Social Choice; and Matchings and Fair Division. Front Matter ....Pages i-xix Front Matter ....Pages 1-1 Optimal On-Line Allocation Rules with Verification (Markos Epitropou, Rakesh Vohra)....Pages 3-17 Strategyproof Facility Location for Three Agents on a Circle (Reshef Meir)....Pages 18-33 Sharing Information with Competitors (Simina Brânzei, Claudio Orlandi, Guang Yang)....Pages 34-48 Mechanism Design for Locating a Facility Under Partial Information (Vijay Menon, Kate Larson)....Pages 49-62 Mechanism Design for Constrained Heterogeneous Facility Location (Maria Kyropoulou, Carmine Ventre, Xiaomeng Zhang)....Pages 63-76 Obvious Strategyproofness, Bounded Rationality and Approximation (Diodato Ferraioli, Carmine Ventre)....Pages 77-91 Front Matter ....Pages 93-93 Risk Robust Mechanism Design for a Prospect Theoretic Buyer (Siqi Liu, J. Benjamin Miller, Alexandros Psomas)....Pages 95-108 The Declining Price Anomaly Is Not Universal in Multi-buyer Sequential Auctions (But Almost Is) (Vishnu V. Narayan, Enguerrand Prebet, Adrian Vetta)....Pages 109-122 Risk-Free Bidding in Complement-Free Combinatorial Auctions (Vishnu V. Narayan, Gautam Rayaprolu, Adrian Vetta)....Pages 123-136 Front Matter ....Pages 137-137 On the Existence of Nash Equilibrium in Games with Resource-Bounded Players (Joseph Y. Halpern, Rafael Pass, Daniel Reichman)....Pages 139-152 On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria (Marie Louisa Tølbøll Berthelsen, Kristoffer Arnsfelt Hansen)....Pages 153-167 Computing Stackelberg Equilibria of Large General-Sum Games (Avrim Blum, Nika Haghtalab, MohammadTaghi Hajiaghayi, Saeed Seddighin)....Pages 168-182 Front Matter ....Pages 183-183 The Impact of Tribalism on Social Welfare (Seunghee Han, Matvey Soloviev, Yuwen Wang)....Pages 185-199 The Online Best Reply Algorithm for Resource Allocation Problems (Max Klimm, Daniel Schmand, Andreas Tönnis)....Pages 200-215 Connected Subgraph Defense Games (Eleni C. Akrida, Argyrios Deligkas, Themistoklis Melissourgos, Paul G. Spirakis)....Pages 216-236 Principal-Agent Problems with Present-Biased Agents (Sigal Oren, Dolav Soker)....Pages 237-251 On a Simple Hedonic Game with Graph-Restricted Communication (Vittorio Bilò, Laurent Gourvès, Jérôme Monnot)....Pages 252-265 Front Matter ....Pages 267-267 Impartial Selection with Additive Approximation Guarantees (Ioannis Caragiannis, George Christodoulou, Nicos Protopapas)....Pages 269-283 The Convergence of Iterative Delegations in Liquid Democracy in a Social Network (Bruno Escoffier, Hugo Gilbert, Adèle Pass-Lanneau)....Pages 284-297 Optimal Truth-Tracking Rules for the Aggregation of Incomplete Judgments (Zoi Terzopoulou, Ulle Endriss)....Pages 298-311 The Distortion of Distributed Voting (Aris Filos-Ratsikas, Evi Micha, Alexandros A. Voudouris)....Pages 312-325 Front Matter ....Pages 327-327 On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences (Chi-Kit Lam, C. Gregory Plaxton)....Pages 329-342 Maximum Stable Matching with One-Sided Ties of Bounded Length (Chi-Kit Lam, C. Gregory Plaxton)....Pages 343-356 Stochastic Matching on Uniformly Sparse Graphs (Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, Nima Reyhani)....Pages 357-373 Fair Division with Subsidy (Daniel Halpern, Nisarg Shah)....Pages 374-389 Correction to: Algorithmic Game Theory (Dimitris Fotakis, Evangelos Markakis)....Pages C1-C1 Back Matter ....Pages 391-393