Abstract

Suppose we want to hire a team of selfish agents to perform a task via auction. Each agent is assumed to have a private cost if being hired. Moreover, only certain combination of agents are feasible which are expressed in a set system. For instance, in the well-studied case of path auctions, each agent are edges of a graph, and we are trying to buy an s-t path. A natural goal for us (the auctioneer) is to seek a mechanism to pay ‘the least’.

In this talk, I will present optimal truthful mechanisms in three classes of set systems: Vertex Covers, k-Flows (generalization of path) and Cuts. For Vertex Covers, we achieve optimal mechanisms using spectral techniques. Our mechanism first scales each bid by a multiplier derived from the dominant eigenvector of a certain matrix related to the adjacency matrix and then runs VCG .

Additionally, we use Vertex Covers mechanism as a primitive and propose a methodology to obtain ‘frugal’ mechanisms for a given set system by pruning it down to a Vertex Cover instance. We show the power of our methodology by achieving optimal mechanisms for flows and cuts.