Prof.  T E S Raghavan, Mathematics department, University of Illinois at Chicago (Emeritus) gave a talk on Two Specific Combinatorial Games on 25 February.

While combinatorics has emerged as a powerful tool tied to the development of computer science, computer scientists are carving out computational game theory as an integral part of their area of research. The talk concentrated on two specific games, the so-called Nim games and the Game of Hex. Nim games are zero-sum two person games and they predate (1904) the foundations of game theory as laid out by von Neumann (1928), and by von Nemann and Morgenstern (1946). Hex is a strategy board game for two players played on a hexagonal grid, theoretically of any size and several possible shapes, but traditionally as an 11 × 11 rhombus. Players alternate placing markers or stones on unoccupied spaces in an attempt to link their opposite sides of the board in an unbroken chain. One player must win; there are no draws. The game has deep strategy, sharp tactics and a profound mathematical underpinning related to the Brouwer fixed-point theorem. It was invented in the 1940s independently by two mathematicians, Piet Hein and John Nash. The game was first marketed as a board game in Denmark under the name Con-tac-tix, and Parker Brothers marketed a version of it in 1952 called Hex; they are no longer in production. The Hex game in an n-dimensional box consists of n players occupying the lattice vertices of the n-dimensional box. Player i is itching to form a connected link of adjacent vertices with one end at any vertex of the face where the ith coordinate has the least possible value and the other end at any vertex of the opposite face where the ith coordinate has the highest possible value. Any player who achieves this is called a winner. Theorem (David Gale (1979)): Any n dimensional Hex game admits at least one winner. One can arrive at a winning path starting from the south west corner of the Hex box. Unlike the Hex board in two dimensions which always has exactly one winner, it is quite possible that there are multiple winners when n > 2. This theorem gives us a constructive proof of the Brouwer’s fixed point theorem by locating an approximate 1 fixed point. The search terminates when one is trying to move along a potential winning path.

Prof. Raghavan’s interests are Game theory; linear, non-linear programming; matrix theory; applied statistics; operations research. Prof. Raghavan has  been running a Gurukulam in Game theory in Pulavanur, TN and professors from IIT (Mumbai), IIT (Chennai), TIFR (Bangalore), IISC ( Bangalore), Dibrugar University Assam , NIT Surat etc have sent their best PhD students to attend his  Gurukulam. He plans to continue running the Gurukulam for students serious to enter game theory.