@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}
}