Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFikioris, Giannis-
dc.description.abstractIn this thesis, we introduce the notion of Perturbation Stability for Combinatorial Auctions, inspired by the recent works on the Endowment Effect and on the Perturbation Stability of problems like Minimum Multiway Cut and k-Median. This helps overcome the various impossibility results for truthful and non-truthful auctions for the more general valuation classes, like submodular and subadditive valuations. In this work, for the case of pure mechanism design, via our definition for Perturbation Stability that conveys in a natural way that the solution of an instance of a combinatorial auction should not change under small perturbations, we proved that by using a simple non-truthful Parallel Auction, one can find the optimal allocation for stable subadditive instances. Also for stable submodular instances we showed that a Parallel Second Price Auction finds the optimal allocation, while at the same time being truthful in an Ex-Post Equilibrium way. We also improved the previous approximation ratio of 1/2 of the Kelso-Crawford Auction for submodular valuations, by proving that, if a submodular instance is stable enough, then the Kelso-Crawford Auction finds the optimal allocation. Additionally, for the case of Price of Anarchy in simple auctions, we showed that the lower bound of 1/2 for Parallel Second Price Auctions with submodular valuations remains tight even for highly-stable instances, until it “jumps” to a guaranteed value of 1. For the case of Parallel First Price Auctions for XOS valuations, we improved the previous bound of 1−1/e, by showing that as an instance of a combinatorial auction becomes more stable,the lower bound for the Price of Anarchy increases, reaching the value of 1 asymptotically.en_US
dc.subjectCombinatorial Auctionsen_US
dc.subjectMechanism Designen_US
dc.subjectBeyond Worst Case Analysisen_US
dc.subjectPerturbation Stabilityen_US
dc.subjectPrice of Anarchyen_US
dc.titlePertubation Stability for Mechanism Designen_US
dc.contributor.supervisorΦωτάκης Δημήτριοςen_US
dc.departmentΤομέας Τεχνολογίας Πληροφορικής και Υπολογιστώνen_US
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
Giannis Fikioris Thesis.pdf663.38 kBAdobe PDFView/Open

Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.