Publication

Weighted Matching Markets with Budget Constraints

Ismaili, A., Hamada, N., Zhang, Y., Suzuki, T. & Yokoo, M., 24-Jul-2019, In : Journal of artificial intelligence research. 65, p. 393-421 29 p.

Research output: Contribution to journalArticleAcademicpeer-review

APA

Ismaili, A., Hamada, N., Zhang, Y., Suzuki, T., & Yokoo, M. (2019). Weighted Matching Markets with Budget Constraints. Journal of artificial intelligence research, 65, 393-421. https://doi.org/10.1613/jair.1.11582

Author

Ismaili, Anisse ; Hamada, Naoto ; Zhang, Yuzhe ; Suzuki, Takamasa ; Yokoo, Makoto. / Weighted Matching Markets with Budget Constraints. In: Journal of artificial intelligence research. 2019 ; Vol. 65. pp. 393-421.

Harvard

Ismaili, A, Hamada, N, Zhang, Y, Suzuki, T & Yokoo, M 2019, 'Weighted Matching Markets with Budget Constraints', Journal of artificial intelligence research, vol. 65, pp. 393-421. https://doi.org/10.1613/jair.1.11582

Standard

Weighted Matching Markets with Budget Constraints. / Ismaili, Anisse; Hamada, Naoto; Zhang, Yuzhe; Suzuki, Takamasa; Yokoo, Makoto.

In: Journal of artificial intelligence research, Vol. 65, 24.07.2019, p. 393-421.

Research output: Contribution to journalArticleAcademicpeer-review

Vancouver

Ismaili A, Hamada N, Zhang Y, Suzuki T, Yokoo M. Weighted Matching Markets with Budget Constraints. Journal of artificial intelligence research. 2019 Jul 24;65:393-421. https://doi.org/10.1613/jair.1.11582


BibTeX

@article{d48487dff2ab4299877fcda965ce3df4,
title = "Weighted Matching Markets with Budget Constraints",
abstract = "We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student's wage, while a college's budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has any incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coNP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is Sigma(P)(2)-complete: NPNP -complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Unfortunately, a pairwise stable matching is not guaranteed to exist either. Thus, we consider a restricted market called a typed weighted market, in which students are partitioned into types that induce their possible wages. We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets.",
keywords = "SCHOOL CHOICE, COLLEGE ADMISSIONS, STABILITY, CONTRACTS, EFFICIENCY, BOUNDS",
author = "Anisse Ismaili and Naoto Hamada and Yuzhe Zhang and Takamasa Suzuki and Makoto Yokoo",
year = "2019",
month = "7",
day = "24",
doi = "10.1613/jair.1.11582",
language = "English",
volume = "65",
pages = "393--421",
journal = "Journal of artificial intelligence research",
issn = "1076-9757",
publisher = "AI ACCESS FOUNDATION",

}

RIS

TY - JOUR

T1 - Weighted Matching Markets with Budget Constraints

AU - Ismaili, Anisse

AU - Hamada, Naoto

AU - Zhang, Yuzhe

AU - Suzuki, Takamasa

AU - Yokoo, Makoto

PY - 2019/7/24

Y1 - 2019/7/24

N2 - We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student's wage, while a college's budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has any incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coNP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is Sigma(P)(2)-complete: NPNP -complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Unfortunately, a pairwise stable matching is not guaranteed to exist either. Thus, we consider a restricted market called a typed weighted market, in which students are partitioned into types that induce their possible wages. We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets.

AB - We investigate markets with a set of students on one side and a set of colleges on the other. A student and college can be linked by a weighted contract that defines the student's wage, while a college's budget for hiring students is limited. Stability is a crucial requirement for matching mechanisms to be applied in the real world. A standard stability requirement is coalitional stability, i.e., no pair of a college and group of students has any incentive to deviate. We find that a coalitionally stable matching is not guaranteed to exist, verifying the coalitional stability for a given matching is coNP-complete, and the problem of finding whether a coalitionally stable matching exists in a given market, is Sigma(P)(2)-complete: NPNP -complete. Other negative results also hold when blocking coalitions contain at most two students and one college. Given these computational hardness results, we pursue a weaker stability requirement called pairwise stability, where no pair of a college and single student has an incentive to deviate. Unfortunately, a pairwise stable matching is not guaranteed to exist either. Thus, we consider a restricted market called a typed weighted market, in which students are partitioned into types that induce their possible wages. We then design a strategy-proof and Pareto efficient mechanism that works in polynomial-time for computing a pairwise stable matching in typed weighted markets.

KW - SCHOOL CHOICE

KW - COLLEGE ADMISSIONS

KW - STABILITY

KW - CONTRACTS

KW - EFFICIENCY

KW - BOUNDS

U2 - 10.1613/jair.1.11582

DO - 10.1613/jair.1.11582

M3 - Article

VL - 65

SP - 393

EP - 421

JO - Journal of artificial intelligence research

JF - Journal of artificial intelligence research

SN - 1076-9757

ER -

ID: 102600703