from Market Design at https://bit.ly/3wMVwX5 on May 26, 2024 at 01:54PM
The May issue of Games and Economic Behavior has several papers on matching that caught my eye:
Games and Economic Behavior, Volume 145, May 2024
Strong core and Pareto-optimality in the multiple partners matching problem under lexicographic preference domains, by Péter Biró and Gergely Csáji
Abstract: We study strong core and Pareto-optimal solutions for multiple partners matching problem under lexicographic preference domains from a computational point of view. The restriction to the two-sided case is called stable many-to-many matching problem and the general one-sided case is called stable fixtures problem. We provide an example to show that the strong core can be empty even for many-to-many problems, and that deciding the non-emptiness of the strong core is NP-hard. On the positive side, we give efficient algorithms for finding a near feasible strong core solution and for finding a fractional matching in the strong core of fractional matchings. In contrast with the NP-hardness result for the stable fixtures problem, we show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many-to-many problems. Finally, we show that for reverse-lexicographic preferences the strong core is always non-empty in the many-to-many case.
Bayesian stable states, by Yi-Chun Chen an, Gaoji Hu b
Abstract: This paper extends the Bayesian stability notion of Liu (2020) to define the Bayesian stability of a market state, which consists of a matching outcome and an information structure. The information structure can be arbitrarily heterogeneous and can accommodate learning among agents. We first establish that a Bayesian stable matching function of Liu (2020) can be recast as Bayesian stable market states with homogeneous information. We then illustrate the usefulness of such an extension by (i) refining Liu’s Bayesian efficiency notion to define the Bayesian efficiency of a market state and (ii) generalizing his result—that Bayesian stable matching functions are Bayesian efficient—to an analogous one for market states. More importantly, we show that (iii) a decentralized matching process converges to a Bayesian stable market state and thereby offer a decentralized foundation for Liu’s Bayesian stable matching function.
Efficient matching under general constraints by Kenzo Imamura, Yasushi Kawase
Abstract: We study indivisible goods allocation problems under constraints and provide algorithms to check whether a given matching is Pareto efficient. We first show that the serial dictatorship algorithm can be used to check Pareto efficiency if the constraints are matroid. To prove this, we develop a generalized top trading cycles algorithm. Moreover, we show that the matroid structure is necessary for obtaining all Pareto efficient matchings by the serial dictatorship algorithm. Second, we provide an extension of the serial dictatorship algorithm to check Pareto efficiency under general constraints. As an application of our results to prioritized allocations, we discuss Pareto improving the deferred acceptance algorithm.
Health Econ Bot 