Font Size: a A A

Science for fun: New impartial board games

Posted on:2010-10-07Degree:Ph.DType:Dissertation
University:Boston UniversityCandidate:Burke, Kyle WebsterFull Text:PDF
GTID:1447390002481470Subject:Mathematics
Abstract/Summary:
We enhance the realm of combinatorial game theory by introducing three new impartial games. These games are born from economic and mathematical topics---both current and classic---in an effort to gather interest and provide potential teaching tools. The three games are Atropos, based on Sperner's Lemma; Matchmaker, inspired by the Stable Matching problem; and Dictator, based on Arrow's Impossibility Theorem.;The first of these, Atropos, has already gained some popularity. Here, players alternate choosing colors for vertices of a two-dimensional Sperner simplex. A player loses when their play creates a three-colored triangle. We show many variants of Atropos, one which is PSPACE-complete.;Our second game, Matchmaker, uses the two players as matchmakers for two lists of candidates. In order to increase the playability, we have limited the scope to settings with universal preference lists. Players take turns matching one couple and the player who makes the last move to reach the stable configuration wins the game. Again, we have many versions of this game and show a few which are solvable in polynomial time.;The last of these games, Dictator is played on an partially-filled list of ballots which are the input to a voting function. In this game, players take turns adding a candidate to one of the ballots, but must avoid creating a situation either where one of the ballots matches the output or the ballots cause the function to violate one of Arrow's requirements for fairness. Two natural problems arise: how to detect violations by the opponent and how to play so that the opponent is the first to cause a violation. We address both in different versions of Dictator.;In addition, we discuss the general benefits of such games, as well as how computational complexity is an important aspect of their enjoyability. Finally, we describe open problems from our games as well as suggest some new possibilities for future combinatorial games.
Keywords/Search Tags:Games, New
Related items