Acyclic roommates

José Alvaro Rodrigues-Neto

doi:10.1016/j.econlet.2012.11.027

Acyclic roommates

José Alvaro Rodrigues-Neto^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

In the context of the stable roommates problem, this paper provides an alternative characterization of acyclic instances with n roommates; one that requires checking n - 1 fewer equations than symmetry of the utility functions (Rodrigues-Neto, 2007). We introduce the concepts of agent-cycles and cycle equations and prove that an instance is acyclic if and only if there exists a representation of preferences such that all cycle equations of agent-cycles of length 3 containing an agent i hold. In this case, there is a unique stable matching.

Original language	English
Pages (from-to)	304-306
Number of pages	3
Journal	Economics Letters
Volume	118
Issue number	2
DOIs	https://doi.org/10.1016/j.econlet.2012.11.027
Publication status	Published - Feb 2013

Access to Document

10.1016/j.econlet.2012.11.027

Cite this

@article{01aad40c662b4f6fa4bd606683dfe457,

title = "Acyclic roommates",

abstract = "In the context of the stable roommates problem, this paper provides an alternative characterization of acyclic instances with n roommates; one that requires checking n - 1 fewer equations than symmetry of the utility functions (Rodrigues-Neto, 2007). We introduce the concepts of agent-cycles and cycle equations and prove that an instance is acyclic if and only if there exists a representation of preferences such that all cycle equations of agent-cycles of length 3 containing an agent i hold. In this case, there is a unique stable matching.",

keywords = "Acyclicity, Cycle, Kidney, Representation, Roommates, Symmetry",

author = "Rodrigues-Neto, \{Jos{\'e} Alvaro\}",

year = "2013",

month = feb,

doi = "10.1016/j.econlet.2012.11.027",

language = "English",

volume = "118",

pages = "304--306",

journal = "Economics Letters",

issn = "0165-1765",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Acyclic roommates

AU - Rodrigues-Neto, José Alvaro

PY - 2013/2

Y1 - 2013/2

N2 - In the context of the stable roommates problem, this paper provides an alternative characterization of acyclic instances with n roommates; one that requires checking n - 1 fewer equations than symmetry of the utility functions (Rodrigues-Neto, 2007). We introduce the concepts of agent-cycles and cycle equations and prove that an instance is acyclic if and only if there exists a representation of preferences such that all cycle equations of agent-cycles of length 3 containing an agent i hold. In this case, there is a unique stable matching.

AB - In the context of the stable roommates problem, this paper provides an alternative characterization of acyclic instances with n roommates; one that requires checking n - 1 fewer equations than symmetry of the utility functions (Rodrigues-Neto, 2007). We introduce the concepts of agent-cycles and cycle equations and prove that an instance is acyclic if and only if there exists a representation of preferences such that all cycle equations of agent-cycles of length 3 containing an agent i hold. In this case, there is a unique stable matching.

KW - Acyclicity

KW - Cycle

KW - Kidney

KW - Representation

KW - Roommates

KW - Symmetry

UR - https://www.scopus.com/pages/publications/84870888122

U2 - 10.1016/j.econlet.2012.11.027

DO - 10.1016/j.econlet.2012.11.027

M3 - Article

SN - 0165-1765

VL - 118

SP - 304

EP - 306

JO - Economics Letters

JF - Economics Letters

IS - 2

ER -

Acyclic roommates

Abstract

Access to Document

Other files and links

Fingerprint

Cite this