Frugal path mechanisms Export

@misc{citeulike:970651, abstract = {We consider the problem of selecting a low cost s t path in a graph, where the edge costs are a secret known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) mechanism, which pays a premium to induce the edges to reveal their costs truthfully. We observe that this premium can be unacceptably high. There are simple instances where the mechanism pays \#(n) times the actual cost of the path, even if...}, author = {Archer, A. and Tardos, E.}, citeulike-article-id = {970651}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.2041}, keywords = {frugal, mechanismdesign}, posted-at = {2006-12-01 17:27:50}, priority = {2}, title = {Frugal path mechanisms}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.2041} }

TY - GEN ID - citeulike:970651 L3 - citeulike-article-id:970651 N2 - We consider the problem of selecting a low cost s t path in a graph, where the edge costs are a secret known only to the various economic agents who own them. To solve this problem, Nisan and Ronen applied the celebrated Vickrey-Clarke-Groves (VCG) mechanism, which pays a premium to induce the edges to reveal their costs truthfully. We observe that this premium can be unacceptably high. There are simple instances where the mechanism pays #(n) times the actual cost of the path, even if... TI - Frugal path mechanisms KW - frugal KW - mechanismdesign AU - Archer, A AU - Tardos, E UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.2041 ER -