Pertubation Stability for Mechanism Design

Abstract

In 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.