Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/54944
Title: Incentive compatible design of reverse auctions.
Authors: Gravin, Nikolai.
Keywords: DRNTU::Science::Mathematics::Discrete mathematics::Theory of computation
DRNTU::Science::Mathematics::Applied mathematics::Game theory
DRNTU::Science::Mathematics::Discrete mathematics::Graph theory
DRNTU::Science::Mathematics::Applied mathematics::Optimization
Issue Date: 2013
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.
URI: http://hdl.handle.net/10356/54944
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Research Reports (Staff & Graduate Students)

Files in This Item:
File Description SizeFormat 
Main.pdf
  Restricted Access
PhD thesis1.17 MBAdobe PDFView/Open

Google ScholarTM

Check

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.