Thursday, January 25, 2024

Games at Mumbai, Day 4 (Final) of Talks

The talks on the final day of Games At Mumbai continued the excellence of the week!  Here are my summaries:

Dhruv Basin, "On ergodicity of a 1-dimensional PCA with parity dependent updation rules" 

Dhruv talked about the site percolation problem--whether there are open clusters on randomly-generated graphs.  In a game version of this, vertices (integer coordinates of the Cartesian plane, so the board is infinite) are randomly either a trap, a target, or open.  Players alternate moving a token along edges that are the same respectively for each vertex.  If you land on a trap, you lose.  If you land on a target, you win.  If both players can force play to continue infinitely, then the game is a draw.  Dhruv showed that, on some loop-free transition choices, how to recursively define the outcome classes.  Then he talked about how this is all related to Probabilistic Cellular Automata.  Dhruv found some range of target/trap probabilities that make the probability of draws become zero.

Anirban Mitra, "A Steckelberg game for cross-channel free-riding"

Anirban discussed multi-channel retailing: the approach of selling goods via multiple platforms.  He described showrooming: looking for products in person, then buying them online as well as the converse: looking for products online, then buying them in person.  Anirban created a Steckelberg model to create an economic game for these phenomena.  He talked about using SPNE (Subgame Perfect Nash Equilibria) to solve the value of Steckelberg games.  He applied SPNE to his showrooming and webrooming model and got meaningful results.

Saraswati Girish Nanati, "Eternal Vertex Cover Game"

Saraswati introduced the Eternal Vertex Cover Game, based on the eternal vertex cover problem.  This is a loopy maker-breaker game.  A position consists of an undirected graph with guards on a subset of the vertices.  Each turn, the attacker selects any edge.  If there are no guards on the vertices incident to that edge, then the attacker wins instantly.  Otherwise, on the defender's turn, they move each guard along up to one edge, one of which must include the edge chosen by the attacker.  (Two guards can cross paths and swap.)  Saraswati related this to the EVC number of a graph.  She showed that finding the smallest necessary set of guards for the defender to win forever is NP-hard by reducing from Red-Blue Dominating Set.  On elementary bipartite graphs, if all guards are in one half of the vertex set, the winning strategy for the defender is to move all guards along the perfect matching.  If not perfect matching exists, then the attacker has a winning strategy.  Saraswati then discussed some variants and open problems she has results for.

Santanu Acharjee, "Scopes of games in bitopological dynamical systems"

Santanu talked about potential applications of CGT to his field: bitopological dynamical systems.  This is concerned with quasi-pseudo-metric spaces when two metrics form a partition on the topology.  (I'm glad I remembered a bit of my college topology class, but I definitely needed to remember more!)  Santanu talked about when many pairwise properties existed across the two metrics.  He then related this to infinite games on topological spaces.  The point of these game, he said, is not to play, but to describe novel infinite strategies.  He talked about Menger, compact, and Alster games (and even more categories beyond these) on bitopological spaces, and many conditions he found for when winning strategies exist.

Matthieu Dufour, "A family of slow exact k-Nim games"

Slow exact k-Nim (SN(n, k)) is a game played on n stacks of tokens.  A move consists of removing exactly 1 token from exactly k different stacks.  Prior results are known for the P-positions on SN(n, 1) (P-positions: when n is even), SN(n,n), SN(3,2), and SN(4,2).  Matthieu has extended this by adding results for many other individual categories.  He started by showing how to identify unplayable tokens to shrink some positions to equivalent smaller stacks.  He called this the NIRB (No stack Is Really Big) condition.  He then listed some other values commonly important to categorize positions.  Matthieu showed his evaluation strategies, explaining when he needed reductions to complete the characterization proofs.

After his talk, Matthieu showed a hilarious "mathematical magic trick" called "Bring the Cat" to close the conference.  He pulled a numerical rabbit from a hat!

Games At Mumbai (Extra Spicy) has been an excellent experience!  I felt really honored to be included, and especially lucky to get to give so many talks.  All of the talks I listened to were awesome and I hope to see many of the new people I met again!  Thank you so much to Urban, Mallik, Prem, Anjali, Ankita, and everyone else who made this happen!




No comments:

Post a Comment