Round3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c23e32c6-f2d5-4cdd-949b-56fe5102be1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import itertools\n",
    "import math\n",
    "from wolframclient.evaluation import WolframLanguageSession\n",
    "from wolframclient.language import wl, wlexpr\n",
    "import heapq\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "257fa476-10b9-47a2-a4ae-909fc37eff65",
   "metadata": {},
   "source": [
    "# Problem statement\n",
    "\n",
    "<p float=\"left\">\n",
    "  <img src=\"https://i.imgur.com/nDe6qQB.png\" width=\"500\" />\n",
    "  <img src=\"https://i.imgur.com/o7ruAe7.png\" width=\"600\" />\n",
    "</p>\n",
    "\n",
    "<img src=\"https://i.imgur.com/3R1W4Ln.png\" width=\"800\" />\n",
    "\n",
    "Here's a breakdown of how your profit from an expedition will be computed:\n",
    "Every spot has its **treasure multiplier** (up to 100) and the number of **hunters** (up to 8). The spot's total treasure is the product of the **base treasure** (7500, same for all spots) and the spot's specific treasure multiplier. However, the resulting amount is then divided by the sum of the hunters and the percentage of all the expeditions (from other players) that took place there. For example, if a field has 5 hunters, and 10% of all the expeditions (from all the other players) are also going there, the prize you get from that field will be divided by 15. After the division, **expedition costs** apply (if there are any), and profit is what remains.\n",
    "\n",
    "Second and third expeditions are optional: you are not required to do all 3. Fee for embarking upon a second expedition is 25 000, and for third it's 75 000. Order of submitted expeditions does not matter for grading.\n",
    "\n",
    "# Solution\n",
    "\n",
    "The profit for an expedition to a destination with $M$ as multiplier, $H$ hunters, and share $p\\in [0,1]$ of all expeditions is:\n",
    "$$\\begin{cases} \n",
    "7500\\frac M{H+100 p} &\\text{if this is the first expedition,}  \n",
    "\\\\ 7500\\frac M{H+100 p} - 25000 &\\text{if this is the second expedition,} \n",
    "\\\\ 7500\\frac M{H+100 p} - 75000 &\\text{if this is the third expedition.} \n",
    "\\end{cases} \n",
    "$$\n",
    "The second expedition is profitable if and only if $p < \\frac{3M - 10 H}{1000}$, and the third is when $p < \\frac{M - 10 H}{1000}$.  \n",
    "Let us see from the data how stringent these conditions are on $p$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0d817c83-1b78-4955-9164-c8d380b6e2bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = np.array([[(24,2), (70,4), (41,3), (21,2), (60,4)],\n",
    "                [(47,3), (82,5), (87,5), (80,5), (35,3)],\n",
    "                [(73,4), (89,5), (100,8), (90,7), (17,2)],\n",
    "                [(77,5), (83,5), (85,5), (79,5), (55,4)],\n",
    "                [(12,2), (27,3), (52,4), (15,2), (30,3)]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9c76af0-5445-4dd2-9dfd-10a57f84365d",
   "metadata": {},
   "source": [
    "The next cell computes the array with entries $\\frac{3M - 10 H}{1000}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6cafab94-9dab-47c6-9f43-8bb8511bd721",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.052 0.17  0.093 0.043 0.14 ]\n",
      " [0.111 0.196 0.211 0.19  0.075]\n",
      " [0.179 0.217 0.22  0.2   0.031]\n",
      " [0.181 0.199 0.205 0.187 0.125]\n",
      " [0.016 0.051 0.116 0.025 0.06 ]]\n"
     ]
    }
   ],
   "source": [
    "thresh = np.zeros((5, 5))\n",
    "for i in range(5):\n",
    "    for j in range(5):\n",
    "        mult, hunt = arr[i, j]\n",
    "        thresh[i, j] = (3*mult - 10*hunt)/1000\n",
    "with np.printoptions(precision=3, suppress=True):\n",
    "    print(thresh)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12a41011-b9e7-4c14-add7-b2eab5cf6147",
   "metadata": {},
   "source": [
    "The entries around the center of the array fluctuate around $20\\%$, hence profitability of a second expedition to one of these destinations is likely.\n",
    "\n",
    "Next, we do the same for $\\frac{M - 10 H}{1000}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f64b2f9f-c9f0-4146-aaa2-1a98dbb297a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.004  0.03   0.011  0.001  0.02 ]\n",
      " [ 0.017  0.032  0.037  0.03   0.005]\n",
      " [ 0.033  0.039  0.02   0.02  -0.003]\n",
      " [ 0.027  0.033  0.035  0.029  0.015]\n",
      " [-0.008 -0.003  0.012 -0.005  0.   ]]\n"
     ]
    }
   ],
   "source": [
    "thresh = np.zeros((5, 5))\n",
    "for i in range(5):\n",
    "    for j in range(5):\n",
    "        mult, hunt = arr[i, j]\n",
    "        thresh[i, j] = (mult - 10*hunt)/1000\n",
    "with np.printoptions(precision=3, suppress=True):\n",
    "    print(thresh)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd12ebe2-216e-4b97-9a65-a7b8fd96be3b",
   "metadata": {},
   "source": [
    "Negative entries correspond to third expeditions that will systematically result in a loss.  \n",
    "The other entries are all smaller than $4\\%$, with many being less than $2\\%$."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a11ba0b-efad-4130-b5da-b4abb9e95329",
   "metadata": {},
   "source": [
    "## 1. Maximin approach"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2ef51ec-1491-4f6c-9f72-f35333dff90a",
   "metadata": {},
   "source": [
    "The shares are computed once the choices of destinations are collected over all the teams.  \n",
    "However, since the number of teams is large, our choice has very little impact on the shares.\n",
    "\n",
    "One way to tackle the uncertainty in the share $p$ is to consider the most pessimistic setting where $p$ is chosen by a malicious adversary in order to make our profit as small as possible.  \n",
    "For a choice of a single destination $(M,H)$, our profit $\\pi(M,H,p)$ rewrites $\\pi(M,H,p^*(M,H))$ where $p^*(M,H)$ is a solution of \n",
    "$$\\min_{p\\in [0,1]}  \\frac {7500M}{H+100 p}.$$\n",
    "For a single expedition, the complete optimization problem is therefore \n",
    "$$\\max_{(M,H)} \\min_{p\\in [0,1]}  \\frac {7500M}{H+100 p} = \\max_{(M,H)}  \\frac {7500M}{H+100}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4a7e55a5-a67b-4ead-9934-4a8cf638ccaf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximin1():\n",
    "    \"\"\"Solves the maximin optimization problem for a single expedition.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    argmax : list of tuple\n",
    "        Maximizers.\n",
    "    max_val : float\n",
    "        Maximal profit.\n",
    "        \n",
    "    \"\"\"\n",
    "    max_val = float('-inf')\n",
    "    argmax = []\n",
    "    for mult, hunt in arr.reshape((25, 2)):\n",
    "        val = mult / (hunt + 100) * 7500\n",
    "        if math.isclose(val, max_val):\n",
    "            argmax.append((mult, hunt))\n",
    "        elif val > max_val:\n",
    "            argmax = [(mult, hunt)]\n",
    "            max_val = val\n",
    "    return (argmax, max_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "f46031c3-849c-4c48-ac16-24a08ad99f69",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([(100, 8)], 6944.444444444444)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximin1()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b122b0e-b2e7-46ce-844c-d08b2fb85545",
   "metadata": {},
   "source": [
    "For a total of two expeditions, the optimization problem is \n",
    "$$\\max_{(M_1,H_1), (M_2,H_2)} \\quad \\min_{\\substack{p_1, p_2\\in [0,1]\\\\ p_1+p_2\\leq 1}}  \\frac {7500M_1}{H_1+100 p_1}+\\frac {7500M_2}{H_2+100 p_2}-25000.$$\n",
    "Since the inner minimization problem is no longer trivial, we make a call to the Mathematica function `NMinimize` to solve it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c4152ac4-1e0c-41a2-93bf-26540f65f8d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "session = WolframLanguageSession()\n",
    "\n",
    "def maximize2():\n",
    "    \"\"\"Solves the maximin optimization problem for two expeditions. Returns only one solution, there may be other.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    argmax1 : tuple\n",
    "        First expedition.\n",
    "    argmax2 : tuple\n",
    "        Second expedition.\n",
    "    max_val : float\n",
    "        Maximal profit.\n",
    "        \n",
    "    \"\"\"\n",
    "    max_val = float('-inf')\n",
    "    max_mult1, max_hunt1 = None, None\n",
    "    max_mult2, max_hunt2 = None, None\n",
    "    for (mult1, hunt1), (mult2, hunt2) in itertools.combinations(arr.reshape((25, 2)), 2):\n",
    "        val_temp = session.evaluate(wlexpr(f'NMinimize[{{{mult1}/({hunt1} + 100*p1) + {mult2}/({hunt2} + 100*p2), 0 <= p1, 0 <= p2, p1 + p2 <= 1}}, {{p1, p2}}]'))[0]\n",
    "        val = -25000 + val_temp * 7500\n",
    "        if math.isclose(val, max_val):\n",
    "            print(\"collision\")\n",
    "        if val > max_val:\n",
    "            max_mult1, max_hunt1 = mult1, hunt1\n",
    "            max_mult2, max_hunt2 = mult2, hunt2\n",
    "            max_val = val\n",
    "    return ((max_mult1, max_hunt1), (max_mult2, max_hunt2), max_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "30b6cc2c-8494-4dd0-a084-27deefc3c42c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((89, 5), (100, 8), 67.23154797644384)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximize2()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2cdbe70e-114a-4bfe-9864-eea56bbcfb39",
   "metadata": {},
   "source": [
    "When proceeding with two expeditions, the maximin profit is only $\\approx 67$.  \n",
    "From the pessimistic maximin standpoint, it is better to go for a single expedition."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35f543cd-c85e-4916-8769-fdf0f3cf1ce5",
   "metadata": {},
   "source": [
    "For a total of three expeditions, the optimization problem is \n",
    "$$\\max_{(M_1,H_1), (M_2,H_2), (M_3,H_3)} \\quad \\min_{\\substack{p_1, p_2, p_3\\in [0,1]\\\\ p_1+p_2+p_3\\leq 1}}  \\frac {7500M_1}{H_1+100 p_1}+\\frac {7500M_2}{H_2+100 p_2}\n",
    "+\\frac {7500M_3}{H_3+100 p_3}-100000.$$\n",
    "We proceed identically as above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "9d7411b9-766f-4691-ac71-f7421272cbbf",
   "metadata": {},
   "outputs": [],
   "source": [
    "def maximize3():\n",
    "    \"\"\"Solves the maximin optimization problem for three expeditions. Returns only one solution, there may be other.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    argmax1 : tuple\n",
    "        First expedition.\n",
    "    argmax2 : tuple\n",
    "        Second expedition.\n",
    "    argmax3 : tuple\n",
    "        Third expedition.\n",
    "    max_val : float\n",
    "        Maximal profit.\n",
    "        \n",
    "    \"\"\"\n",
    "    max_val = float('-inf')\n",
    "    max_mult1, max_hunt1 = None, None\n",
    "    max_mult2, max_hunt2 = None, None\n",
    "    max_mult3, max_hunt3 = None, None\n",
    "    for (mult1, hunt1), (mult2, hunt2), (mult3, hunt3) in itertools.combinations(arr.reshape((25, 2)), 3):\n",
    "        val_temp = session.evaluate(wlexpr(f'NMinimize[{{{mult1}/({hunt1} + 100*p1) + {mult2}/({hunt2} + 100*p2) + {mult3}/({hunt3} + 100*p3), 0<=p1, 0<=p2, 0<=p3, p1+p2+p3 <= 1}}, {{p1,p2,p3}}]'))[0]\n",
    "        val = -100000 + val_temp * 7500\n",
    "        if math.isclose(val, max_val):\n",
    "            print(\"collision\")\n",
    "        if val > max_val:\n",
    "            max_mult1, max_hunt1 = mult1, hunt1\n",
    "            max_mult2, max_hunt2 = mult2, hunt2\n",
    "            max_mult3, max_hunt3 = mult3, hunt3\n",
    "            max_val = val\n",
    "    return ((max_mult1, max_hunt1), (max_mult2, max_hunt2), (max_mult3, max_hunt3), max_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "cea98070-3e5c-4e9a-b285-68ec2de4e6ef",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((87, 5), (89, 5), (100, 8), -47422.72209123209)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximize3()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "439ad2b6-cb8c-40e7-9762-579bfb09b08e",
   "metadata": {},
   "source": [
    "## 2. Optimization given a prior\n",
    "\n",
    "A less pessimistic approach is to model the shares *a priori*.\n",
    "For each destination, the corresponding share is no longer unknown. \n",
    "Instead we posit a value for this share.  \n",
    "Shares are nonnegative and sum to $1$, thus shares are modelled by a probability distribution that we call a prior.\n",
    "\n",
    "Given a prior, the optimization problem is \n",
    "$$\\max_{L\\in \\{1,2,3\\}} \\quad \\max_{(M_i,H_i,p_i)} \\text{fee}(L) + \\sum_{i=1}^L \\frac{7500 M_i}{H_i + 100p_i}   $$\n",
    "\n",
    "### a. Natural prior\n",
    "\n",
    "The ratio $M/H$ seems like a plausible proxy for the attractiveness of a destination.  \n",
    "We compute the array `ratios` with entries $\\frac MH$ and normalize it to obtain the prior array `shares` on the distribution of expeditions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "1769e0d7-ee63-47d5-a0c1-26c345f31f10",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ratios:\n",
      "[[12.   17.5  13.67 10.5  15.  ]\n",
      " [15.67 16.4  17.4  16.   11.67]\n",
      " [18.25 17.8  12.5  12.86  8.5 ]\n",
      " [15.4  16.6  17.   15.8  13.75]\n",
      " [ 6.    9.   13.    7.5  10.  ]]\n"
     ]
    }
   ],
   "source": [
    "ratios = np.zeros((5, 5))\n",
    "for i in range(5):\n",
    "    for j in range(5):\n",
    "        mult, hunt = arr[i, j]\n",
    "        ratios[i, j] = mult/hunt\n",
    "with np.printoptions(precision=2, suppress=True):\n",
    "    print(\"Ratios:\", ratios, sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9c900884-6f8b-4257-be49-5d9143d38fc1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Natural prior:\n",
      "[[0.035 0.052 0.04  0.031 0.044]\n",
      " [0.046 0.048 0.051 0.047 0.034]\n",
      " [0.054 0.052 0.037 0.038 0.025]\n",
      " [0.045 0.049 0.05  0.047 0.04 ]\n",
      " [0.018 0.026 0.038 0.022 0.029]]\n"
     ]
    }
   ],
   "source": [
    "shares = ratios / np.sum(ratios)\n",
    "with np.printoptions(precision=3, suppress=True):\n",
    "    print(\"Natural prior:\", shares, sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a99b1609-893f-4cbe-9112-68b4e010ff25",
   "metadata": {},
   "source": [
    "`shares[0, 0] = 0.035` means that we posit that $3.5\\%$ of all expeditions will go to the destination with multiplier $24$ and $2$ hunters.\n",
    "\n",
    "The difference between larger and smaller values in `ratios` can be accentuated by elevating all the entries of `ratios` to some power."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "51844d14-6716-4fa5-bbfa-85dfec31190a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Natural prior with exponent 5:\n",
      "[[0.014 0.089 0.026 0.007 0.041]\n",
      " [0.051 0.065 0.087 0.057 0.012]\n",
      " [0.11  0.097 0.017 0.019 0.002]\n",
      " [0.047 0.069 0.077 0.054 0.027]\n",
      " [0.    0.003 0.02  0.001 0.005]]\n"
     ]
    }
   ],
   "source": [
    "ratios = np.zeros((5, 5))\n",
    "for i in range(5):\n",
    "    for j in range(5):\n",
    "        mult, hunt = arr[i, j]\n",
    "        ratios[i, j] = mult/hunt\n",
    "ratios = ratios**5\n",
    "shares = ratios / np.sum(ratios)\n",
    "with np.printoptions(precision=3, suppress=True):\n",
    "    print(\"Natural prior with exponent 5:\", shares, sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ccaa605-3fd4-4cee-87f6-2df1e75d9618",
   "metadata": {},
   "source": [
    "The next cell solves the optimization problem by iterating over the whole state space."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "90f95bc6-6052-40a8-bade-4a3741bc7d2a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fee(n):\n",
    "    \"\"\"Compute the fee for a total of n expeditions.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    n : int\n",
    "        Number of expeditions.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    float\n",
    "        Fee.\n",
    "    \"\"\"\n",
    "    if n == 1:\n",
    "        return 0\n",
    "    if n == 2:\n",
    "        return -25000\n",
    "    if n == 3:\n",
    "        return -100000\n",
    "\n",
    "def payoff(mults, hunts, shares):\n",
    "    \"\"\"Compute the final profit after the expeditions.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    mults : list of int\n",
    "        Multipliers for each destination.\n",
    "    hunts : list of int\n",
    "        Hunters for each destination.\n",
    "    shares : list of int\n",
    "        Shares for each destination.\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    float\n",
    "        Profit.\n",
    "    \"\"\"\n",
    "    return 7500 * sum([mult/(hunt + 100*share) for (mult, hunt, share) in zip(mults, hunts, shares)]) + fee(len(mults))\n",
    "\n",
    "def maximize_prior_top(shares, k):\n",
    "    \"\"\"Given the prior, compute solutions that yield top k profits.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    shares : list of int\n",
    "        Shares for each destination.\n",
    "    k : int\n",
    "        Number of solutions\n",
    "    \n",
    "    Returns\n",
    "    -------\n",
    "    list of tuple\n",
    "        Top k profits and optimal expeditions.\n",
    "    \"\"\"\n",
    "    datas = [(mult, hunt, share) for ((mult, hunt), share) in zip(arr.reshape((25, 2)), shares.reshape(25))]\n",
    "    heap = []\n",
    "    iterables = [itertools.combinations(datas, n_exp) for n_exp in range(1, 4)]\n",
    "    for (i, data) in enumerate(itertools.chain.from_iterable(iterables)):\n",
    "        mults = [tupl[0] for tupl in data]\n",
    "        hunts = [tupl[1] for tupl in data]\n",
    "        shares = [tupl[-1] for tupl in data]\n",
    "        val = payoff(mults, hunts, shares)\n",
    "        expeditions = list(zip(mults, hunts))\n",
    "        if i < k:\n",
    "            heapq.heappush(heap, (val, expeditions))\n",
    "        elif val > heap[0][0]:\n",
    "            heapq.heappop(heap)\n",
    "            heapq.heappush(heap, (val, expeditions))\n",
    "    return sorted(heap, reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bde66843-542a-4777-b2bf-f50a4643bf73",
   "metadata": {},
   "source": [
    "Next, we consider the priors obtained by elevating the entries of `ratios` to an exponent `i`.   \n",
    "When `i=0`, the prior is uniformly distributed over all destinations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "df795dff-ac08-4843-8a4a-187054596fa6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Exponent: 0 Profit: 121666.67 Optimal expeditions: [(87, 5), (89, 5)]\n",
      "Exponent: 1 Profit: 128317.87 Optimal expeditions: [(100, 8), (90, 7)]\n",
      "Exponent: 2 Profit: 163391.84 Optimal expeditions: [(100, 8), (90, 7), (52, 4)]\n",
      "Exponent: 3 Profit: 183295.75 Optimal expeditions: [(90, 7), (55, 4), (52, 4)]\n",
      "Exponent: 4 Profit: 196985.94 Optimal expeditions: [(41, 3), (60, 4), (55, 4)]\n",
      "Exponent: 5 Profit: 211548.29 Optimal expeditions: [(60, 4), (77, 5), (55, 4)]\n",
      "Exponent: 6 Profit: 224815.88 Optimal expeditions: [(60, 4), (77, 5), (79, 5)]\n",
      "Exponent: 7 Profit: 234952.17 Optimal expeditions: [(60, 4), (77, 5), (79, 5)]\n",
      "Exponent: 8 Profit: 242128.50 Optimal expeditions: [(80, 5), (77, 5), (79, 5)]\n",
      "Exponent: 9 Profit: 247715.63 Optimal expeditions: [(47, 3), (80, 5), (79, 5)]\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    shares = ratios**i\n",
    "    shares = shares / np.sum(shares)\n",
    "    res = maximize_prior_top(shares, 1)\n",
    "    print(\"Exponent:\", i, \"Profit:\", f\"{res[0][0]:.2f}\", \"Optimal expeditions:\", res[0][1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58928f2d-bbf3-4dec-89fe-c788188efc38",
   "metadata": {},
   "source": [
    "### b. Online poll as prior"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0fdfe32f-aba1-4ebe-a451-72e55f31b965",
   "metadata": {},
   "source": [
    "Another prior can be obtained by exploiting the data from this [online poll](https://docs.google.com/spreadsheets/d/16xO1L8NukksiQCiutmdsTHh51_HXxqulelJez653hjY/edit#gid=0).  \n",
    "Note that the sample size (58) is quite small, and this data is clearly biased and not quite reliable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7b367c66-cf37-447d-8bff-bfdf7ef32f32",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Prior from online poll:\n",
      "[[0.015 0.045 0.038 0.015 0.038]\n",
      " [0.03  0.045 0.053 0.06  0.03 ]\n",
      " [0.068 0.083 0.045 0.053 0.03 ]\n",
      " [0.068 0.053 0.053 0.06  0.053]\n",
      " [0.    0.008 0.03  0.    0.03 ]]\n"
     ]
    }
   ],
   "source": [
    "df = pd.read_csv('data/poll.csv', sep=';', header=None)\n",
    "df = df.to_numpy().flatten()\n",
    "df = df[~np.isnan(df)]\n",
    "counts = {}\n",
    "for n in df:\n",
    "    counts[n] = counts.get(n, 0) + 1\n",
    "shares = np.zeros((5,5))\n",
    "for i in range(5):\n",
    "    for j in range(5):\n",
    "        mult = arr[i, j][0]\n",
    "        shares[i, j] = counts.get(mult, 0)\n",
    "shares = shares / np.sum(shares)\n",
    "with np.printoptions(precision=3, suppress=True):\n",
    "    print(\"Prior from online poll:\", shares, sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "af4261de-d5f6-4bfa-b1be-6969da359271",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(103237.0021283065, [(82, 5), (87, 5)]),\n",
       " (101775.46366676802, [(82, 5), (85, 5)]),\n",
       " (101342.94124219612, [(70, 4), (82, 5)]),\n",
       " (100692.30769230767, [(87, 5), (85, 5)]),\n",
       " (100313.92520522956, [(82, 5), (83, 5)]),\n",
       " (100259.7852677358, [(70, 4), (87, 5)]),\n",
       " (99605.99251292186, [(82, 5), (100, 8)]),\n",
       " (99230.76923076922, [(87, 5), (83, 5)]),\n",
       " (98798.24680619733, [(70, 4), (85, 5)]),\n",
       " (98522.83653846155, [(87, 5), (100, 8)])]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maximize_prior_top(shares, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a855ab8-ab42-4caf-b73a-7fab6d142366",
   "metadata": {},
   "source": [
    "### Results \n",
    "\n",
    "In order to balance the results for the different priors that I explored, my final choice was two expeditions on the tiles with multipliers $100$ and $82$. \n",
    "\n",
    "<img src=\"https://i.imgur.com/n7q6t4x.png\" width=\"1200\" />\n",
    "\n",
    "\n",
    "Some of the true (i.e., ex post) shares are collected [here](https://docs.google.com/spreadsheets/d/1PlQlcJmFzcFJ_DV62cvzkVgphLiW0A5hLf7IwLlvYJQ/edit#gid=0)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "f477af55-8213-4f93-af11-8d94f62836c9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True shares:\n",
      "[[0.015 0.082 0.019   nan 0.037]\n",
      " [0.03  0.062 0.098 0.041 0.012]\n",
      " [0.113 0.108 0.049 0.034 0.006]\n",
      " [0.046 0.054 0.065 0.054 0.026]\n",
      " [  nan   nan 0.019   nan   nan]]\n"
     ]
    }
   ],
   "source": [
    "temp = pd.read_csv('data/shares.csv', sep=';', header=None).to_numpy()\n",
    "dic = {mult:share for (mult, share) in temp}\n",
    "shares_true = np.zeros((5,5))\n",
    "for i in range(5):\n",
    "    for j in range(5):\n",
    "        shares_true[i, j] = dic[arr[i, j][0]]\n",
    "shares_true = shares_true/100\n",
    "with np.printoptions(precision=3, suppress=True):\n",
    "    print(\"True shares:\", shares_true, sep='\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e44e3d87-a83f-4c29-a3d9-066b87ed9365",
   "metadata": {},
   "source": [
    "Filling in the NaNs with equal values, the top 10 choices are displayed below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "e4fb7ea2-7694-40ce-be03-e6a73559781c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(106290.59586034171, [(80, 5), (52, 4)]),\n",
       " (105375.42951194028, [(90, 7), (52, 4)]),\n",
       " (105301.14425749943, [(80, 5), (90, 7)]),\n",
       " (103938.17304238147, [(52, 4), (30, 3)]),\n",
       " (103892.67636555269, [(35, 3), (52, 4)]),\n",
       " (103863.8877879406, [(80, 5), (30, 3)]),\n",
       " (103818.39111111182, [(80, 5), (35, 3)]),\n",
       " (103583.32345590748, [(41, 3), (52, 4)]),\n",
       " (103509.03820146661, [(41, 3), (80, 5)]),\n",
       " (102948.72143953915, [(90, 7), (30, 3)])]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val_nan = (1-np.nansum(shares_true))/np.sum(np.isnan(shares_true))\n",
    "maximize_prior_top(np.nan_to_num(shares_true, nan=val_nan),10)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75dc4cc7-9380-4588-9cd3-9223512fc051",
   "metadata": {},
   "source": [
    "The optimal decision was to go for two expeditions at the tiles with multipliers $80$ and $52$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa08ec9a-72ca-4216-a3c1-c4b3ff3c952a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.12.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}