Title: | Vickrey Prices and Shortest Paths: What is an edge worth? |

Author: | John Hershberger and Subhash Surih |

Book Tittle: | Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science |

Pages: | 252--259 |

Year: | 2001 |

Abstract: | We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auctionbased pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path---the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by Nisan and Ronen. |

Cited by 67

@InProceedings{hershberger01a, author = {John Hershberger and Subhash Surih}, title = {Vickrey Prices and Shortest Paths: What is an edge worth?}, booktitle = {Proceedings of the 42nd {IEEE} Symposium on Foundations of Computer Science}, pages = {252--259}, year = 2001, abstract = {We solve a shortest path problem that is motivated by recent interest in pricing networks or other computational resources. Informally, how much is an edge in a network worth to a user who wants to send data between two nodes along a shortest path? If the network is a decentralized entity, such as the Internet, in which multiple self-interested agents own different parts of the network, then auctionbased pricing seems appropriate. A celebrated result from auction theory shows that the use of Vickrey pricing motivates the owners of the network resources to bid truthfully. In Vickrey's scheme, each agent is compensated in proportion to the marginal utility he brings to the auction. In the context of shortest path routing, an edge's utility is the value by which it lowers the length of the shortest path---the difference between the shortest path lengths with and without the edge. Our problem is to compute these marginal values for all the edges of the network efficiently. The naive method requires solving the single-source shortest path problem up to n times, for an n-node network. We show that the Vickrey prices for all the edges can be computed in the same asymptotic time complexity as one single-source shortest path problem. This solves an open problem posed by Nisan and Ronen.}, url = {http://jmvidal.cse.sc.edu/library/hershberger01a.pdf}, cluster = {1533011697713937168}, keywords = {auctions negotiation} }Last modified: Wed Mar 9 10:15:16 EST 2011