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 Auction. We study the following allocation problem which
arises in budgeted auctions (such as advertisement auctions run by
Google, Microsoft, Yahoo! etc.) : Given a set of m indivisible
items and n agents; agent i is willing to pay b[subscript ij] for item
j and has an overall budget of B[subscript 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 study the computation complexity of the above allocation problem,
and give improved results for the approximation and the hardness of
approximation. We also study the above allocation problem in an
online setting. Online version of the problem has motivation in the
sponsored 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 for
why 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 tree
of a graph, assuming 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 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.
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. These functions form a rich class and
capture the natural properties of economies of scale or the law of
diminishing returns.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.
| Identifer | oai:union.ndltd.org:GATECH/oai:smartech.gatech.edu:1853/29679 |
| Date | 07 July 2009 |
| Creators | Goel, Gagan |
| Publisher | Georgia Institute of Technology |
| Source Sets | Georgia Tech Electronic Thesis and Dissertation Archive |
| Detected Language | English |
| Type | Dissertation |
Page generated in 0.002 seconds