Here's a wide-ranging paper that explores the way the Top Tradinig Cycles (TTC) algorithm 'respects improvements' by rewarding an agent whose endowment becomes more desirable.
Biró, Péter, Flip Klijn, Xenia Klimentova, and Ana Viana. "Shapley–Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange." Mathematics of Operations Research (2023).
"Abstract: In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that, for strict preferences, the unique strong core allocation “respects improvement”—if an agent’s object becomes more desirable for some other agents, then the agent’s allotment in the unique strong core allocation weakly improves. We extend this result to weak preferences for both the strong core (conditional on nonemptiness) and the set of competitive allocations (using probabilistic allocations and stochastic dominance). There are no counterparts of the latter two results in the two-sided matching literature. We provide examples to show how our results break down when there is a bound on the length of exchange cycles. Respecting improvements is an important property for applications of the housing markets model, such as kidney exchange: it incentivizes each patient to bring the best possible set of donors to the market. We conduct computer simulations using markets that resemble the pools of kidney exchange programs. We compare the game-theoretical solutions with current techniques (maximum size and maximum weight allocations) in terms of violations of the respecting improvement property. We find that game-theoretical solutions fare much better at respecting improvements even when exchange cycles are bounded, and they do so at a low efficiency cost. As a stepping stone for our simulations, we provide novel integer programming formulations for computing core, competitive, and strong core allocations."
Here is their literature review:
"The nonemptiness of the core is proved in Shapley and Scarf [47] by showing the balancedness of the corresponding nontransferable utility game and also in a constructive way by showing that David Gale’s famous top trading cycles (TTC) algorithm always yields competitive allocations. Roth and Postlewaite [40] later show that, for strict preferences, the TTC results in the unique strong core allocation, which coincides with the unique competitive allocation in this case. However, if preferences are not strict (i.e., ties are present), the strong core can be empty or contain more than one allocation, but the TTC still produces all competitive allocations. Wako [50] shows that the strong core is always a subset of the set of competitive allocations. Quint and Wako [39] provide an efficient algorithm for finding a strong core allocation whenever there exists one. Their work is further generalized and simplified by Cechlárová and Fleiner [19], who use graph models. Wako [52] shows that the set of competitive allocations coincides with the core based on an antisymmetric weak domination concept, which we refer to as Wako-core in this paper. This equivalence is key for our extension of the definition of competitive allocations to the case of bounded exchange cycles.
1.2.2. Respecting Improvement.
"For Gale and Shapley’s [23] college admissions model, Balinski and Sönmez [11] prove that SOSM respects improvement of student’s quality. Kominers [29] generalizes this result to more general settings. Balinski and Sönmez [11] also show that SOSM is the unique stable mechanism that respects improvement of student quality. Abdulkadiroğlu and Sönmez [3] propose and discuss the use of TTC in a model of school choice, which is closely related to the college admissions model. Abdulkadiroğlu and Che [2] state and Hatfield et al. [25] formally prove that the TTC mechanism respects improvement of student quality.
"Hatfield et al. [25] also focus on the other side of the market and study the existence of mechanisms that respect improvement of a college’s quality. The fact that colleges can match with multiple students leads to a strong impossibility result: they prove that there is no stable or Pareto-efficient mechanism that respects improvement of a college’s quality. In particular, the (Pareto-efficient) TTC mechanism does not respect improvement of a college’s quality.
"In the context of KEPs with pairwise exchanges, the incentives for bringing an additional donor to the exchange pool was first studied by Roth et al. [42]. In the model of housing markets their donor-monotonicity property boils down to the respecting improvement property. They show that so-called priority mechanisms are donor-monotonic if each agent’s preferences are dichotomous, that is, the agent is indifferent between all acceptable donors. However, if agents have nondichotomous preferences, then any mechanism that maximizes the number of pairwise exchanges (so, in particular, any priority mechanism) does not respect improvement. This can be easily seen by means of Example 4 in Section 3.3.
#######
See also
The core of housing markets from an agent’s perspective: Is it worth sprucing up your home? by Ildiko Schlotter, , Peter Biro, and Tamas Fleiner
Abstract. We study housing markets as introduced by Shapley and Scarf (1974). We investigate the computational complexity of various questions regarding the situation of an agent a in a housing market H: we show that it is NP-hard to find an allocation in the core of H where (i) a receives a certain house, (ii) a does not receive a certain house, or (iii) a receives a house other than her own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the core of H where agent a receives a house h, if the value of the house owned by a increases, then the resulting housing market admits an allocation in its core in which a receives either h or a house that a prefers to h; moreover, such an allocation can be found efficiently. We further show an analogous result in the Stable Roommates setting by proving that stable matchings in a one-sided market also respect improvement.
Posts
No comments:
Post a Comment