Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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

Gudmundsson, Jens LU (2014) In Working Paper / Department of Economics, School of Economics and Management, Lund University
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... (More)
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." (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Working paper/Preprint
publication status
published
subject
keywords
Pairing problems, Sequences, Stability, Strategy-proofness, Algorithms
in
Working Paper / Department of Economics, School of Economics and Management, Lund University
issue
40
pages
37 pages
publisher
Department of Economics, Lund University
language
English
LU publication?
yes
id
147930f9-1c63-4941-92a6-96945ef02853 (old id 4865091)
alternative location
http://swopec.hhs.se/lunewp/abs/lunewp2014_040.htm
date added to LUP
2016-04-04 12:02:55
date last changed
2018-11-21 21:08:43
@misc{147930f9-1c63-4941-92a6-96945ef02853,
  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."}},
  author       = {{Gudmundsson, Jens}},
  keywords     = {{Pairing problems; Sequences; Stability; Strategy-proofness; Algorithms}},
  language     = {{eng}},
  note         = {{Working Paper}},
  number       = {{40}},
  publisher    = {{Department of Economics, Lund University}},
  series       = {{Working Paper / Department of Economics, School of Economics and Management, Lund University}},
  title        = {{Sequences in Pairing Problems: A New Approach to Reconcile Stability with Strategy-Proofness for Elementary Matching Problems}},
  url          = {{http://swopec.hhs.se/lunewp/abs/lunewp2014_040.htm}},
  year         = {{2014}},
}