Descending price algorithm for determining market clearing prices in matching markets

A descending price algorithm based auction mechanism in a two-sided matching market is proposed in this paper to determine market clearing prices. For general valuations with a intelligent choice of reverse constricted sets, we prove that the algorithm converges in a finite number of rounds. Then specializing to the rank one valuations in sponsored search markets, the proposed algorithm yields the element-wise maximum market clearing price.