Source-linked AI summary
Peer Effects and Stability in Matching Markets
Elizabeth Bodine-Baron, Christina Lee, Anthony Chong, Babak Hassibi, Adam Wierman
TL;DR
Many-to-one matching with peer effects and complementarities creates stability and efficiency challenges. The paper models these effects through an underlying social network and utility functions, then studies two-sided exchange stability. It proves existence and welfare-related stability results, develops algorithms and efficiency bounds, and shows that network structure affects inefficiency.
Problem
Peer effects and complementarities complicate many-to-one matching, creating challenges for stable outcomes and efficient matching mechanisms.
Method
The paper models peer effects using a social network and utility functions, and analyzes two-sided exchange-stable matchings, algorithms, and social welfare.
Results
Two-sided exchange-stable matchings always exist, while the price of anarchy can be unbounded and depends on social-network structure.
Takeaways & Limitations
The results indicate that clustering properties of the social network are important for understanding the efficiency of stable matchings.
Takeaways & Limitations
The efficiency bounds assume a one-sided market, similar student valuations of houses, and exactly met quotas.
Abstract
from arXiv · showhide
Many-to-one matching markets exist in numerous different forms, such as college admissions, matching medical interns to hospitals for residencies, assigning housing to college students, and the classic firms and workers market. In all these markets, externalities such as complementarities and peer effects severely complicate the preference ordering of each agent. Further, research has shown that externalities lead to serious problems for market stability and for developing efficient algorithms to find stable matchings. In this paper we make the observation that peer effects are often the result of underlying social connections, and we explore a formulation of the many-to-one matching market where peer effects are derived from an underlying social network. The key feature of our model is that it captures peer effects and complementarities using utility functions, rather than traditional preference ordering. With this model and considering a weaker notion of stability, namely two-sided exchange stability, we prove that stable matchings always exist and characterize the set of stable matchings in terms of social welfare. We also give distributed algorithms that are guaranteed to converge to a two-sided exchange stable matching. To assess the competitive ratio of these algorithms and to more generally characterize the efficiency of matching markets with externalities, we provide general bounds on how far the welfare of the worst-case stable matching can be from the welfare of the optimal matching, and find that the structure of the social network (e.g. how well clustered the network is) plays a large role.
1 Introduction
Many-to-one matching markets become difficult to stabilize when peer effects and complementarities make agents care about who else receives the same assignment. This paper models peer effects through social networks, studies two-sided exchange stability, and analyzes existence, algorithms, and efficiency.
- Motivation: Peer effects and complementarities make agents care about assignments beyond their own, complicating preference orderings in many-to-one markets.Examples include friends coordinating housing preferences and hospitals valuing diversity among assigned students.
- Motivation: Externalities make stable matchings difficult to guarantee and can make finding one computationally difficult.Prior work also finds that mechanism design becomes significantly more challenging when externalities are present.
- Approach: The paper models peer effects using a weighted, undirected social network and utility functions whose values depend on neighbors’ assignments.Utilities implicitly define preference orderings while allowing peer effects and complementarities.
- Approach: The paper studies two-sided exchange stability and characterizes stable matchings through existence, algorithms, and social-welfare efficiency.This stability notion is motivated by settings where agents can compare notes and exchange assignments.
- Results: Two-sided exchange-stable matchings always exist, and under shared house-valuation rules, welfare-maximizing matchings are exchange-stable.These results contrast with negative existence and computational findings for other many-to-one models with externalities.
- Results: The price of anarchy can grow with the number of houses, is typically sublinear, and depends on social-network clustering rather than the number of interns.The price of anarchy also bounds efficiency loss from peer effects.
2 Model and notation
The model represents housing assignments between students and houses, with quotas, a weighted friendship graph, utility-based peer effects and complementarities, exchange stability, and social-welfare efficiency measures.
- Utilities: House utility represents the desirability of its assigned student set and allows heterogeneous preferences over groups of students.This utility structure captures complementarities such as preferences for diversity.
- Matching structure: A matching assigns each student to one house and fills each house’s quota, using holes to represent unfilled positions.House quotas may differ, and holes have no friends or house preferences.
- Social network: Student peer effects arise from a weighted, undirected friendship graph whose vertices are students and whose edge weights measure relationship strength.The graph requires symmetric edge weights.
- Utilities: Student utility combines the desirability of the assigned house with the value of friends assigned to the same house.House desirability can represent physical characteristics or common rankings, while friendship weights capture peer effects.
- Stability: Two-sided exchange stability evaluates swaps of students, including swaps with holes, requiring approval from the directly involved agents.Assignments cannot leave the system, so the model considers exchanges rather than unilateral departures or unmatched outcomes.
- Efficiency: Social welfare measures assignment efficiency, while the price of anarchy and price of stability compare optimal welfare with the minimum or maximum welfare among stable matchings.These ratios quantify efficiency loss associated with exchange stability.
3 Existence of stable matchings
The paper establishes existence of two-sided exchange-stable matchings through a potential function and finite local search. Under stronger symmetry and no-vacancy conditions, welfare maximizers are also stable.
- Motivation: Prior matching models with externalities may lack stable outcomes, and finding one can be NP-hard.This motivates examining existence under the paper’s network-based model and exchange-stability notion.
- Potential-function argument: A potential function Φ(µ) is used to analyze exchange-stable matchings in the network-based matching game.The construction relies on the symmetry of the social network.
- Potential-function argument: Every local maximum of Φ(µ) is two-sided exchange-stable.Because the matching set is finite, a local maximum exists and therefore establishes existence of a stable matching.
- Welfare characterization: With exactly met quotas and identical house valuation rules across students, every local maximum of social welfare W(µ) is two-sided exchange-stable.The condition is expressed as equal house valuations for every pair of students.
- Welfare characterization: Under those conditions, a socially optimal matching is two-sided exchange-stable.Not every exchange-stable matching is a local maximum of the potential function or social welfare.
4 Finding stable matchings
The paper develops two natural algorithms for finding two-sided exchange-stable matchings: a distributed greedy welfare-improvement procedure and an MCMC heat-bath method. Experiments on two social networks show a speed–quality trade-off between the algorithms.
- The algorithms operate under the conditions of Theorem 4, including quotas that are exactly met.
- Algorithm 1: Algorithm 1 greedily applies approved student or house swaps that improve social welfare and can be implemented in a distributed manner.Each iteration may require searching many student and house pairs for an approved swap.
- Algorithm 1: Because social welfare strictly increases and welfare local maxima are two-sided exchange-stable, Algorithm 1 converges to a two-sided exchange-stable matching but not necessarily the socially optimal one.
- Algorithm 2: Algorithm 2 uses an MCMC heat bath that randomly swaps student pairs with probability determined by the change in social welfare and records the best matching found.With sufficiently long, perhaps exponential, runtime, it can find the optimal matching.
- Experiments: On the Caltech and Wikipedia networks, Algorithm 2 runs longer than Algorithm 1, while Algorithm 1 reaches sub-optimal welfare of the same order of magnitude as Algorithm 2.The figures plot social welfare at each iteration; the experiments use the Caltech and Wikipedia social-network data sets.
5 Efficiency of stable matchings
The paper measures efficiency loss from exchange-stability using PoS and PoA, showing that stable matchings can be arbitrarily inefficient but may be efficient under favorable network structure. Bounds depend on clustering, heterogeneity, quotas, edge weights, and house valuations rather than directly on student count.
- Price of Stability is 1 because a social-welfare-maximizing matching is exchange-stable.
- The price of anarchy can be unbounded, with four students and two quota-2 houses yielding welfare k optimally versus 2 for an exchange-stable matching.Thus, the price of anarchy grows linearly in k.
- Theorem 5 gives a tight PoA bound for unweighted networks with equal quotas and/or equal house valuations.Its tight example has a stable matching cutting all network edges, so min stable γ_m(µ) = 0.
- Theorem 6 removes the equal-quota and equal-valuation restrictions but provides a slightly weaker bound whose exact tightness remains unclear.A modified example nevertheless achieves price of anarchy Θ(mγ∗_m) asymptotically.
- The PoA has no direct dependence on the number of students, while quota, edge-weight, and house-value heterogeneity significantly affect inefficiency.
- Network effects enter through γ∗_m, which measures clustering into m quota-feasible groups and tends to shrink as m grows, making PoA sublinear in m.The paper relates γ∗_m to clustering metrics including conductance and expansion.
6 Concluding remarks
The paper develops positive results for many-to-one matching with peer effects derived from social networks, showing existence and stability properties while bounding inefficiency. It also identifies practical relevance for housing assignments and emphasizes that broader applicability requires relaxing simplifying assumptions.
- Social-network-based peer effects allow the paper to prove that two-sided exchange-stable matchings always exist and that socially optimal matchings are always stable.
- The paper bounds the maximal inefficiency of exchange-stable matchings and relates it to the clustering structure of the underlying social network.
- For residential housing assignments, reporting both house preferences and desired friends could support the paper’s algorithms and efficiency bounds.
- The efficiency bounds are limited to one-sided markets with similarly valued houses, exact quotas, and no house preferences over students.
A.1 General case: Local maxima of Φ(µ) are two-sided exchange-stable
The proof uses a potential function whose local maxima are two-sided exchange-stable. Because the matching space is finite, a global maximum exists and therefore guarantees a two-sided exchange-stable matching.
- The potential-function argument evaluates swaps involving students, houses, and possible vacancies, with symmetry simplifying the utility changes.
- A swap is analyzed by comparing utility changes for the involved students and the affected houses, whose changes are non-negative under the swap assumptions.
- The proof assumes a local maximum of Φ(µ) and shows that any acceptable swap would strictly increase the potential, yielding a contradiction.
- Since the number of matches is finite, a global maximum of the potential function exists and is two-sided exchange-stable.
- The same proof logic applies when house quotas are exactly met and students value houses according to common rules, including the one-sided market case.
B Proofs of PoA Theorems
The appendix proof specializes to one-sided markets with exactly filled house quotas and common student valuation rules. These assumptions remove vacancies and house-side utilities from the analysis.
- The one-sided proof assumes house utilities are zero and house quotas are exactly satisfied, so no vacancies or “holes” occur.
- Students are assumed to value houses according to the same rules in this one-sided setting.
- The appendix also uses E rather than |E| to denote the social network’s total edge weight.
B.1 Proof of Theorem 5
The proof of Theorem 5 reformulates exchange stability using students’ gains from moving between houses, then derives a lower bound on stable matchings’ internal edge weight. This yields price-of-anarchy bounds under stated assumptions and a tighter special-case bound.
- Exchange stability is expressed through α_µ(s,g), the benefit student s gains by moving to house g under matching µ.
- The resulting price-of-anarchy analysis applies to the one-sided market and notes that the two-sided case is left for future work.
- In the one-sided market, a student pair is exchange-stable when at least one student does not want to swap according to the α-based conditions.
- The proof bounds cross edges for stable matchings, then uses that bound to derive a lower bound on γ_m(µ).
- When E = 0, all matchings have the same welfare and the price of anarchy is 1.
- When D_h = 0, the price of anarchy is bounded by (2m−1)γ∗_m.
B.2 Proof of Theorem 6
The proof of Theorem 6 derives welfare bounds by combining cross-edge bounds from three stability cases, then treats separately whether E exceeds P.
- Cross-edge bounds: The proof first derives an upper bound on cross-edges between houses using stability conditions and lemmas for the possible exchange cases.The three cases cover a student in one house wanting to swap broadly, a student in the other house wanting to swap broadly, or neither condition holding.
- Cross-edge bounds: Because the graph is undirected, the three case-specific bounds can be combined into a single bound for stable matchings.The equality E_hg = E_gh permits the bounds to be summed and consolidated.
- Welfare bound: The resulting lower bound on γm(µ) is inserted into the welfare ratio to bound the price of anarchy.The proof uses Lemma 10, then substitutes for P using Lemma 13.
- Case 1: E > P: When E > P, the proof applies the Lemma 10 bound directly and simplifies the resulting welfare ratio.This case yields the displayed bound after algebraic substitution.
- Case 2: E ≤ P: When E ≤ P, the proof uses γm(µ) ≥ 0 because the alternative bound would be negative, then derives the corresponding welfare ratio.The nonnegativity follows from the nonnegative quantities E_in(µ) and E.
- Final bound: The two cases are combined into one looser bound for the theorem.The final result is obtained by taking a common bound across the cases.
C Technical Lemmas
The technical lemmas translate exchange stability into constraints on student connections and cross-house edges, which are then used to establish bounds under both restricted and general settings.
- Purpose: The appendix supplies lemmas used in the proofs of Theorems 5 and 6, including results for more general settings.The later lemmas parallel earlier arguments while extending their applicability.
- Cross-edge bounds: Lemma 11 bounds cross-edges E_gh when a student in house h has α_µ(s, g) > 1 for another house g.The bound is E_gh ≤ q_g(D_g − D_h) + 2E_gg.
- Student partitions: Lemma 12 partitions students in two houses into six groups according to house membership and α values when quotas or D values are uniform.The α categories are 1, 0, and negative, as illustrated in Figure 6.
- Student partitions: The partition yields three stability constraints: each pair involving α values (1,1), (1,0), or (0,1) must have w(s, t) = 1.These constraints provide a lower bound on edges between the two houses.
- Algebraic bounds: The proof relates graph edges to sums of α values and bounds the resulting quantities using inequalities involving within-house and cross-house edges.The argument specifically controls S1 − S−1 through a lower bound on E_gg and an elementary nonnegative function.
- Scope of bounds: The simple bound requires equal quotas or equal D values; otherwise, Theorem 6 applies, and some proof details are omitted.For unequal quotas with equal D values, the proof still obtains S1 − S−1 ≤ 2E_gg.
- General settings: Lemma 14 handles cases where one student wants to swap with every student in another house, while Lemma 15 handles cases where neither side has such a student.Both lemmas retain dependence on q_g, D_g − D_h, within-house edges, and q_maxw_max.