Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy)

Sampath Kannan; Jamie Morgenstern; Aaron Roth; Zhiwei Steven Wu

doi:10.1137/1.9781611973730.126

Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy)

Sampath Kannan, Jamie Morgenstern, Aaron Roth, Zhiwei Steven Wu

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

10 Scopus citations

Abstract

We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst-case preferences (for schools and students) in large markets.

Original language	English (US)
Title of host publication	Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Publisher	Association for Computing Machinery
Pages	1890-1903
Number of pages	14
Edition	January
ISBN (Electronic)	9781611973747
DOIs	https://doi.org/10.1137/1.9781611973730.126
State	Published - 2015
Externally published	Yes
Event	26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States Duration: Jan 4 2015 → Jan 6 2015

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Number	January
Volume	2015-January

Other

Other	26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Country/Territory	United States
City	San Diego
Period	1/4/15 → 1/6/15

Bibliographical note

Publisher Copyright:
Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

Access

10.1137/1.9781611973730.126

OpenUrl availability

Full text

Cite this

Kannan, S., Morgenstern, J., Roth, A., & Wu, Z. S. (2015). Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy). In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 (January ed., pp. 1890-1903). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2015-January, No. January). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973730.126

Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy). / Kannan, Sampath; Morgenstern, Jamie; Roth, Aaron et al.
Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January. ed. Association for Computing Machinery, 2015. p. 1890-1903 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2015-January, No. January).

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

Kannan, S, Morgenstern, J, Roth, A & Wu, ZS 2015, Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy). in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January edn, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, no. January, vol. 2015-January, Association for Computing Machinery, pp. 1890-1903, 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, United States, 1/4/15. https://doi.org/10.1137/1.9781611973730.126

Kannan S, Morgenstern J, Roth A, Wu ZS. Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy). In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January ed. Association for Computing Machinery. 2015. p. 1890-1903. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; January). doi: 10.1137/1.9781611973730.126

Kannan, Sampath ; Morgenstern, Jamie ; Roth, Aaron et al. / Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy). Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015. January. ed. Association for Computing Machinery, 2015. pp. 1890-1903 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; January).

@inproceedings{c81c61873e624717867bcce83020bf57,

title = "Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy)",

abstract = "We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst-case preferences (for schools and students) in large markets.",

author = "Sampath Kannan and Jamie Morgenstern and Aaron Roth and Wu, {Zhiwei Steven}",

note = "Publisher Copyright: Copyright {\textcopyright} 2015 by the Society for Industrial and Applied Mathmatics.; 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 ; Conference date: 04-01-2015 Through 06-01-2015",

year = "2015",

doi = "10.1137/1.9781611973730.126",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

number = "January",

pages = "1890--1903",

booktitle = "Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015",

edition = "January",

}

TY - GEN

T1 - Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy)

AU - Kannan, Sampath

AU - Morgenstern, Jamie

AU - Roth, Aaron

AU - Wu, Zhiwei Steven

PY - 2015

Y1 - 2015

N2 - We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst-case preferences (for schools and students) in large markets.

AB - We present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school optimal matchings, assuming worst-case preferences (for schools and students) in large markets.

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

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

U2 - 10.1137/1.9781611973730.126

DO - 10.1137/1.9781611973730.126

M3 - Conference contribution

AN - SCOPUS:84938283763

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1890

EP - 1903

BT - Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

PB - Association for Computing Machinery

T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Y2 - 4 January 2015 through 6 January 2015

ER -

Approximately stable, school optimal, and student-truthful many-to-one matchings (via differential privacy)

Abstract

Publication series

Other

Bibliographical note

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this