{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T05:34:36Z","timestamp":1777440876363,"version":"3.51.4"},"reference-count":44,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,11,18]],"date-time":"2013-11-18T00:00:00Z","timestamp":1384732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The stable matching problem (also known as the stable marriage problem) is a well-known problem of matching men to women, so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here, we consider stable marriage problems with weighted preferences: each man (resp., woman) provides a score for each woman (resp., man). Such problems are more expressive than the classical stable marriage problems. Moreover, in some real-life situations, it is more natural to express scores (to model, for example, profits or costs) rather than a qualitative preference ordering. In this context, we define new notions of stability and optimality, and we provide algorithms to find marriages that are stable and\/or optimal according to these notions. While expressivity greatly increases by adopting weighted preferences, we show that, in most cases, the desired solutions can be found by adapting existing algorithms for the classical stable marriage problem. We also consider the manipulability properties of the procedures that return such stable marriages. While we know that all procedures are manipulable by modifying the preference lists or by truncating them, here, we consider if manipulation can occur also by just modifying the weights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, in some cases, we may increase the possibility of manipulating, and this cannot be avoided by any reasonable restriction on the weights.<\/jats:p>","DOI":"10.3390\/a6040782","type":"journal-article","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T03:19:41Z","timestamp":1384831181000},"page":"782-804","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Stability, Optimality and Manipulation in Matching Problems with Weighted Preferences"],"prefix":"10.3390","volume":"6","author":[{"given":"Maria","family":"Pini","sequence":"first","affiliation":[{"name":"Department of Information Engineering, University of Padova, Padova 35131, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesca","family":"Rossi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Padova, Padova 35121, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Venable","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tulane University and IHMC, New Orleans, LA 70118, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toby","family":"Walsh","sequence":"additional","affiliation":[{"name":"NICTA and UNSW, Sydney, NSW 1466, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2013,11,18]]},"reference":[{"key":"ref_1","unstructured":"Gusfield, D., and Irving, R.W. (1989). The Stable Marriage Problem: Structure and Algorithms, MIT Press."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","article-title":"College admissions and the stability of marriage","volume":"69","author":"Gale","year":"1962","journal-title":"Am. Math. Mon."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1007\/s00182-008-0117-6","article-title":"Deferred acceptance algorithms: History, theory, practice, and open questions","volume":"36","author":"Roth","year":"2008","journal-title":"Int. J. Game Theory"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1086\/261272","article-title":"The evolution of the labor market for medical interns and residents: A case study in game theory","volume":"92","author":"Roth","year":"1984","journal-title":"J. Polit. Econ."},{"key":"ref_5","first-page":"384","article-title":"Computational efficiencies for multi-agents: A look at a multi-agent system for sailor assignment","volume":"2","author":"Liebowitz","year":"2005","journal-title":"Electon. Gov. Int. J."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1287\/mnsc.47.9.1252.9784","article-title":"Gale-shapley stable marriage problem revisited: Strategic issues and applications","volume":"47","author":"Teo","year":"2001","journal-title":"Manag. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0216010","article-title":"Three fast algorithms for four problems in stable marriage","volume":"16","author":"Gusfield","year":"1987","journal-title":"SIAM J. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1145\/28869.28871","article-title":"An efficient algorithm for the \u201coptimal\u201d stable marriage","volume":"34","author":"Irving","year":"1987","journal-title":"J. ACM"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1287\/moor.7.4.617","article-title":"The economics of matching: Stability and incentives","volume":"7","author":"Roth","year":"1982","journal-title":"Math. Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1080\/00029890.1985.11971592","article-title":"Semiring-based constraint solving and optimization","volume":"92","author":"Gale","year":"1985","journal-title":"Am. Math. Mon."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1287\/mnsc.1070.0766","article-title":"Maximum commonality problems: Applications and analysis","volume":"54","author":"Dawande","year":"2008","journal-title":"Manag. Sci."},{"key":"ref_12","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2011, January 28\u201330). Stability in Matching Problems with Weighted Preferences. Proceedings of the ICAART\u201911, Rome, Italy."},{"key":"ref_13","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January July). Weights in Stable Marriage Problems Increase Manipulation Opportunities. Proceedings of the TARK\u201911\u2014Best Poster Award, Groningen, The Netherlands."},{"key":"ref_14","first-page":"319","article-title":"Stability and Optimality in Matching Problems With Weighted Preferences","volume":"Volume 271 CCIS","author":"Pini","year":"2012","journal-title":"Proceedings of the Agents and Artificial Intelligence 2011\u2014ICAART\u201911\u2014 Revised Selected Papers"},{"key":"ref_15","unstructured":"Bistarelli, S., Foley, S.N., O\u2019Sullivan, B., and Santini, F. (2008, January 18\u201320). From Marriages to Coalitions: A Soft CSP Approach. Proceedings of the CSCLP, Rome, Italy."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/256303.256306","article-title":"Semiring-based constraint solving and optimization","volume":"44","author":"Bistarelli","year":"1997","journal-title":"J. ACM"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Gent, I.P., Irving, R.W., Manlove, D., Prosser, P., and Smith, B.M. (December, January 26). A Constraint Programming Approach to the Stable Marriage Problem. Proceedings of the CP 2001, Paphos, Cyprus.","DOI":"10.1007\/3-540-45578-7_16"},{"key":"ref_18","unstructured":"Gent, I., and Prosser, P. (, January July). An Empirical Study of the Stable Marriage Problem with Ties and Incomplete Lists. Proceedings of the ECAI 2002, Lyon, France."},{"key":"ref_19","unstructured":"Gent, I., Prosser, P., Smith, B., and Walsh, T. (, January May). Sat Encodings of the Stable Marriage Problem with Ties and Incomplete Lists. Proceedings of the SAT 2002, Cincinnati, Ohio, USA."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Brito, I., and Meseguer, P. (2005, January 1\u20135). Distributed Stable Matching Problems. Proceedings of the CP 2005, Sitges, Spain.","DOI":"10.1007\/11564751_14"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Brito, I., and Meseguer, P. (2006, January 25\u201329). Distributed Stable Matching Problems with Ties and Incomplete Lists. Proceedings of the CP 2006, Nantes, France.","DOI":"10.1007\/11889205_49"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"591","DOI":"10.3390\/a6040591","article-title":"Local search approaches in stable matching problems","volume":"6","author":"Gelain","year":"2013","journal-title":"Algorithms"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (, January 16\u201320). Local Search Algorithms on the Stable Marriage Problem: Experimental Studies. Proceedings of ECAI 2010, Lisbon, Portugal, Lisbon.","DOI":"10.3233\/978-1-60750-606-5-1085"},{"key":"ref_24","first-page":"64","article-title":"Local Search for Stable Marriage Problems With Ties and Incomplete Lists","volume":"Volume 6230 LNCS","author":"Gelain","year":"2010","journal-title":"Proceedings of the PRICAI 2010"},{"key":"ref_25","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2011, January 2\u20136). Procedural Fairness in Stable Marriage Problems. Proceedings of the AAMAS 2011, Taipei, Taiwan."},{"key":"ref_26","first-page":"159","article-title":"Anarchy, Stability, and Utopia: Creating Better Matchings","volume":"Volume 5814 LNCS","author":"Anshelevich","year":"2009","journal-title":"Proceedings of the SAGT 2009"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/s10458-011-9184-3","article-title":"Anarchy, stability, and utopia: Creating better matchings","volume":"26","author":"Anshelevich","year":"2013","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"ref_28","unstructured":"Arrow, K.J., Sen, A.K., and Suzumura, K. (2002). Handbook of Social Choice and Welfare, North-Holland, Elsevier."},{"key":"ref_29","unstructured":"Arrow, K.J. (1963). Social Choice and Individual Values, John Wiley and Sons."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"680","DOI":"10.2307\/1907651","article-title":"A set of independent necessary and sufficient conditions for simple majority decisions","volume":"20","author":"May","year":"1952","journal-title":"Econometrica"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0022-0531(75)90050-2","article-title":"Strategy-proofness and Arrow\u2019s Conditions: Existence and correspondence theorems for voting procedures and social welfare functions","volume":"10","author":"Satterthwaite","year":"1975","journal-title":"J. Econ. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"587","DOI":"10.2307\/1914083","article-title":"Manipulation of voting schemes: A general result","volume":"41","author":"Gibbard","year":"1973","journal-title":"Econometrica"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1236457.1236461","article-title":"When are elections with few candidates hard to manipulate?","volume":"54","author":"Conitzer","year":"2007","journal-title":"J. ACM"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.1016\/j.artint.2010.11.009","article-title":"Incompleteness and incomparability in preference aggregation: Complexity results","volume":"175","author":"Pini","year":"2011","journal-title":"Artif. Intell."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1613\/jair.3186","article-title":"Determining possible and necessary winners given partial orders","volume":"41","author":"Xia","year":"2011","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/s10458-011-9171-8","article-title":"Winner determination in voting trees with incomplete preferences and weighted votes","volume":"25","author":"Lang","year":"2012","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"ref_37","unstructured":"Lang, J., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2007, January 6\u201312). Winner Determination in Sequential Majority Voting. Proceedings of the IJCAI 2007, Hyderabad, India."},{"key":"ref_38","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2007, January 6\u201312). Incompleteness and Incomparability in Preference Aggregation. Proceedings of the IJCAI 2007, Hyderabad, India."},{"key":"ref_39","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2009, January 10\u201315). Manipulation and Gender Neutrality in Stable Marriage Procedures. Proceedings of the AAMAS 2009, Budapest, Hungary."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s10458-010-9121-x","article-title":"Manipulation complexity and gender neutrality in stable marriage procedures","volume":"22","author":"Pini","year":"2011","journal-title":"Auton. Agents Multi-Agent Syst."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0166-218X(01)00322-5","article-title":"The structure of stable marriage with indifference","volume":"122","author":"Manlove","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0166-218X(92)00179-P","article-title":"Stable marriage and indifference","volume":"48","author":"Irving","year":"1994","journal-title":"Discret. Appl. Math."},{"key":"ref_43","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. (2010, January 10\u201314). Male Optimality and Uniqueness in Stable Marriage Problems with Partial Orders\u2014Extended Abstract. Proceedings of the AAMAS 2010, Toronto, Canada."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., and Walsh, T. Male Optimal and Unique Stable Marriages with Partially Ordered Preferences. Proceedings of the CARE 2009\/2010.","DOI":"10.1007\/978-3-642-22427-0_4"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/782\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:50:42Z","timestamp":1760219442000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/6\/4\/782"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,18]]},"references-count":44,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["a6040782"],"URL":"https:\/\/doi.org\/10.3390\/a6040782","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,18]]}}}