EconPapers    
Economics at your fingertips  
 

Sequences in Pairing Problems: A New Approach to Reconcile Stability with Strategy-Proofness for Elementary Matching Problems

Jens Gudmundsson

No 2014:40, Working Papers from Lund University, Department of Economics

Abstract: We study two-sided ("marriage") and general pairing ("roommate") problems. We introduce "sequences," lists of matchings that are repeated in order. Stable sequences are natural extensions of stable matchings; case in point, we show that a sequence of stable matchings is stable. In addition, stable sequences can provide solutions to problems for which stable matchings do not exist. In a sense, they allow us to "balance" the interest of the agents at different matchings. In this way, sequences can be superior to matchings in terms of welfare and fairness. A seminal result due to Roth (1982, Math Oper Res 7(4), 617-628) is that no strategy-proof rule always selects stable matchings. In contrast, we show that there is a weakly group sd-strategy-proof rule that selects stable sequences. We call it the Compromises and Rewards rule, CR. We find that stronger incentive properties are incompatible with much weaker stability properties and vice versa. The CR rule satisfies two fairness axioms: anonymity and side neutrality. For the general problem, the Generalized CR rule is sd-5-stable (cannot be blocked by groups of five or fewer agents), weakly sd-strategy-proof, and anonymous. In addition, the Extended All-Proposing Deferred Acceptance rule is sd-stable, anonymous, and individually rational at all times on a restricted domain. We provide a condition under which our results still hold if agents have cardinal preferences and compare sequences using "expected utility."

Keywords: Pairing problems; Sequences; Stability; Strategy-proofness; Algorithms (search for similar items in EconPapers)
JEL-codes: C62 D02 D60 (search for similar items in EconPapers)
Pages: 37 pages
Date: 2014-11-24
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://project.nek.lu.se/publications/workpap/papers/wp14_40.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to project.nek.lu.se:80 (No such host is known. )

Related works:
Working Paper: Sequences in Pairing Problems: A new approach to reconcile stability with strategy-proofness for elementary matching problems (2014) Downloads
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hhs:lunewp:2014_040

Access Statistics for this paper

More papers in Working Papers from Lund University, Department of Economics School of Economics and Management, Box 7080, S-22007 Lund, Sweden. Contact information at EDIRC.
Bibliographic data for series maintained by Iker Arregui Alegria ().

 
Page updated 2025-02-10
Handle: RePEc:hhs:lunewp:2014_040