Number Game

number-game.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "prospective-tomorrow",
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "N = 10**4\n",
    "K = 20"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "major-audio",
   "metadata": {},
   "source": [
    "***This is based on an exercise from \"Introduction to Probability\" by Blitzstein and Hwang***\n",
    "\n",
    "# Number Game\n",
    "\n",
    "A game is played between two players A and B, such that:\n",
    "\n",
    "1. Both players choose a number between 1 and 100 (inclusive).\n",
    "2. If both A and B choose the same number, j, player A pays B j dollars.\n",
    "\n",
    "A strategy for the game can be represented by a vector $\\overline{v}$ of length 100, such that each component, $v_j$, is the probability that the player will chose number $j$. \n",
    "\n",
    "*We will assume that both players have very bad short-term memories and that the different rounds of the game can be considered independent*\n",
    "\n",
    "We are interested to see how the players can optimise their strategies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "moved-donor",
   "metadata": {},
   "outputs": [],
   "source": [
    "def randomStrat(k=K):\n",
    "    \"\"\"\n",
    "    Generates k random strategies.\n",
    "    \"\"\"\n",
    "    strat = torch.rand(k, 100)\n",
    "    return (strat.T / strat.sum(dim=1)).T\n",
    "\n",
    "def makeChoices(strategies, n=N):\n",
    "    \"\"\"\n",
    "    Makes N choices from 1 to 100 given some strategies.\n",
    "    \"\"\"\n",
    "    return torch.multinomial(strategies, n, replacement=True) + 1.0\n",
    "\n",
    "def countWinnings(A_choices, B_choices):\n",
    "    \"\"\"\n",
    "    Calculates the total winnings for player B.\n",
    "    \"\"\"\n",
    "    try:\n",
    "        return ((A_choices == B_choices) * B_choices).sum(dim=1)\n",
    "    except IndexError:\n",
    "        # handle 1d choices\n",
    "        return ((A_choices == B_choices) * B_choices).sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "assigned-beaver",
   "metadata": {},
   "source": [
    "We can simulate a few rounds of the game where both players have random strategies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "leading-chain",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "average_winnings = tensor(5122.7002)\n",
      "average_winnings / N = tensor(0.5123)\n"
     ]
    }
   ],
   "source": [
    "A_strat = randomStrat()\n",
    "B_strat = randomStrat()\n",
    "\n",
    "A_choices = makeChoices(A_strat)\n",
    "B_choices = makeChoices(B_strat)\n",
    "\n",
    "average_winnings = countWinnings(A_choices, B_choices).mean(dim=0)\n",
    "\n",
    "print(f\"{average_winnings = }\\n{average_winnings / N = }\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "negative-agenda",
   "metadata": {},
   "source": [
    "We can see that with random strategies, B will win around 50 cents per game.\n",
    "\n",
    "## Other Strategies\n",
    "\n",
    "What if player B had some way of knowing the strategy that player A was using? Then player B could always pick the number $j$ with the maximum $jp_j$ to increase their expected winnings. This is because the expected payout of any other strategy would be a weighted average of $ip_i$ less than or equal to $jp_j$, decreasing the expected winnings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "earlier-institution",
   "metadata": {},
   "outputs": [],
   "source": [
    "def adversarialStrat(strategy):\n",
    "    \"\"\"\n",
    "    Creates a strategy for B with the greatest expected value, given the strategy of A\n",
    "    \"\"\"\n",
    "    k = strategy.shape[0]\n",
    "    \n",
    "    # Start with all zeros\n",
    "    B = torch.zeros((k, 100))\n",
    "    \n",
    "    # These are the indicies with the maximum payout\n",
    "    max_payout = (torch.arange(1, 101) * strategy).argmax(dim=1)\n",
    "    \n",
    "    # We want to choose those indicies with probability 1.\n",
    "    B[torch.arange(k),max_payout] = 1\n",
    "    \n",
    "    return B"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "medium-virus",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "tensor([88, 90, 91, 86, 75, 89, 96, 84, 99, 96, 88, 96, 87, 98, 99, 94, 95, 83,\n",
       "        95, 99])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "adversarialStrat(randomStrat()).argmax(dim=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "wicked-customer",
   "metadata": {},
   "source": [
    "It seems that given a random strategy, often the higher numbers will give greater returns. \n",
    "\n",
    "This makes sense, because when we generated the random strategy, we placed no importance on how we chose each number. Therefore, higher numbers should be expected to be chosen at a similar rate to lower numbers. Since the higher numbers pay out more than the lower numbers, and we would expect them to be chosen at a similar rate, it is more likely that they will pay out more.\n",
    "\n",
    "Let's simulate a few rounds where A chooses a random strategy and B chooses the best strategy given A's strategy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "infectious-hearts",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "average_winnings = tensor(17564.5000)\n",
      "average_winnings / N = tensor(1.7565)\n"
     ]
    }
   ],
   "source": [
    "A_strat = randomStrat()\n",
    "B_strat = adversarialStrat(A_strat)\n",
    "\n",
    "A_choices = makeChoices(A_strat)\n",
    "B_choices = makeChoices(B_strat)\n",
    "\n",
    "average_winnings = countWinnings(A_choices, B_choices).mean(dim=0)\n",
    "\n",
    "print(f\"{average_winnings = }\\n{average_winnings / N = }\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "first-invention",
   "metadata": {},
   "source": [
    "Now that B has an idea about A's strategy, they can expect to win much more (about 3.5 times) money than before.\n",
    "\n",
    "## Right Back At 'Ya\n",
    "\n",
    "If A knew that B was able to do this though, A would surely change their strategy to minimise the maximum $jp_j$. They can do this by setting $p_j$ proportional to $1/j$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "reliable-runner",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fairStrat():\n",
    "    \"\"\"\n",
    "    Generates a strategy for A that provides no incentive for B to choose any specific number over another.\n",
    "    \n",
    "    There's no point in setting k any more, as there is only one strategy.\n",
    "    \"\"\"\n",
    "    strat = torch.arange(1, 101)\n",
    "    strat = 1 / strat\n",
    "    strat = strat / strat.sum()\n",
    "    return strat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "interracial-edgar",
   "metadata": {},
   "source": [
    "Let's simulate a few games with B using different strategies:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fitted-briefing",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(tensor(1794.5000), tensor(0.1795))\n",
      "(tensor(1992.8500), tensor(0.1993))\n",
      "(tensor(1998.), tensor(0.1998))\n"
     ]
    }
   ],
   "source": [
    "A_strat = fairStrat()\n",
    "\n",
    "def vsFair(B_strat):\n",
    "    \"\"\"\n",
    "    Simulates some games to calculate average winnings for a strategy of B against A playing the fair strategy.\n",
    "    \"\"\"\n",
    "    winnings = countWinnings(*map(makeChoices, (A_strat, B_strat))).mean()\n",
    "    return winnings, winnings / N\n",
    "\n",
    "print(vsFair(randomStrat()))\n",
    "print(vsFair(adversarialStrat(randomStrat())))\n",
    "print(vsFair(fairStrat()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "peripheral-calgary",
   "metadata": {},
   "source": [
    "It seems that no matter what strategy B adopts, the payout is the same, 20 cents per game. \n",
    "\n",
    "We can apply the same logic from the perspective of A to see that B should also adopt the fair strategy. This causes the game to enter a state of equilibrium ([Nash equilibrium](https://en.wikipedia.org/wiki/Nash_equilibrium)). If either player changes their strategy, their opponent (assuming knowledge of the change) has the opportunity to improve their strategy."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}