Back to search

Georgia Institute of Technology

Some approximation algorithms for multi-agent systems

Abstract

dc:description.abstract

This 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 × 6

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/42726

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Wang, Lei. Some approximation algorithms for multi-agent systems. Georgia Institute of Technology, 2011. http://hdl.handle.net/1853/42726