Showing posts with label Shapley. Show all posts
Showing posts with label Shapley. 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.


Friday, June 30, 2023

Lloyd Shapley (1923-2016) Centennial

 Lloyd Harlow Shapley was born in 1923: he would be (and I guess is) 100 years old this year.  His family is assembling a website honoring his centennial. (It's part of a family of web pages devoted to the life and work of Lloyd's dad, the astronomer Harlow Shapley.)

Here's the page for the Lloyd Shapley Centennial

It appears to be a work in progress, with many links. It begins this way:

"Lloyd Shapley (1923-2016) was a Nobel prizewinning mathematician. Shapley’s "intellectual life and career ... was among the most fertile of the 20th century." For the Centennial of Lloyd’s birth the Harlow Shapley Project offers this easy-access guide to Lloyd's WORK, his favorite GAME Kriegspiel, personal STORIES not published before and his four PRIZES.

"Lloyd Shapley was one of the founding giants of game theory. He shared the 2012 Nobel Prize in Economics for his seminal work with the late David Gale on stable matching – situations in which there are no two agents who would prefer one another over their current counterparts. But "he could have won a Nobel for any of a number of his papers that initiated whole literatures,” wrote Alvin E. Roth, Lloyd’s Nobel co-winner (right).

"Mathematical giant John von Neumann (right) invited Lloyd to leave RAND for Princeton on the basis of a two-page paper Lloyd sent him. After getting his Princeton PhD Lloyd returned to RAND full-time. He was a very productive member of the fabled Mathematics Division. Lloyd was almost unbeatable in the Division’s lunchtime Kriegspiel matches. 

"The Work page has summaries of Lloyd’s main contributions prepared by Dr. Bruce E. Krell, a game theorist who was a colleague of Lloyd’s at RAND. The Work page also offers a bibliography of selected descriptions of his work. The Work includes the 1962 “marriage problem” paper with David Gale (right), which won the Nobel."