Algorithms for budgeted auctions and multi-agent covering problems

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 bij for item j and has an overall budget of Bi (i.e. the maximum total amount agent i 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 factor, improving upon the previous best known factor of s 0.632. We use linear programming based techniques, and our approximation ratio is optimal in the sense that it matches the integrality gap of the linear program used by us and by the other authors [24, 2, 3]. We also show hardness of approximation factor of 15/16 for the above problem, and use our techniques to improve the hardness results for 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 a natural greedy algorithm has a competitive ratio of 1 − 1/e in this model, which we also show to be tight. Lastly, we define a new bidding language for budgeted auctions—Decreasing valuation bids. We make a case for why this language is better both for the sellers and the buyers. Multi-agent covering problems. To motivate this class of problems, consider the network design problem of constructing a spanning tree of a graph, assuming that there are many agents willing to construct different parts of the tree. The cost of each agent for constructing a particular set of edges could be a complicated 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 one 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. Above 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. A function f : 2X → R is said to be submodular if, for all S,T ⊆ X, f(S ∩ T) + f(S ∪ T) ≤ f(S) + f(T). Submodular functions form a rich class and capture the natural properties of economies 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 (|X| = n) and a collection C ⊆ 2X. 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 non-decreasing submodular cost function fi : 2X → R+. The goal is to find a set S ∈ C and a partition S1,…, Sk of S such that ∑ i fi(Si) 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. The approximation ratio (upper bound) and the hardness of approximation (lower bound) for each of these problems is presented in the table below.* *Please refer to dissertation for diagram.