A flow-based ascending auction to compute buyer-optimal Walrasian prices (Q6599058)

In this paper, the authors provide a flow-based ascending auction for multi-unit markets where all buyers have truncated additive valuations. It is shown that by iteratively raising the prices on a left-most min cut we can compute buyer-optimal Walrasian prices via an ascending auction. More precisely, the authors present a combinatorial network flow algorithm to compute buyer-optimal Walrasian prices in a multi-unit matching market with truncated additive valuation functions. The new part here is the simple and efficient flow-based algorithm to determine the sets on which prices should be raised in the ascending auction, namely the minimal maximum overdemanded sets. The authors prove the monotonicity of the buyer-optimal Walrasian prices with respect to changes in supply or demand (see Section 4 for more details).