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, where the most influential 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; and
c) demonstrate that this new mechanism achieves game-theoretic and computational guarantees, with evidence suggesting that significantly better alternatives are unlikely.

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