Research Library

Premium First‐passage percolation on a ladder graph, and the path cost in a VCG auction
Author(s)
Flaxman Abraham,
Gamarnik David,
Sorkin Gregory B.
Publication year2011
Publication title
random structures and algorithms
Resource typeJournals
PublisherWiley Subscription Services
Abstract This paper studies the time constant for first‐passage percolation, and the Vickrey‐Clarke‐Groves (VCG) payment, for the shortest path on a ladder graph (a width‐2 strip) with random edge costs, treating both in a unified way based on recursive distributional equations. For first‐passage percolation where the edge costs are independent Bernoulli random variables we find the time constant exactly; it is a rational function of the Bernoulli parameter. For first‐passage percolation where the edge costs are uniform random variables we present a reasonably efficient means for obtaining arbitrarily close upper and lower bounds. Using properties of 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 cost distribution. For the VCG payment, with Bernoulli‐distributed costs the payment for an n ‐long ladder, divided by n , tends to an explicit rational function of the Bernoulli parameter. Again, our methods apply more generally. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 350‐364, 2011
Subject(s)aerospace engineering , bernoulli distribution , bernoulli's principle , biology , bounded function , combinatorics , computer science , constant (computer programming) , engineering , evolutionary biology , function (biology) , graph , mathematical analysis , mathematical optimization , mathematics , path (computing) , programming language , random graph , random variable , shortest path problem , statistics
Language(s)English
SCImago Journal Rank1.314
H-Index69
eISSN1098-2418
pISSN1042-9832
DOI10.1002/rsa.20328

Seeing content that should not be on Zendy? Contact us.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here