Limitations of randomized mechanisms for combinatorial auctions

Details Limitations of randomized mechanisms for combinatorial auctions Limitations of randomized mechanisms for combinatorial auctions

2011-09-06

arxiv.org/abs/1109.1055v1

Computer Science

Computer Science and Game Theory

Scientific paper

Recently, a randomized mechanism has been discovered [Dughmi, Roughgarden and Yan; STOC'11] for combinatorial auctions that is truthful in expectation and guarantees a (1-1/e)-approximation to the optimal social welfare when players have coverage valuations. This approximation ratio is the best possible even for non-truthful algorithms, assuming $P \neq NP$. Given the recent sequence of negative results for combinatorial auctions under more restrictive notions of incentive compatibility, this development raises a natural question: Are truthful-in-expectation mechanisms compatible with polynomial-time approximation in a way that deterministic or universally truthful mechanisms are not? In particular, can polynomial-time truthful-in-expectation mechanisms guarantee a near-optimal approximation ratio for more general variants of combinatorial auctions? We prove that this is not the case. Specifically, the result of Dughmi, Roughgarden and Yan cannot be extended to combinatorial auctions with submodular valuations in the value oracle model. (Absent strategic considerations, a (1-1/e)-approximation is still achievable in this setting.) More precisely, we prove that there is a constant \gamma>0 such that there is no randomized mechanism that is truthful-in-expectation--- or even approximately truthful-in-expectation --- and guarantees an m^{-\gamma}-approximation to the optimal social welfare for combinatorial auctions with submodular valuations in the value oracle model. We also prove an analogous result for the flexible combinatorial public projects (CPP) problem. Both our results present an unexpected separation between coverage functions and submodular functions, which does not occur for these problems without strategic considerations.

Affiliated with

Also associated with

No associations

Rating

Limitations of randomized mechanisms for combinatorial 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 Limitations of randomized mechanisms for combinatorial auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Limitations of randomized mechanisms for combinatorial auctions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-92748