Algorithmic Game Theory: 15th International Symposium, SAGT 2022, Colchester, UK, September 12–15, 2022, Proceedings (Lecture Notes in Computer Science, 13584)

Description

This book constitutes the proceedings of the 15th International Symposium on Algorithmic Game Theory, SAGT 2022, which took place in Colchester, UK, in September 2022. The 31 full papers included in this book were carefully reviewed and selected from 83 submissions. They were organized in topical sections as follows: Auctions, markets and mechanism design; computational aspects in games; congestion and network creation games; data sharing and learning; social choice and stable matchings. 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 3 Weak Stability 4 Strong Stability 5 Super Stability 6 Similarity Leads to Tractability 7 Conclusion References Collective Schedules: Axioms and Algorithms 1 Introduction 2 Preliminaries 3 Axiomatic Properties 3.1 Neutrality and PTA Neutrality 3.2 Distance 3.3 PTA Condorcet Consistency 3.4 Incompatibilities Between Axioms and Properties 3.5 Length Reduction Monotonicity 3.6 Reinforcement 3.7 Unanimity 3.8 Summary 4 Computational Complexity and Algorithms 5 Experiments 6 Discussion and Conclusion References Justifying Groups in Multiwinner Approval Voting 1 Introduction 1.1 Our Contribution 2 Preliminaries 3 General Guarantees 4 Instance-Specific Optimization 4.1 GreedyCC 4.2 GreedyCandidate 4.3 Tree Representation 5 Gender Balance 6 Experiments 6.1 Set-up 6.2 Empirical Evaluation of Theorem 1 6.3 Performance of GreedyCC and GreedyCandidate 7 Conclusion and Future Work References Fairness in Temporal Slot Assignment 1 Introduction 1.1 Our Contributions 1.2 Related Work 2 Preliminaries 2.1 Model 2.2 Welfare and Fairness Concepts 3 Welfare and Fairness with Constant Number of Agents 3.1 A General-Purpose Randomized Algorithm 3.2 PROP1 Outcomes Exist for Two Agents 4 Beyond a Constant Number of Agents 4.1 Utilitarian Social Welfare 4.2 Egalitarian Social Welfare 4.3 Equitability 4.4 Proportionality 5 Conclusion and Future Work References Gehrlein Stable Committee with Multi-modal Preferences 1 Introduction 2 Preliminaries 3 Global Stability 4 Individual Stability 4.1 Intractable Cases 4.2 Tractable Cases 5 Pairwise Stability 6 Conclusion References Online Max-min Fair Allocation 1 Introduction 1.1 Related Work 1.2 Our Results 2 Preliminaries 3 Algorithms for Adversarial Arrival 3.1 Randomized Algorithm 3.2 Derandomization 4 Algorithm for i.i.d. Arrival 5 Impossibilities for Adversarial Arrival 6 Impossibilities for i.i.d. Arrival 7 Concluding Remarks References Incomplete List Setting of the Hospitals/Residents Problem with Maximally Satisfying Lower Quotas 1 Introduction 2 Problem Definition 3 Algorithm 4 Maximum Gaps and Approximation Factors 4.1 Marriage Model 4.2 Uniform Model 4.3 General Model and R-side ML Model 5 Inapproximability Results 5.1 Uniform Model 5.2 Other Models 6 Conclusion References Strategic Voting in the Context of Stable-Matching of Teams 1 Introduction 2 Related Work 3 Preliminaries 4 Men's Side 4.1 Single Manipulator 4.2 Coalitional Manipulation 5 Women's Side 5.1 Single Manipulator 5.2 Coalitional Manipulation 6 Conclusion References Abstracts Competition and Recall in Selection Problems References Optimality of the Coordinate-Wise Median Mechanism for Strategyproof Facility Location in Two Dimensions References Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics Author Index