First-Passage Percolation on a Width-2 Strip, and the Path Cost in a VCG Auction (title in journal: First-Passage Percolation on a Ladder Graph, and the Path Cost in a VCG Auction)

This paper studies the time constant for first-passage percolation and the Vickery-Clarke-Groves (VCG) payment for the shortest path on a width-2 strip with random edge costs. These statistics attempt to describe two seemingly unrelated phenomena, arising in physics and economics respectively: the first-passage percolation time predicts how long it takes for a fluid to spread through a random medium, while the VCG payment for the shortest path is the cost maximizing social welfare among selfish agents. However, our analyses of the two are quite similar, and require solving (slightly different) recursive distributional equations. For first-passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly. It turns out to be a rational function of the Bernoulli parameter; for example, for Be(1/2) the time constant is 9/28.

For first-passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining upper and lower bounds; our calculations show the time constant to be between 0.42 and 0.43. Using Harris chains we also show that the incremental cost to advance through the medium has a unique stationary distribution, and we compute stochastic lower and upper bounds. We rely on no special properties of the uniform distribution; the same methods could be applied to any well-behaved, bounded distribution.

For the VCG payment, we restrict our attention to the case where the edge costs are independent Bernoulli random variables. Here we find that the VCG payment for a strip of length n tends to n times a rational function of the Bernoulli parameter, which we determine explicitly. For Be(1/2), the VCG payment over n tends to 1829/1568 1.166, which is about 3.63 times the length of the shortest path.

By: Abraham Flaxman; David Gamarnik; Gregory B. Sorkin

Published in: Random Structures and Algorithms, volume 38, (no 3), pages 350-64 in 2011

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .