First-price path auctions

We study first-price auction mechanisms for auctioning flow between given nodes in a graph.We assume edges are independent agents with fixed capacities and costs, and their objective is to maximize their profit. We characterize all strong ffl-Nash equilibria of a first-price auction for this problem, and show that the total payment is never significantly more than, and often less than, the well known dominant strategy Vickrey-Clark-Groves (VCG) mechanism. We then present a randomized version of the first-price auction, for which the equilibrium condition can be relaxed to ffl-Nash equilibrium. We next consider a model in which the amount of demand is uncertain, but its probability distribution is known to the edges. For this model, we show that a simple ex ante first-price auction may not have any ffl-Nash equilibria. We then present a modified auction mechanism with 2-parameter bids, and show that it has an