Randomization and computation in strategic settings
Abstract/Contents
- 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Dughmi, Shaddin Faris |
|---|---|
| Associated with | Stanford University, Computer Science Department |
| Primary advisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Plotkin, Serge A |
| Thesis advisor | Saberi, Amin |
| Advisor | Plotkin, Serge A |
| Advisor | Saberi, Amin |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Shaddin Dughmi. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Shaddin Faris Dughmi
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...