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 {\it strong $\epsilon$-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 $\epsilon$-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 {\em ex ante} first-price auction may not have any $\epsilon$-Nash equilibria. We then present a modified auction mechanism with $2$-parameter bids, and show that it has an $\epsilon$-Nash equilibrium.