2 Search Results for "Tardos, �va"

Document
DOI: 10.4230/LIPIcs.ITCS.2021.74
Randomness and Fairness in Two-Sided Matching with Limited Interviews

Authors: Hedyeh Beyhaghi and Éva Tardos

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
We study the outcome in a matching market where both sides have limited ability to consider options. For example, in the national residency matching program, doctors are limited to apply to a small set of hospitals, and hospitals are limited by the time required to interview candidates. Our main findings are the following: (1) In markets where jobs can only consider a limited number of candidates for interview, it increases the size of the resulting matching if the system has a limit on the number of applications a candidate can send. (2) The fair system of all applicants being allowed to apply to the exact same number of positions maximizes the expected size of the matching. More particularly, starting from an integer k as the number of applications, the matching size decreases as a few applicants are allowed to apply to one additional position (and then increases again as they are all allowed to apply to k+1). Although it seems natural to expect that the size of the matching would be a monotone increasing and concave function in the number of applications, our results show that neither is true. These results hold even in a market where a-priori all jobs and all candidates are equally likely to be good, and the judgments of different employers and candidates are independent. Our main technical contribution is computing the expected size of the matching found via the deferred acceptance algorithm as a function of the number of interviews and applications in a market where preferences are uniform and independent. Through simulations we confirm that these findings extend to markets where rankings become correlated after the interviews.
Cite as

Hedyeh Beyhaghi and Éva Tardos. Randomness and Fairness in Two-Sided Matching with Limited Interviews. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 74:1-74:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{beyhaghi_et_al:LIPIcs.ITCS.2021.74,
  author =	{Beyhaghi, Hedyeh and Tardos, \'{E}va},
  title =	{{Randomness and Fairness in Two-Sided Matching with Limited Interviews}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{74:1--74:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.74},
  URN =		{urn:nbn:de:0030-drops-136139},
  doi =		{10.4230/LIPIcs.ITCS.2021.74},
  annote =	{Keywords: Matching with Short Lists, Stable Matching, Balls in Bins Problem}
}
Document
DOI: 10.4230/DagRep.3.4.69
Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161)

Authors: Sergiu Hart, Éva Tardos, and Bernhard von Stengel

Published in: Dagstuhl Reports, Volume 3, Issue 4 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13161 "Interface of Computation, Game Theory, and Economics". The workshop was strongly interdisciplinary, on the leading edge of current topics generally connected to algorithmic game theory: Mechanism design and auctions, interactions in networks, social models, and dynamics and equilibrium in games and markets. We summarize these topics, give the talk abstracts, and comment on experiences related to the organization of the workshop.
Cite as

Sergiu Hart, Éva Tardos, and Bernhard von Stengel. Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161). In Dagstuhl Reports, Volume 3, Issue 4, pp. 69-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{hart_et_al:DagRep.3.4.69,
  author =	{Hart, Sergiu and Tardos, \'{E}va and von Stengel, Bernhard},
  title =	{{Interface of Computation, Game Theory, and Economics (Dagstuhl Seminar 13161)}},
  pages =	{69--90},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{4},
  editor =	{Hart, Sergiu and Tardos, \'{E}va and von Stengel, Bernhard},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.3.4.69},
  URN =		{urn:nbn:de:0030-drops-41341},
  doi =		{10.4230/DagRep.3.4.69},
  annote =	{Keywords: Algorithmic Game Theory, Economics, Internet, Nash Equilibrium, Mechanism Design, Auctions}
}
  • Refine by Author
  • 2 Tardos, Éva
  • 1 Beyhaghi, Hedyeh
  • 1 Hart, Sergiu
  • 1 von Stengel, Bernhard

  • Refine by Classification
  • 1 Theory of computation → Algorithmic mechanism design

  • Refine by Keyword
  • 1 Algorithmic Game Theory
  • 1 Auctions
  • 1 Balls in Bins Problem
  • 1 Economics
  • 1 Internet
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2013
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact