Algorithmic game theory : 15th International Symposium, SAGT 2022, Colchester, UK, September 12-15, 2022, proceedings / / Panagiotis Kanellopoulos, Maria Kyropoulou and Alexandros Voudouris, editors

• Pubblicazione: Cham, Switzerland : , : Springer Nature Switzerland AG, , [2022]; ©2022
• Descrizione fisica: 1 online resource (596 pages)
• Disciplina: 518.1
• Soggetto topico: Algorithms; Game theory
• Persona (resp. second.): KyropoulouMaria; KanellopoulosPanagiotis; VoudourisAlexandros
• Note generali: Includes index.
• Nota di contenuto: Intro -- Preface -- Organization -- Abstracts of Invited Talks -- New Fairness Concepts for Allocating Indivisible Items -- Decentralizing Information Technology: The Advent of Resource Based Systems -- Algorithmic Game Theory Meets Behavioral Economics -- Contents -- Invited Talk -- Decentralizing Information Technology: The Advent of Resource Based Systems -- 1 Introduction -- 2 Fundamental Characteristics of Resource Based Systems -- 3 Resource-Based Participation -- 4 Tokenomics -- 5 Decentralized Service Provision -- 6 Rewards Sharing -- 7 A High-Level Blueprint for a Stake-Based System -- 8 Concluding Remarks -- References -- Auctions, Markets and Mechanism Design -- How Bad is the Merger Paradox? -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work -- 2 Model -- 2.1 Known Properties of Cournot Markets -- 3 Markets with Concave Demand -- 4 Markets with Affine Demand -- 4.1 Warm Up - Affine Demand, Linear Costs -- 4.2 Main Result -- 4.3 Arbitrarily High Losses Due to Merging -- References -- Greater Flexibility in Mechanism Design Through Altruism -- 1 Introduction -- 2 Preliminaries -- 3 Modeling Other-Regarding Preferences -- 3.1 Utility Model with Other-Regarding Preferences -- 3.2 Characterization of Truthful Mechanisms -- 3.3 Design Template -- 4 Minimizing Payments -- 5 A Case Study: Altruism -- 5.1 Two Altruism Models and Design Objectives -- 5.2 Mechanisms for Altruistic Players -- 5.3 Discussion -- 6 Impact of Altruism -- 6.1 Bilateral Trade -- 6.2 Funding a Public Project -- 6.3 Minimizing Payments -- 7 Conclusion -- References -- Lookahead Auctions with Pooling -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work -- 2 Preliminaries -- 3 LAP for Independent Valuations -- 3.1 Extension to Irregular Distributions -- 4 LAP for Correlated Values -- A Truthfulness of LAP -- References. ; Budget Feasible Mechanisms for Procurement Auctions with Divisible Agents -- 1 Introduction -- 2 Preliminaries -- 3 Linear Valuation Functions -- 4 Competitive Markets -- 5 Agent Types with Capped Linear Valuation Functions -- 6 Conclusion and Future Work -- References -- On Improved Interval Cover Mechanisms for Crowdsourcing Markets -- 1 Introduction -- 2 Preliminaries -- 3 An Improved Truthful Approximation Mechanism -- 4 A Truthful FPTAS for a Small Number of Tasks -- 4.1 A Pseudopolynomial Dynamic Programming Algorithm -- 4.2 The FPTAS -- 5 Further Implications and Extensions -- 5.1 Relation to Unsplittable Flow Problems and (In)approximability -- 5.2 Generalization to Non-interval Structures -- 6 Discussion and Open Problems -- References -- Explicitly Simple Near-Tie Auctions -- 1 Introduction -- 1.1 Contribution -- 1.2 Related Literature -- 2 Preliminaries -- 2.1 The Myerson Lemma -- 2.2 Explicit Representation -- 3 Complexity of the Myerson Payment Rule -- 3.1 Two Agents -- 3.2 Beyond Two Agents -- 4 Explicitly Simple Auctions -- 4.1 Conditions for Strategyproofness -- 5 Two-State PSAs and Near-Ties -- 5.1 Identifying All Boundary and Tie Profiles -- 5.2 Indifference Constraints -- 5.3 Explicitly Simple Implementation for Single-Top PSA -- 5.4 Beyond the Two States Solution -- 6 Conclusion -- References -- Computational Aspects in Games -- Simultaneous Contests with Equal Sharing Allocation of Prizes: Computational Complexity and Price of Anarchy -- 1 Introduction -- 1.1 Our Results -- 1.2 Related Work -- 2 General Model, Pure Nash Equilibrium, and Price of Anarchy -- 2.1 Existence of Pure-Strategy Nash Equilibrium -- 2.2 Approximate Pure-Strategy Nash Equilibrium Using Better-Response -- 2.3 Social Welfare, Price of Anarchy, and Price of Stability -- 3 Multi-activity Games: Hardness of Best-Response. ; 4 Single-Activity Games: PPADPLS-Completeness -- 5 Conclusion and Future Work -- References -- Complexity of Public Goods Games on Graphs -- 1 Introduction -- 2 Model and Notation -- 3 Hardness of the Single-Neighbor Pattern -- 4 Algorithm for the At-Most-Single-Neighbor Pattern -- 5 More Hard Patterns -- 5.1 Flat Patterns -- 5.2 Sloped Patterns -- 5.3 Sharp Patterns Followed by Two 1's -- 5.4 Adding 1,0 to Non-flat Patterns -- References -- PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games -- 1 Introduction -- 1.1 Background, Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Basic Game Theoretic and Complexity Concepts -- 2.2 Lipschitz Polymatrix Games -- 3 Results -- 3.1 Containment in PPAD -- 3.2 Hardness for PPAD -- 4 Upper Bound for Additional Actions -- 5 Discussion -- References -- Seniorities and Minimal Clearing in Financial Network Games -- 1 Introduction -- 2 Clearing Games -- 3 Clearing Games with Seniorities -- 3.1 Max-Clearing -- 3.2 Min-Clearing -- 4 Clearing Games with Fixed Seniorities -- References -- Financial Networks with Singleton Liability Priorities -- 1 Introduction -- 2 Model and Preliminaries -- 3 Hardness of cds-priority-clearing -- 4 Hardness of Deciding the Best Priority Profile -- 5 Conclusions and Future Work -- References -- Automated Equilibrium Analysis of 222 Games -- 1 Introduction -- 2 General Form of the Game -- 3 Partially Mixed Equilibria -- 4 Completely Mixed Equilibria -- 4.1 Finding the Completely Mixed Equilibria Algebraically -- 4.2 Displaying Best-Response Surfaces -- 4.3 A Well-Known Example -- 5 Conclusions -- References -- Congestion and Network Creation Games -- An Improved Bound for the Tree Conjecture in Network Creation Games -- 1 Introduction -- 1.1 Background -- 2 Preliminaries -- 2.1 Min-Cycles -- 2.2 Basic Strategic Options or a Vertex -- 3 Equilibria Conditions. ; 3.1 Biconnected Components -- 3.2 The Key Lemma -- 4 The Tree Conjecture Holds for > -- 3(n-1) -- 5 Conclusion -- References -- A Common Generalization of Budget Games and Congestion Games -- 1 Introduction -- 2 Preliminaries -- 2.1 Matroids -- 2.2 Previous Models -- 3 Our Model: Generalized Budget Games -- 3.1 Model -- 3.2 Special Cases -- 4 PNE in Matroid g-Budget Games -- 5 Singleton g-Budget Games -- 5.1 Computing a PNE in Linear Time -- 5.2 Remark on the Reverse Player Order -- 6 Discussion -- References -- Cost-Sharing Games with Rank-Based Utilities -- 1 Introduction -- 2 Model and Preliminaries -- 2.1 Our Results -- 2.2 Related Work -- 3 General Singleton CSRB-Games -- 3.1 Symmetric CSRB-Games -- 3.2 Small Number of Resources or Players -- 4 CSRB-Games with Unit-Cost Resources -- 5 Fair CSRB-Games -- 6 Conclusions and Open Problems -- References -- On Tree Equilibria in Max-Distance Network Creation Games -- 1 Introduction -- 2 Related Work -- 3 Game Model -- 4 Equilibrium Graphs -- 4.1 Cycles in the Equilibrium Graph -- 4.2 Lower Bound for Average Degree -- 4.3 Upper Bound on Average Degree -- 4.4 Tree Nash Equilibria and Price of Anarchy -- 5 Conclusion -- References -- On the Impact of Player Capability on Congestion Games -- 1 Introduction -- 2 Distance-Bounded Network Congestion Game -- 2.1 Distance-Bounded Network Congestion Game with Default Action -- 3 Impact of Player Capability on Social Welfare in DncDa -- 4 Gold and Mines Game -- 5 Impact of Player Capability on Social Welfare in GMG -- 6 Case Study: Alternating Ordering Game -- References -- Data Sharing and Learning -- Learning Approximately Optimal Contracts -- 1 Introduction -- 1.1 The Challenge of Learning Contracts with Risk Averse Agents -- 2 Preliminaries -- 2.1 Multi-armed Bandit -- 3 Main Technical Result -- 3.1 Learnable Contracts -- 3.2 Algorithm. ; 3.3 Discretization of the Contract Space -- 4 Applications -- 5 Conclusions -- References -- Coopetition Against an Amazon -- 1 Introduction -- 2 Model and Preliminaries -- 3 Jointly Complete Information -- 4 No Jointly Complete Information -- 5 Do Players Share More with or Without an Amazon? -- 6 Conclusion -- References -- Data Curation from Privacy-Aware Agents -- 1 Introduction -- 2 The Model -- 2.1 A Preliminary Result -- 3 Informational Profitability -- 4 The Competitive Protocol -- 4.1 Uniqueness -- 4.2 Existence -- 4.3 Optimality -- 5 Beyond Equilibrium - Fair Competitive Protocol -- References -- Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games -- 1 Introduction -- 2 Preliminaries -- 2.1 Two-Player Extensive Form Games -- 2.2 Two-Player Extensive Form Games in Sequence Form -- 2.3 Optimistic Mirror Descent -- 3 Our Setting -- 3.1 Network Zero-Sum Extensive Form Games -- 3.2 Network Extensive Form Games in Sequence Form -- 4 Our Convergence Results -- 5 Experimental Results -- 6 Conclusion -- References -- Social Choice and Stable Matchings -- Decentralized Update Selection with Semi-strategic Experts -- 1 Introduction -- 1.1 Our Contributions -- 1.2 Related Work -- 2 Preliminaries -- 3 Approval Voting -- 3.1 Approximate Equilibria of MAV -- 3.2 Price of Anarchy of MAV -- 4 The Repeated Game -- 5 Conclusions and Open Problems -- References -- Fair Ride Allocation on a Line -- 1 Introduction -- 2 Model -- 3 Solution Concepts -- 4 Stable and Socially Optimal Allocations -- 5 Envy-Free Allocations -- 5.1 Constant Number of Taxis -- 5.2 Small Number of Types -- 5.3 Constant Capacity -- 5.4 Hardness Results -- 6 Conclusion -- References -- Stable Matching with Multilayer Approval Preferences: Approvals Can Be Harder Than Strict Preferences -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions. ; 2 Preliminaries.
• Titolo autorizzato: Algorithmic Game Theory
• ISBN: 3-031-15714-1
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996490363803316
• Lo trovi qui: Univ. di Salerno
• Serie: Lecture notes in computer science ; ; 13584.