Some approximation algorithms for multi-agent systems

Combinatorial optimization;Mechanism design

Wang, Lei ; Computing

University:Georgia Institute of Technology

Department:Computing

关键词: Combinatorial optimization;    Mechanism design;   

Others  :  https://smartech.gatech.edu/bitstream/1853/42726/1/wang_lei_201108_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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.