Chapter 10: Bayesian Estimation of Linear Sum Assignment Problems

The authors propose an Markov Chain Monte Carlo (MCMC) method for estimating a class of linear sum assignment problems (LSAP; the discrete case of the optimal transport problems). Prominent examples include multi-item auctions and mergers in industrial organizations. This contribution is to decompose the joint likelihood of the allocation and prices by exploiting the primal and dual linear programming formulation of the underlying LSAP. Our decomposition, coupled with the data augmentation technique, leads to an MCMC sampler without a repeated model-solving phase.