The (Non)-existence of stable mechanisms in incomplete information environments

Nick Arnosti; Nicole Immorlica; Brendan Lucier

doi:10.1007/978-3-662-48995-6_4

The (Non)-existence of stable mechanisms in incomplete information environments

Nick Arnosti, Nicole Immorlica, Brendan Lucier

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We consider two-sided matching markets, and study the incentives of agents to circumvent a centralized clearing house by signing binding contracts with one another. It is well-known that if the clearing house implements a stable match and preferences are known, then no group of agents can profitably deviate in this manner. We ask whether this property holds even when agents have incomplete information about their own preferences or the preferences of others. We find that it does not. In particular, when agents are uncertain about the preferences of others, every mechanism is susceptible to deviations by groups of agents. When, in addition, agents are uncertain about their own preferences, every mechanism is susceptible to deviations in which a single pair of agents agrees in advance to match to each other.

Original language	English (US)
Title of host publication	Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings
Editors	Guido Schäfer, Evangelos Markakis
Publisher	Springer Verlag
Pages	46-59
Number of pages	14
ISBN (Print)	9783662489949
DOIs	https://doi.org/10.1007/978-3-662-48995-6_4
State	Published - 2015
Externally published	Yes
Event	11th International Conference on Web and Internet Economics, WINE 2015 - Amsterdam, Netherlands Duration: Dec 9 2015 → Dec 12 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9470
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	11th International Conference on Web and Internet Economics, WINE 2015
Country/Territory	Netherlands
City	Amsterdam
Period	12/9/15 → 12/12/15

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.

Access

10.1007/978-3-662-48995-6_4

Cite this

Arnosti, N., Immorlica, N., & Lucier, B. (2015). The (Non)-existence of stable mechanisms in incomplete information environments. In G. Schäfer, & E. Markakis (Eds.), Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings (pp. 46-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9470). Springer Verlag. https://doi.org/10.1007/978-3-662-48995-6_4

The (Non)-existence of stable mechanisms in incomplete information environments. / Arnosti, Nick; Immorlica, Nicole; Lucier, Brendan.

Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings. ed. / Guido Schäfer; Evangelos Markakis. Springer Verlag, 2015. p. 46-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9470).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Arnosti, N, Immorlica, N & Lucier, B 2015, The (Non)-existence of stable mechanisms in incomplete information environments. in G Schäfer & E Markakis (eds), Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9470, Springer Verlag, pp. 46-59, 11th International Conference on Web and Internet Economics, WINE 2015, Amsterdam, Netherlands, 12/9/15. https://doi.org/10.1007/978-3-662-48995-6_4

Arnosti N, Immorlica N, Lucier B. The (Non)-existence of stable mechanisms in incomplete information environments. In Schäfer G, Markakis E, editors, Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings. Springer Verlag. 2015. p. 46-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-662-48995-6_4

Arnosti, Nick ; Immorlica, Nicole ; Lucier, Brendan. / The (Non)-existence of stable mechanisms in incomplete information environments. Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings. editor / Guido Schäfer ; Evangelos Markakis. Springer Verlag, 2015. pp. 46-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b979501213c649a08be0278798dd9520,

title = "The (Non)-existence of stable mechanisms in incomplete information environments",

abstract = "We consider two-sided matching markets, and study the incentives of agents to circumvent a centralized clearing house by signing binding contracts with one another. It is well-known that if the clearing house implements a stable match and preferences are known, then no group of agents can profitably deviate in this manner. We ask whether this property holds even when agents have incomplete information about their own preferences or the preferences of others. We find that it does not. In particular, when agents are uncertain about the preferences of others, every mechanism is susceptible to deviations by groups of agents. When, in addition, agents are uncertain about their own preferences, every mechanism is susceptible to deviations in which a single pair of agents agrees in advance to match to each other.",

author = "Nick Arnosti and Nicole Immorlica and Brendan Lucier",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 11th International Conference on Web and Internet Economics, WINE 2015 ; Conference date: 09-12-2015 Through 12-12-2015",

year = "2015",

doi = "10.1007/978-3-662-48995-6_4",

language = "English (US)",

isbn = "9783662489949",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "46--59",

editor = "Guido Sch{\"a}fer and Evangelos Markakis",

booktitle = "Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings",

}

TY - GEN

T1 - The (Non)-existence of stable mechanisms in incomplete information environments

AU - Arnosti, Nick

AU - Immorlica, Nicole

AU - Lucier, Brendan

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2015.

PY - 2015

Y1 - 2015

N2 - We consider two-sided matching markets, and study the incentives of agents to circumvent a centralized clearing house by signing binding contracts with one another. It is well-known that if the clearing house implements a stable match and preferences are known, then no group of agents can profitably deviate in this manner. We ask whether this property holds even when agents have incomplete information about their own preferences or the preferences of others. We find that it does not. In particular, when agents are uncertain about the preferences of others, every mechanism is susceptible to deviations by groups of agents. When, in addition, agents are uncertain about their own preferences, every mechanism is susceptible to deviations in which a single pair of agents agrees in advance to match to each other.

AB - We consider two-sided matching markets, and study the incentives of agents to circumvent a centralized clearing house by signing binding contracts with one another. It is well-known that if the clearing house implements a stable match and preferences are known, then no group of agents can profitably deviate in this manner. We ask whether this property holds even when agents have incomplete information about their own preferences or the preferences of others. We find that it does not. In particular, when agents are uncertain about the preferences of others, every mechanism is susceptible to deviations by groups of agents. When, in addition, agents are uncertain about their own preferences, every mechanism is susceptible to deviations in which a single pair of agents agrees in advance to match to each other.

UR - http://www.scopus.com/inward/record.url?scp=84951873425&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84951873425&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48995-6_4

DO - 10.1007/978-3-662-48995-6_4

M3 - Conference contribution

AN - SCOPUS:84951873425

SN - 9783662489949

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 46

EP - 59

BT - Web and Internet Economics - 11th International Conference, WINE 2015, Proceedings

A2 - Schäfer, Guido

A2 - Markakis, Evangelos

PB - Springer Verlag

T2 - 11th International Conference on Web and Internet Economics, WINE 2015

Y2 - 9 December 2015 through 12 December 2015

ER -

The (Non)-existence of stable mechanisms in incomplete information environments

Abstract

Publication series

Other

Bibliographical note

Access

Other files and links

Fingerprint

Cite this