Descending Price Auction Algorithm for Determining Market Clearing Prices in Matching Markets

Matching markets occur in many real-world scenarios: sponsored search auctions, hospital-resident matching, kidney matching, etc. In many instances such as sponsored search auctions, market making is facilitated by assessing prices for goods. We will consider the simplest setting of a two-sided matching market with sellers selling at most one copy of a good and buyers interested in at most one good, which has connections to cross-bar switches. We will present a descending price algorithm based auction mechanism to determine market clearing prices so that efficiency obtains. For general valuations with an 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, corresponding to sponsored search markets, we demonstrate that the proposed algorithm yields the element-wise maximum market clearing price. If time permits we will discuss further results on characterizing the computational complexity of the algorithm and final price vector, both for general valuations.

This is joint work with Shih-Tang Su, Jake Abernethy and Grant Schoenebeck, EECS, University of Michigan, Ann Arbor.

Vijay Subramaniam received the B.Tech. degree in Electronics Engineering from IIT Madras in 1993. Subsequently, he obtained M.Sc. (Engg.) degree in Electrical Communication Engineering from IISc Bangalore in 1995 and Ph.D. in Electrical Engineering from University of Illinois at Urbana-Champaign. Currently, he is an Assistant Professor in the EECS Department at the University of Michigan. His interests are in stochastic modeling, communications, information theory and applied mathematics.