Paper Info
Title
On the expected payment of mechanisms for task allocation: [extended abstract]
Abstract
We study a generic task allocation problem called shortest paths: Let G be a directed graph in which the edges are owned by self interested agents. Each edge has an associated cost that is privately known to its owner. Let s and t be two distinguished nodes in G. Given a distribution on the edge costs, the goal isto design a mechanism (protocol) which acquires a cheap s-t path. We first prove that the class of generalized VCG mechanisms has certain monotonicity properties. We exploit this observation to obtain, under an independence assumption, expected payments whichare significantly better than the worst case bounds of. We then investigate whether these payments canbe improved when there is a competition among paths. Surprisingly, we give evidence to the fact that typically such competition hardly helps incentive compatible mechanisms. In particular, we show this for the celebrated VCG mechanism. We then construct anovel general protocol combining the advantages of incentive compatible and non-incentive compatible mechanisms. Under reasonable assumptions on the agents we show that the overpayment of our mechanism is very small. Finally, we demonstrate that many task allocation problems can be reduced to shortest paths.
Year
DOI
Venue
2004
10.1145/988772.988819
EC
Keywords
Field
DocType
anovel general protocol,non-incentive compatible mechanism,celebrated vcg mechanism,expected payment,associated cost,generic task allocation problem,shortest path,task allocation problem,edge cost,incentive compatible mechanism,generalized vcg mechanism,directed graph,incentive compatibility,mechanism design
Monotonic function,Mathematical optimization,Incentive compatibility,Computer science,Directed graph,Exploit,Mechanism design,Vickrey–Clarke–Groves auction,Payment,Statistical assumption
Conference
ISBN
Citations 
PageRank 
1-58113-771-0
6
0.81
References 
Authors
4
2
Name
Order
Citations
PageRank
Artur Czumaj11444133.35
Amir Ronen21152169.60