{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:50:03Z","timestamp":1770994203825,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T00:00:00Z","timestamp":1683158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T00:00:00Z","timestamp":1683158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001215","name":"La Trobe University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001215","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Game Theory"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The Sprague\u2013Grundy (SG) theory reduces the disjunctive compound of impartial games to the classical game of <jats:italic>NIM<\/jats:italic>. We generalize this concept by introducing hypergraph compounds of impartial games. An impartial game is called SG-decreasing if its SG value is decreased by every move. Extending the SG theory, we reduce hypergraph compounds of SG-decreasing games to hypergraph compounds of single-pile <jats:italic>NIM<\/jats:italic> games. We show that this reduction works only if all games involved in the compound are SG-decreasing. A hypergraph is called SG-decreasing if the corresponding hypergraph compound of single-pile <jats:italic>NIM<\/jats:italic> games is an SG-decreasing game. We provide some necessary and some sufficient conditions for a hypergraph to be SG-decreasing. In particular, for hypergraphs with hyperedges of size at most 3 we obtain a necessary and sufficient condition verifiable in polynomial time.<\/jats:p>","DOI":"10.1007\/s00182-023-00850-7","type":"journal-article","created":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T09:02:58Z","timestamp":1683190978000},"page":"1119-1144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Impartial games with decreasing Sprague\u2013Grundy function and their hypergraph compound"],"prefix":"10.1007","volume":"53","author":[{"given":"Endre","family":"Boros","sequence":"first","affiliation":[]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[]},{"given":"Nhan Bao","family":"Ho","sequence":"additional","affiliation":[]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Mursic","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,5,4]]},"reference":[{"key":"850_CR1","doi-asserted-by":"publisher","DOI":"10.1201\/b10691","volume-title":"Lessons in play: an introduction to combinatorial game theory","author":"MH Albert","year":"2007","unstructured":"Albert MH, Nowakowski RJ, Wolfe D (2007) Lessons in play: an introduction to combinatorial game theory, 2nd edn. A K Peters Ltd., Wellesley, MA","edition":"2"},{"key":"850_CR2","unstructured":"Beideman C, Bowen M, M\u00fcyesser A (2020) The Sprague-Grundy function for some selective compound games. Integers, G4, Vol. 20"},{"key":"850_CR3","first-page":"129","volume":"32","author":"C Berge","year":"1953","unstructured":"Berge C (1953) Sur une Thdorie ensembliste des Jeux alternatifs. J Math Pures Appl 32:129\u2013184","journal-title":"J Math Pures Appl"},{"key":"850_CR4","doi-asserted-by":"crossref","unstructured":"Berlekamp ER, Conway JH, Guy RK (2004) Winning ways for your mathematical plays, vol.1-4, second edition, A.K. Peters, Natick, MA, 2001\u20132004","DOI":"10.1201\/9780429487309"},{"key":"850_CR5","unstructured":"Bogdanov I (2017) Private communications"},{"key":"850_CR6","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/BF01904851","volume":"16","author":"B Bollob\u00e1s","year":"1965","unstructured":"Bollob\u00e1s B (1965) On generalized graphs. Acta Math Aced Sci Hungar 16:447\u2013452","journal-title":"Acta Math Aced Sci Hungar"},{"key":"850_CR7","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/s00182-020-00707-3","volume":"50","author":"E Boros","year":"2021","unstructured":"Boros E, Gurvich V, Ho NB, Makino K (2021) On the Sprague-Grundy function of extensions of proper Nim. Int J Game Theory 50:635\u2013654","journal-title":"Int J Game Theory"},{"key":"850_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2017.08.007","volume":"239","author":"E Boros","year":"2018","unstructured":"Boros E, Gurvich V, Ho NB, Makino K, Mursic P (2018) On the Sprague-Grundy function of exact $$k$$-Nim. Discrete Appl Math 239:1\u201314","journal-title":"Discrete Appl Math"},{"key":"850_CR9","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.jcta.2019.02.006","volume":"165","author":"E Boros","year":"2019","unstructured":"Boros E, Gurvich V, Ho NB, Makino K, Mursic P (2019) Sprague-Grundy function of symmetric hypergraphs. J Combin Theory Ser A 165:176\u2013186","journal-title":"J Combin Theory Ser A"},{"key":"850_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2019.09.041","volume":"799","author":"E Boros","year":"2019","unstructured":"Boros E, Gurvich V, Ho NB, Makino K, Mursic P (2019) On the Sprague-Grundy function of matroids and related hypergraphs. Theor Comput Sci 799:40\u201358","journal-title":"Theor Comput Sci"},{"key":"850_CR11","doi-asserted-by":"crossref","unstructured":"Bouton CL (1901) Nim, a game with a complete mathematical theory. Ann Math 2-nd Ser. 3 (1901\u20131902) 35\u201339","DOI":"10.2307\/1967631"},{"key":"850_CR12","volume-title":"On numbers and games","author":"JH Conway","year":"1976","unstructured":"Conway JH (1976) On numbers and games. Acad. Press, London, NY, San Francisco"},{"key":"850_CR13","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"key":"850_CR14","first-page":"6","volume":"2","author":"PM Grundy","year":"1939","unstructured":"Grundy PM (1939) Mathematics of games. Eureka 2:6\u20138","journal-title":"Eureka"},{"issue":"1","key":"850_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/BF01784796","volume":"9","author":"TA Jenkyns","year":"1980","unstructured":"Jenkyns TA, Mayberry JP (1980) The skeletion of an impartial game and the Nim-Function of Moore\u2019s Nim$$_k$$. Int J Game Theory 9(1):51\u201363","journal-title":"Int J Game Theory"},{"key":"850_CR16","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume":"1972","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems, in R.E. Miller and J.W Thatcher. Complex Comput Comput Plenum 1972:85\u2013103","journal-title":"Complex Comput Comput Plenum"},{"issue":"4","key":"850_CR17","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra HW Jr (1983) Integer programming with a fixed number of variables. Math Oper Res 8(4):538\u2013548","journal-title":"Math Oper Res"},{"key":"850_CR18","doi-asserted-by":"crossref","unstructured":"Milnor J (1953) Sums of positional games, contributions to the theory of games 2 (Annals of Math. Studies 28), Princeton, NJ, pp 291\u2013303","DOI":"10.1515\/9781400881970-017"},{"key":"850_CR19","doi-asserted-by":"crossref","unstructured":"Moore E H (1910) A generalization of the game called Nim, Annals of Math., Second Series, 11:3, 93\u201394","DOI":"10.2307\/1967321"},{"key":"850_CR20","unstructured":"von Neumann J, Morgenstern O (1944) Theory of games and economic behavior. Princeton University Press, Princeton"},{"key":"850_CR21","doi-asserted-by":"crossref","unstructured":"Siegel AN (2013) Combinatorial game theory. Graduate Studies in Mathematics, Vol 146, AMS","DOI":"10.1090\/gsm\/146"},{"key":"850_CR22","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0021-9800(66)80005-4","volume":"1","author":"CAB Smith","year":"1966","unstructured":"Smith CAB (1966) Graphs and composite games. J Combin Theory 1:51\u201381","journal-title":"J Combin Theory"},{"key":"850_CR23","unstructured":"Sprague R \u00dcber mathematische Kampfspiele. Tohoku Math J 41:438\u2013444"},{"key":"850_CR24","first-page":"351","volume":"43","author":"R Sprague","year":"1937","unstructured":"Sprague R (1937) \u00dcber zwei abarten von nim. Tohoku Math J 43:351\u2013354","journal-title":"Tohoku Math J"},{"key":"850_CR25","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W Tutte","year":"1954","unstructured":"Tutte W (1954) A short proof of the factor theorem for finite graphs. Can J Math 6:347\u2013352","journal-title":"Can J Math"}],"container-title":["International Journal of Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00182-023-00850-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00182-023-00850-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00182-023-00850-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T08:53:40Z","timestamp":1738140820000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00182-023-00850-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,4]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["850"],"URL":"https:\/\/doi.org\/10.1007\/s00182-023-00850-7","relation":{},"ISSN":["0020-7276","1432-1270"],"issn-type":[{"value":"0020-7276","type":"print"},{"value":"1432-1270","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,4]]},"assertion":[{"value":"2 March 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}