2018 CMS Winter Meeting
Vancouver, December 7 - 10, 2018
- DANIEL ASHLOCK, Univesity of Guelph
Game Theory: simulation versus theory. [PDF]
-
Game theory has a beautiful mathematical form, rich in theorems, which often falls apart when build simulations of human behaviour based on it. This presentation examines assorted points of divergence between theory and practice when game playing agents are trained via evolutionary computation. This training technique violates the defining hypothesis of a Nash equilibrium, often fails to find Nash equilibria, and yet it can be similar to the way humans learn social interaction. Evolving agents have invented nepotism, searched for stability over quality of outcome, and generally not behaved like the idealized optimizers of standard game theory. Factors affecting these deviations from theory include kin selection, drift, and finite population effects, all of which violate the hypotheses of many forms of game theoretic analysis.
The clean simplicity of mathematical game theory can also be modified by constraints arising from a situation that change its character substantially. In the latter part of the talk we will examine a mechanic that translates a mathematical game into a card game and demonstrate at least one card game that is useful in instruction at the K-12 level.
- JORDAN BARRET, Dalhousie University
The Power Index Game [PDF]
-
The power index game models a political committee in which a bill is proposed and party members vouch to pass or reject the bill. In more general terms, this game models the effect your acquaintances have on your decisions. We use a connected graph to model a group of committee members, where vertices represent members and edges represent relationships among members. The game takes place in rounds where in each round, members keep or change their decision on passing the bill based on the influence of their local neighbourhood. The main result of the talk will focus on finding well known discrete structures within the model and using them to construct cycles in the game.
This is joint work with Dr. Richard Nowakowski and Dr. Christopher Duffy.
- NANCY CLARKE, Acadia University
Farsighted Cops and Robber [PDF]
-
A variation of the Cops and Robber game is introduced in which the robber is invisible to the cop side unless outside the neighbourhood of a cop. The hyperopic copnumber is analogous to the copnumber. We present a variety of results, including a characterization of the graphs with hyperopic copnumber 1. We also characterize those graphs with largest possible hyperopic copnumber, and consider graphs in terms of diameter and planarity. This is joint work with A. Bonato, D. Cox, S. Finbow, F. Mc Inerney, and M.E. Messenger.
- MONICA COJOCARU, University of Guelph
The replicator dynamics for generalized Nash Games [PDF]
-
Generalized Nash Games are a powerful modelling tool that have
seen some development in the past two decades. Evolutionary Games have
been around a bit longer and seek describe how natural selection can drive
phenotypic changes in interacting populations. We show how these two independently
formulated models can be linked under a common framework and
how this framework can be used to expand each model. At the center of this
unified model is the Replicator Equation and the relationship we establish
between it and the lesser known Projected Dynamical System.
- CHRIS DUFFY, University of Saskatchewan
The Evacuation Number of a Graph [PDF]
-
Joint work with Danielle Cox (Mount Saint Vincent University).
Graph evacuation is a eternal dominating-like process in which defending resources are single-use. That is, once a defender has been utilized to defend a vertex, it is not available in subsequent rounds. In this talk we examine the evacuation number of a graph, the fewest number of defenders needed so that imperilled persons appearing at unoccupied vertices can be eternally evacuated. We show the evacuation number is bounded by standard domination parameters, and that it is NP-hard to compute evacuation number of an arbitrary input graph.
- CHARLIE GERRIE, Dalhousie University
The Power Index Game On A Lattice [PDF]
-
In 1954, Lloyd Shapley and Martin Shubik introduced the Shapley-Shubik power index as a perspective model of voting behavior. Richard Nowakowski recently applied this to game theory, developing the power-index game. We used simulations of the power-index on a torus to explore long-term behavior. We also investigated using Markov chains to predict proportions of large-scale structures. Through this we built a case that there is a global structure to the game when run on large boards.
This is joint work with Jordan Barrett and Dr. Jeanette Janssen.
- RYAN HAYWARD, University of Alberta
A Hex History Mystery: Who Posed the Puzzles? [PDF]
-
From December 1942 through August 1943,
Piet Hein wrote a series of newspaper columns on Hex,
then called Polygon.
Most columns featured a puzzle.
But Hein publicly professed to being a poor Polygon player:
how had he crafted 49 perplexing puzzles?
In October 2017 Bjarne Toft and the speaker solved this Hex history mystery. I will give clues and then reveal the true Polygon puzzlist. I will also mention some open Hex problems. All this and more will appear in Hex, inside and out: the full story by Hayward and Toft, CRC Press, January 2019.
- RICHARD HOSHINO AND MAXIMILIAN KAHN, Quest University Canada
Birds of a Feather: a perfect-information solitaire card game [PDF]
-
In this talk, we present our analysis of Birds of a Feather (BoaF), a recently-invented perfect-information solitaire card game that was the subject of an undergraduate research challenge for an international conference in Artificial Intelligence. While the large majority of BoaF deals are solvable, the set of unsolvable deals share certain characteristics that can be determined from the adjacency matrix of the corresponding "compatibility graph". We create a binary decision tree based on just three variables to predict whether a given deal is solvable. Our predictive model, tested on 30,000 random deals, correctly classifies over 99.9\% of our data.
- RICHARD NOWAKOWSKI, Dalhousie University
The Orthogonal Colouring Game on Graphs [PDF]
-
Lois and Rita are playing with two $n\times n$ matrices, one labeled L and one labeled R. On their turn, a player can write in an integer between 1 and $n$ in either matrix. However, the matrices must have the latin property (no row or column can have a repeated number) and the two matrices must be orthogonal (no pair of numbers can be repeated). When no moves are available the game is over and Lois's (Rita's) score is the number of entries in the matrix L (R). The player with the greater score wins. We'll assume that Lois play's first. When $n=2$, Rita can force a win. For other $n$, Rita has a strategy that ensures a tie, even if the entries are restricted to 1 through $k$ with $k <n$.
This game can be extended to playing on graphs. We characterize, via matchings, a class of graphs in which Rita can always tie.
This is joint work with Sephan Andres, Melissa Huggan and Fionn Mc Inerney.
- PETER TAYLOR AND STEFANIE KNEBEL, Queen's
The parent game in the grade 11 classroom [PDF]
-
Some of our work has been focused on what might be called a reinvention of the high school mathematics curriculum, in which we work with “hands-on” activities that are structurally complex. We find game theory to be a wonderful source of such activities. Here we will discuss a graphical version, using contour diagrams, of the parent game that seems to work well in grade 11. This talk might look like it belongs in the education sessions but we feel that it will be of interest to the game-theory community; indeed it might inspire other similar activities.
- BOTING YANG, University of Regina
Fast Searching Game on Cartesian Products of Graphs [PDF]
-
Given a graph that contains an invisible fugitive, we want to find the minimum number of searchers to capture the fugitive in the fast searching game. In this talk, we consider the fast search number of the Cartesian product of an Eulerian graph and a path. We also consider the fast search number of hypercubes, toroidal grids, and variants of the Cartesian product. (This is joint work with Yuan Xue).
- HEDAYAT ZARKOOB, University of British Columbia
Report-sensitive spot-checking in peer grading system [PDF]
-
Peer grading has many advantages: making large courses more scalable; providing students with faster and more detailed feedback;
and helping students to learn by thinking critically about the work of others. A key strategy for motivating strategic students to provide accurate
grades is spot-checking. Previous work has considered mechanisms that spot check each submission with a fixed probability. In this talk, I will discuss that the same incentives can be provided at lower cost by spot checking students based on the grades they
report. I will show that our proposed mechanism outperforms the fixed-probability mechanism and indeed minimizes the required
amount of spot checking. I will also discuss a surprising consequence of our main theorem, which is that the amount of TA work needed to incentivize students can be reduced by sometimes declining to compare student reports to TA reports even when TA reports are available.