Algorithms and mechanism design for multi-agent systems

Multi-agent systems;Online auction;Algorithms;Mechanism design

Karande, Chinmay ; Computing

University:Georgia Institute of Technology

Department:Computing

关键词: Multi-agent systems;    Online auction;    Algorithms;    Mechanism design;   

Others  :  https://smartech.gatech.edu/bitstream/1853/37229/1/karande_chinmay_d_201012_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

A scenario where multiple entities interact with a common environment to achieve individual and common goals either co-operatively or competitively canbe classified as a Multi-Agent System. In this thesis, we concentrate on the situations where the agents exhibit selfish, competitive and strategic behaviour, giving rise to interesting game theoretic and optimization problems. From a computational point of view, the presence of multiple agents introduces strategic and temporal issues, apart from enhancing the difficulty of optimization.We study the following natural mathematical models of such multi-agent problems faced in practice: a) combinatorial optimization problems with multi-agent submodular cost functions, b) combinatorial auctions with partially public valuations and c) online vertex-weighted bipartite matching and single bid budgeted allocations. We provide approximation algorithms, online algorithms and hardness of approximation results for these problems.