Title: Algorithms for Budgeted Auctions and Multi-agent Covering Problems
| Time: | Monday, June 15, 3:00pm |
| Location: | Klaus Conference Room 2100 |
| Advisor: | Dr. Vijay Vazirani, College of Computing |
| Committee: | Dr. Robin Thomas, School of Mathematics |
| Dr. Milena Mihail, College of Computing | |
| Dr. Adam Kalai, College of Computing | |
| Dr. Prasad Tetali, School of Mathematics | |
| Reader: | Dr. Prasad Tetali, School of Mathematics |
Abstract:
In this thesis, we do an algorithmic study of optimization problems in budgeted auctions, and some well known covering problems in the multi-agent setting. We give new results for the design of approximation algorithms, online algorithms and hardness of approximation for these problems. Along the way we give new insights for many other related problems.
Budgeted Auctions. We study the following allocation problem which arises in budgeted auctions: Given a set of m indivisible items and n agents; agent i is willing to pay b_{ij} for item j and has an overall budget of B_i (i.e. the maximum total amount he is willing to pay). The goal is to allocate items to the agents so as to maximize the total revenue obtained.
We give two approximation algorithms with 3/4-approximation ratio, improving upon the previous best of \simeq 0.632. We use LP based techniques, and our approximation ratio is optimal in the sense that it matches the integrality gap of the LP used by us and the previous results. We also show hardness of approximation factor of 15/16, significantly improving upon the previous results. We use these new techniques to improve hardness factors for many other related allocation problems.
We also study the above allocation problem in an online setting. Online version of the problem has motivation in Ad Auctions which are run by search engines such as Google, Microsoft Live, Yahoo!. Previously, the online version was mostly studied in the worst-case setting. But in applications such as Ad Auctions it is unlikely to see a worst-case sequence of items as input. Motivated by this, we study the online version of the problem in which the items arrive in a random order i.e. the set of items are adversarially chosen but the order in which they arrive is random. Our main result is an analysis to show that Greedy has competitive ratio 1-1/e in this model, which is also tight.
Lastly, we define a new bidding language for budgeted auctions- Decreasing valuation bids. We argue that why this language is better for both seller and buyers.
Multi-agent Covering Problems. Consider the network design problem of constructing a spanning tree of graph G, assuming there are many agents (or constructors) willing to construct different parts of the tree. The cost of each agent for constructing a particular set of edges could be a complex function. For instance, some agents might provide discounts depending on how many edges they construct. The algorithmic question that one would be interested in is: Can we find a spanning tree of minimum cost in polynomial time in these complex settings? Note that such an algorithm will have to find a spanning tree, and partition its edges among the agents.
These are the type of questions that we are trying to answer for various combinatorial problems. We look at the case when the agents' cost functions are submodular. These functions form a rich class and capture the natural properties of economy of scale or the law of diminishing returns. Based on these considerations, we define the following general class of problems - We are given a set of elements X and a collection C \subseteq 2^X. Here the collection C is given via some combinatorial structure like a matroid or a graph property (for instance the set of all spanning trees in a graph G with edge set X). We are also given k agents, where each agent i specifies a monotone submodular cost function f_i: 2^X \rightarrow R^+. The goal is to find a set S \in C and a partition S_1, ..., S_k of S such that \sum_i f_i(S_i) is minimized. Note that one can study various covering type problems in this setting by suitably defining the collection set C.
We study the following fundamental problems in this setting- Vertex Cover, Spanning Tree, Perfect Matching, Reverse Auctions. We look at both the single agent and the multi-agent case, and study the approximability of each of these problems.
<
Full-Text Page >