examples/demo_deterministic_reranking.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### This notebook demonstrates the capabilities of the DeterministicReranking algorithm.\n",
    "The algorithm provides a way to construct balanced rankings of candidates based on precalculated scores.\n",
    "\n",
    "*Based on: [Sahin Cem Geyik, Stuart Ambler, & Krishnaram Kenthapadi (2019). Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining](https://doi.org/10.48550/arXiv.1905.01989).*\n",
    "\n",
    "The notebook is organized as follows:\n",
    "1. Introduction;\n",
    "2. A toy example;\n",
    "3. Theoretical background."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. Introduction"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ranking algorithms are at the core of search and recommendation systems used in, among others, hiring, college admissions, and web-searches. It is clear that algorithmic bias in such cases can create or amplify unacceptable discrimination based on race, gender, or other attributes. Thus, a way of constructing \"fair\" rankings is needed."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Algorithms presented here take as input a **dataset that has already been ranked** (scored), possibly by some other machine learning model, and order them in a way that satisfies specified **fairness requirements**, expressed in a form of a **distribution over the protected attributes**."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. A toy example"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's say we have a collection of 10 balls: 5 red and 5 blue. We assign each of them a score from 0 to 100; however, for some reason the red balls have a higher average score than the blue ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Red mean score: 73.0\n",
      "Blue mean score: 50.0\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "balls = pd.DataFrame([['r', 100],['r', 90],['r', 85],['r', 70],['b', 70],['b', 60],['b', 50],['b', 40],['b', 30],['r', 20]],\n",
    "                     columns=['color', 'score'])\n",
    "\n",
    "print(f\"Red mean score: {np.mean(balls[balls['color'] == 'r']['score'])}\")\n",
    "print(f\"Blue mean score: {np.mean(balls[balls['color'] == 'b']['score'])}\")"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, say we want to take the 6 best balls based on their score. In real life, the need for this limited \"sub-ranking\" may arise for many reasons. For example, the landing page of our ball-selling website may only have space for 6 items. \n",
    "\n",
    "This is similar to the case presented in the original paper, where the algorithm is used to rank job-seekers for recruiters on LinkedIn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>color</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>r</td>\n",
       "      <td>100</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>r</td>\n",
       "      <td>90</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>r</td>\n",
       "      <td>85</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>r</td>\n",
       "      <td>70</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>b</td>\n",
       "      <td>70</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>b</td>\n",
       "      <td>60</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  color  score\n",
       "0     r    100\n",
       "1     r     90\n",
       "2     r     85\n",
       "3     r     70\n",
       "4     b     70\n",
       "5     b     60"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balls.sort_values(by='score', ascending=False)[:6]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, we notice that we have only 2 blue balls in this ranking, and it is in the last position! On one hand, it seems fair in terms of scores. However, we may want a more **equal representation** of different colors in the ranking. The possible motivations for that in real life are clear.\n",
    "\n",
    "In our case, the color is the **protected attribute**, and the red balls are a **privileged class**."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may get a fairer ranking using the `DeterministicReranking` class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "WARNING:root:\n",
      "`load_boston` has been removed from scikit-learn since version 1.2.\n",
      "\n",
      "The Boston housing prices dataset has an ethical problem: as\n",
      "investigated in [1], the authors of this dataset engineered a\n",
      "non-invertible variable \"B\" assuming that racial self-segregation had a\n",
      "positive impact on house prices [2]. Furthermore the goal of the\n",
      "research that led to the creation of this dataset was to study the\n",
      "impact of air quality but it did not give adequate demonstration of the\n",
      "validity of this assumption.\n",
      "\n",
      "The scikit-learn maintainers therefore strongly discourage the use of\n",
      "this dataset unless the purpose of the code is to study and educate\n",
      "about ethical issues in data science and machine learning.\n",
      "\n",
      "In this special case, you can fetch the dataset from the original\n",
      "source::\n",
      "\n",
      "    import pandas as pd\n",
      "    import numpy as np\n",
      "\n",
      "    data_url = \"http://lib.stat.cmu.edu/datasets/boston\"\n",
      "    raw_df = pd.read_csv(data_url, sep=\"\\s+\", skiprows=22, header=None)\n",
      "    data = np.hstack([raw_df.values[::2, :], raw_df.values[1::2, :2]])\n",
      "    target = raw_df.values[1::2, 2]\n",
      "\n",
      "Alternative datasets include the California housing dataset and the\n",
      "Ames housing dataset. You can load the datasets as follows::\n",
      "\n",
      "    from sklearn.datasets import fetch_california_housing\n",
      "    housing = fetch_california_housing()\n",
      "\n",
      "for the California housing dataset and::\n",
      "\n",
      "    from sklearn.datasets import fetch_openml\n",
      "    housing = fetch_openml(name=\"house_prices\", as_frame=True)\n",
      "\n",
      "for the Ames housing dataset.\n",
      "\n",
      "[1] M Carlisle.\n",
      "\"Racist data destruction?\"\n",
      "<https://medium.com/@docintangible/racist-data-destruction-113e3eff54a8>\n",
      "\n",
      "[2] Harrison Jr, David, and Daniel L. Rubinfeld.\n",
      "\"Hedonic housing prices and the demand for clean air.\"\n",
      "Journal of environmental economics and management 5.1 (1978): 81-102.\n",
      "<https://www.researchgate.net/publication/4974606_Hedonic_housing_prices_and_the_demand_for_clean_air>\n",
      ": LawSchoolGPADataset will be unavailable. To install, run:\n",
      "pip install 'aif360[LawSchoolGPA]'\n",
      "WARNING:root:No module named 'tensorflow': AdversarialDebiasing will be unavailable. To install, run:\n",
      "pip install 'aif360[AdversarialDebiasing]'\n",
      "WARNING:root:No module named 'tensorflow': AdversarialDebiasing will be unavailable. To install, run:\n",
      "pip install 'aif360[AdversarialDebiasing]'\n",
      "WARNING:root:No module named 'fairlearn': ExponentiatedGradientReduction will be unavailable. To install, run:\n",
      "pip install 'aif360[Reductions]'\n",
      "WARNING:root:No module named 'fairlearn': GridSearchReduction will be unavailable. To install, run:\n",
      "pip install 'aif360[Reductions]'\n",
      "c:\\Users\\andre\\miniconda3\\envs\\aif\\lib\\site-packages\\torch\\_functorch\\deprecated.py:58: UserWarning: We've integrated functorch into PyTorch. As the final step of the integration, functorch.vmap is deprecated as of PyTorch 2.0 and will be deleted in a future version of PyTorch >= 2.3. Please use torch.vmap instead; see the PyTorch 2.0 release notes and/or the torch.func migration guide for more details https://pytorch.org/docs/master/func.migrating.html\n",
      "  warn_deprecated('vmap', 'torch.vmap')\n",
      "WARNING:root:No module named 'fairlearn': GridSearchReduction will be unavailable. To install, run:\n",
      "pip install 'aif360[Reductions]'\n"
     ]
    }
   ],
   "source": [
    "from aif360.datasets import RegressionDataset\n",
    "from aif360.algorithms.postprocessing.deterministic_reranking import DeterministicReranking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize a RegressionDataset with color as the protected attribute and red as the privileged class.\n",
    "balls_ds = RegressionDataset(df=balls, dep_var_name='score', protected_attribute_names=['color'], privileged_classes=[['r']])\n",
    "# keep the un-normalized scores for clarity; RegressionDataset normalizes them to be from 0 to 1.\n",
    "balls_ds.labels = np.transpose([balls['score']])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To initialize the DeterministicReranking class, we need to pass the **protected attribute values** of the privileged and unprivileged groups.\n",
    "We do that using a list of dictionaries for each group, with the **name of the attribute as the key**. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The RegressionDataset class automatically maps the privileged attribute value (color='red') to 1 and the other to 0.\n",
    "dr = DeterministicReranking(unprivileged_groups=[{'color': 0}], privileged_groups=[{'color': 1}])"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the `fit_predict` method to get the ranking. The arguments are:\n",
    "- `dataset` is the dataset to construct a ranking from;\n",
    "- `rec_size` is the **size** of the ranking we need - in our case 6;\n",
    "- `target_prop` is the **desired proportion** of items of each group in the ranking in the form of dictionary; the keys are the corresponding protected attribute values. We need equal representation, so we pass `{0: 0.5, 1: 0.5}`;\n",
    "- `rerank_type` is the algorithm to use; for further details, skip to section 4 of this notebook. For now, we stick to the default `Constrained`;\n",
    "- `renormalize_scores` will normalize the scores in the result so that the lowest is 0 and the highest is 1. Default is `False`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>color</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1.0</td>\n",
       "      <td>100.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0.0</td>\n",
       "      <td>70.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.0</td>\n",
       "      <td>90.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0.0</td>\n",
       "      <td>60.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1.0</td>\n",
       "      <td>85.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>0.0</td>\n",
       "      <td>50.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   color  score\n",
       "0    1.0  100.0\n",
       "4    0.0   70.0\n",
       "1    1.0   90.0\n",
       "5    0.0   60.0\n",
       "2    1.0   85.0\n",
       "6    0.0   50.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fair_ranking = dr.fit_predict(dataset=balls_ds, rec_size=6, target_prop=[0.5, 0.5], rerank_type='Constrained')\n",
    "fair_ranking.convert_to_dataframe()[0]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this result, the proportions are equal. Additionally, as the algorithm goes through positions in the ranking one-by-one, checking each time for violations of fairness, the items belonging to the unprivileged group (blue balls) **aren't all at the \"bottom\"** of the ranking."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can complicate the task a little by adding another protected attribute: let's call it `size`, which can be \"large\" or \"small\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>color</th>\n",
       "      <th>size</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.8750</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.8125</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.6250</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.6250</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.5000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>0.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.3750</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.2500</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>0.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.1250</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   color  size   score\n",
       "0    1.0   1.0  1.0000\n",
       "1    1.0   0.0  0.8750\n",
       "2    1.0   1.0  0.8125\n",
       "3    1.0   0.0  0.6250\n",
       "4    0.0   1.0  0.6250\n",
       "5    0.0   0.0  0.5000\n",
       "6    0.0   1.0  0.3750\n",
       "7    0.0   0.0  0.2500\n",
       "8    0.0   1.0  0.1250\n",
       "9    1.0   1.0  0.0000"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balls['size'] = ['l', 's', 'l', 's', 'l', 's', 'l', 's', 'l', 'l']\n",
    "balls_ds = RegressionDataset(df=balls, dep_var_name='score',\n",
    "                             protected_attribute_names=['color', 'size'],\n",
    "                             privileged_classes=[['r'], ['l']])\n",
    "balls_ds.convert_to_dataframe()[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's say that we want all possible combinations of the values to be represented equally in the output. We can do so by specifying more than one privileged/unprivileged group (the distinction between privileged and unprivileged groups isn't relevant in this algorihtm)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>color</th>\n",
       "      <th>size</th>\n",
       "      <th>score</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.8750</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.6250</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.5000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1.0</td>\n",
       "      <td>1.0</td>\n",
       "      <td>0.8125</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1.0</td>\n",
       "      <td>0.0</td>\n",
       "      <td>0.6250</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   color  size   score\n",
       "0    1.0   1.0  1.0000\n",
       "1    1.0   0.0  0.8750\n",
       "4    0.0   1.0  0.6250\n",
       "5    0.0   0.0  0.5000\n",
       "2    1.0   1.0  0.8125\n",
       "3    1.0   0.0  0.6250"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dr = DeterministicReranking(unprivileged_groups=[{'color': 0, 'size': 0}, {'color': 0, 'size': 1}, {'color': 1, 'size': 0}],\n",
    "                            privileged_groups=[{'color': 1, 'size': 1}])\n",
    "fair_ranking = dr.fit_predict(dataset=balls_ds, rec_size=6, target_prop=[0.25, 0.25, 0.25, 0.25])\n",
    "fair_ranking.convert_to_dataframe()[0]"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 3. Variations of the algorithm"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `predict` and `fit_predict` methods of the algorithm include a `rerank_type` parameter. It refers to the different algorithms described in the original paper: **Greedy**, **Conservative**, **Relaxed** and **Constrained**. The difference between them lies in how, given a desired proportion of groups, they choose the next element in the ranking."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before getting into the details, we need to formalize the properties we want our ranking to satisfy:\n",
    "- $\\forall k \\le |\\tau_r|, \\quad \\forall a \\in A: \\quad count_k(a) \\ge \\lfloor p_a*k \\rfloor$,\n",
    "- $\\forall k \\le |\\tau_r|, \\quad \\forall a \\in A: \\quad count_k(a) \\le \\lceil p_a*k \\rceil$\n",
    "\n",
    "where $|\\tau_r|$ is the size of the ranking, $A$ is the set of groups, $count_k(a)$ is the number of elements of group $a$ in first $k$ elements of the ranking, and $p_a$ is the desired proportion of elements belonging to the group $a$ in the ranking.\n",
    "\n",
    "We refer to these properties as the minimum and the maximum representation constraints, respectively.\n",
    "\n",
    "The demand for the properties to be satisfied at every $k$ comes from the observation that the position of an element in the ranking can have a significant impact on the response of the user."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **Greedy** variant works as follows:\n",
    "- If there are any groups for which the minimum representation constraint is violated (the proportion of the group in the ranking is too small), choose the element with the highest score among those groups;\n",
    "- Otherwise, choose the element with the highest score among groups that do not violate the maximum constraint (i.e. aren't overrepresented)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **Conservative** and **Relaxed** variants give preference to underrepresented groups:\n",
    "- If there are any groups for which the minimum representation constraint is violated, choose the element with the highest score among those groups (analogous to Greedy)\n",
    "- Otherwise, among groups that do not violate the maximum constraint, pick the group that minimizes $\\frac{\\lceil p_a*k \\rceil}{p_a}$ if Conservative or $\\lceil\\frac{\\lceil p_a*k \\rceil}{p_a}\\rceil$ if Relaxed. From this group, choose the element with the highest score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **Constrained** variant differs significantly from both of the previous ones:\n",
    "- Starting with 0, increase the value of *k* until the minimum representation constraint is increased for at least one group. If there are more than one such groups, order them according to the descending score of their highest-scoring candidates not yet in the ranking.\n",
    "- For each group in the list above:\n",
    "    1. Insert the next candidate from the group to the next empty index in the ranking\n",
    "    2. Swap the candidate towards earlier indices until:\n",
    "        - Either the score of the candidate in the earlier index is larger, or,\n",
    "        - Swapping will violate the minimum condition for the group of the candidate in the earlier index."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Experimental results (see reference) show that all algorithms exhibit similar performance in terms of both list utility and fairness. The Greedy algorithm generates ranked lists with higher utility, but doesn't strictly adhere to the fairness constraints; among the rest, Constrained shows the best utility."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "aif",
   "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.10.12"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}