{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T21:01:37Z","timestamp":1773522097829,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"crossref","award":["LP2016-3\/2018"],"award-info":[{"award-number":["LP2016-3\/2018"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"crossref","award":["K128611"],"award-info":[{"award-number":["K128611"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/K010042\/1"],"award-info":[{"award-number":["EP\/K010042\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["FT140100048"],"award-info":[{"award-number":["FT140100048"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"crossref","award":["DP150101134"],"award-info":[{"award-number":["DP150101134"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Austrian Science Fund","award":["J4047"],"award-info":[{"award-number":["J4047"]}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"crossref","award":["KEP-6\/2018"],"award-info":[{"award-number":["KEP-6\/2018"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"crossref"}]},{"name":"UNSW Scientia Fellowship"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the two-sided stable matching setting in which there may be uncertainty about the agents\u2019 preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model\u2014for each agent, there is a probability distribution over linear preferences, (2) compact indifference model\u2014for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model\u2014there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.<\/jats:p>","DOI":"10.1007\/s00453-019-00650-0","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T13:02:20Z","timestamp":1573736540000},"page":"1410-1433","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Stable Matching with Uncertain Linear Preferences"],"prefix":"10.1007","volume":"82","author":[{"given":"Haris","family":"Aziz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e9ter","family":"Bir\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"de Haan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicholas","family":"Mattei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0985-573X","authenticated-orcid":false,"given":"Baharak","family":"Rastegari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"650_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8, 121\u2013123 (1979)","journal-title":"Inf. Process. Lett."},{"key":"650_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-662-53354-3_16","volume-title":"Algorithmic Game Theory","author":"Haris Aziz","year":"2016","unstructured":"Aziz, H., Bir\u00f3, P., Gaspers, S., de\u00a0Haan, R., Mattei, N., Rastegari, B.: Stable matching with uncertain linear preferences. In: Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT), pp. 195\u2013206 (2016)"},{"key":"650_CR3","unstructured":"Aziz, H., Bir\u00f3, P., Fleiner, T., Gaspers, S., de\u00a0Haan, R., Mattei, N., Rastegari, B.: Stable matching with uncertain pairwise preferences. In: Proceedings of the 16th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 344\u2013352 (2017a)"},{"key":"650_CR4","doi-asserted-by":"crossref","unstructured":"Aziz, H., de\u00a0Haan, R., Rastegari, B.: Pareto optimal allocation under uncertain preferences. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1472\u20131474 (2017b)","DOI":"10.24963\/ijcai.2017\/12"},{"key":"650_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.artint.2019.08.002","volume":"276","author":"H Aziz","year":"2019","unstructured":"Aziz, H., Bir\u00f3, P., de Haan, R., Rastegari, B.: Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity. Artif. Intell. 276, 57\u201378 (2019a)","journal-title":"Artif. Intell."},{"key":"650_CR6","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1609\/aaai.v33i01.33011740","volume":"33","author":"Haris Aziz","year":"2019","unstructured":"Aziz, H., de\u00a0Haan, R., Rastegari, B.: Pareto optimal allocation under compact uncertain preferences. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) (2019b)","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"650_CR7","doi-asserted-by":"crossref","unstructured":"Chen, J., Niedermeier, R., Skowron, P.: Stable marriage with multi-modal preferences. In: Proceedings of the 19th ACM Conference on Electronic Commerce (ACM-EC), pp. 269\u2013286 (2018)","DOI":"10.1145\/3219166.3219168"},{"issue":"3","key":"650_CR8","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(80)90236-8","volume":"30","author":"DP Dailey","year":"1980","unstructured":"Dailey, D.P.: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Math. 30(3), 289\u2013293 (1980)","journal-title":"Discrete Math."},{"key":"650_CR9","doi-asserted-by":"crossref","unstructured":"Drummond, J., Boutilier, C.: Preference elicitation and interview minimization in stable matchings. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pp. 645\u2013653 (2014)","DOI":"10.1609\/aaai.v28i1.8829"},{"key":"650_CR10","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.jet.2015.01.008","volume":"157","author":"L Ehlers","year":"2015","unstructured":"Ehlers, L., Mass\u00f3, J.: Matching markets under (in)complete information. J. Econ. Theory 157, 295\u2013314 (2015)","journal-title":"J. Econ. Theory"},{"issue":"1","key":"650_CR11","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"650_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"650_CR13","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)"},{"issue":"3","key":"650_CR14","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/1273340.1273346","volume":"3","author":"Magn\u00fas M. Halld\u00f3rsson","year":"2007","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation results for the stable marriage problem. ACM Trans. Algorithms 3(3) (2007). https:\/\/dl.acm.org\/citation.cfm?id=1273346","journal-title":"ACM Transactions on Algorithms"},{"key":"650_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2012.04.009","volume":"189","author":"N Hazon","year":"2012","unstructured":"Hazon, N., Aumann, Y., Kraus, S., Wooldridge, M.: On the evaluation of election outcomes under uncertainty. Artif. Intell. 189, 1\u201318 (2012)","journal-title":"Artif. Intell."},{"key":"650_CR16","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","volume":"48","author":"RW Irving","year":"1994","unstructured":"Irving, R.W.: Stable marriage and indifference. Discrete Appl. Math. 48, 261\u2013272 (1994)","journal-title":"Discrete Appl. Math."},{"key":"650_CR17","doi-asserted-by":"crossref","unstructured":"Irving, R.W., Manlove, D.F., Scott, S.: The hospitals\/residents problem with ties. In: Proceedings the 7th Scandinavian Workshop on Algorithm Theory (SWAT), Volume 1851 of Lecture Notes in Computer Science, pp. 259\u2013271. Springer (2000)","DOI":"10.1007\/3-540-44985-X_24"},{"key":"650_CR18","doi-asserted-by":"crossref","unstructured":"Li, Y., Conitzer, V.: Cooperative game solution concepts that maximize stability under noise. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pp. 979\u2013985 (2015)","DOI":"10.1609\/aaai.v29i1.9300"},{"key":"650_CR19","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"D Manlove","year":"2013","unstructured":"Manlove, D.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company, Singapore (2013)"},{"key":"650_CR20","unstructured":"Manlove, D.F.: Stable marriage with ties and unacceptable partners. Technical Report TR-1999-29, University of Glasgow, Department of Computing Science (1999)"},{"key":"650_CR21","doi-asserted-by":"crossref","unstructured":"Mattei, N., Walsh, T.: PrefLib: A library for preferences, http:\/\/www.preflib.org. In: Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT) (2013)","DOI":"10.1007\/978-3-642-41575-3_20"},{"key":"650_CR22","unstructured":"Mattei, N., Walsh, T.: A PrefLib.Org Retrospective: lessons learned and new directions. In: Endriss, U. (ed.), Trends in Computational Social Choice, chapter\u00a015, pp. 289\u2013309. AI Access Foundation (2017)"},{"key":"650_CR23","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"2003","unstructured":"Papadimitriou, C.H.: Computational Complexity. Wiley, New York (2003)"},{"key":"650_CR24","doi-asserted-by":"crossref","unstructured":"Rastegari, B., Condon, A., Immorlica, N., Leyton-Brown, K.: Two-sided matching with partial information. In: Proceedings of the 14th ACM Conference on Electronic Commerce (ACM-EC), pp. 733\u2013750. ACM (2013)","DOI":"10.1145\/2482540.2482607"},{"key":"650_CR25","doi-asserted-by":"crossref","unstructured":"Rastegari, B., Condon, A., Immorlica, N., Irving, R., Leyton-Brown, K.: Reasoning about optimal stable matching under partial information. In: Proceedings of the 15th ACM Conference on Electronic Commerce (ACM-EC), pp. 431\u2013448. ACM (2014)","DOI":"10.1145\/2600057.2602884"},{"issue":"6","key":"650_CR26","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92(6), 991\u20131016 (1984)","journal-title":"J. Polit. Econ."},{"key":"650_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL052139015X","volume-title":"Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis","author":"AE Roth","year":"1990","unstructured":"Roth, A.E., Sotomayor, M.A.O.: Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge University Press, Cambridge (1990)"},{"issue":"7","key":"650_CR28","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskretnyi Analiz 3(7), 25\u201330 (1964)","journal-title":"Diskretnyi Analiz"},{"issue":"3","key":"650_CR29","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1063\/1.533181","volume":"41","author":"DJA Welsh","year":"2000","unstructured":"Welsh, D.J.A., Merino, C.: The Potts model and the Tutte polynomial. J. Math. Phys. 41(3), 1127\u20131152 (2000)","journal-title":"J. Math. Phys."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00650-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00650-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00650-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T04:27:28Z","timestamp":1664944048000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00650-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["650"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00650-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,14]]},"assertion":[{"value":"1 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}