TL;DR
This paper introduces "mechanism design over social networks" for two-sided matching, where one side (students) is distributed across a network and not fully known to the designer. They propose three novel mechanisms and analyze their trade-offs across incentive compatibility, efficiency, stability, and fairness, demonstrating that existing mechanisms are insufficient for this new setting.
What Problem Does This Paper Address?
Traditional two-sided matching mechanisms, like the Gale-Shapley Deferred Acceptance (DA) and Shapley-Scarf Top-Trading-Cycles (TTC), assume the designer has full knowledge of all participants. However, in many real-world scenarios, such as school choice or resource allocation, one group of participants (e.g., students) is spread across a social network, and their participation and preferences are not directly observable. Information about matching programs often diffuses through peer-to-peer networks. This paper tackles the challenge of designing mechanisms that incentivize participants to spread information about the matching program within their social networks, while still ensuring desirable properties like strategy-proofness, efficiency, stability, and fairness.
Methods
The authors propose three new mechanisms for two-sided matching over social networks:
- One-Shot College-Offering (OSCO): This mechanism is designed from scratch. Colleges make offers to a subset of "safe" students (those not attacked by others in the network). Students then choose their best offer. This mechanism is designed to be strategy-proof (SP) and achieve fairness (FRN) and a relaxed form of stability (MB-C).
- Sequential Deferred-Acceptance (SeqDA): This mechanism adapts the standard DA algorithm. It applies DA sequentially based on the "distance" of students from the moderator in the social network. This approach aims to achieve weak group strategy-proofness (W-GSP), fairness (FRD), efficiency (NW), and a relaxed stability (MB-D).
- Sequential Top-Trading-Cycles (SeqTTC): Similar to SeqDA, this mechanism adapts the TTC algorithm by applying it sequentially based on student distance from the moderator. It aims to achieve W-GSP, Pareto efficiency (PE), and a relaxed stability (MB-D).
The paper also rigorously defines 13 properties across four criteria (incentives, efficiency, stability, fairness) and proves several impossibility results, showing which combinations of properties cannot be simultaneously achieved. These impossibility results are crucial for understanding the Pareto frontier of achievable outcomes.
Datasets
Not discussed in the paper. The paper focuses on theoretical mechanism design and uses simulated social network structures and preference profiles for proofs and analysis.
Key Insights and Ideas
- Social Diffusion is Key: The core insight is that in networked environments, information diffusion is critical, and mechanisms must incentivize this diffusion. This fundamentally changes the design space compared to traditional matching.
- Trade-offs are Inevitable: The paper highlights significant trade-offs between efficiency, fairness, and incentive compatibility. For instance, achieving Pareto efficiency (PE) is incompatible with the weakest fairness property (FRD) when strategy-proofness is also required.
- Relaxed Stability is Necessary: Traditional stability concepts (like MB) are often too strong to achieve in networked settings with incentive constraints. The paper introduces and utilizes weaker stability notions (MB-C, MB-D) that are more achievable.
- Sequential Application of Standard Mechanisms Works (with caveats): Adapting well-known mechanisms like DA and TTC by applying them sequentially based on network distance is a viable strategy, but it doesn't solve all problems and still faces limitations.
- "Safe" Students are Crucial for OSCO: The OSCO mechanism's design hinges on identifying "safe" students, who are less susceptible to manipulation, to make initial offers.
Key Results
The paper proposes three mechanisms (OSCO, SeqDA, SeqTTC) that are shown to be on the Pareto frontier with respect to the 13 defined properties. This means that for each mechanism, no single property can be strengthened without weakening another property, given the other properties it already satisfies.
Key results include:
- Impossibility Theorems: Several theorems demonstrate the incompatibility of certain desirable properties, e.g., PE and FRD cannot coexist; SP, FR, and MB-D cannot coexist.
- Mechanism Properties:
- OSCO satisfies SP, FRN, and MB-C.
- SeqDA satisfies W-GSP, FRD, NW, and MB-D.
- SeqTTC satisfies W-GSP, PE, and MB-D.
- Pareto Frontier: The proposed mechanisms collectively demonstrate the achievable boundaries of these properties, showing what is possible and what is not in this new domain.
Limitations and Future Work
- Limited Scope of Impossibility Results: While the impossibility results are tight for the 13 properties considered, there might be other combinations of properties or slightly stronger/weaker versions that could lead to different conclusions.
- Focus on Specific Network Structures: The proofs often rely on specific network structures (e.g., Diffusion Critical Trees - DCTs). Generalizing these results to arbitrary complex networks could be challenging.
- Future Work:
- Investigate mechanisms that satisfy slightly stronger properties than those achieved by the proposed mechanisms, potentially by finding properties that lie "between" the defined ones.
- Extend the model to scenarios where both students and colleges are distributed over networks.
- Explore more general formulations of two-sided matching over social networks.
Summary updated