Computer Science – Computer Science and Game Theory
Scientific paper
2009-09-04
Computer Science
Computer Science and Game Theory
Scientific paper
We consider mechanisms for utilitarian combinatorial allocation problems, where agents are not assumed to be single-minded. This class of problems includes combinatorial auctions, multi-unit auctions, unsplittable flow problems, profit-maximizing scheduling, and others. We study the price of anarchy for such mechanisms, which is a bound on the approximation ratio obtained at any mixed Nash equilibrium. We demonstrate that a broad class of greedy approximation algorithms can be implemented as mechanisms for which the price of anarchy nearly matches the performance of the original algorithm. This is true even in Bayesian settings, where the agents' valuations are drawn from publicly known distributions. Furthermore, for a rich subclass of allocation problems, pure Nash equilibria are guaranteed to exist for these mechanisms. For many problems, the approximation factors obtained at equilibrium improve upon the best known results for deterministic truthful mechanisms. In particular, we exhibit a simple deterministic mechanism for the general combinatorial auction with $O(\sqrt{m})$ price of anarchy.
Borodin Allan
Lucier Brendan
No associations
LandOfFree
Price of Anarchy for Greedy Auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Price of Anarchy for Greedy Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Price of Anarchy for Greedy Auctions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-35988