University of Cambridge > > Microsoft Research Cambridge, public talks > Frugal Procurement Auction Design

Frugal Procurement Auction Design

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

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.

This talk is part of the Microsoft Research Cambridge, public talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity