First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction

@incollection{citeulike:1469924, abstract = {We study both 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 of maximizing social welfare among selfish agents. However, our analyses of the two are quite similar, and require solving (slightly different) recursive distributional equations. Using Harris chains, we can characterize distributions, not just expectations.}, author = {Flaxman, Abraham and Gamarnik, David and Sorkin, Gregory}, citeulike-article-id = {1469924}, doi = {10.1007/11944874_10}, journal = {Internet and Network Economics}, keywords = {auction, first-passage, path, percolation, vcg}, pages = {99--111}, posted-at = {2007-07-20 17:10:23}, priority = {0}, title = {First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction}, url = {http://dx.doi.org/10.1007/11944874_10}, year = {2006} }

TY - CHAP ID - citeulike:1469924 L3 - citeulike-article-id:1469924 N2 - We study both 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 of maximizing social welfare among selfish agents. However, our analyses of the two are quite similar, and require solving (slightly different) recursive distributional equations. Using Harris chains, we can characterize distributions, not just expectations. JF - Internet and Network Economics EP - 111 TI - First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction SP - 99 KW - auction KW - first-passage KW - path KW - percolation KW - vcg AU - Flaxman, Abraham AU - Gamarnik, David AU - Sorkin, Gregory PY - 2006/// UR - http://dx.doi.org/10.1007/11944874_10 ER -