Collusion-resistant cost-sharing mechanisms : design techniques, analyses, trade-offs / Florian Schoppmann. 2009
Content
- Introduction
- Algorithmic Mechanism Design
- Cost Sharing
- Design Techniques for Cost-Sharing Mechanisms
- Contribution
- Lexicographic Maximization: Beyond Cross-Monotonicity
- Cost Sharing Without Indifferences: To Be or Not to Be (Served)
- Does Coalition Size Matter?
- Generalizing the Model
- Other Related Work
- Organization
- Prerequisites
- Bibliographic Notes
- Preliminaries
- The Formal Model
- Notation
- Cost-Sharing Problems and Mechanisms
- Non-Manipulability
- Cost-Sharing Methods
- Dealing with Indifferences
- Budget Balance and Economic Efficiency
- Special Cost Functions
- Previous Design Techniques
- Optimization Problems
- Lexicographic Maximization: Beyond Cross-Monotonicity
- Overview of Contribution
- Symmetric Mechanisms
- Symmetric Mechanisms for Symmetric Subadditive Costs
- Computing Two-Price Cost-Sharing Forms
- Lower Bound on the Performance of Symmetric Mechanisms
- What Can Be Achieved with One Price?
- Applications
- Characterizing Symmetry and 1-BB
- Beyond Symmetric Costs
- Conclusion
- Cost Sharing Without Indifferences: To Be or Not to Be (Served)
- Overview of Contribution
- Cost Sharing Without Indifferences
- Definitions
- Equivalence of Models Without Indifferences
- WSGSP Implies Separability
- WGSP Does Not Imply Separability
- Egalitarian Mechanisms
- Efficiency of Egalitarian Mechanisms
- Most Cost-Efficient Set Selection
- Submodular and Supermodular Costs
- Acyclic Mechanisms and SGSP
- A Framework for Polynomial-Time Computation
- Applications
- Makespan Minimization and Bin Packing Cost-Sharing Problems
- Monotonic Approximation Algorithms
- Non-Monotonic Approximation Algorithms with a Polynomial-Time Computable Monotonic Bound
- Makespan Problems with Monotonic Optimal Costs
- Scheduling Problems with Supermodular Costs
- Conclusion
- Does Coalition Size Matter?
- Overview of Contribution
- Notions of Non-Manipulability by Small Coalitions
- Resistance Against Coalitions with Side-Payments
- Some Preliminary Implications by SP and WUNB
- k-GSP Is Strictly Weaker Than GSP
- Group-Strategyproofness Against Only Two Players
- Weak Group-Strategyproofness and Non-Bossiness
- Separability and 2-WGSP Do Not Imply WGSP
- 2-GSP Implies WGSP
- Relationship Between Collusion-Resistance and Non-Bossiness Properties
- Conclusion
- Generalizing the Model
- Bibliography
- Index