COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |
University of Cambridge > Talks.cam > Microsoft Research Cambridge, public talks > Frugal Procurement Auction Design
Frugal Procurement Auction DesignAdd 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. This talk is included in these lists:
Note that ex-directory lists are not shown. |
Other listsCambridge Evolutionary Genetics Type the title of a new list here The Audrey Richards Annual Lecture in African StudiesOther talksLARMOR LECTURE - Exoplanets, on the hunt of Universal life What is the Market Potential of Multilingualism? Saving the People of the Forest: one chocolate bar and one nebulizer treatment at a time Regulators of Muscle Stem Cell Fate and Function Lipschitz Global Optimization Computing knot Floer homology Crowding and the disruptive effect of clutter throughout the visual system Market Socialism and Community Rating in Health Insurance Inferring the Evolutionary History of Cancers: Statistical Methods and Applications Cambridge Rare Disease Summit 2017 Organoid systems to study the maternal-fetal dialogue of early pregnancy |