College of Computing and Informatics

Research

Explores the overpayment of the VCG auction mechanism in a complex algorithmic setting

The Uncapacitated Facility Location Problem focuses on minimizing facility opening costs and client connect costs over a set of given facilities. We examine the private information setting of this problem where facility opening costs are only known to the facilities themselves and we must determine their value through an auction. We use the Vickrey-Clarke-Groves auction to find the optimal solution, and our main focus is establishing a bound on the frugality ratio of this problem, where frugality is defined as total overpayment compared to the second-cheapest disjoint solution. Our research resolves this problem by proving an upper bound of 2 on the frugality ratio via a charging argument, and establishes that this bound is tight by providing an instance of Uncapacitated Facility Location that achieves a frugality ratio of 2.

Copyright © CCI Drexel 2019