Algorithms for budgeted auctions and multi-agent covering problems

Game theory;Covering problems;Budgeted auctions;Approximation algorithms;Algorithms

Goel, Gagan ; Computing

University:Georgia Institute of Technology

Department:Computing

关键词: Game theory;    Covering problems;    Budgeted auctions;    Approximation algorithms;    Algorithms;   

Others  :  https://smartech.gatech.edu/bitstream/1853/29679/1/goel_gagan_200908_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

In this thesis, we do an algorithmic study ofoptimization problems in budgeted auctions, and some well knowncovering problems in the multi-agent setting. We give new resultsfor the design of approximation algorithms, online algorithms andhardness of approximation for these problems. Along the way we givenew insights for many other related problems.Budgeted Auction. We study the following allocation problem whicharises in budgeted auctions (such as advertisement auctions run byGoogle, Microsoft, Yahoo! etc.) : Given a set of m indivisibleitems and n agents; agent i is willing to pay b[subscript ij] for itemj and has an overall budget of B[subscript i] (i.e. the maximum totalamount he is willing to pay). The goal is to allocate items to theagents so as to maximize the total revenue obtained.We study the computation complexity of the above allocation problem,and give improved results for the approximation and the hardness ofapproximation. We also study the above allocation problem in anonline setting. Online version of the problem has motivation in thesponsored search auctions which are run by search engines. Lastly,we propose a new bidding language for the budgeted auctions:decreasing bid curves with budget constraints. We make a case forwhy this language is better both for the sellers and for the buyers.Multi-agent Covering Problems. To motivate this class of problems,consider the network design problem of constructing a spanning treeof a graph, assuming there are many agents willing to constructdifferent parts of the tree. The cost of each agent for constructinga particular set of edges could be a complex function. For instance,some agents might provide discounts depending on how many edges theyconstruct. The algorithmic question that one would be interested inis: Can we find a spanning tree of minimum cost in polynomial timein these complex settings? Note that such an algorithm will have tofind a spanning tree, and partition its edges among the agents.Above are the type of questions that we are trying to answer forvarious combinatorial problems. We look at the case when the agents'cost functions are submodular. These functions form a rich class andcapture the natural properties of economies of scale or the law ofdiminishing returns.We study the following fundamental problems inthis setting-Vertex Cover, Spanning Tree, Perfect Matching,Reverse Auctions. We look at both the single agent and themulti-agent case, and study the approximability of each of theseproblems.