Skip to content

Instantly share code, notes, and snippets.

@ostrowr

ostrowr/compiler_explorer_sponsors.ipynb

Last active March 21, 2023 16:46
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ostrowr/8fb2c18ec5f6a0addd8b8d0b3e1839ec to your computer and use it in GitHub Desktop.
Save ostrowr/8fb2c18ec5f6a0addd8b8d0b3e1839ec to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
compiler_explorer_sponsors.ipynb
{
"cells": [
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"# The Compiler Explorer Problem\n",
"\n",
"(This is a messy solution to the problem posed in https://www.twoscomplement.org/podcast/the_ce_problem.mp3)\n",
"\n",
"Compiler explorer has a number of sponsors. Each of those sponsors pays to be shown on some percentage of page loads\n",
"– but the site only has a certain number of slots to show. Is it possible to find \n",
"\n",
"* (a) whether it's even possible to fufull these commitments?, and\n",
"* (b) what's the most fair way to do so?\n",
"\n",
"## Defining the problem\n",
"\n",
"It's pretty clear that it's not possible to fufill these commitments in the general case. If you commit to 4 sponsors\n",
"that you'll show them all on 100% of page loads and only have 3 slots... well, you'd better make room for a 4th or prepare\n",
"a refund.\n",
"\n",
"Fairness is a less well-defined concept. In the podcast, Matt poses a constraint like the following:\n",
"\n",
"\"if two people are paying to be shown the same amount, they should be shown basically the same amount.\"\n",
"\n",
"Now, this makes sense, but I think it isn't general enough and doesn't jive with my understanding of fairness. Instead,\n",
"the mean square error between the actual probabilities and the desired ones seems like a better solution (though nearly\n",
"any metric could be used.)\n",
"\n",
"Why MSE rather than bucketing per-user? Trying to bucket into discrete segments only preserves fairness over people who \n",
"paid the same amount, which doesn’t seem quite as fair to me (though this is a social value, not a mathematical one.) \n",
"For example, consider 2 slots with 3 sponsors:\n",
"\n",
"* A pays for 10%\n",
"* B pays for 50%\n",
"* and C pays for 50% \n",
"\n",
"With the bucketing approach, just trying to minimize the difference between parties in the same bucket,\n",
"we’ll end up with A showing up 100% of the time while B and C will get exactly 50% each. This seems bad. Instead, if \n",
"there must be error, MSE tries to spread it evenly across all of the sponsors.\n",
"\n",
"So, now, we've concretely defined the problem:\n",
"\n",
"Given input of tuples `(sponsor_id, percentageTarget)` and `n` ad slots, write a generating function for an infinite list of `n` `sponsor_ids` at a time (or indicate that it isn't possible) which \n",
"* (a) guarantees that the ID shows up at least percentageTarget time and \n",
"* (b) minimizes the MSE between the actual percentage each ID shows up and the percentageTarget."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example:\n",
"Let's consider the example Matt gave in the podcast, where there are 3 slots for ads and a bunch of commitments to sponsors. We'll choose arbitrarily that Matt committed to \n",
"\n",
"* Sponsor 0 gets shown at least 20% of the time\n",
"* Sponsor 1: >= 40%\n",
"* Sponsor 2: >= 20%\n",
"* Sponsor 3: >= 30%\n",
"* Sponsor 4: >= 90%\n",
"* Sponsor 5: >= 42%"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"N_SLOTS = 3\n",
"SPONSOR_COMMITMENTS = np.array([0.2, 0.4, 0.2, 0.3, 0.9, 0.42])"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"## A closed-ish form solution for small-ish problem sizes:\n",
"\n",
"If we can generate probabilities for each choice of sponsors, then we've solved the problem. If we know that sponsors (0, 1, 2) should be selected 10% of the time and (0, 3, 4) should be selected 20% of the time, it's trivial to write a generating function that converges to those probabilities.\n",
"\n",
"So, the tricky bit is actually finding those probabilities!\n",
"\n",
"First, let's just enumerate all of the possible choices of sponsors.\n",
"\n",
"If we have `n` sponsors and `s` ad slots and have enough memory to store (n choose s) bitarrays of length `n`, then we can enumerate every combination of sponsors into ad slots and fit that in memory. This won't work for millions of sponsors, but for reasonable choices of `n` and `s` is very tractable."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 1, 5), (0, 2, 3), (0, 2, 4), (0, 2, 5), (0, 3, 4), (0, 3, 5), (0, 4, 5), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]\n"
]
}
],
"source": [
"import itertools\n",
"combinations = list(itertools.combinations(range(len(SPONSOR_COMMITMENTS)), N_SLOTS))\n",
"print(combinations)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"We want to deal with a matrix, though – let's generate an assignments matrix where every column is an assignment of sponsors to slots:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[[1. 1. 1. 1. 1. 1. 0. 0. 0. 0.]\n",
" [1. 1. 1. 0. 0. 0. 1. 1. 1. 0.]\n",
" [1. 0. 0. 1. 1. 0. 1. 1. 0. 1.]\n",
" [0. 1. 0. 1. 0. 1. 1. 0. 1. 1.]\n",
" [0. 0. 1. 0. 1. 1. 0. 1. 1. 1.]]\n"
]
}
],
"source": [
"def generate_assignments_matrix(n_sponsors, n_ad_slots):\n",
" def chosen_sponsor_ids_to_array(selected_sponsor_ids):\n",
" \"\"\"\n",
" Create numpy array of length num_sponsors with 1 in\n",
" index i if sponsor_i is selected, otherwise 0\n",
" \"\"\"\n",
" arr = np.zeros(n_sponsors)\n",
" arr[[selected_sponsor_ids]] = 1\n",
" return arr\n",
"\n",
" ids = list(range(n_sponsors))\n",
"\n",
" combinations = list(itertools.combinations(ids, n_ad_slots))\n",
"\n",
" # all possible sponsor assignments. One row is one possible assignment.\n",
" # For example, [1, 1, 0, 0, 1] means that there are 3 ad slots, which go to sponsors 0, 1, and 4.\n",
" assignments = np.array([chosen_sponsor_ids_to_array(c) for c in combinations])\n",
" transposed_assignments = np.transpose(assignments)\n",
" return transposed_assignments\n",
"\n",
"print(generate_assignments_matrix(5, 3))"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"Note above that column 1 means that we've selected sponsors 0, 1, and 2, column 2 means that we select 0, 1, 3, etc.\n",
"\n",
"Now we're basically solving a traditional constraint satisfaction problem. \n",
"\n",
"If `A` is the assignments matrix we generate and `b` is the probabilities we've committed to for each sponsor, we want to find the vector `x` that minimizes `Ax - b`. subject to the following constraints:\n",
"\n",
"1. All `x_i >= 0` – `x_i` is essentially \"the probability that we choose sponsor selection `i`, and negative probabilities don't make sense.\n",
"2. `sum(x) = 1` – the probabilities of each selection need to sum to 1\n",
"3. For all `x_i`, `x_i >= b_i` – `b` here is the minimum probability that we have committed to for each sponsor, so we can't show fewer than this!\n",
"\n",
"If we find a solution, we can run with it. If we can't, we might have overcommitted.\n",
"\n",
"Now, it's been a long time since I've done linear algebra and I'm sure there's a much better way to express these constraints – maybe even a fully closed form. However, scipy has an easy time of this formulation:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"import scipy\n",
"\n",
"def constrained_least_squares(A, b):\n",
" n = A.shape[1]\n",
"\n",
" # minimizing this function – least squares here, but could be anything\n",
" def objective(x):\n",
" return np.linalg.norm((A @ x) - b)**2\n",
"\n",
" # sum of probabilities must equal 1\n",
" equality_constraint = scipy.optimize.NonlinearConstraint(lambda x: np.sum(x), 1, 1)\n",
"\n",
" # resulting assignments must be >= the minimum assignments that were paid for\n",
" inequality_constraint = scipy.optimize.LinearConstraint(A, lb=b)\n",
"\n",
" # Solve the optimization problem\n",
" res = scipy.optimize.minimize(fun=objective, x0=np.zeros(n), constraints=[equality_constraint, inequality_constraint], bounds=scipy.optimize.Bounds(lb=0))\n",
" if res.success:\n",
" return res.x\n",
" return None"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"Finally, we can actually try it out! Let's use the parameters we specified above:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"You should show sponsors [0, 1, 2] with probability 0.0\n",
"You should show sponsors [0, 1, 3] with probability 0.0\n",
"You should show sponsors [0, 1, 4] with probability 0.0846\n",
"You should show sponsors [0, 1, 5] with probability 0.0\n",
"You should show sponsors [0, 2, 3] with probability 0.0011\n",
"You should show sponsors [0, 2, 4] with probability 0.0547\n",
"You should show sponsors [0, 2, 5] with probability 0.0022\n",
"You should show sponsors [0, 3, 4] with probability 0.0635\n",
"You should show sponsors [0, 3, 5] with probability 0.0\n",
"You should show sponsors [0, 4, 5] with probability 0.0905\n",
"You should show sponsors [1, 2, 3] with probability 0.0\n",
"You should show sponsors [1, 2, 4] with probability 0.0846\n",
"You should show sponsors [1, 2, 5] with probability 0.0\n",
"You should show sponsors [1, 3, 4] with probability 0.1313\n",
"You should show sponsors [1, 3, 5] with probability 0.0\n",
"You should show sponsors [1, 4, 5] with probability 0.1962\n",
"You should show sponsors [2, 3, 4] with probability 0.0635\n",
"You should show sponsors [2, 3, 5] with probability 0.0\n",
"You should show sponsors [2, 4, 5] with probability 0.0905\n",
"You should show sponsors [3, 4, 5] with probability 0.1372\n",
"Probability of each sponsor showing up: [0.29666291 0.49667389 0.29666291 0.39664674 0.99670122 0.51665232]\n",
"error (actual - committed) [0.09666291 0.09667389 0.09666291 0.09664674 0.09670122 0.09665232]\n",
"Sanity check: total probability: 1.0\n"
]
}
],
"source": [
"def solve(sponsor_commitments, n_slots):\n",
" assignments = generate_assignments_matrix(len(sponsor_commitments), n_slots)\n",
" solution = constrained_least_squares(assignments, sponsor_commitments)\n",
" return assignments, solution\n",
"\n",
"def print_solution(sponsor_commitments, n_slots):\n",
" assignments, solution = solve(sponsor_commitments, n_slots)\n",
" if solution is not None:\n",
" for i, prob in enumerate(solution):\n",
" assigned_sponsors = [i for i, e in enumerate(assignments[:,i]) if e]\n",
" print(f\"You should show sponsors {assigned_sponsors} with probability {round(prob, 4)}\")\n",
" print(\"Probability of each sponsor showing up:\", assignments @ solution)\n",
" print(\"error (actual - committed)\", assignments @ solution - sponsor_commitments)\n",
" print(\"Sanity check: total probability:\", sum(solution))\n",
" else: \n",
" print(\"Could not find a solution.\")\n",
" \n",
"print_solution(SPONSOR_COMMITMENTS, N_SLOTS)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"Note above that the error for each of these is the same, which suggests that this is indeed an optimal solution! If you show each three sponsors as this solution suggests, each sponsor will have underpaid by about 10% and will be happy."
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"To be safe, let's check a solution that we know doesn't work:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Could not find a solution.\n"
]
}
],
"source": [
"print_solution([0.9, 0.9, 0.9, 0.9, 0.1], 3)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"This makes sense – it's impossible to show 4 sponsors 90% of the time if you only have 3 slots!\n",
"\n",
"Let's try a few more:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"You should show sponsors [0, 1, 2] with probability 0.0\n",
"You should show sponsors [0, 1, 3] with probability 0.2984\n",
"You should show sponsors [0, 1, 4] with probability 0.0\n",
"You should show sponsors [0, 2, 3] with probability 0.4288\n",
"You should show sponsors [0, 2, 4] with probability 0.0\n",
"You should show sponsors [0, 3, 4] with probability 0.0979\n",
"You should show sponsors [1, 2, 3] with probability 0.0477\n",
"You should show sponsors [1, 2, 4] with probability 0.0\n",
"You should show sponsors [1, 3, 4] with probability 0.0789\n",
"You should show sponsors [2, 3, 4] with probability 0.0484\n",
"Probability of each sponsor showing up: [0.82500508 0.42503802 0.5248245 1. 0.22513241]\n",
"error (actual - committed) [0.12500508 0.12503802 0.1248245 0.1 0.12513241]\n",
"Sanity check: total probability: 1.0\n"
]
}
],
"source": [
"print_solution([0.7, 0.3, 0.4, 0.9, 0.1], 3)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"You should show sponsors [0, 1, 2, 3] with probability 0.0005\n",
"You should show sponsors [0, 1, 2, 4] with probability 0.0005\n",
"You should show sponsors [0, 1, 2, 5] with probability 0.0005\n",
"You should show sponsors [0, 1, 2, 6] with probability 0.0005\n",
"You should show sponsors [0, 1, 2, 7] with probability 0.0005\n",
"You should show sponsors [0, 1, 2, 8] with probability 0.0001\n",
"You should show sponsors [0, 1, 2, 9] with probability 0.0144\n",
"You should show sponsors [0, 1, 3, 4] with probability 0.0005\n",
"You should show sponsors [0, 1, 3, 5] with probability 0.0005\n",
"You should show sponsors [0, 1, 3, 6] with probability 0.0005\n",
"You should show sponsors [0, 1, 3, 7] with probability 0.0005\n",
"You should show sponsors [0, 1, 3, 8] with probability 0.0001\n",
"You should show sponsors [0, 1, 3, 9] with probability 0.0144\n",
"You should show sponsors [0, 1, 4, 5] with probability 0.0005\n",
"You should show sponsors [0, 1, 4, 6] with probability 0.0005\n",
"You should show sponsors [0, 1, 4, 7] with probability 0.0005\n",
"You should show sponsors [0, 1, 4, 8] with probability 0.0001\n",
"You should show sponsors [0, 1, 4, 9] with probability 0.0144\n",
"You should show sponsors [0, 1, 5, 6] with probability 0.0005\n",
"You should show sponsors [0, 1, 5, 7] with probability 0.0005\n",
"You should show sponsors [0, 1, 5, 8] with probability 0.0001\n",
"You should show sponsors [0, 1, 5, 9] with probability 0.0144\n",
"You should show sponsors [0, 1, 6, 7] with probability 0.0005\n",
"You should show sponsors [0, 1, 6, 8] with probability 0.0001\n",
"You should show sponsors [0, 1, 6, 9] with probability 0.0144\n",
"You should show sponsors [0, 1, 7, 8] with probability 0.0001\n",
"You should show sponsors [0, 1, 7, 9] with probability 0.0144\n",
"You should show sponsors [0, 1, 8, 9] with probability 0.0055\n",
"You should show sponsors [0, 2, 3, 4] with probability 0.0005\n",
"You should show sponsors [0, 2, 3, 5] with probability 0.0005\n",
"You should show sponsors [0, 2, 3, 6] with probability 0.0005\n",
"You should show sponsors [0, 2, 3, 7] with probability 0.0005\n",
"You should show sponsors [0, 2, 3, 8] with probability 0.0001\n",
"You should show sponsors [0, 2, 3, 9] with probability 0.0144\n",
"You should show sponsors [0, 2, 4, 5] with probability 0.0005\n",
"You should show sponsors [0, 2, 4, 6] with probability 0.0005\n",
"You should show sponsors [0, 2, 4, 7] with probability 0.0005\n",
"You should show sponsors [0, 2, 4, 8] with probability 0.0001\n",
"You should show sponsors [0, 2, 4, 9] with probability 0.0144\n",
"You should show sponsors [0, 2, 5, 6] with probability 0.0005\n",
"You should show sponsors [0, 2, 5, 7] with probability 0.0005\n",
"You should show sponsors [0, 2, 5, 8] with probability 0.0001\n",
"You should show sponsors [0, 2, 5, 9] with probability 0.0144\n",
"You should show sponsors [0, 2, 6, 7] with probability 0.0005\n",
"You should show sponsors [0, 2, 6, 8] with probability 0.0001\n",
"You should show sponsors [0, 2, 6, 9] with probability 0.0144\n",
"You should show sponsors [0, 2, 7, 8] with probability 0.0001\n",
"You should show sponsors [0, 2, 7, 9] with probability 0.0144\n",
"You should show sponsors [0, 2, 8, 9] with probability 0.0055\n",
"You should show sponsors [0, 3, 4, 5] with probability 0.0005\n",
"You should show sponsors [0, 3, 4, 6] with probability 0.0005\n",
"You should show sponsors [0, 3, 4, 7] with probability 0.0005\n",
"You should show sponsors [0, 3, 4, 8] with probability 0.0001\n",
"You should show sponsors [0, 3, 4, 9] with probability 0.0144\n",
"You should show sponsors [0, 3, 5, 6] with probability 0.0005\n",
"You should show sponsors [0, 3, 5, 7] with probability 0.0005\n",
"You should show sponsors [0, 3, 5, 8] with probability 0.0001\n",
"You should show sponsors [0, 3, 5, 9] with probability 0.0144\n",
"You should show sponsors [0, 3, 6, 7] with probability 0.0005\n",
"You should show sponsors [0, 3, 6, 8] with probability 0.0001\n",
"You should show sponsors [0, 3, 6, 9] with probability 0.0144\n",
"You should show sponsors [0, 3, 7, 8] with probability 0.0001\n",
"You should show sponsors [0, 3, 7, 9] with probability 0.0144\n",
"You should show sponsors [0, 3, 8, 9] with probability 0.0055\n",
"You should show sponsors [0, 4, 5, 6] with probability 0.0005\n",
"You should show sponsors [0, 4, 5, 7] with probability 0.0005\n",
"You should show sponsors [0, 4, 5, 8] with probability 0.0001\n",
"You should show sponsors [0, 4, 5, 9] with probability 0.0144\n",
"You should show sponsors [0, 4, 6, 7] with probability 0.0005\n",
"You should show sponsors [0, 4, 6, 8] with probability 0.0001\n",
"You should show sponsors [0, 4, 6, 9] with probability 0.0144\n",
"You should show sponsors [0, 4, 7, 8] with probability 0.0001\n",
"You should show sponsors [0, 4, 7, 9] with probability 0.0144\n",
"You should show sponsors [0, 4, 8, 9] with probability 0.0055\n",
"You should show sponsors [0, 5, 6, 7] with probability 0.0005\n",
"You should show sponsors [0, 5, 6, 8] with probability 0.0001\n",
"You should show sponsors [0, 5, 6, 9] with probability 0.0144\n",
"You should show sponsors [0, 5, 7, 8] with probability 0.0001\n",
"You should show sponsors [0, 5, 7, 9] with probability 0.0144\n",
"You should show sponsors [0, 5, 8, 9] with probability 0.0055\n",
"You should show sponsors [0, 6, 7, 8] with probability 0.0001\n",
"You should show sponsors [0, 6, 7, 9] with probability 0.0144\n",
"You should show sponsors [0, 6, 8, 9] with probability 0.0055\n",
"You should show sponsors [0, 7, 8, 9] with probability 0.0055\n",
"You should show sponsors [1, 2, 3, 4] with probability 0.0005\n",
"You should show sponsors [1, 2, 3, 5] with probability 0.0005\n",
"You should show sponsors [1, 2, 3, 6] with probability 0.0005\n",
"You should show sponsors [1, 2, 3, 7] with probability 0.0005\n",
"You should show sponsors [1, 2, 3, 8] with probability 0.0001\n",
"You should show sponsors [1, 2, 3, 9] with probability 0.0144\n",
"You should show sponsors [1, 2, 4, 5] with probability 0.0005\n",
"You should show sponsors [1, 2, 4, 6] with probability 0.0005\n",
"You should show sponsors [1, 2, 4, 7] with probability 0.0005\n",
"You should show sponsors [1, 2, 4, 8] with probability 0.0001\n",
"You should show sponsors [1, 2, 4, 9] with probability 0.0144\n",
"You should show sponsors [1, 2, 5, 6] with probability 0.0005\n",
"You should show sponsors [1, 2, 5, 7] with probability 0.0005\n",
"You should show sponsors [1, 2, 5, 8] with probability 0.0001\n",
"You should show sponsors [1, 2, 5, 9] with probability 0.0144\n",
"You should show sponsors [1, 2, 6, 7] with probability 0.0005\n",
"You should show sponsors [1, 2, 6, 8] with probability 0.0001\n",
"You should show sponsors [1, 2, 6, 9] with probability 0.0144\n",
"You should show sponsors [1, 2, 7, 8] with probability 0.0001\n",
"You should show sponsors [1, 2, 7, 9] with probability 0.0144\n",
"You should show sponsors [1, 2, 8, 9] with probability 0.0055\n",
"You should show sponsors [1, 3, 4, 5] with probability 0.0005\n",
"You should show sponsors [1, 3, 4, 6] with probability 0.0005\n",
"You should show sponsors [1, 3, 4, 7] with probability 0.0005\n",
"You should show sponsors [1, 3, 4, 8] with probability 0.0001\n",
"You should show sponsors [1, 3, 4, 9] with probability 0.0144\n",
"You should show sponsors [1, 3, 5, 6] with probability 0.0005\n",
"You should show sponsors [1, 3, 5, 7] with probability 0.0005\n",
"You should show sponsors [1, 3, 5, 8] with probability 0.0001\n",
"You should show sponsors [1, 3, 5, 9] with probability 0.0144\n",
"You should show sponsors [1, 3, 6, 7] with probability 0.0005\n",
"You should show sponsors [1, 3, 6, 8] with probability 0.0001\n",
"You should show sponsors [1, 3, 6, 9] with probability 0.0144\n",
"You should show sponsors [1, 3, 7, 8] with probability 0.0001\n",
"You should show sponsors [1, 3, 7, 9] with probability 0.0144\n",
"You should show sponsors [1, 3, 8, 9] with probability 0.0055\n",
"You should show sponsors [1, 4, 5, 6] with probability 0.0005\n",
"You should show sponsors [1, 4, 5, 7] with probability 0.0005\n",
"You should show sponsors [1, 4, 5, 8] with probability 0.0001\n",
"You should show sponsors [1, 4, 5, 9] with probability 0.0144\n",
"You should show sponsors [1, 4, 6, 7] with probability 0.0005\n",
"You should show sponsors [1, 4, 6, 8] with probability 0.0001\n",
"You should show sponsors [1, 4, 6, 9] with probability 0.0144\n",
"You should show sponsors [1, 4, 7, 8] with probability 0.0001\n",
"You should show sponsors [1, 4, 7, 9] with probability 0.0144\n",
"You should show sponsors [1, 4, 8, 9] with probability 0.0055\n",
"You should show sponsors [1, 5, 6, 7] with probability 0.0005\n",
"You should show sponsors [1, 5, 6, 8] with probability 0.0001\n",
"You should show sponsors [1, 5, 6, 9] with probability 0.0144\n",
"You should show sponsors [1, 5, 7, 8] with probability 0.0001\n",
"You should show sponsors [1, 5, 7, 9] with probability 0.0144\n",
"You should show sponsors [1, 5, 8, 9] with probability 0.0055\n",
"You should show sponsors [1, 6, 7, 8] with probability 0.0001\n",
"You should show sponsors [1, 6, 7, 9] with probability 0.0144\n",
"You should show sponsors [1, 6, 8, 9] with probability 0.0055\n",
"You should show sponsors [1, 7, 8, 9] with probability 0.0055\n",
"You should show sponsors [2, 3, 4, 5] with probability 0.0005\n",
"You should show sponsors [2, 3, 4, 6] with probability 0.0005\n",
"You should show sponsors [2, 3, 4, 7] with probability 0.0005\n",
"You should show sponsors [2, 3, 4, 8] with probability 0.0001\n",
"You should show sponsors [2, 3, 4, 9] with probability 0.0144\n",
"You should show sponsors [2, 3, 5, 6] with probability 0.0005\n",
"You should show sponsors [2, 3, 5, 7] with probability 0.0005\n",
"You should show sponsors [2, 3, 5, 8] with probability 0.0001\n",
"You should show sponsors [2, 3, 5, 9] with probability 0.0144\n",
"You should show sponsors [2, 3, 6, 7] with probability 0.0005\n",
"You should show sponsors [2, 3, 6, 8] with probability 0.0001\n",
"You should show sponsors [2, 3, 6, 9] with probability 0.0144\n",
"You should show sponsors [2, 3, 7, 8] with probability 0.0001\n",
"You should show sponsors [2, 3, 7, 9] with probability 0.0144\n",
"You should show sponsors [2, 3, 8, 9] with probability 0.0055\n",
"You should show sponsors [2, 4, 5, 6] with probability 0.0005\n",
"You should show sponsors [2, 4, 5, 7] with probability 0.0005\n",
"You should show sponsors [2, 4, 5, 8] with probability 0.0001\n",
"You should show sponsors [2, 4, 5, 9] with probability 0.0144\n",
"You should show sponsors [2, 4, 6, 7] with probability 0.0005\n",
"You should show sponsors [2, 4, 6, 8] with probability 0.0001\n",
"You should show sponsors [2, 4, 6, 9] with probability 0.0144\n",
"You should show sponsors [2, 4, 7, 8] with probability 0.0001\n",
"You should show sponsors [2, 4, 7, 9] with probability 0.0144\n",
"You should show sponsors [2, 4, 8, 9] with probability 0.0055\n",
"You should show sponsors [2, 5, 6, 7] with probability 0.0005\n",
"You should show sponsors [2, 5, 6, 8] with probability 0.0001\n",
"You should show sponsors [2, 5, 6, 9] with probability 0.0144\n",
"You should show sponsors [2, 5, 7, 8] with probability 0.0001\n",
"You should show sponsors [2, 5, 7, 9] with probability 0.0144\n",
"You should show sponsors [2, 5, 8, 9] with probability 0.0055\n",
"You should show sponsors [2, 6, 7, 8] with probability 0.0001\n",
"You should show sponsors [2, 6, 7, 9] with probability 0.0144\n",
"You should show sponsors [2, 6, 8, 9] with probability 0.0055\n",
"You should show sponsors [2, 7, 8, 9] with probability 0.0055\n",
"You should show sponsors [3, 4, 5, 6] with probability 0.0005\n",
"You should show sponsors [3, 4, 5, 7] with probability 0.0005\n",
"You should show sponsors [3, 4, 5, 8] with probability 0.0001\n",
"You should show sponsors [3, 4, 5, 9] with probability 0.0144\n",
"You should show sponsors [3, 4, 6, 7] with probability 0.0005\n",
"You should show sponsors [3, 4, 6, 8] with probability 0.0001\n",
"You should show sponsors [3, 4, 6, 9] with probability 0.0144\n",
"You should show sponsors [3, 4, 7, 8] with probability 0.0001\n",
"You should show sponsors [3, 4, 7, 9] with probability 0.0144\n",
"You should show sponsors [3, 4, 8, 9] with probability 0.0055\n",
"You should show sponsors [3, 5, 6, 7] with probability 0.0005\n",
"You should show sponsors [3, 5, 6, 8] with probability 0.0001\n",
"You should show sponsors [3, 5, 6, 9] with probability 0.0144\n",
"You should show sponsors [3, 5, 7, 8] with probability 0.0001\n",
"You should show sponsors [3, 5, 7, 9] with probability 0.0144\n",
"You should show sponsors [3, 5, 8, 9] with probability 0.0055\n",
"You should show sponsors [3, 6, 7, 8] with probability 0.0001\n",
"You should show sponsors [3, 6, 7, 9] with probability 0.0144\n",
"You should show sponsors [3, 6, 8, 9] with probability 0.0055\n",
"You should show sponsors [3, 7, 8, 9] with probability 0.0055\n",
"You should show sponsors [4, 5, 6, 7] with probability 0.0005\n",
"You should show sponsors [4, 5, 6, 8] with probability 0.0001\n",
"You should show sponsors [4, 5, 6, 9] with probability 0.0144\n",
"You should show sponsors [4, 5, 7, 8] with probability 0.0001\n",
"You should show sponsors [4, 5, 7, 9] with probability 0.0144\n",
"You should show sponsors [4, 5, 8, 9] with probability 0.0055\n",
"You should show sponsors [4, 6, 7, 8] with probability 0.0001\n",
"You should show sponsors [4, 6, 7, 9] with probability 0.0144\n",
"You should show sponsors [4, 6, 8, 9] with probability 0.0055\n",
"You should show sponsors [4, 7, 8, 9] with probability 0.0055\n",
"You should show sponsors [5, 6, 7, 8] with probability 0.0001\n",
"You should show sponsors [5, 6, 7, 9] with probability 0.0144\n",
"You should show sponsors [5, 6, 8, 9] with probability 0.0055\n",
"You should show sponsors [5, 7, 8, 9] with probability 0.0055\n",
"You should show sponsors [6, 7, 8, 9] with probability 0.0055\n",
"Probability of each sponsor showing up: [0.35998986 0.3599897 0.35998975 0.3599897 0.35998975 0.35998962\n",
" 0.35998971 0.35998976 0.16010461 0.95997756]\n",
"error (actual - committed) [0.05998986 0.0599897 0.05998975 0.0599897 0.05998975 0.05998962\n",
" 0.05998971 0.05998976 0.06010461 0.05997756]\n",
"Sanity check: total probability: 1.0000000000000004\n"
]
}
],
"source": [
"print_solution([0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.3, 0.1, 0.9], 4)"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"There are lots of interesting variants to this problem – what if we don't want ads to always show up next to each other? What if the fairness metric is different?\n",
"\n",
"And, of course, in the spirit of two's complement, this needs testing – but that's all I have time for this evening! Thanks for a fun podcast as always."
]
}
],
"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.10.4"
},
"orig_nbformat": 4
},
"nbformat": 4,
"nbformat_minor": 2
}
@mattgodbolt
Copy link

Love it!! Thanks so much :) cc @benrady :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment