Second-order quantile methods for experts and combinatorial games

We aim to design strategies for sequential decision making that adjust to the difficulty of the learning problem. We study this question both in the setting of prediction with expert advice, and for more general combinatorial decision tasks. We are not satisfied with just guaranteeing minimax regret rates, but we want our algorithms to perform significantly better on easy data. Two popular ways to formalize such adaptivity are second-order regret bounds and quantile bounds. The underlying notions of 'easy data', which may be paraphrased as "the learning problem has small variance" and "multiple decisions are useful", are synergetic. But even though there are sophisticated algorithms that exploit one of the two, no existing algorithm is able to adapt to both. In this paper we outline a new method for obtaining such adaptive algorithms, based on a potential function that aggregates a range of learning rates (which are essential tuning parameters). By choosing the right prior we construct efficient algorithms and show that they reap both benefits by proving the first bounds that are both second-order and incorporate quantiles.

On Games on Non-Wellfounded Sets and Stationary Sets

In this thesis we study a few games related to non-wellfounded and stationary sets. Games have turned out to be an important tool in mathematical logic ranging from semantic games defining the truth of a sentence in a given logic to for example games on real numbers whose determinacies have important effects on the consistency of certain large cardinal assumptions. The equality of non-wellfounded sets can be determined by a so called bisimulation game already used to identify processes in theoretical computer science and possible world models for modal logic. Here we present a game to classify non-wellfounded sets according to their branching structure. We also study games on stationary sets moving back to classical wellfounded set theory. We also describe a way to approximate non-wellfounded sets with hereditarily finite wellfounded sets. The framework used to do this is domain theory. In the Banach-Mazur game, also called the ideal game, the players play a descending sequence of stationary sets and the second player tries to keep their intersection stationary. The game is connected to precipitousness of the corresponding ideal. In the pressing down game first player plays regressive functions defined on stationary sets and the second player responds with a stationary set where the function is constant trying to keep the intersection stationary. This game has applications in model theory to the determinacy of the Ehrenfeucht-Fraisse game. We show that it is consistent that these games are not equivalent.

Weak Ehrenfeucht-Fraïssé Games

In this paper we define a game which is played between two players I and II on two mathematical structures A and B. The players choose elements from both structures in moves, and at the end of the game the player II wins if the chosen structures are isomorphic. Thus the difference of this to the ordinary Ehrenfeucht-Fra¨ıss´e game is that the isomorphism can be arbitrary, whereas in the ordinary EF-game it is determined by the moves of the players. We investigate determinacy of the weak EF-game for different (the length of the game) and its relation to the ordinary EF-game.

Labor unions and Nash bargaining using coalition formation games

In this paper we examine the properties of stable coalitions under sequential and simultaneous bargaining by competing labor unions. We do this using the Nash bargaining solution and various notions of stability, namely, Nash, coalitional, contractual and core stability. (C) 2011 Elsevier B.V. All rights reserved,

Nash equilibria of network formation games under consent

We investigate the Nash equilibria of game theoretic models of network formation based on explicit consent in link formation. These so-called “consent models” explicitly take account of link formation costs. We provide characterizations of Nash equilibria of such consent models under both one-sided and two-sided costs of link formation. We relate these equilibrium concepts to link-based stability concepts, in particular strong link deletion proofness.

Efficiency in Uncertain Cooperative Games

A contingent contract in a transferable utility game under uncertainty specifies an outcome for each possible state. It is assumed that coalitions evaluate these contracts by considering the minimal possible excesses. A main question of the paper concerns the existence and characterization of efficient contracts. It is shown that they exist if and only if the set of possible coalitions contains a balanced subset. Moreover, a characterization of values that result in efficient contracts in the case of minimally balanced collections is provided.

On Limits to the Use of Linear Markov Strategies in Common Property Natural Resource Games

We derive conditions that must be satisfied by the primitives of the problem in order for an equilibrium in linear Markov strategies to exist in some common property natural resource differential games. These conditions impose restrictions on the admissible form of the natural growth function, given a benefit function, or on the admissible form of the benefit function, given a natural growth function.

Formulating generalised 'goal games' against nature: An illustration from decision-making under uncertainty in agriculture

The games-against-nature approach to the analysis of uncertainty in decision-making relies on the assumption that the behaviour of a decision-maker can be explained by concepts such as maximin, minimax regret, or a similarly defined criterion. In reality, however, these criteria represent a spectrum and, the actual behaviour of a decision-maker is most likely to embody a mixture of such idealisations. This paper proposes that in game-theoretic approach to decision-making under uncertainty, a more realistic representation of a decision-maker's behaviour can be achieved by synthesising games-against-nature with goal programming into a single framework. The proposed formulation is illustrated by using a well-known example from the literature on mathematical programming models for agricultural-decision-making. (c) 2005 Elsevier Inc. All rights reserved.

Students' conflicting attitudes towards games as a vehicle for learning mathematics : a methodological dilemma

Mathematics games are widely employed in school classrooms for such reasons as a reward for early finishers or to enhance students' attitude towards mathematics. During a four week period, a total of 222 Grade 5 and 6 (9 to 12 years old) children from Melbourne, Australia, were taught multiplication and division of decimal numbers using calculator games or rich mathematical activities. Likert scale surveys of the children's attitudes towards games as a vehicle for learning mathematics revealed unexpectedly high proportions of negative attitudes at the conclusion of the research. In contrast, student interview data revealed positive associations between games and mathematical learning. This article reports on the methodological dilemma of resultant conflicting attitudinal data related to game- playing. Concerns arising from the divergence in the results are raised in this article. Implications based on the experience of this study may inform educational researchers about future methodological choices involving attitudinal research.

Dice-rolling games : yahtzee, poker dice and others

Provides information on some dice rolling games and the social need for mathematical information on gambling. Pass the pig; Heads, tails or odds; Yahtzee.

Get to know your local games shop

Provides information on the mathematical potential of commercial board games. Mastermind; Snakes and Ladders; Ludo.

Strategy games for gifted students

Numero is a card game popular with people of all ages. It is engaging, challenging and a whole lot of fun. The mental strategies underlying Numero make it a wonderful game for the classroom. Come along to this hands-on workshop to learn the basics of Numero and tips on how to increase the challenge for your secondary students. Play it once and you'll be hooked.