Towards Practical Mechanism Design Techniques for Combinatorial Auctions

Abstract

This research focuses on implementation of strategy–proof approximation algorithms for combinatorial auctions and evaluates it in terms of social welfare, revenue generated, running time and truthfulness. Further, on the basis of those findings, we suggest suitable mechanisms for online auction market. We will focus on the Lavy–Swamy(LS) approach ([22]) which is for designing truthful–in–expectation mechanisms. It is a sufficiently general black–box reduction technique that can be applied to many problems including combinatorial auctions. However, a direct implementation of this method would be highly inefficient in practice, due to its use of computationally demanding optimization methods such as the Ellipsoid method. We implement to use the simpler and faster multiplicative weights update methods from convex optimization to speed–up this LS–approach. This thesis focuses around implementation of such methods and in particular compares the VCG–based mechanism with the Generalize Second Price mechanism [24].

Date of Award	May 2014
Original language	American English
Supervisor	Khaled ElBassioni (Supervisor)