Web and Internet Economics: 17th International Conference, WINE 2021, Potsdam, Germany, December 14–17, 2021, Proceedings (Lecture Notes in Computer Science, 13112)

Preface
Organization
Contents
Mechanism Design and Pricing
Two-Way Greedy: Algorithms for Imperfect Rationality
	1 Introduction
	2 Preliminaries and Notation
	3 A Characterization of OSP Mechanisms
		3.1 OSP is Equivalent to Weak Interleaving
	4 Two-Way Greedy Algorithms
	5 Conclusions
	References
Bayesian Persuasion in Sequential Trials
	1 Introduction
	2 Problem Formulation
		2.1 Model of Binary-Outcome Experiments in Two-Phase Trials
	3 Binary-Outcome Experiments in Two-Phase Trials
		3.1 Experiments with Screenings
		3.2 Assumptions and Induced Strategies
		3.3 Constraints Given by Phase-II Experiments
		3.4 Persuasion Ratio and the Optimal Signaling Structure
		3.5 Comparison with Classical Bayesian Persuasion Strategies
	4 Binary-Outcome Experiments in Multi-phase Trials
		4.1 Model of Binary-Outcome Experiments in Multi-phase Trials
		4.2 Determined Versus Sender-Designed Experiments
		4.3 Multi-phase Model and Classical Bayesian Persuasion
	References
The Optimality of Upgrade Pricing
	1 Introduction
		1.1 Motivation and Results
		1.2 Related Literature
		1.3 Structure of the Paper
	2 Model
	3 Optimal Mechanisms for Regular Distributions
		3.1 Duality
		3.2 A Sufficient Condition for Regular Distributions
	4 Optimal Mechanisms for Non-regular Distributions
	5 Upgrade Pricing and Separate Pricing
	6 Conclusion
	References
On Symmetries in Multi-dimensional Mechanism Design
	1 Introduction
		1.1 Results and Technical Highlights
		1.2 Related Work
	2 Preliminaries
	3 Main Result: BRev is a Constant-Factor Approximation to SymRev
		3.1 Comparing BRev to SSRev
	4 Conclusions
	References
Welfare-Preserving -BIC to BIC Transformation with Negligible Revenue Loss
	1 Introduction
		1.1 Model and Notation
		1.2 Previous -BIC to BIC Transformations
		1.3 Our Contributions
		1.4 Our Techniques
	2 Warm-Up: Single Agent with Uniform Type Distribution
		2.1 Lower Bound on Revenue Loss
		2.2 Tighter Bound of Revenue Loss for Settings with Finite Menus
	3 Single Agent with General Type Distribution
		3.1 -BIC to BIC Transformation
		3.2 Impossibility Result for -EEIC Transformation
	4 Multiple Agents with Independent Private Types
		4.1 Impossibility Results
	5 Application to Automated Mechanism Design
	References
Strategyproof Facility Location in Perturbation Stable Instances
	1 Introduction
		1.1 Other Related Work
	2 Notation, Definitions and Preliminaries
	3 Perturbation Stability: Definition and Properties
	4 Optimal is Strategyproof for (2+3)-Stable Instances
	5 Dealing with Singleton Deviations Deterministically
	6 Inapproximability by Deterministic Mechanisms
	7 A Randomized O(1)-Approximate Mechanism
	References
Contract Design for Afforestation Programs
	1 Introduction
	2 Model
		2.1 The Principal\'s Problem
	3 Computing the Optimal Contract
		3.1 The Agent\'s Perspective
		3.2 Encoding the Principal\'s Problem
		3.3 How Much to Pay
		3.4 Computation
		3.5 Discussion: Payment to Maintain a Mature Tree
	4 Special Case: Uniform Costs
		4.1 The Agent\'s Perspective – Uniform Costs
		4.2 Who Drops Out and When
		4.3 Structure of Optimal Payments Under Uniform Costs
	5 Application: Optimal Payments for Real-World Cost Data
		5.1 Restricting the Pool of Agents
		5.2 Robustness Checks
	6 Limitations and Extensions
	References
Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching
	1 Introduction
		1.1 Our Results and Techniques
		1.2 Roapmap
	2 A Local-Lemma-Type Probability Statement
	3 Sequential Posted Pricing
	4 Prophet Inequality
		4.1 A Uniform Threshold Policy
		4.2 Non-uniform Threshold Strategies
	5 Matchings in Random Bipartite Graphs
		5.1 A Tight Upper Bound
	References
Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness
	1 Introduction
	2 Preliminaries
		2.1 Fairness Notions
		2.2 Mechanisms and Equilibria
	3 Fairness of Nash Equilibria of Round-Robin
	4 Towards EFX Equilibria: The Case of Two Agents
		4.1 A Mechanism with EFX Nash Equilibria
		4.2 The Enhanced Fairness of EFX Nash Equilibria
	5 Discussion
	References
On the Benefits of Being Constrained When Receiving Signals
	1 Introduction
		1.1 The Model: An Overview
		1.2 Our Results
		1.3 Related Work
	2 Problem Formulation
		2.1 State of the World, Actions, and Utilities
		2.2 Signaling Schemes
		2.3 Constrained Receiver
	3 Our Main Result
		3.1 Necessity of Partial Alignment
	4 Failure of the Main Result with Larger State Spaces
	5 Discussion
		5.1 Larger State/Action Spaces
		5.2 Finding Optimal Signaling Schemes
		5.3 Receiver\'s Strategic Behaviors on Constraint Enforcement
	References
Towards a Characterization of Worst Case Equilibria in the Discriminatory Price Auction
	1 Introduction
		1.1 Contribution
		1.2 Related Work
	2 Notation and Definitions
	3 Towards a Characterization of Inefficient Mixed Equilibria
		3.1 Mixed Nash Equilibria with Demand Revelation
		3.2 Existence of Non-empty-handed Bidders
		3.3 The Support and the CDFs of Mixed Nash Equilibria
	4 Price of Anarchy for Mixed Equilibria
		4.1 The Case of Two Bidders
		4.2 Multiple Bidders
	5 A Separation Between Mixed and Bayesian Cases
	References
Matching, Markets and Equilibria
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
	1 Introduction
		1.1 Our Contributions
	2 Background
	3 Relaxing Assumptions
	4 LP Formulation
		4.1 Formulating the Constraints
		4.2 Formulating the Objective
		4.3 Extending the Discretized Function to the Unit Square
	5 Checking the Bound
	6 Computational Results
		6.1 Precomputing Tables
		6.2 Parallelization
	7 Limits of Our Method
	8 Conclusion
	References
Beyond Pigouvian Taxes: A Worst Case Analysis
	1 Introduction
		1.1 Public-Good Congestion Games
		1.2 Ride Sharing Games
		1.3 Related Work
	2 The Model
	3 Bounds on TPoA
	4 Ride Sharing Games
		4.1 Ride Sharing Game Definition
		4.2 Examples of Ride Sharing Games
		4.3 Results for Ride Sharing Games
	5 Externality on Public Good Users only (Train)
	References
The Core of Housing Markets from an Agent\'s Perspective: Is It Worth Sprucing Up Your Home?
	1 Introduction
		1.1 Our Contribution
		1.2 Related Work
	2 Preliminaries
	3 The Core of Housing Markets: Some Computational Problems
		3.1 Top Trading Cycles for Preferences with Incomparability
		3.2 Allocations in the Core with Arc Restrictions
		3.3 Maximizing the Number of Agents Trading in a Core Allocation
	4 The Effect of Improvements in Housing Markets
		4.1 Description of Algorithm HM-Improve
		4.2 Correctness of Algorithm HM-Improve
		4.3 Strict Improvement
	5 The Effect of Improvements in Stable Roommates
	6 Further Research
	References
Mechanisms for Trading Durable Goods
	1 Introduction
	2 Model
	3 A Strategyproof l-Approximation Algorithm
		3.1 Computing an Optimal Static Execution
		3.2 A Strategyproof Algorithm for Computing an Optimal Static Execution
	4 Limitations of Dynamic Executions
		4.1 Pareto Efficiency and Strategyproofness
		4.2 Computational Hardness
	5 Conclusion and Discussion
	References
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
	1 Introduction
		1.1 Greedy Algorithms
		1.2 Randomized Partition Algorithms
		1.3 Related Work and Brief Summary
	2 Preliminaries
	3 Greedy Algorithms
		3.1 A Class of Greedy Algorithms
		3.2 Hard Instance: The Hat
		3.3 Main Result: Ruling out all Greedy Algorithms
	4 Randomized Partition Algorithms
		4.1 Defining Randomized Partition Algorithms
		4.2 Randomized Partitions
	References
Threshold Tests as Quality Signals: Optimal Strategies, Equilibria, and Price of Anarchy
	1 Introduction
		1.1 Other Applications and Model Discussion
		1.2 Our Results
	2 Model and Preliminaries
		2.1 Qualities, Tests and Selection
		2.2 Endogenous Test Selection and Quantile Thresholds
		2.3 Extension to More Firms
	3 Optimal I.I.D. Tests
		3.1 Characterizing the Expected-Inversions Functional
		3.2 Optimizing the Objective Function
	4 Optimal Correlated Tests
	5 Endogenous Test Selection and Price of Anarchy
	6 Endogenous Test Selection with Restricted Tests
		6.1 Suboptimality of All Symmetric Equilibria
	7 Conclusions
	References
The Platform Design Problem
	1 Introduction
	2 PDP: Intractability of the General Case
	3 Flower Case: The Agent\'s Problem
		3.1 The Greedy Algorithm
	4 Flower Case: The Designer\'s Problem
		4.1 FPTAS for the PDP
	5 Discussion and Future Work
	References
A Consumer-Theoretic Characterization of Fisher Market Equilibria
	1 Introduction
	2 Preliminaries and an Overview of Results
		2.1 Consumer Theory
		2.2 Fisher Markets
		2.3 Subdifferential Calculus and Generalized Gradient Descent
		2.4 A High-level Overview of Our Contributions
	3 A New Convex Program for CCH Fisher Markets
	4 Equivalence of Mirror Descent and Tâtonnement
	5 Convergence of Discrete Tâtonnement
	6 Conclusion
	References
Learning, Fairness, Privacy and Behavioral Models
A Tight Negative Example for MMS Fair Allocations
	1 Introduction
		1.1 Our Results
		1.2 Related Work
		1.3 Preliminaries
	2 An MMS Gap of 140
	3 MMS Gaps that Are Inverse Polynomial in the Number of Agents
	4 An MMS Allocation Whenever m n + 5
		4.1 Three Agents, Eight Items
		4.2 Four Agents, Nine Items
		4.3 Five Agents, Ten Items
	5 Tightness of MMS Ratio for Nine Items
	6 Extension to Chores
	7 Discussion
	References
Approximating Nash Social Welfare Under Binary XOS and Binary Subadditive Valuations
	1 Introduction
	2 Notation and Preliminaries
	3 Approximation Algorithm for Nash Social Welfare
	4 Hardness of Approximation for Binary XOS Valuations
	5 Lower Bound for Binary Subadditive Valuations
		5.1 Proof of Theorem 5
	6 Conclusion and Future Work
	References
Default Ambiguity: Finding the Best Solution to the Clearing Problem
	1 Introduction
	2 Related Work
	3 Model Definition
		3.1 Banks and Contracts
		3.2 Assets and Liabilities
	4 Properties of the Solution Space
	5 Finding the ``Best\'\' Solution
		5.1 Tools and Gadgets
		5.2 Example: Maximizing the Equity of a Node
		5.3 Global Objective Functions
		5.4 More Complex Objectives
	6 Restricted Financial Networks
		6.1 Unweighted Networks
		6.2 Restricted Network Structure
		6.3 Green Systems and Regularity
		6.4 Combined Restrictions: a Unique Solution
	References
Planning on an Empty Stomach: On Agents with Projection Bias
	1 Introduction
	2 Model and Preliminaries
	3 On the Utility of the -Biased Agent
		3.1 The Structure of a Minimal Optimal Subgraph
		3.2 Hardness of Computing an Optimal Subgraph
	4 Non-monotonicity and the Number of Different Paths
		4.1 Planning for Different Time Horizons
		4.2 Agents with Different Values of
	5 Extensions - State Graphs with Cycles
	References
Eliciting Social Knowledge for Creditworthiness Assessment
	1 Introduction
		1.1 Related Work
	2 Preliminaries
	3 Unconstrained-Liquidity Setting: Truncated Winkler Mechanism
		3.1 The Truncated Winkler Mechanism
		3.2 Strict IIC with the Grain-of-no-veto Condition
		3.3 Failure of Truncated Winkler with Constrained Liquidity
	4 The VCG Scoring Mechanism
		4.1 Strict Properness of the VCG Scoring Mechanism
		4.2 Strong Ex Post IR
		4.3 Incentive Alignment with Better Reporting Quality
		4.4 Relation to Chen et al.\'s Impossibility Result
		4.5 Linear Belief Aggregation
	5 Conclusion
	References
Social Choice and Cryptocurrencies
Decentralized Asset Custody Scheme with Security Against Rational Adversary
	1 Introduction
		1.1 Related Works
		1.2 Our Contributions
	2 Model
	3 Constructions of Group Assignment Schemes
		3.1 Symmetric Design
		3.2 Polynomial Design
		3.3 Block Design
	4 Compressing Group Assignment Schemes via Random Sampling
	5 Summary and Discussion
	References
The Distortion of Distributed Metric Social Choice
	1 Introduction
		1.1 Our Contributions
		1.2 Related Work
	2 Preliminaries
		2.1 Objectives
		2.2 Distortion of Voting Rules and Distributed Mechanisms
	3 Composition Results for General Metric Spaces
	4 Improved Results on the Line Metric
		4.1 Ordinal Mechanisms
		4.2 Cardinal Mechanisms
	5 Extensions and Generalizations
		5.1 Mechanisms that Select from the Set of Representatives
		5.2 More General Objectives
	6 Open Problems
	References
Maximal Information Propagation via Lotteries
	1 Introduction
		1.1 Our Contribution
		1.2 Related Works
	2 Game Theoretic Model and Preliminaries
	3 Main Results
		3.1 Technical Lemmas
		3.2 Main Results
	4 A Class of Non-tree Networks
	5 Experiments
	6 Conclusion and Future Directions
	References
Envy-free Division of Multi-layered Cakes
	1 Introduction
	2 Preliminaries
	3 Envy-Free Division Using n-1 Long Knives
		3.1 Tools from Equivariant Topology
		3.2 Proof of Theorem 1
	4 Envy-Free Division Using One Short Knife and One Long Knife
		4.1 Existence of an Envy-Free Multi-division
		4.2 FPTAS
	5 Concluding Remarks
	References
Computing Envy-Freeable Allocations with Limited Subsidies
	1 Introduction
		1.1 Related Work
		1.2 Roadmap
	2 Preliminaries
	3 An Approximation Algorithm
	4 Hardness of Approximating SMEF
		4.1 The Reduction
		4.2 Lower Bound on Subsidies
		4.3 Upper Bound on Minimum Subsidies
		4.4 Adapting the Proof for the Case =0
	5 Concluding Remarks
	References
Abstracts
Asymptotically Optimal Competitive Ratio for Online Allocation of Reusable Resources
Dynamic Bipartite Matching Market with Arrivals and Departures
Static Pricing for Multi-unit Prophet Inequalities (Extended Abstract)
Fairness Maximization Among Offline Agents in Online-Matching Markets*-8pt
Funding Public Projects: A Case for the Nash Product Rule
Screening with Limited Information: The Minimax Theorem and a Geometric Approach
Optimal DSIC Auctions for Correlated Private Values: Ex-Post Vs. Ex-Interim IR
Throttling Equilibria in Auction Markets
Generalized Nash Equilibrium Problems with Mixed-Integer Variables
In Which Matching Markets Do Costly Compatibility Inspections Lead to a Deadlock?
Contest Design with Threshold Objectives
Confounding Equilibria for Platforms with Private Information on Promotion Value
Author Index