Cardinal-Utility Matching Markets: Pricing is Intractability, but Nash Bargaining Works!

Vijay Vazirani (UC Irvine)

Cardinal-Utility Matching Markets: Pricing is Intractability, but Nash Bargaining Works! 

For a mechanism to be truly impactful, it must combine strong game-theoretic properties with computational efficiency -- a classic example is the Gale–Shapley (1962) stable matching algorithm. This talk focuses on cardinal-utility matching markets, for which the most well known mechanism is the pricing-based approach of Hylland and Zeckhauser (1979). While this mechanism satisfies several desirable game-theoretic properties, recent work has shown it to be computationally intractable, both in theory and in practice.

This talk will review a series of papers that:
a) establish this intractability;
b) propose an alternative mechanism based on Nash bargaining; 
c) demonstrate that this new mechanism achieves game-theoretic and computational guarantees; and
d) provide evidence that significantly better alternatives are unlikely.

This talk is self contained and is based on these (1, 2, 3, 4, 5) and related papers.