Incentive compatible design of reverse auctions.

Abstract

We consider two classes of optimization problems that emerge in the set up of the reverse auctions (a.k.a. procurement auctions). Unlike the standard optimization taking place for a commonly known input, we assume that every individual submits his piece of the input and may misreport his data or not follow the protocol, in order to gain a better outcome. The study of scenarios falling into this framework has been well motivated by the advent of the Internet and, in particular, by rapidly growing industries such as sponsored-search ad-auctions, on-line auction services for consumer-to-consumer sales, marketing in social networks, etc. Our work contributes to the field of algorithmic mechanism design, which seeks to obtain nearly optimal algorithms and protocols that are robust against strategic manipulations of selfish participants.

The first part of this thesis is devoted to the problem of payment minimization under feasibility constraints overlaid on top of an underlying combinatorial structure of the outcome. We analyze the performance of incentive compatible procedures against two standard benchmarks and introduce a general scheme that proved to be optimal on some subclasses of vertex cover and all k-paths set systems. Our results completely settled the design of optimal frugal mechanism in path auctions, a decade-long standing open problem in algorithmic mechanism design proposed by Archer and Tardos.

In the second part of this thesis we study procurement auctions in which

sellers have private costs to supply their items and the auctioneer aims to maximize the value of a purchased item bundle, while keeping payments under a budget constraint. For a few important classes of auctioneer's value functions defined over all item sets we give budget feasible incentive compatible mechanisms with desirable approximation guarantees and answer the ``fundamental question'' posed by Dobzinski, Papadimitriou, Singer.