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

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