Designing a strategic bipartite matching market

Abstract

We consider a version of the Gale-Shapley matching problem and the Shapley-Shubik assignment game. It involves matching n buyers with m sellers. Each seller offers a distinct good and a buyer has a different valuation for various goods, and it only wants one. The matching may also involve an exchange of numeraire to be paid by the buyers, and to the sellers. The players are strategic. The key requirements are ex ante individual rationality, strong budget-balance and efficiency at equilibrium. The motivation is a advertiser-host matching system. We propose an auction-based matching mechanism. The mechanism is non-VCG (Vickrey-Clarke-Groves) type, ex ante individual rational and is able to achieve strong budget-balance. Further, we show that there exists a Nash equilibrium that is efficient. © 2007 IEEE.