טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentFrank Roy
SubjectRevenue-Maximizing Allocations in Constrained Multi-Object
and Combinatorial Auctions
DepartmentDepartment of Computer Science
Supervisor Professor Michal Penn


Abstract

Multi-object auctions are auctions in which the auctioneer puts a set of items for sale, and every bidder can submit bids on any of the items. Constrained multi-object auctions are multi-object auctions in which restrictions are imposed upon the set of feasible allocations. Combinatorial auctions are multi-object auctions in which bidders can submit bids on bundles of items, and not only on singletons. Constrained multi-object and combinatorial auctions may present desirable features that cannot be implemented in single-object auctions.

Recently, multi-object auction theory has become an active research area. Studies in this area include the computational aspect of different multi-object auction schemes, optimal and approximate allocations in multi-object auctions environment, efficient representation of bids and others.

The multi-object auction problem is the following: given a multi-object auction, find a feasible allocation of the items that maximizes the auctioneer's revenue. Most of the constrained multi-object and combinatorial auction problems are NP-hard. We consider some special cases of the constrained multi-object and combinatorial auction problems. We solve these problems using techniques such as general b-matching in graphs, shortest path, dynamic programming and linear programming. Our solutions lead to polynomial time algorithms. We follow previous research done by Rothkopf, Pekec & Harstad, Sandholm, Penn, Tennenholtz, Van Hoesel &  Muller, among others. In some of the cases we present solutions to constrained versions of previously discussed problems and solve them in a more efficient way than the way in which the original, more relaxed problem was solved. In other cases, we present minor generalizations to previously discussed problems and solve them efficiently.