Showing posts with label Scarf. Show all posts
Showing posts with label Scarf. Show all posts

Monday, March 4, 2024

50th anniversary of Shapley and Scarf (1974), and of the Journal of Mathematical Economics

Now available online is the first in what I understand will be a series of papers commemorating the 50th anniversary of the Journal of Mathematical Economics.  The paper by Shapley and Scarf appeared in volume 1, number 1. (Thayer Morrill and I will have a paper surveying the literature on the Top Trading Cycle (TTC) algorithm, which was introduced in that first paper.)

Housing markets since Shapley and Scarf by Mustafa Oğuz Afacan, Gaoji Hu, and Jiangtao Li, Journal of Mathematical Economics, Available online 1 March 2024, In Press, Journal Pre-proof, https://doi.org/10.1016/j.jmateco.2024.102967

Abstract: Shapley and Scarf (1974) appeared in the first issue of the Journal of Mathematical Economics, and is one of the journal’s most impactful publications. As we approach the remarkable milestone of the journal’s 50th anniversary (1974–2024), this article serves as a commemorative exploration of Shapley and Scarf (1974) and the extensive body of literature that follows it.

Thursday, November 16, 2023

Top trading cycles 'respect improvements' by rewarding agents whose endowments become more desirable

 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 Hwe 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.


Wednesday, February 9, 2022

Stability in Matching Markets with Complex Constraints by H. Nguyen, T. Nguyen, and A. Teytelboym

 Here's a paper motivated in part by the issues that arise in matching refugee families to localities in which to settle (once they have been granted asylum in a particular country).  It's also a good example of the way that operations research methods are playing an increasing role in market design.

Hai Nguyen, Thành Nguyen, Alexander Teytelboym (2021) Stability in Matching Markets with Complex Constraints. Management Science 67(12):7438-7454. https://doi.org/10.1287/mnsc.2020.3869

Abstract. "We develop a model of many-to-one matching markets in which agents with multiunit demand aim to maximize a cardinal linear objective subject to multidimensional knapsack constraints. The choice functions of agents with multiunit demand are therefore not substitutable. As a result, pairwise stable matchings may not exist and even when they do, may be highly inefficient. We provide an algorithm that finds a group-stable matching that approximately satisfies all the multidimensional knapsack constraints. The novel ingredient in our algorithm is a combination of matching with contracts and Scarf’s Lemma. We show that the degree of the constraint violation under our algorithm is proportional to the sparsity of the constraint matrix. The algorithm, therefore, provides practical constraint violation bounds for applications in contexts, such as refugee resettlement, day care allocation, and college admissions with diversity requirements. Simulations using refugee resettlement data show that our approach produces outcomes that are not only more stable, but also more efficient than the outcomes of the Deferred Acceptance algorithm. Moreover, simulations suggest that in practice, constraint violations under our algorithm would be even smaller than the theoretical bounds."


"Around 50,000 refugees are resettled to the United States every year. Nine American resettlement agencies coordinate networks of dozens of local communities (which we refer to as localities) that support refugees during their first few years in the United States. Localities are allowed to admit different numbers of refugees and offer different services (e.g., language support, support for large families, support for single parents, etc.) that may or may not match the needs of the refugees (Ahani et al. 2021, Delacrétaz et al. 2019). In order to secure government approval to conduct resettlement, resettlement agencies must aim to maximize the number of refugees who are employed within 90 days of arrival. Some resettlement agencies have begun using integer optimization and machine learning in order to improve refugee outcomes (Bansak et al. 2018, Ahani et al. 2021); however, as far as we know, refugees’preferences over localities are presently not collected anywhere in the world.

...

Our algorithm is a novel combination of Scarf’s Lemma and a rounding procedure. We build on the approach of Nguyen and Vohra (2018); however, we make a number of substantial extensions and modifications. The novelty of our approach is the way we apply Scarf’s Lemma to capture group stability. To use Scarf’s Lemma for stable matching problems, one needs to create a constraint matrix Q, where each column corresponds to a possible blocking coalition. Hitherto, two methods to construct such a matrix have been proposed: first, with columns corresponding to all possible blocking coalitions (Scarf 1967); second, with columns corresponding to small blocking coalitions (a hospital and a doctor or a doctor couple and two hospitals) (see Nguyen and Vohra 2018). Although the method of Nguyen and Vohra only obtains matchings that are immune to deviations by small coalitions, Scarf’s method can, in principle, capture group stability. However, the disadvantage of Scarf’s method is that the resulting constraint matrix is not sparse, which prevents us from guaranteeing small error bounds in the rounding procedure.

"Our main structural contribution is a new way of combining ideas from matching with contracts with Scarf’s method in order to create an appropriate constraint matrix. A contract specifies both agents in the match as well as a “price” for one of the dimensions of the knapsack constraints. Our method allows us to get the best of both methods: the sparsity of our constraint matrix does not change, but the prices specified in the contracts still allow us to capture group stability via pairwise stability."

***********

Earlier:

Sunday, October 19, 2014

Tuesday, November 17, 2015

Herb Scarf, RIP

Rakesh Vohra memorializes Herb Scarf (1930-2015) with a quote from Horace, and passes along the sad news that Scarf passed away two days ago, on November 15.

Scarf was, as Vohra says, a colossus at the intersection of economics and operations research.

In my small corner of the world, a very important paper was Shapley and Scarf (1974), "On Cores and Indivisibility," published in volume 1 number 1 of the Journal of Mathematical Economics. It built on Scarf's work on the core of games without sidepayments, and introduced a way of thinking about barter for indivisible goods, via the top trading cycle algorithm (which Shapley and Scarf attributed to David Gale).

***************
Update: see obituraries,
http://economics.yale.edu/news/memory-herbert-e-scarf-july-25-1930-november-15-2015 

http://www.legacy.com/obituaries/nytimes/obituary.aspx?page=lifestory&pid=176545873