{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:38:42Z","timestamp":1760243922821,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2010,9,13]],"date-time":"2010-09-13T00:00:00Z","timestamp":1284336000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>This article surveys studies on universally balanced properties of cooperative games defined in a succinct form. In particular, we focus on combinatorial optimization games in which the values to coalitions are defined through linear optimization programs, possibly combinatorial, that is subject to integer constraints. In economic settings, the integer requirement reflects some forms of indivisibility. We are interested in the classes of games that guarantee a non-empty core no matter what are the admissible values assigned to the parameters defining these programs. We call such classes universally balanced. We present characterization and complexity results on the universally balancedness property for some classes of interesting combinatorial optimization games. In particular, we focus on the algorithmic properties for identifying universally balancedness for the games under discussion.<\/jats:p>","DOI":"10.3390\/g1030299","type":"journal-article","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T09:41:46Z","timestamp":1284889306000},"page":"299-316","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Universally Balanced Combinatorial Optimization Games"],"prefix":"10.3390","volume":"1","author":[{"given":"Gabrielle","family":"Demange","sequence":"first","affiliation":[{"name":"Paris School of Economics, 48 bd Jourdan, 75014 Paris, France"}]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong"}]}],"member":"1968","published-online":{"date-parts":[[2010,9,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0165-4896(82)90015-4","article-title":"Cores of partitioning games","volume":"3","author":"Kaneko","year":"1982","journal-title":"Math. Soc. Sci."},{"key":"ref_2","unstructured":"Faigle, U., and Kern, W. (1995). Partition games and the core of hierarchically convex cost games. Universiteit Twente, Faculteit der Toegepaste Wiskunde, Memorandum., 1269."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0165-4896(97)00007-3","article-title":"Stable families of coalitions and normal hypergraphs","volume":"34","author":"Boros","year":"1997","journal-title":"Math. Soc. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1287\/moor.3.3.189","article-title":"Computational complexity and the game theory approach to cost allocation for a tree","volume":"3","author":"Megiddo","year":"1978","journal-title":"Math. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01681356","article-title":"On the core of linear production games","volume":"9","author":"Owen","year":"1975","journal-title":"Math. Program."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01753437","article-title":"The assignment game I: The core","volume":"1","author":"Shapley","year":"1971","journal-title":"Int. J. Game Theor."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Demange, G., and Wooders, M. (2005). Group Formation in Economics: Networks, Clubs and Coalitions, Cambridge University Press.","DOI":"10.1017\/CBO9780511614385"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/BF01271134","article-title":"Strongly balanced cooperative games","volume":"20","author":"Owen","year":"1992","journal-title":"Int. J. Game Theor."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-4068(94)90035-3","article-title":"Intermediate preferences and stable coalition structures","volume":"23","author":"Demange","year":"1994","journal-title":"J. Math. Econ."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"754","DOI":"10.1086\/421171","article-title":"On group stability in hierarchies and networks","volume":"112","author":"Demange","year":"2004","journal-title":"J. Polit. Econ."},{"key":"ref_11","first-page":"119","article-title":"Some applications of linear programming methods to the theory of cooperative games","volume":"10","author":"Bondareva","year":"1963","journal-title":"Problemy Kybernetiki"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1002\/nav.3800140404","article-title":"On balanced sets and cores","volume":"14","author":"Shapley","year":"1967","journal-title":"Nav. Res. Logist. Quart."},{"key":"ref_13","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees, and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.19.2.257","article-title":"On the complexity of cooperative game solution concepts","volume":"19","author":"Deng","year":"1994","journal-title":"Math. Oper. Res."},{"key":"ref_16","unstructured":"Cook, S.A. The Complexity of Theorem-Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, OH, USA."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Miller, R.E., and Thatcher, J.W. (1972). Complexity of Computer Computations, Plenum.","DOI":"10.1007\/978-1-4684-2001-2"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.geb.2003.10.003","article-title":"NP-completeness in Hedonic Games","volume":"49","author":"Ballester","year":"2004","journal-title":"Games Econ. Behav."},{"key":"ref_19","unstructured":"Van Velzen, S. (2005). CentER Discussion Paper, Center for Economic Research, Tilburg University."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1287\/moor.24.3.751","article-title":"Algorithmic aspects of the core of combinatorial optimization games","volume":"24","author":"Deng","year":"1999","journal-title":"Mathe. Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","article-title":"The strong perfect graph theorem","volume":"164","author":"Chudnovsky","year":"2006","journal-title":"Ann. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","article-title":"Recognizing Berge graphs","volume":"25","author":"Chudnovsky","year":"2005","journal-title":"Combinatorica"},{"key":"ref_23","first-page":"104","article-title":"Gr\u00e1fok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok \u00e9s a halmazok elm\u00e9let\u00e9re","volume":"34","year":"1916","journal-title":"Matematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtesit\u00f6"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s10107-007-0103-y","article-title":"The complexity of recognizing linear systems with certain integrality properties","volume":"114","author":"Ding","year":"2008","journal-title":"Math. Program."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1086\/261411","article-title":"Multi-item auctions","volume":"94","author":"Demange","year":"1986","journal-title":"J. Polit. Econ."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1257\/aer.97.1.242","article-title":"Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords","volume":"97","author":"Edelman","year":"2007","journal-title":"Amer. Econ. Rev."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1016\/j.ijindorg.2006.10.002","article-title":"Position auction","volume":"25","author":"Varian","year":"2007","journal-title":"Int. J. Ind. Organ."},{"key":"ref_28","unstructured":"Pulleyblank, W. (1994). Progress in Combinatorial Optimization, Academic Press."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"50","DOI":"10.2307\/1909383","article-title":"The core of an n-person game","volume":"35","author":"Scarf","year":"1967","journal-title":"Econometrica"}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/1\/3\/299\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:03:21Z","timestamp":1760220201000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/1\/3\/299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,13]]},"references-count":29,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2010,9]]}},"alternative-id":["g1030299"],"URL":"https:\/\/doi.org\/10.3390\/g1030299","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2010,9,13]]}}}