Georgia Institute of Technology
Some approximation algorithms for multi-agent systems
Abstract
dc:description.abstractThis thesis makes a number of contributions to the theory of approximation algorithm design for multi-agent systems. In particular, we focus on two research directions. The first direction is to generalize the classical framework of combinatorial optimization to the submodular setting, where we assume that each agent has a submodular cost function. We show hardness results from both the information-theoretic and computational aspects for several fundamental optimization problems in the submodular setting, and provide matching approximation algorithms for most of them. The second direction is to introduce game-theoretic issues to approximation algorithm design. Towards this direction, we study the application of approximation algorithms in the theory of truthful mechanism design. We study both the standard objectives of revenue and social welfare, by designing efficient algorithms that satisfy the requirement of truthfulness and guarantee approximate optimality.
Degree
thesis:*- Department dc:contributor.department
- Computing
- Grantor dc:publisher
- Georgia Institute of Technology
- Year dc:date.issued
- 2011
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Wang, Lei
- Advisor dc:contributor.advisor
-
- Vazirani, Vijay V.
- Committee members dc:contributor.committeemember
-
- Cook, Bill
- Balcan, Nina
- Tetali, Prasad
- Thomas, Robin
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1853/42726