{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "OpOHLyhPpaxC"
   },
   "source": [
    "# Algorithms for Data Science"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "NvZ7rLY2pg8i"
   },
   "source": [
    "## Matching Bids to Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "NqIyJ2BgplVA"
   },
   "source": [
    "### 1. Preliminaries \n",
    "\n",
    "The objective of this lab is to implement the Adwords algorithm in the particular case when we have $N$ advertisers having budget $B$ and each bidding an amount of $1$. Moreover, queries arrive in batches of $B$ queries, $N$ times, and only advertises $A_i,\\dots,A_n$ bid on round $i$. The optimal algorithm would have revenue $NB$. Our aim is to see what the revenue of the BALANCE algorithm is."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "uj1GxrPF_DxQ"
   },
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'numpy'",
     "output_type": "error",
     "traceback": [
      "\u001b[31m---------------------------------------------------------------------------\u001b[39m",
      "\u001b[31mModuleNotFoundError\u001b[39m                       Traceback (most recent call last)",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[2]\u001b[39m\u001b[32m, line 2\u001b[39m\n\u001b[32m      1\u001b[39m \u001b[38;5;28;01mimport\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[34;01mrandom\u001b[39;00m\n\u001b[32m----> \u001b[39m\u001b[32m2\u001b[39m \u001b[38;5;28;01mimport\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[34;01mnumpy\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[38;5;28;01mas\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[34;01mnp\u001b[39;00m\n\u001b[32m      4\u001b[39m \u001b[38;5;66;03m#parameters\u001b[39;00m\n\u001b[32m      5\u001b[39m N = \u001b[32m100\u001b[39m\n",
      "\u001b[31mModuleNotFoundError\u001b[39m: No module named 'numpy'"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "\n",
    "#parameters\n",
    "N = 100\n",
    "B = 100\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "GgKzrJj3_oiX"
   },
   "source": [
    "### 2. BALANCE algorithm\n",
    "\n",
    "The balance algorithm simply gives the query to the bidder having the most budget available. In this case, BALANCE achieves a competitive ratio of $1-1/e$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 1000
    },
    "id": "IbQ0B1a3BpAV",
    "outputId": "c26d4b87-eb10-4626-e82c-b1484e080272"
   },
   "outputs": [],
   "source": [
    "# array of budgets (they all have the same budget initially) \n",
    "Bs = [B]*N\n",
    "revenue = 0\n",
    "\n",
    "for i in range(N): #rounds\n",
    "  for j in range(B): #queries\n",
    "    idx = np.argmax(Bs[i:]) # taking the index with the most budget, from the list(greedy approach)\n",
    "    #print (Bs[i:])\n",
    "    if Bs[i+idx]>0:\n",
    "      Bs[i+idx] -= 1\n",
    "      revenue += 1\n",
    "      print (f'Round {i} query {j} -- allocated to bidder {i+idx}')\n",
    "    else:\n",
    "      print (f'Round {i} query {j} -- not allocated')\n",
    "\n",
    "print (f'Total revenue: {revenue}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Dz9rNT2Na35t"
   },
   "source": [
    "### 3. **TASK** Generalized BALANCE Algorithm\n",
    "\n",
    "Implement the generalized BALANCE algorithm, where the bids can be arbitrary, and the bidder is selected based on the $\\psi$ function presented in the lecture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "id": "tan6ZeaXY3wx"
   },
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'numpy'",
     "output_type": "error",
     "traceback": [
      "\u001b[31m---------------------------------------------------------------------------\u001b[39m",
      "\u001b[31mModuleNotFoundError\u001b[39m                       Traceback (most recent call last)",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[1]\u001b[39m\u001b[32m, line 1\u001b[39m\n\u001b[32m----> \u001b[39m\u001b[32m1\u001b[39m \u001b[38;5;28;01mimport\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[34;01mnumpy\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[38;5;28;01mas\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[34;01mnp\u001b[39;00m\n\u001b[32m      3\u001b[39m \u001b[38;5;66;03m# Parameters\u001b[39;00m\n\u001b[32m      4\u001b[39m N = \u001b[32m100\u001b[39m  \u001b[38;5;66;03m# Number of advertisers\u001b[39;00m\n",
      "\u001b[31mModuleNotFoundError\u001b[39m: No module named 'numpy'"
     ]
    }
   ],
   "source": [
    "# Parameters\n",
    "N = 100  # Number of advertisers\n",
    "B = 100  # Initial budget\n",
    "R = 100  # Number of rounds\n",
    "\n",
    "def generalized_balance(N, B, R):\n",
    "    \"\"\"\n",
    "    Generalized BALANCE algorithm\n",
    "    Selects advertiser with highest ψ_i = x_i * (1 - e^(-f_i))\n",
    "    where f_i = 1 - (spent_i / B) and x_i = 1 (uniform bid)\n",
    "    \"\"\"\n",
    "    budgets = [B] * N\n",
    "    spent = [0] * N\n",
    "    revenue = 0\n",
    "    \n",
    "    for r in range(R):\n",
    "        for q in range(B):\n",
    "            # Calculate psi for eligible advertisers\n",
    "            eligible = [i for i in range(r, N) if budgets[i] > 0]\n",
    "            \n",
    "            if len(eligible) > 0:\n",
    "                best_idx = max(eligible, key=lambda i: 1 * (1 - np.exp(-(1 - spent[i]/B))))\n",
    "                budgets[best_idx] -= 1\n",
    "                spent[best_idx] += 1\n",
    "                revenue += 1\n",
    "                print(f'Round {r} query {q} -- allocated to bidder {best_idx}')\n",
    "            else:\n",
    "                print(f'Round {r} query {q} -- not allocated')\n",
    "    \n",
    "    return revenue\n",
    "\n",
    "\n",
    "revenue = generalized_balance()\n",
    "print(f'\\nTotal revenue: {revenue}')\n",
    "         \n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "FZHcE7Jve1PR"
   },
   "source": [
    "_You can use this cell to write your discussion of the results_"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "m2_ds_algods_lab5_adwords.ipynb",
   "provenance": []
  },
  "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.13.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}