[et_pb_section fb_built=”1″ make_equal=”on” use_custom_gutter=”on” gutter_width=”1″ specialty=”on” background_color_2=”gcid-e428b4a0-8f75-478b-bc91-d4c919946667″ padding_top_1=”0px” padding_top_2=”20px” padding_right_1=”0px” padding_right_2=”15px” padding_bottom_1=”0px” padding_bottom_2=”40px” padding_left_1=”0px” padding_left_2=”15px” padding_top_bottom_link_1=”false” padding_top_bottom_link_2=”false” padding_left_right_link_1=”false” padding_left_right_link_2=”false” _builder_version=”4.25.2″ _module_preset=”default” width=”100%” max_width=”100%” inner_width=”100%” inner_max_width=”100%” custom_margin=”0px|0px|0px|0px|false|false” custom_padding=”0px|0px|0px|0px|false|false” border_width_top=”7px” border_color_top=”gcid-e428b4a0-8f75-478b-bc91-d4c919946667″ locked=”off” global_colors_info=”{%22gcid-e428b4a0-8f75-478b-bc91-d4c919946667%22:%91%22border_color_top%22,%22background_color_2%22%93}”][et_pb_column type=”3_4″ specialty_columns=”3″ _builder_version=”4.16″ custom_padding=”|||” global_colors_info=”{}” custom_padding__hover=”|||”][et_pb_row_inner use_custom_gutter=”on” gutter_width=”1″ make_equal=”on” _builder_version=”4.25.2″ _module_preset=”default” width=”100%” max_width=”100%” custom_margin=”0px|0px|0px|0px|false|false” custom_padding=”40px|40px|10px|40px|false|false” global_colors_info=”{}”][et_pb_column_inner saved_specialty_column_type=”3_4″ _builder_version=”4.25.2″ _module_preset=”default” custom_padding=”0px|0px|0px|0px|false|false” global_colors_info=”{}”][et_pb_heading title=”Combinatorial Game Theory Colloquium IV” _builder_version=”4.25.2″ _module_preset=”default” title_text_color=”#f29062″ title_font_size=”22px” global_colors_info=”{}”][\/et_pb_heading][et_pb_heading title=”(Lisbon, 23-25 January, 2023)” _builder_version=”4.25.2″ _module_preset=”default” title_level=”h6″ custom_margin=”-5px||||false|false” custom_padding=”0px||||false|false” locked=”off” global_colors_info=”{}”][\/et_pb_heading][et_pb_text _builder_version=”4.27.3″ _module_preset=”default” text_orientation=”justified” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″]<\/p>\n
Combinatorial Game Theory<\/strong>\u00a0(CGT) is a branch\u00a0of mathematics that studies\u00a0sequential games\u00a0with perfect information<\/strong>. Combinatorial games\u00a0include well-known rulesets like Amazons,\u00a0Clobber, Domineering, Hackenbush, Konane,\u00a0Nim, Octal Games, Wythoff\u2019s Nim.\u00a0After John Conway’s\u00a0On Numbers and Games\u00a0<\/em>(1976), Elwyn Berlekamp, John Conway, and Richard Guy published \u201cthe book\u201d\u00a0Winning Ways\u00a0<\/em>(1982).\u00a0In\u00a0that\u00a0work,\u00a0one can\u00a0find a unified\u00a0mathematical\u00a0theory able to analyze a large class of rulesets. The books\u00a0Lessons in Play<\/em>\u00a0(2007), by Michael Albert, David Wolfe, and Richard Nowakowski, and\u00a0Combinatorial Game Theory<\/em>\u00a0(2013), by Aaron Siegel, are also mandatory reading.<\/p>\n Combinatorial Game Theory Colloquia<\/strong>\u00a0are held every\u00a0two years<\/span>, in Portugal.\u00a0Associa\u00e7\u00e3o Ludus\u00a0will organize\u00a0in\u00a0S. Miguel, Azores<\/strong>,\u00a0the\u00a0fourth edition of the CGTC,\u00a0<\/strong>January, 23-25, 2023<\/strong>, with support of C\u00e2mara Municipal de Lagoa,\u00a0Centro de An\u00e1lise Funcional, Estruturas Lineares e Aplica\u00e7\u00f5es, Centro de Matem\u00e1tica Aplicada \u00e0 Previs\u00e3o e Decis\u00e3o Econ\u00f3mica, Centro de Matem\u00e1tica e Aplica\u00e7\u00f5es (NovaMath, FCT NOVA),\u00a0Expolab – Centro de Ci\u00eancia Viva, Faculdade de Ci\u00eancias e Tecnologia – Universidade dos A\u00e7ores, Governo dos A\u00e7ores, N\u00facleo Interdisciplinar da Crian\u00e7a e do Adolescente, Sociedade Afonso Chaves, and Sociedade Portuguesa de Matem\u00e1tica<\/span>.<\/span><\/p>\n The meeting will take place at\u00a0\u00a0<\/span>Expolab – Centro de Ci\u00eancia Viva<\/span><\/a>.\u00a0See a map\u00a0<\/span>here<\/a>.<\/span><\/span><\/p>\n <\/p>\n [\/et_pb_text][et_pb_image src=”https:\/\/ludicum.org\/wp-content\/uploads\/2024\/11\/cgtc-4-poster.jpg” _builder_version=”4.27.3″ _module_preset=”default” title_text=”Screenshot” align=”center” custom_padding=”||40px||false|false”][\/et_pb_image][et_pb_text _builder_version=”4.27.3″ _module_preset=”default” text_orientation=”justified” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″]<\/p>\n For informations about submissions and registrations, just mail us:\u00a0<\/span>cgtc@cgtc.eu<\/a><\/span><\/strong><\/p>\n The\u00a0International Journal of Game Theory<\/a>\u00a0(IJGT) invites submissions of significant papers in Combinatorial Game Theory.\u00a0Combinatorial games are traditionally two-player perfect-information games with compact rules such as Nim or Chess, with more general\u00a0games now being studied. Their theory was pioneered by Elwyn R. Berlekamp, John H. Conway and Richard K. Guy in\u00a0<\/span>Winning Ways<\/em>\u00a0(1982),\u00a0republished in 2009 by A. K. Peters.<\/p>\n All articles will be refereed to the high standards of IJGT.\u00a0Accepted papers are published online first in a\u00a0<\/span>Collection<\/em><\/a>\u00a0<\/span>of papers that groups them in a single place. At the appropriate time, they will be published in print in a special issue of the journal. The first\u00a0special issue<\/a>\u00a0on Combinatorial Games\u00a0appeared as issue 2 in volume 47 of IJGT in 2018.<\/p>\n In Portugal, under the auspices of Associa\u00e7\u00e3o Ludus, Carlos Pereira dos Santos has been organizing the Combinatorial Game Theory Colloquia taking place every\u00a0two years, starting in January 2015, 2017, 2019, 2023. Authors of significant original results related to (or\/and presented at) the conference are also encouraged to\u00a0<\/span>submit them by November 1, 2023<\/strong>\u00a0<\/span>to the\u00a0<\/span>International Journal of Game Theory<\/a>, in order to, if accepted, become part of the\u00a0<\/span>Collection<\/em>.\u00a0It is important to note that\u00a0<\/span>it is not necessary to have participated in the conference to do so<\/strong>.<\/p>\n IJGT Collection on Combinatorial Games<\/strong>\u00a0 \u00a0 \u00a0Guest Editors:<\/p>\n Urban Larsson, Indian Institute of Technology Bombay, Mumbai, India<\/p>\n Carlos P. Santos, Center for Mathematics and Applications, Nova University of Lisbon, Portugal<\/p>\n Bernhard von Stengel, London School of Economics and Political Science, London, UK<\/p>\n [\/et_pb_text][et_pb_tabs _builder_version=”4.27.3″ _module_preset=”default” custom_margin=”20px||||false|false” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″][et_pb_tab title=”Organization” _builder_version=”4.27.3″ _module_preset=”default” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″]<\/p>\n Aaron Siegel<\/a><\/strong>, San Francisco, California Alda Carvalho<\/strong>, ISEL-IPL & CEMAPRE\/REM-University of Lisbon<\/span> [\/et_pb_tab][et_pb_tab title=”Program” _builder_version=”4.25.0″ _module_preset=”default” global_colors_info=”{}”]<\/p>\n <\/p>\n [\/et_pb_tab][et_pb_tab title=”Abstracts” _builder_version=”4.25.0″ _module_preset=”default” global_colors_info=”{}”]<\/p>\n Aaron Siegel<\/strong><\/span>, United States of America Abstract:\u00a0<\/strong><\/span>This talk will be a brief, high-level overview of three topics in combinatorial game theory: temperature theory, misere play of partizan games, and calculation of octal games. These topics (among many others) have attracted considerable attention over many years, are deeply interesting from a mathematical and historical perspective, and, I will argue, are fertile ground for further advances. I will highlight some research directions in each topic that appear especially promising.<\/span><\/p>\n \u00a0 \u00a0\u00a0 Abstract:\u00a0<\/strong><\/span>We present a method to evaluate if a ruleset only has positions whose game values are numbers.<\/span><\/p>\n (Joint work with Melissa Huggan,\u00a0Richard J. Nowakowski, and Carlos Pereira dos Santos)<\/span><\/p>\n \u00a0\u00a0<\/strong><\/span><\/span><\/p>\n Aline Parreau<\/strong>, CNRS, Lyon 1 University, France<\/span><\/p>\n Title:\u00a0<\/strong>Maker-Breaker Domination Game<\/span><\/strong><\/span><\/p>\n Abstract:\u00a0<\/strong>The Maker-Breaker Domination Game is played on a graph\u00a0<\/span>G<\/em>\u00a0with two players Dominator and Staller. At his turn, Dominator, selects a vertex in order to dominate the graph while at his turn Staller forbids a vertex to Dominator in order to prevent him to reach his goal. Both players play alternately without missing their turn.\u00a0 We study the problem of deciding who has a winning strategy for a given graph\u00a0<\/span>G<\/em>. We prove that this problem is PSPACE-complete, even for bipartite graphs and split graphs but is polynomial for cographs, trees and block graphs. We in particular focus on pairing strategies for Dominator and prove that having a pairing strategy is the only way to win in cographs, trees, block graphs and interval graphs.<\/span><\/p>\n (Joint work with Guillaume Bagan, Eric Duch\u00eane, Valentin Gledel, Tuomo Lehtil\u00e4, and Gabriel Renault)<\/span><\/p>\n \u00a0 \u00a0<\/strong><\/span><\/span><\/p>\n Antoine Dailly<\/strong>, Laboratory of Informatics, Modelling and Optimization of the Systems, France<\/span><\/p>\n Title:\u00a0<\/strong><\/span>Subtraction games on graphs<\/span><\/p>\n Abstract:\u00a0<\/strong>Subtraction Games are taking-breaking games defined by a set\u00a0S\u00a0<\/em>of integers, in which a player may remove\u00a0k<\/em>\u00a0counters if\u00a0k<\/em>\u00a0is in\u00a0S<\/em>. In (Beaudou et al., 2018) and (Dailly et al., 2019), we extended the definition of subtraction games to play them on graphs: a player may remove a connected subgraph of order\u00a0k<\/em>\u00a0if\u00a0k<\/em>\u00a0is in\u00a0S<\/em>, and if the resulting graph is still connected. A similar extension was also defined for octal games.\u00a0This talk will be an overview of the results obtained in subtraction and octal games on graphs, ranging from structral (ultimate periodicity of a kind of Grundy sequence) and general complexity (PSPACE-completeness of finite subtraction games with 1 not in\u00a0S<\/em>) to polynomial-time algorithms on specific games and graph families (S<\/em>={1,…,N<\/em>} on stars, and stronger results for small values of\u00a0N<\/em>). I will also highlight several open problems.<\/span><\/span><\/p>\n \u00a0 \u00a0 \u00a0\u00a0<\/strong>\u00a0 \u00a0 \u00a0\u00a0<\/strong><\/span><\/span><\/p>\n Bernhard von Stengel<\/strong>, London School of Economics, United Kingdom<\/span> Abstract:\u00a0<\/strong>The minimax theorem for zero-sum games is easily proved from the strong duality theorem of linear programming. For the converse direction, the standard proof by Dantzig (1951) is massively incomplete, as we argue in this article. We explain and combine classical theorems about solving linear equations with nonnegative variables to give a correct alternative proof.<\/span><\/p>\n <\/p>\n <\/p>\n Bojan Ba\u0161i\u0107<\/strong>, University of Novi Sad, Serbia<\/span> Abstract:\u00a0<\/strong><\/span>The game in which a warden arranges\u00a0<\/span>n<\/em>\u00a0<\/span>prisoners in a line and then each of them guesses (one by one) whether the hat on his head is white or black, aiming to maximize the total number of correct guesses, is a folklore thing. Those who hear it for the first time (though today it is not easy to meet such a person) are usually surprised when they learn that (spoiler alert!) all the prisoners with the exception of only one can secure correct guesses. And furthermore, nothing changes if the hats come in more than two colors: in that case, too, one prisoner can single-handedly transmit enough information so that all the other prisoners be able to deduce their hat colors. They simply establish a bijection between the available hat colors and a complete residue system modulo the number of colors, and then the first prisoners declares the sum of hats of all the other prisoners (under the same modulus).\u00a0<\/span>This is one of many puzzles in circulation featuring prisoners and a warden. And although they are formulated in an informal fashion and often presented as a matter of recreational mathematics, many of them hide serious science under their facade. There are tight connections between these puzzles and game theory, information theory, coding theory etc.\u00a0<\/span>In this talk we introduce a variant of this game, where information that prisoners can relay to other prisoners is much more restricted. In particular, each prisoner is asked whether he wants to take a guess on his hat color, to which question he answers aloud (everybody hears that); if the answer is affirmative, he takes a guess but the other prisoners do not hear what his guess is, they only get to know whether the guess was correct. Therefore, basically, each prisoner is able to transmit only a single binary bit (\u00abyes\u00bb\/\u00abno\u00bb answer), and although the other prisoners do get a little more information (the outcome of the guess), the prisoner who takes a guess cannot directly control this further affair. Clearly, if there are 4 possible colors, the first two prisoners can encode the sum of colors of all the remaining prisoners, and thus all but the first two prisoners can assure correct guesses. What is, however, perhaps somewhat surprising, and which will be the first case seen in the talk, is that, if there are 5 hat colors, the prisoners still can arrange a strategy that will guarantee correct guesses for all of them but the first two (and 5 is the largest such number). We shall then present some results on the general question what the maximal possible number of colors is such that, given a positive integer\u00a0<\/span>m<\/em>, if\u00a0<\/span>n<\/em>\u00a0<\/span>prisoners are playing the game with the indicated number of colors, they can devise a strategy such that all but\u00a0<\/span>m<\/em>\u00a0<\/span>prisoners are guaranteed to guess correctly.<\/span><\/p>\n (Joint work with Vlado Uljarevi\u0107)<\/span><\/p>\n <\/p>\n Carlos Pereira dos Santos<\/strong>, Center for Mathematics and Applications (NovaMath), FCT NOVA, Portugal<\/span><\/p>\n Title:\u00a0<\/strong>Chess and Combinatorial Game Theory<\/span><\/strong><\/span><\/p>\n Abstract:\u00a0<\/strong><\/span>Combinatorial Game Theory was born in twentieth century.\u00a0<\/span>The seminal works\u00a0<\/span><\/span>On Numbers and Games\u00a0<\/em>and\u00a0Winning Ways<\/em>\u00a0are\u00a0<\/span>masterpieces of mathematical creativity. S<\/span>ome games are numbers, some games are not.\u00a0<\/span>John Horton Conway said in some interviews that the co-invention of Combinatorial Game Theory was\u00a0<\/span>one of his mathematical achievements he was most proud of. In some conferences he explained\u00a0<\/span>how happy he was when discovered the value 1\/2 in the context of games.\u00a0<\/span>Here, a not artificial Chess problem related to\u00a0<\/span>the discovery of the dyadic numbers is presented.\u00a0 Its construction was inspired\u00a0<\/span>by a “mysterious” well-known game played by the world chess champions Jose Raul\u00a0<\/span>Capablanca and Emanuel Lasker.\u00a0<\/span><\/p>\nREGISTRATION<\/span><\/h5>\n
CALL FOR PAPERS<\/span><\/strong><\/h5>\n
Scientific Committee<\/h3>\n
Alda Carvalho<\/strong>, ISEL & CEMAPRE<\/span>
Bernhard von Stengel<\/strong><\/a>, London School of Economics and Political Science<\/span>
Carlos Pereira dos Santos<\/strong><\/a>, LA & CEAFEL-University of Lisbon<\/span>
Eric Duchene<\/strong><\/a>, IUT Lyon 1, LIRIS lab.<\/span>
Jo\u00e3o Pedro Neto<\/strong><\/a>, University of Lisbon<\/span>
Jorge Nuno Silva<\/strong><\/a>, University of Lisbon<\/span>
Richard Nowakowski<\/strong><\/a>, Dalhousie University<\/span>
Thane Plambeck<\/strong>, Counterwave, Inc<\/span>
Urban Larsson<\/strong><\/a>, Industrial Engineering and Management, Technion<\/span><\/p>\n<\/ul>\n
Organizing Committee<\/h3>\n
Ana Paula Garr\u00e3o<\/strong><\/a>, NICA-UAc & University of Azores
Carlos Pereira dos Santos<\/strong><\/a>, Center for Mathematics and Applications (NovaMath), FCT NOVA<\/span>
Jorge Nuno Silva<\/strong><\/a>, CIUHCT-University of Lisbon<\/span>
Margarida Raposo<\/strong><\/a>, NICA-UAc & University of Azores<\/span>
Ricardo Cunha Teixeira<\/strong><\/a>, NICA-UAc & University of Azores<\/span>
Tiago Hirth<\/strong><\/a>, Ludus Assoiation<\/span><\/p>\n
<\/b>
Working Sessions, Afternoons (15:00-18:00)
<\/strong><\/google-sheets-html-origin>\u00a0<\/p>\n\n
\n <\/td>\n 23\/1 – Monday<\/td>\n 24\/1 – Tuesday<\/td>\n 25\/1 – Wednesday<\/td>\n<\/tr>\n \n 9:00-9:20<\/td>\n Opening ceremony<\/td>\n <\/td>\n <\/td>\n<\/tr>\n \n 9:20-9:30<\/td>\n \n <\/td>\n <\/td>\n<\/tr>\n \n 9:30-9:50<\/td>\n Milos Stojakovic,
University of Novi Sad,
Strong avoiding positional games<\/td>\nDana Ernst, Northern Arizona University, Impartial geodetic convexity achievement and avoidance games on graphs<\/td>\n<\/tr>\n \n 9:50-10:10<\/td>\n Alda Carvalho,
ISEL-IPL & CEMAPRE\/REM-UL, \u00abAll is number\u00bb? Not so easy, Mr. Pythagoras<\/td>\nDanijela Popovi\u0107,
Mathematical Institute of SASA,
A new approach to equivalence of games<\/td>\nNeil McKay,
University of New Brunswick,
Numbers and ordinal sums<\/td>\n<\/tr>\n\n 10:10-10:30<\/td>\n Paul Ellis,
Rutgers University,
The arithmetic-periodicity of Cut for C = {1, 2c}<\/td>\nMichael Fisher,
West Chester University,
Olympic games: three impartial games with infinite octal codes<\/td>\nAntoine Dailly,
Laboratory of Informatics, Modelling and Optimization of the Systems,
Subtraction games on graphs<\/td>\n<\/tr>\n\n 10:30-10:50<\/td>\n Koki Suetsugu,
National Institute of Informatics,
Some new universal partizan rulesets<\/td>\nRichard J. Nowakowski,
Dalhousie University,
The game of Flipping Coins<\/td>\nCraig Tennenhouse,
University of New England,
Vexing vexillological logic<\/td>\n<\/tr>\n\n 10:50-11:10<\/td>\n Carlos Pereira dos Santos, CMA (NovaMath), FCT NOVA, Chess and Combinatorial Game Theory<\/td>\n Tomoaki Abuku,
National Institute of Informatics,
A Multiple Hook Removing Game whose starting position is a rectangular Young diagram with unimodal numbering<\/td>\nUrban Larsson, Indian Institute of Technology Bombay,
Feasible outcomes of Bidding Combinatorial Games<\/td>\n<\/tr>\n\n 10:10-11:40<\/td>\n Coffee-break<\/td>\n Coffee-break<\/td>\n Coffee-break<\/td>\n<\/tr>\n \n 11:40-12:00<\/td>\n Bernhard von Stengel,
London School of Economics,
Zero-sum games and linear programming duality<\/td>\nKyle Burke, Florida Southern College, Forced-Capture Hnefatafl<\/td>\n Nandor Sieben, Northern Arizona University, Impartial hypergraph games<\/td>\n<\/tr>\n \n 12:00-12:20<\/td>\n Bojan Ba\u0161i\u0107,
University of Novi Sad,
A twist on the classical
prisoners-in-a-line hat-guessing game<\/td>\nKanae Yoshiwatari, Nagoya University, Complexity of Colored Arc Kayles<\/td>\n Svenja Huntemann, Concordia University of Edmonton, Temperature of Partizan ArcKayles Trees<\/td>\n<\/tr>\n \n 12:20-12:40<\/td>\n Hironori Kiya, Kyushu University, Normal-play with dead-end-winning convention<\/td>\n Eric Duch\u00eane, LIRIS, Lyon 1 University, Partizan subtraction games<\/td>\n Florian Galliot,
University of Grenoble Alpes,
The Maker-Breaker game on hypergraphs of rank 3: structural results and a polynomial-time algorithm<\/td>\n<\/tr>\n\n 12:40-13:00<\/td>\n Silvia Heubach,
California State University,
On the Structure of the P-positions
of Slow Exact k-Nim<\/td>\nAline Parreau,
CNRS, Lyon 1 University,
Maker-Breaker Domination Game<\/td>\nPrem Kant,
Indian Institute of Technology Bombay,
Bidding combinatorial games<\/td>\n<\/tr>\n\n 13:00-13:20<\/td>\n Keito Tanemura,
Kwansei Gakuin University,
Chocolate games with a pass and
an application of symbolic regression to these games<\/td>\nHikaru Manabe,
Keimei Gakuen Elementary Junior & Senior High School,
Four-dimensional chocolate games and chocolate games with a pass move<\/td>\nNacim Oijid,
University of Lyon,
Bipartite instances of Influence<\/td>\n<\/tr>\n\n 13:20-15:00<\/td>\n Break for lunch<\/td>\n Break for lunch<\/td>\n Break for lunch<\/td>\n<\/tr>\n \n 15:00-18:00<\/td>\n Working sessions<\/td>\n Working sessions<\/td>\n Working sessions<\/td>\n<\/tr>\n \n 19:00-23:00<\/td>\n <\/td>\n Conference Dinner<\/td>\n <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Title:\u00a0<\/strong>Horizons in Combinatorial Game Theory<\/span><\/strong><\/span><\/p>\n
<\/strong>Alda Carvalho<\/strong>, ISEL-IPL&CEMAPRE\/REM-University of Lisbon, Portugal<\/span>
Title:\u00a0<\/strong>\u00abAll is number\u00bb? Not so easy, Mr. Pythagoras<\/span><\/strong><\/span><\/p>\n
Title:\u00a0<\/strong>Zero-sum games and linear programming duality<\/span>
<\/strong><\/span><\/p>\n
Title:\u00a0<\/strong>A twist on the classical prisoners-in-a-line hat-guessing game<\/span><\/strong><\/span><\/p>\n