Compromises and Rewards: Stable and Non-manipulable Probabilistic Pairing

Can we reconcile stability with non-manipulability in pairing problems by selecting lotteries over matchings?We examine the problem of eliciting preferences to make pairs as introduced by Gale and Shapley (1962). We develop ex-ante notions of stability and non-manipulability that are parameterized by collections of utility functions. In particular, we study the collection of utility functions with increasing differences for which stability and non-manipulability turn out to characterize Compromises and Rewards. This is a novel rule that is fundamentally different from the one that has attracted most attention in the literature, Deferred Acceptance.