Shaddin Dughmi
Randomization and Computation in Strategic Settings
Download
Stanford University, August 2011
Abstract
This thesis considers the following question: In large-scale systems involving many self-interested participants, how can we effectively allocate scarce resources among competing interests despite strategic behavior by the participants, as well as the limited computational power of the system? Work at the interface between computer science and economics has revealed a fundamental tension between the economic objective, that of achieving the goals of the system designer despite strategic behavior, and the computational objective, that of implementing aspects of the system efficiently. In particular, this tension has been most apparent in systems that allocate resources deterministically.
The realization that careful use of randomization can reconcile economic and computational goals is the starting point for this thesis. Our contributions are twofold: (1) We design randomized mechanisms for several fundamental problems of resource allocation; our mechanisms perform well even in the presence of strategic behavior, and can be implemented efficiently. (2) En route to our results, we develop new and flexible techniques for exploiting the power of randomization in the design of computationally-efficient mechanisms for resource allocation in strategic settings.
Table of Contents
- I. Background and Overview
- 1. Introduction
- 1.1. This Thesis in a Nutshell
- 1.2. Three Illustrative Examples
- 1.3. Informal Preliminaries
- 1.4. Incentive Compatibility and Tractability
- 1.5. Deterministic vs. Randomized Mechanisms
- 1.6. Contributions of this Thesis
- 1.7. Related Work
- 1.8. Tips for Reading this Thesis
- 1.9. Bibliographic Notes
- 2. Technical Preliminaries
- 2.1. Notation
- 2.2. Mechanism Design Basics
- 2.3. Basics of Optimization and Algorithms
- 2.4. Mechanism Design and Optimization
- 2.5. Classifying Mechanism Design Problems
- 2.6. Commentary on Our Model
- 3. Welfare Maximization Background
- 3.1. Welfare Maximization Problems
- 3.2. The Vickrey-Clarke-Groves Mechanism
- 3.3. Deterministic VCG-based Mechanisms
- 3.4. Randomized VCG-Based Mechanisms
- II. Convex Rounding
- 4. The Convex Rounding Framework
- 4.1. Introduction
- 4.2. Relaxations and Rounding Schemes
- 4.3. Convex Rounding Schemes
- 5. Combinatorial Auctions
- 5.1. Introduction
- 5.2. Model and Preliminaries
- 5.3. Result Statement and Proof Overview
- 5.4. The Poisson Rounding Scheme
- 5.5. Convexity of the Poisson Rounding Scheme
- 5.6. Additional Results
- 6. Combinatorial Public Projects
- 6.1. Introduction
- 6.2. Model and Preliminaries
- 6.3. Result Statement and Proof Overview
- 6.4. The k-Bounded-Lottery Rounding Scheme
- 6.5. Convexity of the k-Bounded-Lottery Rounding Scheme
- III. Perturbation-Based Mechanisms
- 7. The Linear Perturbation Framework
- 7.1. Introduction
- 7.2. Model and Preliminaries
- 7.3. An Overly Simplistic Approach
- 7.4. Adjoint Perturbations
- 7.5. The Perturbation-Based Allocation Rule
- 8. A Black Box Result
- 8.1. Introduction
- 8.2. Model and Preliminaries
- 8.3. The Random Singleton Scheme
- 8.4. The Black Box Result
- 8.5. Example Problems
- 8.6. Extensions
- 9. Multi-Unit Auctions
- 9.1. Introduction
- 9.2. Model and Preliminaries
- 9.3. Outline of our Approach
- 9.4. The 2-adic Perturbation
- 9.5. Combining the 2-adic and Random Singleton Perturbation Schemes
- 9.6. The Truthful-in-Expectation FPTAS
- IV. Mechanisms for Single-Parameter Problems
- 10. Single-Parameter Scheduling Problems
- 10.1. Introduction
- 10.2. A Monotone PTAS for Minimizing Makespan
- 10.3. Additional Results
- V. Conclusion
- 11. Conclusions and Open Questions
- VI. Appendices
- A. Additional Preliminaries
- A.1. Matroid Theory
- A.2. Convex Optimization
- A.3. Single-Parameter Mechanism Design
- B. Omitted Proofs
- B.1. Solving The Convex Program of Chapter 5
- B.2. Solving The Convex Program of Chapter 6
- Bibliography
