\n",
"\n",
"# The Stable Matching Problem\n",
"\n",
"The **[stable matching problem](https://en.wikipedia.org/wiki/Stable_marriage_problem#Algorithmic_solution)** involves two equally-sized disjoint sets of actors that want to pair off in a way that maximizes happiness. It could be a set of women and a set of men that want to pair off in heterosexual marriage; or a a set of job-seekers and a set of employers. Every year, there is a large-scale application of this problem in which:\n",
"- Graduating medical students state which hospitals they would prefer to be residents at.\n",
"- Hospitals in turn state which students they prefer. \n",
"- An algorithm finds a stable matching.\n",
"\n",
"Each actor has **preferences** for who they would like to be matched with. A matching is **stable** if it is **not** the case that there is an actor from one side and an actor from the other side who both have a higher preference for each other than they have for who they are currently matched with. \n",
"\n",
"In the default way of stating the problem, preferences are expressed as an **ordering**: each actor rates the possible matches on the other side from most preferred to least preferred. But in this notebook we will allow each actor to say more: to express their preference for each possible match as a **utility**: a number between 0 and 1. For example actor $A$ on one side could say that they would like to be paired with actor β on the other side with utility 0.9 (meaning a very desireable match) and with actor γ on the other side with utility 0.1 (meaning an undesireable match). The matching algorithm we present actually pays attention only to the ordering of preferences, but we will use the utilities to analyze how well each side does, on average.\n",
"\n",
"\n",
"\n",
"# Gale-Shapley Matching Algorithm\n",
"\n",
"The **[Gale-Shapley Stable Matching Algorithm](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm)** (*Note: David Gale was my father's [PhD advisor](https://www.genealogy.math.ndsu.nodak.edu/id.php?id=4381).*) works as follows: one side is chosen to be the **proposers** and the other side the **acceptors**. Until everyone has been matched the algorithm repeats the following steps:\n",
"- An unmatched proposer, $p$, proposes a match to the highest-ranked acceptor, $a$, that $p$ has not yet proposed to.\n",
"- If $a$ is unmatched, then $a$ tentatively accepts the proposal to be a match.\n",
"- If $a$ is matched, but prefers $p$ to their previous match, then $a$ breaks the previous match and tentatively accepts $p$.\n",
"- If $a$ is matched and prefers their previous match to $p$, then $a$ rejects the proposal.\n",
"\n",
"I will define the function `stable_matching(P, A)`, which is passed two preference arrays: $N \\times N$ arrays of utility values such that `P[p][a]` is the utility that proposer `p` has for being matched with `a`, and `A[a][p]` is the utility that acceptor `a` has for being matched with `p`. The function returns a set of matches, `{(p, a), ...}`. To implement the algorithm sketched above, we keep track of the following variables:\n",
"- `ids`: If there are $N$ actors on each side, we number them $0$ to $N-1$; `ids` is the collection of these numbers.\n",
"- `unmatched`: the set of proposers that have not yet been matched to any acceptor.\n",
"- `matched`: A mapping from acceptors to their matched proposers: `matched[a] = p`.\n",
"- `proposals`: Keeps track of who each proposer should propose to next. `proposals[p]` is a list of acceptors sorted by increasing utility, which means that `proposals[p].pop()` returns (and removes) the best acceptor for $p$ to propose to next. "
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"from statistics import mean, stdev\n",
"from typing import *\n",
"import random\n",
"\n",
"# Types\n",
"ID = int # ID number for an actor\n",
"Utility = float # Real number form 0 to 1 indicating degree of preference\n",
"Match = Tuple[ID, ID] # A pair of actors who are matched\n",
"PrefArray = List[List[Utility]] # Preference of each actor on a side for each actor on other side\n",
"\n",
"def stable_matching(P: PrefArray, A: PrefArray) -> Set[Match]:\n",
" \"\"\"Compute a stable match, a set of (p, a) pairs.\n",
" P and A are square preference arrays: P[p][a] is how much p likes a;\n",
" A[a][p] is how much a likes p. Stable means there is no (p, a)\n",
" such that both prefer each other over the partner they are matched with.\"\"\"\n",
" ids = range(len(P)) # ID numbers of all actors on either side\n",
" unmatched = set(ids) # Members of P that are not yet matched to anyone\n",
" matched = {} # {a: p} mapping of who acceptors are matched with\n",
" proposals = [sorted(ids, key=lambda a: P[p][a]) \n",
" for p in ids] # proposals[p] is an ordered list of who p should propose to\n",
" while unmatched:\n",
" p = unmatched.pop() # p is an arbitrary unmatched Proposer\n",
" a = proposals[p].pop() # a is p's most preferred remaining acceptor\n",
" if a not in matched: # first proposal to a; a tentatively accepts\n",
" matched[a] = p\n",
" elif A[a][p] > A[a][matched[a]]: # a breaks previous engagement and accepts\n",
" unmatched.add(matched[a])\n",
" matched[a] = p\n",
" else:\n",
" unmatched.add(p) # proposal declined; p remains unmatched\n",
" return {(p, a) for (a, p) in matched.items()}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The algorithm has the following properties:\n",
"- The algorithm will always terminate.\n",
"- The output of the algorithm will always be a stable matching.\n",
"- Out of all possible stable matchings, it will produce the one that is optimal for proposers: each proposer gets the best possible match they could get. That's true because the proposers propose in order of preference, so the acceptor that they most prefer who also prefers them will accept their proposal.\n",
"- The acceptors have no such luck; they might not get their best possible match, because a proposer who is a better match for them might not ever propose to them.\n",
"\n",
"What I want to get a handle on is: *how bad is this for the acceptors?* What's the gap in expected utility between the proposers and the acceptors?\n",
"\n",
"# Preference Arrays\n",
"\n",
"Let's define some preference arrays. `I` is the identity matrix: it says that every proposer number $i$ likes acceptor $i$ best, and dislikes the others equally. "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"I = [[1, 0, 0, 0, 0],\n",
" [0, 1, 0, 0, 0],\n",
" [0, 0, 1, 0, 0],\n",
" [0, 0, 0, 1, 0],\n",
" [0, 0, 0, 0, 1]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If both sides have this same preference array, it should result in a stable matching of (*i*, *i*) pairs:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)}"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"stable_matching(I, I)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can measure the average utility for both sides:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def mean_utilities(P, A):\n",
" \"\"\"The mean utility over all members of P, and the mean utility over all members of A,\n",
" for the matching given by stable_matching(P, A).\"\"\"\n",
" matching = stable_matching(P, A)\n",
" return (mean(P[p][a] for (p, a) in matching),\n",
" mean(A[a][p] for (p, a) in matching))"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1, 1)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean_utilities(I, I)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Perfect! Both sides achieve the maximum utility, 1.\n",
"\n",
"Next, preference array `X` is almost the same as the identity matrix, except that proposer 3 prefers 4, not 3, and proposer 4 prefers 3, not 4."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"X = [[1, 0, 0, 0, 0],\n",
" [0, 1, 0, 0, 0],\n",
" [0, 0, 1, 0, 0],\n",
" [0, 0, 0, 0, 1],\n",
" [0, 0, 0, 1, 0]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that the way that 3 and 4 get matched depends on which side is the proposer:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)}"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"stable_matching(I, X)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0), (1, 1), (2, 2), (3, 4), (4, 3)}"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"stable_matching(X, I)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The proposers always do better (or no worse than) the acceptors in mean utility:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1, 0.6)"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean_utilities(I, X)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1, 0.6)"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean_utilities(X, I)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Similar results hold when we use preference arrays that have utilities that are spread out between 0 and 1; it is still better to be the proposing side:"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"A = [[.9, .4, .3, .2, .1],\n",
" [.1, .9, .4, .3, .2],\n",
" [.2, .1, .9, .4, .3],\n",
" [.3, .2, .1, .9, .4],\n",
" [.4, .3, .2, .1, .9]]\n",
"\n",
"B = [[.9, .4, .3, .2, .1],\n",
" [.1, .9, .4, .3, .2],\n",
" [.2, .1, .9, .4, .3],\n",
" [.1, .2, .3, .4, .9],\n",
" [.9, .4, .3, .2, .1]]"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)}"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"stable_matching(A, B)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(0.9, 0.64)"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean_utilities(A, B)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0), (1, 1), (2, 2), (3, 4), (4, 3)}"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"stable_matching(B, A)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(0.76, 0.64)"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean_utilities(B, A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Preferences with Common and Private Values\n",
"\n",
"If the Gale-Shapley algorithm is used in high-stakes applications like matching medical residents to hospitals, does it make a big difference which side is the proposers? In the toy examples above, it does make a difference; in some cases the acceptors got only 60% of their possible utility, while the proposers got up to 100%. \n",
"\n",
"I will address the question by examining some randomized preference arrays and getting a feeling for how they perform. But I don't want them to be completely random; I want them to reflect, in a very abstract way, some properties of the real world:\n",
"- Some choices have intrinsic properties that make them widely popular (or unpopular). For example, Massachusetts General Hospital is considered an excellent choice by many aspiring residents. The amount of utility that is commonly agreed upon is called the **common value** of a choice.\n",
"- Some choices have idiosyncratic properties that appeal only to specific actors. For example, you might really want to be a resident at your hometown hospital, even if it is not highly-regarded by others. This is the **private value** of a choice.\n",
"- In real world situations there is usually a mix of common and private value.\n",
"\n",
"The function call `preferences(N, 0.75)`, for example, creates an NxN array of preferences, where each preference is 75% common value and 25% individual value. I implement individual value as being proportional to the ID number (`a` in the code); that is equivalent to assuming that the hospitals (say) are sorted in increasing order of quality by ID number."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [],
"source": [
"def preferences(N=25, c=0.75):\n",
" \"\"\"Create an NxN preference array, weighted: c × common + (1 - c) × random.\"\"\"\n",
" return [[round(c * (a + 0.5) / N + (1 - c) * random.uniform(0, 1), 3)\n",
" for a in range(N)] \n",
" for p in range(N)]\n",
"\n",
"random.seed(99) # For reproducability"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Below is a 7x7 preference array that is half common, half private. You can see as you go across a row that the utilities tend to increase, but not always monotonically:"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0.238, 0.207, 0.268, 0.374, 0.701, 0.518, 0.656],\n",
" [0.378, 0.376, 0.648, 0.495, 0.532, 0.699, 0.573],\n",
" [0.487, 0.294, 0.373, 0.591, 0.398, 0.723, 0.889],\n",
" [0.205, 0.581, 0.443, 0.637, 0.556, 0.594, 0.599],\n",
" [0.04, 0.209, 0.673, 0.517, 0.552, 0.843, 0.767],\n",
" [0.524, 0.286, 0.286, 0.71, 0.402, 0.789, 0.762],\n",
" [0.527, 0.579, 0.509, 0.269, 0.333, 0.63, 0.874]]"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"preferences(7, 0.5)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here's a preference array with no common value; the utilities are completely random, uncorrelated to their position:"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0.081, 0.425, 0.086, 0.31, 0.006, 0.33, 0.523],\n",
" [0.201, 0.787, 0.055, 0.211, 0.258, 0.404, 0.764],\n",
" [0.354, 0.695, 0.922, 0.131, 0.864, 0.6, 0.747],\n",
" [0.608, 0.408, 0.096, 0.144, 0.174, 0.178, 0.146],\n",
" [0.208, 0.561, 0.771, 0.798, 0.846, 0.117, 0.822],\n",
" [0.186, 0.072, 0.288, 0.586, 0.048, 0.216, 0.399],\n",
" [0.822, 0.399, 0.414, 0.371, 0.093, 0.88, 0.923]]"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"preferences(7, 0.0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"And here's a preference array with 100% common value: every row is identical, and the utilities monotonically increase across the row:"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0.1, 0.3, 0.5, 0.7, 0.9],\n",
" [0.1, 0.3, 0.5, 0.7, 0.9],\n",
" [0.1, 0.3, 0.5, 0.7, 0.9],\n",
" [0.1, 0.3, 0.5, 0.7, 0.9],\n",
" [0.1, 0.3, 0.5, 0.7, 0.9]]"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"preferences(5, 1.0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The `preferences` function has been designed so that the average utility value is close to 0.5, for all values of `c`:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.4996304"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean(map(mean, preferences(100, c=0.8)))"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.5004173"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mean(map(mean, preferences(100, c=0.2)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now for one more helpful function: `examples` returns a list of the form `[(P, A), ...]` where `P` and `A` are preference arrays."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"def examples(N=25, c=0.5, repeat=10000):\n",
" \"\"\"A list of pairs of preference arrays, (P, A), of length `repeat`.\"\"\"\n",
" return [(preferences(N, c), preferences(N, c)) for _ in range(repeat)]"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[([[0.181, 0.736, 0.7], [0.207, 0.734, 0.599], [0.572, 0.745, 0.715]],\n",
" [[0.537, 0.72, 0.784], [0.281, 0.256, 0.582], [0.452, 0.657, 0.554]]),\n",
" ([[0.464, 0.575, 0.662], [0.23, 0.416, 0.821], [0.342, 0.381, 0.658]],\n",
" [[0.471, 0.517, 0.603], [0.201, 0.365, 0.482], [0.102, 0.347, 0.479]])]"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"examples(N=3, repeat=2)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Histograms of Acceptor/Proposer Utility\n",
"\n",
"Now we're ready to answer the original question: how much worse is it to be an acceptor rather than a proposer? The function `show` displays two overlapping histograms of mean utilities: one for acceptors and one for proposers. "
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [],
"source": [
"def show(N=25, c=0.5, repeat=10000, bins=50):\n",
" \"\"\"Show two histograms of mean utility values over examples, for proposers and acceptors.\"\"\"\n",
" pr, ac = transpose(mean_utilities(P, A) for (P, A) in examples(N, c, repeat))\n",
" plt.hist(pr, bins=bins, alpha=0.5)\n",
" plt.hist(ac, bins=bins, alpha=0.5);\n",
" print(f'''{repeat:,d} examples with N = {N} actors, common value ratio c = {c}\n",
" Acceptors: {mean(ac):.3f} ± {stdev(ac):.3f}\n",
" Proposers: {mean(pr):.3f} ± {stdev(pr):.3f}''')\n",
" \n",
"def transpose(matrix): return list(zip(*matrix))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We'll start with preferences that are completely private; no common value:"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10,000 examples with N = 25 actors, common value ratio c = 0.0\n",
" Acceptors: 0.729 ± 0.063\n",
" Proposers: 0.871 ± 0.035\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAASzUlEQVR4nO3df6zd933X8eerbtP9Xp3FNq7tzCk4XZ1JzeDKa1UB6UyIGWzuEJFcBLOqIAMKUxcQxO4fTAhZeEK0VGIRsroxI9ZGZluJqVg3z1sooLSus6Y/nNTNXcyci018m6qUDpRh980f9+vu2D7X53t9z7k/Pvf5kK6+5/s53+8974+v/Lqf+znf7+ekqpAkteV1y12AJGn8DHdJapDhLkkNMtwlqUGGuyQ16PXLXQDAXXfdVdu3b1/uMiRpVXn22We/WlUbhj23IsJ9+/btnDlzZrnLkKRVJckfzPec0zKS1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktSgFXGHqiQtxodOfuW6/ccevHeZKlk5HLlLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktSgkeGe5K1Jnhv4+kaSn01yZ5KTSV7stusHzjmUZDrJuSQPTbYLkqQbjbyJqarOAfcDJFkH/A/g48BB4FRVHUlysNt/PMlOYB9wH/Bm4LeT3FtVVyfTBUm63uBNTWv1hqaF3qG6G/j9qvqDJHuBB7r2Y8DTwOPAXuDJqnoNOJ9kGtgFPDOWiiVpAdbq3asLnXPfB3yse7ypqi4BdNuNXfsW4OWBc2a6tuskOZDkTJIzs7OzCyxDknQrvcM9yR3ATwL/ftShQ9rqpoaqo1U1VVVTGzZs6FuGJKmHhUzL/CXg96rqlW7/lSSbq+pSks3A5a59Btg2cN5W4OLiS5WkOTdOtehmC5mWeS9/PCUDcALY3z3eDzw10L4vyRuT3APsAE4vtlBJUn+9Ru5Jvgt4EPjbA81HgONJHgEuAA8DVNXZJMeB54ErwKNeKSNJS6tXuFfV/wF+4Ia2V5m7embY8YeBw4uuTpJ0W7xDVZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAYt5GP2JGnVG/yIvscevHcZK5ksR+6S1CDDXZIaZLhLUoN6hXuSNyX51SRfTvJCkncmuTPJySQvdtv1A8cfSjKd5FyShyZXviRpmL4j9w8Dn6yqHwLeDrwAHAROVdUO4FS3T5KdwD7gPmAP8ESSdeMuXJI0v5HhnuT7gD8H/CJAVf1RVX0d2Asc6w47Bryne7wXeLKqXquq88A0sGu8ZUuSbqXPyP0twCzwb5J8LslHknw3sKmqLgF0243d8VuAlwfOn+narpPkQJIzSc7Mzs4uqhOSpOv1uc799cCfBn6mqj6T5MN0UzDzyJC2uqmh6ihwFGBqauqm5yWtbYPXo0Pb16RPQp+R+wwwU1Wf6fZ/lbmwfyXJZoBue3ng+G0D528FLo6nXElSHyNH7lX1P5O8nOStVXUO2A08333tB45026e6U04AH03yQeDNwA7g9CSKl7R23DiS1631XX7gZ4BfSXIH8BLwPuZG/ceTPAJcAB4GqKqzSY4zF/5XgEer6urYK5ckzatXuFfVc8DUkKd2z3P8YeDw7ZclSVoM71CVpAYZ7pLUIMNdkhpkuEtSg/ywDul2/O4/u7nt3YdW/2utMS3fKOXIXZIaZLhLUoOclpEmbdi0yjBOtXgX6hgZ7tJK0feXgNSD0zKS1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXI69ylcVnK69Tney1vhFLHkbskNciRu6Rl43IDk9Nr5J7kvyf5YpLnkpzp2u5McjLJi912/cDxh5JMJzmX5KFJFS9JGm4h0zLvrqr7q+raB2UfBE5V1Q7gVLdPkp3APuA+YA/wRJJ1Y6xZkjTCYqZl9gIPdI+PAU8Dj3ftT1bVa8D5JNPALuCZRbyWtDxczEurVN+RewG/leTZJAe6tk1VdQmg227s2rcALw+cO9O1XSfJgSRnkpyZnZ29veolSUP1Hbm/q6ouJtkInEzy5VscmyFtdVND1VHgKMDU1NRNz0uSbl+vkXtVXey2l4GPMzfN8kqSzQDd9nJ3+AywbeD0rcDFcRUsSRptZLgn+e4k33vtMfAXgS8BJ4D93WH7gae6xyeAfUnemOQeYAdwetyFS5Lm12daZhPw8STXjv9oVX0yyWeB40keAS4ADwNU1dkkx4HngSvAo1V1dSLVS5KGGhnuVfUS8PYh7a8Cu+c55zBweNHVSZJui3eoSlLnxjtmH3vw3mWqZPFcW0aSGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yEshpZYMW8XSj95bkxy5S1KDDHdJapDhLkkNcs5da5Nz02qcI3dJapDhLkkNclpG0pK5cdVFTY4jd0lqkOEuSQ1yWka6ZtgVNNIqZbhLrZvvl5aXfjat97RMknVJPpfkE93+nUlOJnmx264fOPZQkukk55I8NInCJUnzW8ic+/uBFwb2DwKnqmoHcKrbJ8lOYB9wH7AHeCLJuvGUK0nqo1e4J9kK/GXgIwPNe4Fj3eNjwHsG2p+sqteq6jwwDewaS7WSpF76jtz/JfCPgG8NtG2qqksA3XZj174FeHnguJmu7TpJDiQ5k+TM7OzsQuuWJN3CyDdUk/wV4HJVPZvkgR7fM0Pa6qaGqqPAUYCpqambnpek5TZ409VjD967jJUsXJ+rZd4F/GSSHwe+A/i+JP8OeCXJ5qq6lGQzcLk7fgbYNnD+VuDiOIuWevPyRq1RI6dlqupQVW2tqu3MvVH6O1X1N4ATwP7usP3AU93jE8C+JG9Mcg+wAzg99solSfNazHXuR4DjSR4BLgAPA1TV2STHgeeBK8CjVXV10ZVKknpbULhX1dPA093jV4Hd8xx3GDi8yNokTZJr2jfNtWUkqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSg1zPXdJE+bmpy8ORuyQ1yHCXpAYZ7pLUIOfc1Q5XgJS+zZG7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUEjwz3JdyQ5neTzSc4m+Sdd+51JTiZ5sduuHzjnUJLpJOeSPDTJDkiSbtZn5P4a8GNV9XbgfmBPkncAB4FTVbUDONXtk2QnsA+4D9gDPJFk3QRqlyTNY2S415xvdrtv6L4K2Asc69qPAe/pHu8Fnqyq16rqPDAN7Bpn0ZKkW+u1tkw38n4W+FPAL1TVZ5JsqqpLAFV1KcnG7vAtwKcHTp/p2m78ngeAAwB333337fdA0vgMW5/n3YeWvg4tWq83VKvqalXdD2wFdiX54VscnmHfYsj3PFpVU1U1tWHDhl7FSpL6WdDVMlX1deBp5ubSX0myGaDbXu4OmwG2DZy2Fbi42EIlSf2NnJZJsgH4f1X19STfCfwF4OeBE8B+4Ei3fao75QTw0SQfBN4M7ABOT6B2rVUu7SuN1GfOfTNwrJt3fx1wvKo+keQZ4HiSR4ALwMMAVXU2yXHgeeAK8GhVXZ1M+ZKkYUaGe1V9AfiRIe2vArvnOecwcHjR1UmSboufxCRprD508ivLXYIw3CWNMt97HF4iuaK5towkNchwl6QGOS0jST3c+F7CYw/eu0yV9OPIXZIa5Mhd0qJ4dczK5MhdkhpkuEtSgwx3SWqQ4S5JDfINVa1srgAp3RZH7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNWhkuCfZluR3k7yQ5GyS93ftdyY5meTFbrt+4JxDSaaTnEvy0CQ7IEm6WZ+R+xXgH1TV24B3AI8m2QkcBE5V1Q7gVLdP99w+4D5gD/BEknWTKF6SNNzIO1Sr6hJwqXv8v5O8AGwB9gIPdIcdA54GHu/an6yq14DzSaaBXcAz4y5eDfFOVGmsFjTnnmQ78CPAZ4BNXfBf+wWwsTtsC/DywGkzXduN3+tAkjNJzszOzt5G6ZKk+fReWybJ9wC/BvxsVX0jybyHDmmrmxqqjgJHAaampm56XtLK9cxLr/LpK35Ix0rWa+Se5A3MBfuvVNWvd82vJNncPb8ZuNy1zwDbBk7fClwcT7mSpD76XC0T4BeBF6rqgwNPnQD2d4/3A08NtO9L8sYk9wA7gNPjK1mSNEqfaZl3AX8T+GKS57q2DwBHgONJHgEuAA8DVNXZJMeB55m70ubRqro67sIlLa93XDh6U9un7z6wDJVomD5Xy/xXhs+jA+ye55zDwOFF1CVJWgTvUJWkBhnuktQgw12SGmS4S1KD/IBsLT2XGpAmznCXNDbDLo+ENi+R/NDJP75D97EH713GSoZzWkaSGuTIXZPlFEwTnnnp1eUuQQvkyF2SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAZ5nbvGw+vZpRXFcJc0cX5q09Iz3CUN5V2pq5tz7pLUoJHhnuSXklxO8qWBtjuTnEzyYrddP/DcoSTTSc4leWhShUuS5tdn5P7LwJ4b2g4Cp6pqB3Cq2yfJTmAfcF93zhNJ1o2tWkkT88xLr173pdVtZLhX1aeAr93QvBc41j0+BrxnoP3Jqnqtqs4D08Cu8ZQqSerrdufcN1XVJYBuu7Fr3wK8PHDcTNd2kyQHkpxJcmZ2dvY2y5AkDTPuN1QzpK2GHVhVR6tqqqqmNmzYMOYyJGltu91LIV9JsrmqLiXZDFzu2meAbQPHbQUuLqZArUDesCSteLcb7ieA/cCRbvvUQPtHk3wQeDOwAzi92CIlaSUb/DxVWBmfqToy3JN8DHgAuCvJDPBzzIX68SSPABeAhwGq6myS48DzwBXg0aq6OqHaJa1ia+nDtJfDyHCvqvfO89TueY4/DBxeTFGSJs/LHdvmHaqS1CDDXZIa5MJhmp9XxUirluEurSGrYZ7d5YHHw2kZSWqQ4S5JDTLcJalBhrskNcg3VNcar4BZU1bDG6iaDMNdksZsJaw147SMJDXIkbukFc9r3xfOcJdWuRvn1d/5lh9Ypkq0khjuLfPN0zXJN1EFzrlLUpMcuUurjCNz9WG4t8IpmKYZ6Foow13SquTH9N2a4b6SORpfUwZH517xosWaWLgn2QN8GFgHfKSqjkzqtVY9Q1w3cBrm9q3Ea+IH71hdqrtVJxLuSdYBvwA8CMwAn01yoqqen8TrrViGtgYY2FpKkxq57wKmq+olgCRPAnuByYR73xB996Gley01ayE3DRnoK8NKmp9fqnVnJhXuW4CXB/ZngB8dPCDJAeDav+w3k5ybUC0DPjCJb3oX8NVJfOMVyv62bY31918se3///uJO/8H5nphUuGdIW123U3UUGP7rdBVJcqaqppa7jqVif9tmf9sxqTtUZ4BtA/tbgYsTei1J0g0mFe6fBXYkuSfJHcA+4MSEXkuSdIOJTMtU1ZUkfw/4TeYuhfylqjo7iddaAVb91NIC2d+22d9GpKpGHyVJWlVcFVKSGmS4S1KDDPcekuxJci7JdJKDQ55/IMn/SvJc9/WPl6POcRnV3+6YB7q+nk3yn5e6xnHq8fP9hwM/2y8luZrkzuWodRx69Pf7k/zHJJ/vfr7vW446x6VHf9cn+XiSLyQ5neSHl6POsasqv27xxdwbwr8PvAW4A/g8sPOGYx4APrHctS5hf9/E3N3Gd3f7G5e77kn294bjfwL4neWue8I/3w8AP9893gB8DbhjuWufYH//OfBz3eMfAk4td93j+HLkPtq3l1Koqj8Cri2l0Ko+/f3rwK9X1QWAqrq8xDWO00J/vu8FPrYklU1Gn/4W8L1JAnwPc+F+ZWnLHJs+/d0JnAKoqi8D25NsWtoyx89wH23YUgpbhhz3zu7P2N9Ict/SlDYRffp7L7A+ydNJnk3y00tW3fj1/fmS5LuAPcCvLUFdk9Knv/8KeBtzNx5+EXh/VX1racobuz79/TzwVwGS7GLulv6tS1LdBLme+2gjl1IAfg/4war6ZpIfB/4DsGPShU1In/6+HvgzwG7gO4Fnkny6qr5y05krX5/+XvMTwH+rqq9NsJ5J69Pfh4DngB8D/iRwMsl/qapvTLi2SejT3yPAh5M8x9wvs8+xev9S+TZH7qONXEqhqr5RVd/sHv8n4A1J7lq6Eseqz9IRM8Anq+oPq+qrwKeAty9RfeO2kKUy9rG6p2SgX3/fx9y0W1XVNHCeubno1ajv/9/3VdX9wE8z9z7D+SWrcEIM99FGLqWQ5E9085PX/qx7HbBa13rts3TEU8CfTfL6bqriR4EXlrjOcem1VEaS7wf+PHN9X8369PcCc3+V0c09vxV4aUmrHJ8+/3/f1D0H8LeAT63Sv1Ku47TMCDXPUgpJ/k73/L8G/hrwd5NcAf4vsK+6t95Xmz79raoXknwS+ALwLeY+aetLy1f17ev58wX4KeC3quoPl6nUsejZ338K/HKSLzI3rfF49xfaqtOzv28D/m2Sq8xdBfbIshU8Ri4/IEkNclpGkhpkuEtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QG/X9yg2EHRH+LDwAAAABJRU5ErkJggg==\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"show(c=0.0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The acceptors (the orange histogram) have a mean utility of 0.730 while the proposers (blue histogram) do much better with a mean of 0.870. Both sides do much better than the 0.5 average utility that they would average if we just used a random (non-stable) matching. \n",
"\n",
"It is clear that proposers do much better than acceptors. That suggests that the `stable_matching` algorithm is very unfair. But before drawing that conclusion, let's consider preferences with a 50/50 mix of private/common value. We'll do that for two different population sizes, 25 and 50:"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10,000 examples with N = 25 actors, common value ratio c = 0.5\n",
" Acceptors: 0.621 ± 0.021\n",
" Proposers: 0.638 ± 0.019\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD4CAYAAADvsV2wAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAS+klEQVR4nO3dbYwd133f8e/P9ENq58FitFIYPpRyQTmRDMh2CEaui8CuqopxHqgXVcEUSZlABRFAbm0hSUMmaJsWIKymqJ2grYKyiVsmscOyiV0RRuuEZaQGbS3LlCs/ULIsWnKoLRmSltPayQsZYv59sUPrirq7e3f33t25e74fYHFnzpwz97/D4f+ePTP3TKoKSdL694q1DkCStDpM+JLUCBO+JDXChC9JjTDhS1IjXrnWAQBce+21tX379rUOQ5KmyqOPPvqVqpoZtX4vEv727ds5derUWochSVMlyR8vpb5DOpLUCBO+JDXChC9JjTDhS1IjTPiS1AgTviQ1woQvSY0w4UtSI0z4ktSIXnzTVtL4feDEF19Wdu/tN65BJOoLe/iS1AgTviQ1woQvSY1wDF/SUMOuAYDXAaaZCV+acvMl5qXUNYm3wSEdSWqECV+SGuGQjrSWHnzf8PJ3HlzdONQEe/iS1AgTviQ1wiEdSUu600fTyx6+JDXChC9JjTDhS1IjTPiS1IiREn6S1yf53SRfSPJEkrcl2ZjkRJKnutdrBuofTHImyZNJ7phc+JKkUY3aw/9V4ONV9T3ALcATwAHgZFXtAE526yS5CdgL3AzsBu5PsmHcgUuSlmbR2zKTfDvwA8BPAlTVN4BvJNkDvKOrdgR4CPh5YA9wtKqeB55JcgbYBXxizLFLzfH2Sa3EKPfhvwG4BPz7JLcAjwLvAa6vqvMAVXU+yXVd/c3AwwPtZ7uyl0iyH9gPsG3btmX/AlLvOF2CemqUIZ1XAm8Ffq2q3gL8Od3wzTwypKxeVlB1uKp2VtXOmZmZkYKVJC3fKAl/Fpitqk9267/L3AfAhSSbALrXiwP1tw603wKcG0+4kqTlWjThV9WfAM8meWNXdBvwOHAc2NeV7QMe6JaPA3uTvCbJDcAO4JGxRi1JWrJR59L5+8CHkrwaeBr4KeY+LI4luRs4C9wFUFWnkxxj7kPhBeCeqro89sglSUsyUsKvqseAnUM23TZP/UPAoeWHJa1D813MlVaJ37SVpEaY8CWpEc6HL/XQJ37jZ4dv2LZ/dQPRumIPX5IaYQ9fmiK3nj08tPxhe/4agT18SWqEPXxpubzNUlPGHr4kNcIevqQlmW+K5ntvv3GVI9FS2cOXpEaY8CWpESZ8SWqECV+SGmHCl6RGmPAlqRHeliktxi9YaZ2why9JjbCHL11hT17rnD18SWqECV+SGmHCl6RGmPAlqREjJfwkX07yuSSPJTnVlW1MciLJU93rNQP1DyY5k+TJJHdMKnhJ0uiW0sN/Z1W9uap2dusHgJNVtQM42a2T5CZgL3AzsBu4P8mGMcYsSVqGlQzp7AGOdMtHgDsHyo9W1fNV9QxwBti1gveRJI3BqPfhF/AHSQr4t1V1GLi+qs4DVNX5JNd1dTcDDw+0ne3KJE2IDzfXKEZN+G+vqnNdUj+R5AsL1M2QsnpZpWQ/sB9g27ZtI4YhSVqukRJ+VZ3rXi8m+ShzQzQXkmzqevebgItd9Vlg60DzLcC5Ifs8DBwG2Llz58s+EKQWfOLp59Y6BDVk0YSf5HXAK6rq693y3wT+GXAc2Afc170+0DU5Dnw4yfuB7wZ2AI9MIHZJPTLsWbc+57ZfRunhXw98NMmV+h+uqo8n+RRwLMndwFngLoCqOp3kGPA48AJwT1Vdnkj0kqSRLZrwq+pp4JYh5c8Bt83T5hBwaMXRSZLGxm/aSlIjTPiS1Ajnw1d7nPdejbKHL0mNMOFLUiNM+JLUCBO+JDXChC9JjTDhS1IjTPiS1AgTviQ1wi9eSeuYD0bRIHv4ktQIE74kNcKEL0mNcAxfWiU+zlBrzR6+JDXChC9JjXBIR+uX895LL2EPX5IaYcKXpEaY8CWpEY7hSw1yyoU2jdzDT7Ihyf9O8rFufWOSE0me6l6vGah7MMmZJE8muWMSgUuSlmYpQzrvAZ4YWD8AnKyqHcDJbp0kNwF7gZuB3cD9STaMJ1xJ0nKNlPCTbAF+CPj1geI9wJFu+Qhw50D50ap6vqqeAc4Au8YSrSRp2Ubt4f8K8A+Bvxgou76qzgN0r9d15ZuBZwfqzXZlL5Fkf5JTSU5dunRpqXFLkpZo0YSf5IeBi1X16Ij7zJCyellB1eGq2llVO2dmZkbctSRpuUa5S+ftwI8meRfwLcC3J/lt4EKSTVV1Pskm4GJXfxbYOtB+C3BunEFLkpZu0R5+VR2sqi1VtZ25i7F/WFU/DhwH9nXV9gEPdMvHgb1JXpPkBmAH8MjYI5ckLclK7sO/DziW5G7gLHAXQFWdTnIMeBx4Abinqi6vOFJJ0oosKeFX1UPAQ93yc8Bt89Q7BBxaYWySpDHym7bSmPmgkxd94MQXh5bfe/uNqxyJwLl0JKkZJnxJaoQJX5IaYcKXpEaY8CWpESZ8SWqECV+SGmHCl6RGmPAlqREmfElqhAlfkhphwpekRjh5mqRvuvXs4ZeVPbxt/xpEokkw4Wv6Pfi+tY5AmgomfGkFnApZ08SEL2nVDZsn3znyJ8+LtpLUCBO+JDXChC9JjXAMX9PFO3KkZbOHL0mNWDThJ/mWJI8k+UyS00n+aVe+McmJJE91r9cMtDmY5EySJ5PcMclfQJI0mlF6+M8Df72qbgHeDOxOcitwADhZVTuAk906SW4C9gI3A7uB+5NsmEDskqQlWDTh15w/61Zf1f0UsAc40pUfAe7slvcAR6vq+ap6BjgD7Bpn0JKkpRtpDD/JhiSPAReBE1X1SeD6qjoP0L1e11XfDDw70Hy2K7t6n/uTnEpy6tKlSyv4FSRJoxgp4VfV5ap6M7AF2JXkTQtUz7BdDNnn4araWVU7Z2ZmRgpWkrR8S7pLp6r+L/AQc2PzF5JsAuheL3bVZoGtA822AOdWGqgkaWVGuUtnJsnru+W/BPwN4AvAcWBfV20f8EC3fBzYm+Q1SW4AdgCPjDluSdISjfLFq03Ake5Om1cAx6rqY0k+ARxLcjdwFrgLoKpOJzkGPA68ANxTVZcnE74kaVSLJvyq+izwliHlzwG3zdPmEHBoxdFJksbGqRUk9cKwKZPBaZPHyakVJKkR9vClEfhkK60HJnxJCxr2YHPw4ebTyCEdSWqECV+SGmHCl6RGmPAlqREmfElqhAlfkhphwpekRngfvqRl8f786WMPX5IaYQ9f/fTg+9Y6AmndsYcvSY2why8NcJI0rWf28CWpEfbwJfWaD0YZH3v4ktQIE74kNcKEL0mNMOFLUiMWTfhJtiZ5MMkTSU4neU9XvjHJiSRPda/XDLQ5mORMkieT3DHJX0CSNJpRevgvAD9TVd8L3Arck+Qm4ABwsqp2ACe7dbpte4Gbgd3A/Uk2TCJ4SdLoFk34VXW+qj7dLX8deALYDOwBjnTVjgB3dst7gKNV9XxVPQOcAXaNOW5J0hItaQw/yXbgLcAngeur6jzMfSgA13XVNgPPDjSb7cqu3tf+JKeSnLp06dIyQpckLcXICT/JtwK/B7y3qr62UNUhZfWygqrDVbWzqnbOzMyMGoYkaZlG+qZtklcxl+w/VFUf6YovJNlUVeeTbAIuduWzwNaB5luAc+MKWOuMs2JKq2aUu3QC/AbwRFW9f2DTcWBft7wPeGCgfG+S1yS5AdgBPDK+kCVJyzFKD//twE8An0vyWFf2C8B9wLEkdwNngbsAqup0kmPA48zd4XNPVV0ed+CSpKVZNOFX1f9g+Lg8wG3ztDkEHFpBXJKkMXO2TElTadgsms6guTCnVpCkRtjD1+ro4d04Pt1KrbGHL0mNsIcvaaxuPXt4aPnD2/avciS6mj18SWqECV+SGmHCl6RGmPAlqREmfElqhAlfkhrhbZla9/yClTTHHr4kNcKEL0mNMOFLUiNM+JLUCBO+JDXCu3QkrQonVVt79vAlqREmfElqhEM6Gq8ePtlK0hx7+JLUiEV7+Ek+CPwwcLGq3tSVbQT+I7Ad+DLwt6vqT7ttB4G7gcvAP6iq359I5NIQTqMgzW+UIZ3/APxr4DcHyg4AJ6vqviQHuvWfT3ITsBe4Gfhu4L8lubGqLo83bEnrhXfvrJ5Fh3Sq6o+Ar15VvAc40i0fAe4cKD9aVc9X1TPAGWDXeEKVJK3Eci/aXl9V5wGq6nyS67ryzcDDA/VmuzKtN16cVQ994MQXh5bfe/uNqxxJP437om2GlNXQisn+JKeSnLp06dKYw5AkXW25Cf9Ckk0A3evFrnwW2DpQbwtwbtgOqupwVe2sqp0zMzPLDEOSNKrlDukcB/YB93WvDwyUfzjJ+5m7aLsDeGSlQUpX824caelGuS3zd4B3ANcmmQX+CXOJ/liSu4GzwF0AVXU6yTHgceAF4B7v0JGkflg04VfVj82z6bZ56h8CDq0kKEnS+PlNW0lqhAlfkhphwpekRjhbpnrNu3Gk8bGHL0mNMOFLUiMc0tGLhs2P886Dqx+HNGbD5thpcX4dE74W5iRp0rrhkI4kNcKEL0mNMOFLUiMcw1dveM+9NFkmfEm9NN+zbofx+bejcUhHkhphD79F3mopNfn8WxO+JA1Yzx8EDulIUiPs4a9nDt2oEfNd4PVi7kvZw5ekRtjDXw+mrCfv/fbS2jDhS9II1sOMmyb8adLjnvx8vfa3veE7VzkS6UWO7b+UCV8T5fCN1B8TS/hJdgO/CmwAfr2q7pvUe02tHvfYpfVsXD3/abtnfyIJP8kG4N8AtwOzwKeSHK+qxyfxfloZe+HS5PXhw2FSPfxdwJmqehogyVFgDzCZhL+UR/PN16teoH5fxqdNzNJkLWXCtoV84EQ/rxGkqsa/0+RvAbur6u916z8BfH9VvXugzn7gylF5I/DkMt7qWuArKwx3tU1bzNMWL0xfzNMWL0xfzNMWL4wW81+uqplRdzipHn6GlL3kk6WqDgMr+jhNcqqqdq5kH6tt2mKetnhh+mKetnhh+mKetnhhMjFP6pu2s8DWgfUtwLkJvZckaQSTSvifAnYkuSHJq4G9wPEJvZckaQQTGdKpqheSvBv4feZuy/xgVZ2ewFuN5wrL6pq2mKctXpi+mKctXpi+mKctXphAzBO5aCtJ6h9ny5SkRpjwJakRvUr4SXYneTLJmSQHhmx/R5L/l+Sx7ucfd+VbkzyY5Ikkp5O8Z6DNLyX5PwNt3rXW8Xbbvpzkc135qYHyjUlOJHmqe71mXPGuJOYkbxwoeyzJ15K8t9u2Zsd4IObHun/7/75Y27U+xvPF3NfzeL54u/JensfzxdzX8zjJzw287+eTXE6ycaG2yzrGVdWLH+Yu7n4JeAPwauAzwE1X1XkH8LEhbTcBb+2Wvw344pW2wC8BP9uneLttXwauHVL+y8CBbvkA8M/7EvNV+/kT5r70sdbH+PXMfYN7W7d+3WJte3CM54u5r+fx0Hh7fh7PG3Mfz+Or6v8I8IeTOI/71MP/5nQMVfUN4Mp0DIuqqvNV9elu+evAE8DmiUU6Z9nxLmIPcKRbPgLcOYZ9XjGumG8DvlRVfzzG2IYZJd6/A3ykqs4CVNXFEdqu9TEeGnOPz+P5jvFCenmMr9Kn83jQjwG/M0LbJR/jPiX8zcCzA+uzDD/Z35bkM0n+a5Kbr96YZDvwFuCTA8XvTvLZJB8c45+WK423gD9I8mjmppm44vqqOg9zCQC4bkzxjiPmK/by4gl5xVod4xuBa5I81B3LvztC27U+xvPF/E09O48Xirev5/Gix5h+nccAJHktsBv4vRHaLvkY9ynhLzodA/Bp5v78ugX4V8B/fskOkm9l7kC9t6q+1hX/GvBXgDcD54F/2ZN4315VbwV+ELgnyQ+MKa6FjOMYvxr4UeA/DRSv5TF+JfB9wA8BdwD/KMmNI7adhJXEPLeD/p3HC8Xb1/N4sWPct/P4ih8B/mdVfXUZbRfVp4S/6HQMVfW1qvqzbvm/AK9Kci1Aklcx95/kQ1X1kYE2F6rqclX9BfDvmPsTac3jrapz3etF4KMDcV1Isqn7nTYBo/z5vCoxd34Q+HRVXRhos2bHuKvz8ar686r6CvBHwC2LtF3TY7xAzL08jxeKt6/n8UIxd/p2Hl9x9V8d4z2Px3lxYiU/zH0iPw3cwIsXJ26+qs538eKXxXYBZ5n7BAzwm8CvDNnvpoHle4GjPYj3dcC3deWvA/4Xc7OLAvwLXnoh5pf7cIwHth8FfqpHx/h7gZNd3dcCnwfetFDbHhzj+WLu63k8X7x9Po+HxtzX87ir9x3AV4HXjdJ2Ocd4LP8AY/yHfBdzdyZ8CfjFruyngZ/ult8NnO5+6YeBv9qV/zXm/sz5LPBY9/OubttvAZ/rth0f/Eddw3jf0JV9ptv+iwP7/M7uRH2qe93Yh2PcbXst8BzwHVftc82Ocbf+c8zdkfF55oZB5m3bh2M8X8x9PY8XiLe35/Ei50Vfz+OfZMiHzDjPY6dWkKRG9GkMX5I0QSZ8SWqECV+SGmHCl6RGmPAlqREmfElqhAlfkhrx/wFDVFmkms9TVgAAAABJRU5ErkJggg==\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"show(c=0.5, N=25)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10,000 examples with N = 50 actors, common value ratio c = 0.5\n",
" Acceptors: 0.647 ± 0.013\n",
" Proposers: 0.661 ± 0.012\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXgAAAD4CAYAAADmWv3KAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAASUElEQVR4nO3dbYyc11nG8f9F2qbvJCFOcG0Hp8IpTSqVllVIKapSQmnEm8OHIBe1GBRkIYUABUFtJAR8sBoJaBsJKmQFiqu+BBOKYlWobTAJb2qSOm2gcdKkJinOYhNvUwqFD6ns3nzYx+1kPbs7szOzs3v8/0mreebMeWbv47WvPT7zzJlUFZKk9nzbtAuQJE2GAS9JjTLgJalRBrwkNcqAl6RGPW/aBQBcfPHFtXXr1mmXIUnryoMPPvjlqtqw2ONrIuC3bt3K4cOHp12GJK0rSf59qcddopGkRhnwktQoA16SGmXAS1KjDHhJapQBL0mNMuAlqVEGvCQ1yoCXpEatiXeySs25591nt715z+rXoXOaM3hJatRAAZ/kgiR3JvlCkkeTvCHJRUnuTvLF7vbCnv57khxN8liSt06ufEnSYgadwd8GfKKqvgd4LfAosBs4VFXbgEPdfZJcCewArgKuB96f5LxxFy5JWtqya/BJXg68Cfg5gKr6OvD1JNuBa7tu+4F7gXcB24E7qupZ4MkkR4GrgU+PuXZpfem3Lg+uzWtiBpnBvxKYAz6Q5HNJbk/yEuDSqjoB0N1e0vXfBDzVc/5s1/YcSXYlOZzk8Nzc3EiDkCSdbZCraJ4HvB64paruT3Ib3XLMItKnrc5qqNoH7AOYmZk563FJk/feux8/q+2db7liCpVoEgaZwc8Cs1V1f3f/TuYD/+kkGwG625M9/bf0nL8ZOD6eciVJg1p2Bl9V/5nkqSSvqqrHgOuAR7qvncCt3e1d3SkHgY8keQ/wCmAb8MAkipembrF1dWkNGPSNTrcAH07yAuAJ4OeZn/0fSHITcAy4EaCqjiQ5wPwvgFPAzVV1euyVS5KWNFDAV9VDwEyfh65bpP9eYO/Ky5IkjcqtCqRzRL8XVNU2tyqQpEYZ8JLUKJdopAa5HCNwBi9JzTLgJalRLtFIC/lhHWqEAS+tc663azEGvDQItyTQOuQavCQ1yhm8tM64JKNBGfCSlrXwl4p7xq8PLtFIUqOcwUvTtsY+q9UloHY4g5ekRhnwktQoA16SGmXAS1KjDHhJapRX0UhrmFe0aBTO4CWpUQa8JDXKJRq1b429kUhaLc7gJalRzuClteqed3PNsWee03TfZbumVIzWo4ECPsmXgK8Bp4FTVTWT5CLgL4CtwJeAn66q/+r67wFu6vr/clV9cuyVS6PyQzzUuGFm8G+uqi/33N8NHKqqW5Ps7u6/K8mVwA7gKuAVwN8muaKqTo+taklT1e/yTbcQXntGWYPfDuzvjvcDN/S031FVz1bVk8BR4OoRvo8kaQUGDfgCPpXkwSRnFgEvraoTAN3tJV37JuCpnnNnu7bnSLIryeEkh+fm5lZWvSRpUYMu0byxqo4nuQS4O8kXluibPm11VkPVPmAfwMzMzFmPS5JGM9AMvqqOd7cngb9mfsnl6SQbAbrbk133WWBLz+mbgePjKliSNJhlAz7JS5K87Mwx8CPAw8BBYGfXbSdwV3d8ENiR5PwklwPbgAfGXbgkaWmDLNFcCvx1kjP9P1JVn0jyGeBAkpuAY8CNAFV1JMkB4BHgFHCzV9BI43HNsX19270+Xv0sG/BV9QTw2j7tzwDXLXLOXmDvyNVJklbMrQokqVEGvCQ1yoCXpEa52Zi0Rnz6iWeW7yQNwRm8JDXKgJekRhnwktQoA16SGmXAS1KjDHhJapQBL0mN8jp4qQFuQqZ+nMFLUqOcwasd97x72hVIa4ozeElqlAEvSY0y4CWpUQa8JDXKgJekRhnwktQoL5OUpsAP99BqcAYvSY0y4CWpUS7RSBqL9979+Flt73zLFVOoRGcMPINPcl6SzyX5eHf/oiR3J/lid3thT989SY4meSzJWydRuCRpacMs0fwK8GjP/d3AoaraBhzq7pPkSmAHcBVwPfD+JOeNp1xJ0qAGCvgkm4EfA27vad4O7O+O9wM39LTfUVXPVtWTwFHg6rFUK0ka2KBr8O8DfhN4WU/bpVV1AqCqTiS5pGvfBNzX02+2a5PGx50jpWUtO4NP8uPAyap6cMDnTJ+26vO8u5IcTnJ4bm5uwKeWJA1qkCWaNwI/meRLwB3ADyX5EPB0ko0A3e3Jrv8ssKXn/M3A8YVPWlX7qmqmqmY2bNgwwhAkSf0sG/BVtaeqNlfVVuZfPP27qno7cBDY2XXbCdzVHR8EdiQ5P8nlwDbggbFXLkla0ijXwd8KHEhyE3AMuBGgqo4kOQA8ApwCbq6q0yNXKkkaylABX1X3Avd2x88A1y3Sby+wd8TaJEkjcKsCSWqUAS9JjXIvGkkT4/400+UMXpIaZcBLUqMMeElqlAEvSY0y4CWpUV5FI03YND9g+5pj+85qu++yXVOoRNPgDF6SGmXAS1KjDHhJapQBL0mN8kVWSavK7QtWjzN4SWqUAS9JjTLgJalRBrwkNcoXWaUxmua7VqWFnMFLUqMMeElqlAEvSY0y4CWpUQa8JDXKgJekRi0b8ElemOSBJP+S5EiS3+vaL0pyd5IvdrcX9pyzJ8nRJI8leeskByBJ6m+QGfyzwA9V1WuB7wWuT3INsBs4VFXbgEPdfZJcCewArgKuB96f5LwJ1C5JWsKyAV/z/re7+/zuq4DtwP6ufT9wQ3e8Hbijqp6tqieBo8DV4yxakrS8gd7J2s3AHwS+G/jjqro/yaVVdQKgqk4kuaTrvgm4r+f02a5t4XPuAnYBXHbZZSsfgdp2z7unXUFz+n1OK/hZrS0a6EXWqjpdVd8LbAauTvKaJbqn31P0ec59VTVTVTMbNmwYqFhJ0uCGuoqmqr4K3Mv82vrTSTYCdLcnu26zwJae0zYDx0ctVJI0nEGuotmQ5ILu+EXADwNfAA4CO7tuO4G7uuODwI4k5ye5HNgGPDDmuiVJyxhkDX4jsL9bh/824EBVfTzJp4EDSW4CjgE3AlTVkSQHgEeAU8DNVXV6MuVLkhazbMBX1b8Cr+vT/gxw3SLn7AX2jlydJGnF3A9ea4NXy0hjZ8BLK+SHe2itcy8aSWqUAS9JjTLgJalRBrwkNcqAl6RGGfCS1CgDXpIaZcBLUqN8o5OkqXvv3Y+f1fbOt1wxhUraYsBLAvwgkBa5RCNJjTLgJalRBrwkNco1eK0+twaWVoUzeElqlAEvSY0y4CWpUQa8JDXKgJekRhnwktQoL5OUBuSHbK8u96cZnTN4SWqUAS9JjVp2iSbJFuCDwHcC3wD2VdVtSS4C/gLYCnwJ+Omq+q/unD3ATcBp4Jer6pMTqV5rm+9YlaZqkBn8KeDXq+rVwDXAzUmuBHYDh6pqG3Cou0/32A7gKuB64P1JzptE8ZKkxS0b8FV1oqo+2x1/DXgU2ARsB/Z33fYDN3TH24E7qurZqnoSOApcPea6JUnLGGoNPslW4HXA/cClVXUC5n8JAJd03TYBT/WcNtu1LXyuXUkOJzk8Nze3gtIlSUsZOOCTvBT4K+BXq+p/lurap63OaqjaV1UzVTWzYcOGQcuQJA1ooIBP8nzmw/3DVfWxrvnpJBu7xzcCJ7v2WWBLz+mbgePjKVeSNKhlAz5JgD8FHq2q9/Q8dBDY2R3vBO7qad+R5PwklwPbgAfGV7IkaRCDvJP1jcA7gM8neahr+y3gVuBAkpuAY8CNAFV1JMkB4BHmr8C5uapOj7twSdLSlg34qvon+q+rA1y3yDl7gb0j1CVJGpHvZJWkRhnwktQoA16SGuV2wZKWdM2xfX3b77ts1ypXomE5g5ekRhnwktQoA16SGuUavKR1Y+HH+PkRfksz4DW6Bj/Yw89fVQtcopGkRhnwktQoA16SGuUavM55rrerVc7gJalRzuAlrUi/LQzcvmBtMeA1nAYviZRa5RKNJDXKgJekRhnwktQoA16SGmXAS1KjDHhJapSXSeqc4rtWdS4x4CWNzWp/fuvC/eHBPeJ7LbtEk+TPkpxM8nBP20VJ7k7yxe72wp7H9iQ5muSxJG+dVOGSpKUNMoP/c+CPgA/2tO0GDlXVrUl2d/ffleRKYAdwFfAK4G+TXFFVp8dbtibOd6xK696yM/iq+gfgKwuatwP7u+P9wA097XdU1bNV9SRwFLh6PKVKkoax0qtoLq2qEwDd7SVd+ybgqZ5+s13bWZLsSnI4yeG5ubkVliFJWsy4L5NMn7bq17Gq9lXVTFXNbNiwYcxlSJJWehXN00k2VtWJJBuBk137LLClp99m4PgoBUor5SWROtetdAZ/ENjZHe8E7upp35Hk/CSXA9uAB0YrUZK0EsvO4JN8FLgWuDjJLPA7wK3AgSQ3AceAGwGq6kiSA8AjwCngZq+gkaTpWDbgq+ptizx03SL99wJ7RylKGpbLMdLZfCerpKb47tZvcbMxSWqUAS9JjTLgJalRBrwkNcoXWc91biomNcuAP5c0FOZeFiktz4CX1Lxz9dJJ1+AlqVEGvCQ1yiUaSRO32p/VqnnO4CWpUQa8JDXKJZoWNXQ5JHhJpLRSBrykc9K5cOmkAS9pavq9+OoLr+PjGrwkNcqAl6RGuUSznjX2YqoEXjM/Tga81hSvmNE0tfbCq0s0ktQoZ/BrzTm07OJsXZosA16rwjCXVp8BL2ldWOzF1358QXaeAT8tDS/FOFuX1oaJBXyS64HbgPOA26vq1kl9r1W3WDi/ec/q1iFp4vpdWbPQWr3SZiIBn+Q84I+BtwCzwGeSHKyqRybx/daMxmblg8zE3/DK71iFSqS1bZBfArD6vwgmNYO/GjhaVU8AJLkD2A5MJuAbC9ZB9AvfQcN2nEsoLsdoLRpmvX5Yo6zvr/Z19pMK+E3AUz33Z4Hv7+2QZBdw5k/qf5M8NqFaJuFi4MvTLmLCWh+j41vfpji+Pxzrs/1a/+ZBx/ddSz04qYBPn7Z6zp2qfcDkfs1OUJLDVTUz7TomqfUxOr71zfENZlLvZJ0FtvTc3wwcn9D3kiT1MamA/wywLcnlSV4A7AAOTuh7SZL6mMgSTVWdSvJLwCeZv0zyz6rqyCS+15Ssy6WlIbU+Rse3vjm+AaSqlu8lSVp33E1SkhplwEtSowz4BZJcn+SxJEeT7F6kz7VJHkpyJMnfD3PutK10fEm2JLknyaNd+6+sbuWDGeXn1z12XpLPJfn46lQ8nBH/fl6Q5M4kX+h+jm9YvcoHN+IY39m1PZzko0leuHqVD2a58SX5jW5sD3XjOJ3kokHOPUtV+dV9Mf+C8L8BrwReAPwLcOWCPhcw/47cy7r7lwx67rS/RhzfRuD13fHLgMdbGl/P478GfAT4+LTHM+7xAfuBX+iOXwBcMO0xjfnv6CbgSeBF3f0DwM9Ne0zDjm9B/58A/m4l51aVM/gFvrnFQlV9HTizxUKvnwE+VlXHAKrq5BDnTtuKx1dVJ6rqs93x14BHmf8HtZaM8vMjyWbgx4DbV6neYa14fEleDrwJ+NOu/etV9dXVKnwII/0Mmb8y8EVJnge8mLX3/pthc+JtwEdXeK4Bv0C/LRYWhtgVwIVJ7k3yYJKfHeLcaRtlfN+UZCvwOuD+SRW6QqOO733AbwLfmGiVKzfK+F4JzAEf6Jagbk/yksmXPLQVj7Gq/gP4A+AYcAL476r61CrUPIyBcyLJi4Hrgb8a9twz3A/+uZbdYoH5P7PvA64DXgR8Osl9A547bSseX1U9DpDkpcz/hfvVqvqfSRa7AqP8/K4ATlbVg0munWSRIxhlfM8DXg/cUlX3J7kN2A389gTrXYlRxjjH/Iz2cuCrwF8meXtVfWhy5Q5tmJz4CeCfq+orKzgXMOAXGmSLhVngy1X1f8D/JfkH4LUDnjtto4zv8STPZz7cP1xVH1uNgoc0yvheD/xkkh8FXgi8PMmHqurtq1D3oEYZ3z8Cs1V15n9ddzIf8GvNKGMEeLKq5gCSfAz4AWAtBfwwObGDby3PDHvuvGm/6LCWvpj/hfcE8zOAMy9iXLWgz6uBQ13fFwMPA68Z5Nxpf404vgAfBN437XFMYnwL+lzL2nyRdaTxMR/yr+qOfxf4/WmPacx/R78fONK1hfkXlW+Z9piGHV/X79uBrwAvGfbc3i9n8D1qkS0Wkvxi9/ifVNWjST4B/Cvza7W3V9XDAGt9e4ZRxpfkB4F3AJ9P8lD3lL9VVX+z+iPpb9Sf31o3hvHdAnw48/tDPQH8/OqPYmlj+Dd4J/BZ4BTwOdbYlgaDjK/r+lPAp2r+fylLnrvU93OrAklqlFfRSFKjDHhJapQBL0mNMuAlqVEGvCQ1yoCXpEYZ8JLUqP8HMD/pUCuExEwAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"show(c=0.5, N=50)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that the gap between proposer and acceptor has been greatly reduced (but not eliminated). With more actors, the variance is smaller (the histogram is not as wide). \n",
"\n",
"What happens with 90% common value? How aboout 99%?"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10,000 examples with N = 25 actors, common value ratio c = 0.9\n",
" Acceptors: 0.509 ± 0.005\n",
" Proposers: 0.510 ± 0.005\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAStUlEQVR4nO3df6zd933X8edrWZsx1mlJYwfPP+YUOUBSKW11CR1FVUsIjUqFg9RUngQyYMmalK5pBKL2kGD8YTUbYumElCHTlhro5lpsJdY0WjwvZSAlTZ0qbeOkSUwSnDub2AsdXUHKsPfmj/NNcmyfc++595xzz7kfPx/S0fmez/l8z33fr49f93M+3x8nVYUkqS0/NOsCJEmTZ7hLUoMMd0lqkOEuSQ0y3CWpQT886wIAbrjhhtq+ffusy5CkdeWJJ574g6raMOi5uQj37du3c+LEiVmXIUnrSpL/Mew5p2UkqUGGuyQ1yHCXpAYZ7pLUIMNdkhpkuEtSgwx3SWqQ4S5JDTLcJalBc3GGqjT3Hvn04PYP7l/bOqQROXKXpAYZ7pLUIMNdkhpkuEtSg9yhKk3Ig8eeG9h+/503r3ElkiN3SWrSSCP3JD8BfBZ4J1DA3weeBb4EbAdeAj5WVd/r+u8H9gAXgU9U1VcnXLe07jnS1zSNOnL/FeArVfXngduAZ4B9wPGq2gEc7x6T5BZgF3ArcBfwUJJrJl24JGm4ZcM9yY8D7wc+B1BVf1xVfwjsBA513Q4Bd3fLO4HDVfVaVb0InAJun2zZkqSljDIt8w7gPPBvktwGPAHcB9xYVWcBqupsko1d/83AY33rL3Ztl0iyF9gLsG3btlX/AtI8eu/pg28+eOTtby57RqvWyCjTMj8MvAf41ap6N/B/6KZghsiAtrqioepgVS1U1cKGDQO/vFuStEqjhPsisFhVX+8e/wd6Yf9Kkk0A3f25vv5b+9bfApyZTLmSpFEsG+5V9T+Bl5P8ua7pDuBp4Ciwu2vbDTzcLR8FdiW5NslNwA7g8YlWLUla0qgnMf0c8MUkbwVeAP4evT8MR5LsAU4D9wBU1ckkR+j9AbgA3FtVFydeuSRpqJHCvaqeBBYGPHXHkP4HgAOrL0uSNA7PUJWkBnltGWmFHn3h1TeWH7sw+CxTadYcuUtSgxy5S1PmSF+z4MhdkhpkuEtSgwx3SWqQc+7SGC65QJg0Rxy5S1KDDHdJapDhLkkNMtwlqUGGuyQ1yHCXpAZ5KKTU75FPz7oCaSIMd2kNDTsu/rFte9e4ErXOaRlJapDhLkkNclpGVyfn1tU4w12aMw8eW9k13++/8+YpVaL1zHCX5oA7WjVpzrlLUoMMd0lqkNMy0hD93306z4bN0TsXf3UbaeSe5KUk30nyZJITXdv1SY4leb67v66v//4kp5I8m+RD0ypekjTYSqZlPlhV76qqhe7xPuB4Ve0AjnePSXILsAu4FbgLeCjJNROsWZK0jHHm3HcCh7rlQ8Ddfe2Hq+q1qnoROAXcPsbPkSSt0KjhXsB/TvJEktePzbqxqs4CdPcbu/bNwMt96y52bZdIsjfJiSQnzp8/v7rqJUkDjbpD9X1VdSbJRuBYku8u0TcD2uqKhqqDwEGAhYWFK56XJsIzUXWVGmnkXlVnuvtzwJfpTbO8kmQTQHd/ruu+CGztW30LcGZSBUuSlrdsuCf500ne9voy8NeBp4CjwO6u227g4W75KLArybVJbgJ2AI9PunBJ0nCjTMvcCHw5yev9f62qvpLkG8CRJHuA08A9AFV1MskR4GngAnBvVV2cSvWSpIGWDfeqegG4bUD7q8AdQ9Y5ABwYuzppgtbLSUn9vOaMVsvLD0hSgwx3SWqQ4S5JDTLcJalBhrskNchL/krrkEfRaDmO3CWpQYa7JDXIcJekBhnuktQgw12SGmS4S1KDDHdJapDhLkkNMtwlqUGGuyQ1yMsPqA1+EbZ0CUfuktQgw12SGmS4S1KDDHdJapA7VLW+uON0ZA8ee25g+/133rzGlWgWHLlLUoMMd0lq0MjTMkmuAU4Av19VH0lyPfAlYDvwEvCxqvpe13c/sAe4CHyiqr464bqloR594dVZlyDN3EpG7vcBz/Q93gccr6odwPHuMUluAXYBtwJ3AQ91fxgkSWtkpHBPsgX4G8Bn+5p3Aoe65UPA3X3th6vqtap6ETgF3D6RaiVJIxl15P4Z4B8Bf9LXdmNVnQXo7jd27ZuBl/v6LXZtl0iyN8mJJCfOnz+/0rolSUtYNtyTfAQ4V1VPjPiaGdBWVzRUHayqhapa2LBhw4gvLUkaxSg7VN8H/M0kHwZ+BPjxJP8eeCXJpqo6m2QTcK7rvwhs7Vt/C3BmkkVLWj2Pf786LDtyr6r9VbWlqrbT21H6u1X1t4GjwO6u227g4W75KLArybVJbgJ2AI9PvHJJ0lDjnKH6AHAkyR7gNHAPQFWdTHIEeBq4ANxbVRfHrlSSNLIVhXtVfQ34Wrf8KnDHkH4HgANj1iZJWiXPUJWkBhnuktQgw12SGmS4S1KDDHdJapBf1iE15L2nDw5sf2zb3mXX9eSmtjhyl6QGOXLXuuV126XhDHfN1rDvRP3g/rWtQ2qM0zKS1CDDXZIaZLhLUoMMd0lqkOEuSQ3yaBnNp2FH0UgaiSN3SWqQ4S5JDTLcJalBzrlLV4FxLiim9cmRuyQ1yHCXpAYZ7pLUIMNdkhq0bLgn+ZEkjyf5VpKTSf5Z1359kmNJnu/ur+tbZ3+SU0meTfKhaf4CkqQrjTJyfw34q1V1G/Au4K4k7wX2AceragdwvHtMkluAXcCtwF3AQ0mumULtkqQhlg336vlB9/At3a2AncChrv0QcHe3vBM4XFWvVdWLwCng9kkWLUla2khz7kmuSfIkcA44VlVfB26sqrMA3f3Grvtm4OW+1Re7tstfc2+SE0lOnD9/foxfQZJ0uZFOYqqqi8C7kvwE8OUk71yiewa9xIDXPAgcBFhYWLjieUnT58lN7VrR0TJV9YfA1+jNpb+SZBNAd3+u67YIbO1bbQtwZtxCJUmjG+VomQ3diJ0kfwr4a8B3gaPA7q7bbuDhbvkosCvJtUluAnYAj0+4bknSEkaZltkEHOqOePkh4EhV/VaSR4EjSfYAp4F7AKrqZJIjwNPABeDeblpHkrRGlg33qvo28O4B7a8CdwxZ5wBwYOzqJODRF16ddQnSuuMZqpLUIC/5K2lJDx57bmD7/XfevMaVaCUcuUtSgwx3SWqQ4S5JDTLcJalBhrskNchwl6QGeSikpu+RT8+6Aumq48hdkhpkuEtSg5yW0dzwGjLS5Dhyl6QGGe6S1CCnZSRdwa/fW/8cuUtSgwx3SWqQ4S5JDTLcJalBhrskNcijZSStil+/N98cuUtSgwx3SWqQ4S5JDVo23JNsTfJIkmeSnExyX9d+fZJjSZ7v7q/rW2d/klNJnk3yoWn+ApKkK42yQ/UC8A+q6ptJ3gY8keQY8HeB41X1QJJ9wD7gU0luAXYBtwI/CfxOkpur6uJ0fgWtN179UZq+ZUfuVXW2qr7ZLf8R8AywGdgJHOq6HQLu7pZ3Aoer6rWqehE4Bdw+4bolSUtY0aGQSbYD7wa+DtxYVWeh9wcgycau22bgsb7VFru2y19rL7AXYNu2bSsuXHPIr9OT5sbIO1ST/BjwG8Anq+r7S3Ud0FZXNFQdrKqFqlrYsGHDqGVIkkYwUrgneQu9YP9iVf1m1/xKkk3d85uAc137IrC1b/UtwJnJlCtJGsUoR8sE+BzwTFX9ct9TR4Hd3fJu4OG+9l1Jrk1yE7ADeHxyJUuSljPKnPv7gL8DfCfJk13bzwMPAEeS7AFOA/cAVNXJJEeAp+kdaXOvR8pI0tpaNtyr6r8xeB4d4I4h6xwADoxRl6R1ymvOzAfPUJWkBnlVSK3ciIc8erKSNDuGu6SR+cXZ64fhLmlNOBe/tpxzl6QGGe6S1CDDXZIaZLhLUoMMd0lqkOEuSQ0y3CWpQYa7JDXIk5gkjc0zV+ePI3dJapDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIA+F1HAjfuOSNIyHSM6OI3dJapDhLkkNclpGY/OLsKX548hdkhq07Mg9yeeBjwDnquqdXdv1wJeA7cBLwMeq6nvdc/uBPcBF4BNV9dWpVK7Jccep1JxRRu5fAO66rG0fcLyqdgDHu8ckuQXYBdzarfNQkmsmVq0kaSTLjtyr6veSbL+seSfwgW75EPA14FNd++Gqeg14Mckp4Hbg0QnVK+kq8eCx5wa233/nzWtcyfq02jn3G6vqLEB3v7Fr3wy83NdvsWu7QpK9SU4kOXH+/PlVliFJGmTSO1QzoK0Gdayqg1W1UFULGzZsmHAZknR1W224v5JkE0B3f65rXwS29vXbApxZfXmSpNVY7XHuR4HdwAPd/cN97b+W5JeBnwR2AI+PW6Tmg8ezaxqGza1rPKMcCvnr9Hae3pBkEfin9EL9SJI9wGngHoCqOpnkCPA0cAG4t6ouTql2SdIQoxwt8zNDnrpjSP8DwIFxipIkjcfLD1xNRjxZyekXaf3z8gOS1CBH7pLWnNd5nz5H7pLUIEfuLfJCYNJVz5G7JDXIkftVzKNitB55QbHROHKXpAYZ7pLUIKdlJM2NYYdIgodJrpQjd0lqkCP39cxDHiUN4chdkhpkuEtSg5yWkdS0q/W4eMNd0rqw3MXG/EanSxnuDfGMU0mvM9zXA4+KkYby8sGDGe7rkCN0ScvxaBlJapAj93ni9Is0MVf7dI3hPguGuKQpc1pGkhrkyH2axhyhu+NUmp7WT26aWrgnuQv4FeAa4LNV9cC0fta8ef1N897Tl4bzT7/j7QP7G+LS7L0xR//IZf9PP7h/7YuZgFTV5F80uQZ4DrgTWAS+AfxMVT09qP/CwkKdOHFi4nUsa9jIetg/5ogjccNaat9qd8xO8pNBkieqamHQc9Maud8OnKqqF7oCDgM7gYHhPq43R8rDL/Tfb9gIeqUMcenqNWreXGGNPhlMK9w3Ay/3PV4E/lJ/hyR7gdf/9P0gybNTqmWQG4A/GP70z69ZIQMsU9vMzGtdYG2rZW2rM+Haxsqbnxr2xLTCPQPaLpn/qaqDwCr/9I0nyYlhH2VmbV5rm9e6wNpWy9pWZ55r6zetQyEXga19j7cAZ6b0syRJl5lWuH8D2JHkpiRvBXYBR6f0syRJl5nKtExVXUjyceCr9A6F/HxVnZzGz1qlmUwHjWhea5vXusDaVsvaVmeea3vDVA6FlCTNlpcfkKQGGe6S1KB1H+5J7krybJJTSfYt0e8vJrmY5KN9bfcleSrJySSf7Gu/PsmxJM9399fNUW2/kOT3kzzZ3T48jdqSfCDJ/+77Of9kuXXXarutsraxt9uYdX0+ybkkT122zjxss2G1zfS9lmRrkkeSPNP9P7ivb52ZbrdlapvIdhtbVa3bG72dtf8deAfwVuBbwC1D+v0u8NvAR7u2dwJPAT9Kb8fy7wA7uud+CdjXLe8DfnGOavsF4B9Oe7sBHwB+ayXrrtV2W2VtY223cerqnns/8B7gqcvaZ7rNlqlt1u+1TcB7uuW30bukyby815aqbeztNonbeh+5v3GZg6r6Y+D1yxxc7ueA3wDO9bX9BeCxqvq/VXUB+C/A3+qe2wkc6pYPAXfPUW2TMGptK113LbfbpNed6mtX1e8B/2vAU7PeZkvVNgmrrq2qzlbVN7vlPwKeoXf2O8x4uy1T21xY7+E+6DIHl2zgJJvpBeO/umzdp4D3J3l7kh8FPsybJ17dWFVnofePCGyco9oAPp7k293H6dV8HF22ts5PJ/lWkv+U5NYR1l2T7bbK2mC87TZOXUuZ9TZbzizfa29Ish14N/D1rmluttuA2mD87Ta29R7uy17mAPgM8KmqunhJp6pngF8EjgFfofeR7MI6qO1XgT8LvAs4C/yLKdX2TeCnquo24F8C/3EF645jWrWNu93GqWvaplXbrN9rvRdIfozep9tPVtX3V1HDWtc2ie02tvUe7qNc5mABOJzkJeCjwENJ7gaoqs9V1Xuq6v30PpY+363zSpJNAN39OVZuKrVV1StVdbGq/gT41/Q+Wk68tqr6flX9oFv+beAtSW5YZt012W6rqW0C222cupYy62021By810jyFnrh+cWq+s2+1Wa+3YbVNqHtNr5ZT/qPc6O3s/EF4Cbe3CFy6xL9v0C307J7vLG73wZ8F7iue/zPuXRnzS/NUW2b+vrcDxyeRm3An+HNk9xuB07TG+kMXXetttsqaxtru41TV9/z27lyp+VMt9kytc36vRbg3wKfGfC6s36vLVXb2NttErc1/4ET/wV689HP0dvr/Y+7tp8FfnZA3y9waYD+V3rXmP8WcEdf+9uB4/RGy8eB6+eotn8HfAf4Nr3r9WyaRm3Ax4GT3c9/DPjLS627ltttlbWNvd3GrOvX6X1E/3/0Rox75mibDattpu814K/Qmyb5NvBkd/vwPGy3ZWqbyHYb9+blBySpQet9zl2SNIDhLkkNMtwlqUGGuyQ1yHCXpAYZ7pLUIMNdkhr0/wHPvD9QB1Oe+wAAAABJRU5ErkJggg==\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"show(c=0.9)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"10,000 examples with N = 25 actors, common value ratio c = 0.99\n",
" Acceptors: 0.500 ± 0.001\n",
" Proposers: 0.500 ± 0.001\n"
]
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjUuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/YYfK9AAAACXBIWXMAAAsTAAALEwEAmpwYAAAUSElEQVR4nO3dfYxc133e8e9j2VbiNK71QjI0X0oJpVyLBiQnW1aCAVcsK5tJDVNBTINGEhAxWzYBE8dqg4psgRZFQViJDStGE6UgoiQ0aptmYrti08QyzVgNClCWKVdORL0ykkJuyZK0otRJ3col/esfe2kNyRnu7O7M7M7l9wMQc+fMvTO/Odx99uyZe8+mqpAktctr5rsASdLgGe6S1EKGuyS1kOEuSS1kuEtSC712vgsAuP7662vVqlXzXYYkjZXHHnvsm1W1qNtjCyLcV61axeHDh+e7DEkaK0n+vNdjTstIUgsZ7pLUQoa7JLWQ4S5JLWS4S1ILGe6S1EKGuyS1kOEuSS1kuEtSCy2IK1SlK8V9B57t2n73nTeNuBK1nSN3SWohw12SWshwl6QWMtwlqYUMd0lqoWnDPclbkjze8e9bST6c5NokB5I819xe03HMziRHkzyT5N3DfQuSpItNG+5V9UxV3VpVtwI/Anwb+AKwAzhYVauBg819ktwMbAbWABuA+5NcNZzyJUndzHRaZj3wZ1X158BGYE/Tvge4q9neCOytqleq6gXgKLB2ALVKkvo003DfDHym2V5SVScBmtvFTfsy4HjHMZNN2wWSbEtyOMnhM2fOzLAMSdLl9B3uSV4PvBf43el27dJWlzRU7a6qiaqaWLSo6993lSTN0kxG7j8KfL2qTjX3TyVZCtDcnm7aJ4EVHcctB07MtVBJUv9msrbMB3h1SgZgP7AFuLe5fbCj/dNJPg68GVgNPDr3UqXeXLNFulBf4Z7kDcCdwD/taL4X2JdkK3AM2ARQVUeS7AOeBM4C26vq3ECrliRdVl/hXlXfBq67qO0lps6e6bb/LmDXnKuTJM2KV6hKUgsZ7pLUQoa7JLWQ4S5JLWS4S1ILGe6S1EKGuyS10EyuUJU0LF/5SPf2dTtHW4daw5G7JLWQ4S5JLeS0jBYupyqkWXPkLkktZLhLUgsZ7pLUQoa7JLWQ4S5JLWS4S1ILGe6S1EKGuyS1UF/hnuRNSX4vydNJnkpye5JrkxxI8lxze03H/juTHE3yTJJ3D698SVI3/Y7cPwF8sar+DnAL8BSwAzhYVauBg819ktwMbAbWABuA+5NcNejCJUm9TRvuSd4IvBN4AKCqvlNVfwlsBPY0u+0B7mq2NwJ7q+qVqnoBOAqsHWzZkqTL6WfkfiNwBvjtJP89yW8m+QFgSVWdBGhuFzf7LwOOdxw/2bRdIMm2JIeTHD5z5syc3oQk6UL9hPtrgR8GfqOq3g78b5opmB7Spa0uaajaXVUTVTWxaNGivoqVJPWnn3CfBCar6qvN/d9jKuxPJVkK0Nye7th/Rcfxy4ETgylXktSPacO9qv4ncDzJW5qm9cCTwH5gS9O2BXiw2d4PbE5ydZIbgNXAowOtWpJ0Wf2u5/4LwKeSvB54HvgZpn4w7EuyFTgGbAKoqiNJ9jH1A+AssL2qzg28cklST32Fe1U9Dkx0eWh9j/13AbtmX5YkaS68QlWSWshwl6QWMtwlqYUMd0lqIcNdklrIcJekFur3PHfpyvaVj3RvX7dztHVIfTLcpbkw9LVAOS0jSS1kuEtSCxnuktRChrsktZDhLkkt5NkyUof7Djzbtf1uv1M0Zhy5S1ILOR6R+nDo+Ze6tt9+43UjrkTqj+GuK1fXC5B+YuRlSMNguKvVes2hA9x2rMtofOUQi5FGyDl3SWqhvkbuSV4E/go4B5ytqokk1wKfBVYBLwLvr6qXm/13Alub/T9UVQ8NvHJpCG47tnu+S5AGYibTMuuq6psd93cAB6vq3iQ7mvv3JLkZ2AysAd4MfDnJTVV1bmBVSwvc5aaDpFGYy5z7RuCOZnsP8DBwT9O+t6peAV5IchRYCxyaw2tJszYfo/Fer/nIym0jrkRXqn7n3Av4UpLHkpz/6lxSVScBmtvFTfsy4HjHsZNN2wWSbEtyOMnhM2fOzK56SVJX/Y7c31FVJ5IsBg4kefoy+6ZLW13SULUb2A0wMTFxyeOSpNnrK9yr6kRzezrJF5iaZjmVZGlVnUyyFDjd7D4JrOg4fDlwYoA1S2Or5xSRF0NpwKadlknyA0l+8Pw28C7gCWA/sKXZbQvwYLO9H9ic5OokNwCrgUcHXbgkqbd+Ru5LgC8kOb//p6vqi0m+BuxLshU4BmwCqKojSfYBTwJnge2eKaO26rUsgTTfpg33qnoeuKVL+0vA+h7H7AJ2zbk6SdKseIWqJLWQ4S5JLWS4S1ILuSqkxk+XpXq7rvAoXcEcuUtSCxnuktRChrsktZDhLkktZLhLUgsZ7pLUQoa7JLWQ4S5JLeRFTBorrsIo9cdwlxayLlfjArBu52jr0NhxWkaSWshwl6QWMtwlqYUMd0lqIcNdklqo77NlklwFHAb+R1W9J8m1wGeBVcCLwPur6uVm353AVuAc8KGqemjAdUut0usUz9tvvG7ElagtZjJy/0XgqY77O4CDVbUaONjcJ8nNwGZgDbABuL/5wSBJGpG+Ru5JlgP/CNgF/LOmeSNwR7O9B3gYuKdp31tVrwAvJDkKrAUODaxqtd59B571rytJc9DvyP1XgX8BfLejbUlVnQRobhc37cuA4x37TTZtkqQRmTbck7wHOF1Vj/X5nOnSVl2ed1uSw0kOnzlzps+nliT1o59pmXcA703yY8D3AW9M8h+BU0mWVtXJJEuB083+k8CKjuOXAycuftKq2g3sBpiYmLgk/CVd5oPWdSMuRGNn2pF7Ve2squVVtYqpD0r/qKp+CtgPbGl22wI82GzvBzYnuTrJDcBq4NGBVy5J6mkuC4fdC+xLshU4BmwCqKojSfYBTwJnge1VdW7OlUqS+jajcK+qh5k6K4aqeglY32O/XUydWSNJmgdeoSpJLWS4S1ILGe6S1EKGuyS1kH9mT/Ovy5+Sc+kBaW4cuUtSCxnuktRChrsktZDhLkktZLhLUgsZ7pLUQoa7JLWQ57lLY+jQA7/Utf32rR8bcSVaqBy5S1ILGe6S1EJOy2he3XfgWZcakIbAcNfouIaMNDJOy0hSCzly10g4/SKNliN3SWqhacM9yfcleTTJN5IcSfJvm/ZrkxxI8lxze03HMTuTHE3yTJJ3D/MNSJIu1c/I/RXgH1TVLcCtwIYktwE7gINVtRo42Nwnyc3AZmANsAG4P8lVQ6hdktTDtOFeU/66ufu65l8BG4E9Tfse4K5meyOwt6peqaoXgKPA2kEWLUm6vL4+UG1G3o8Bfxv49ar6apIlVXUSoKpOJlnc7L4MeKTj8Mmm7eLn3AZsA1i5cuXs34GG6r4Dz3Ztv/vOm0ZciaSZ6OsD1ao6V1W3AsuBtUnedpnd0+0pujzn7qqaqKqJRYsW9VWsJKk/Mzpbpqr+EniYqbn0U0mWAjS3p5vdJoEVHYctB07MtVBJUv/6OVtmUZI3NdvfD/xD4GlgP7Cl2W0L8GCzvR/YnOTqJDcAq4FHB1y3JOky+plzXwrsaebdXwPsq6rfT3II2JdkK3AM2ARQVUeS7AOeBM4C26vq3HDKlyR1M224V9WfAG/v0v4SsL7HMbuAXXOuTpI0K16hKkkt5NoyUpt0WXkTgHU7R1uH5p3hLrXIoee7L852+7oRF6J557SMJLWQI3cNVK8rWiWNliN3SWohR+4auNuO7Z7vEqQrniN3SWohR+7SlWCGp0i6Guj4M9ylK4CnSF55nJaRpBYy3CWphZyWka5gXpfQXo7cJamFDHdJaiGnZTQr/jovLWyO3CWphQx3SWohw12SWmjaOfckK4BPAj8EfBfYXVWfSHIt8FlgFfAi8P6qerk5ZiewFTgHfKiqHhpK9ZpXLhAmLVz9jNzPAv+8qt4K3AZsT3IzsAM4WFWrgYPNfZrHNgNrgA3A/UmuGkbxkqTupg33qjpZVV9vtv8KeApYBmwE9jS77QHuarY3Anur6pWqegE4CqwdcN2SpMuY0Zx7klXA24GvAkuq6iRM/QAAFje7LQOOdxw22bRd/FzbkhxOcvjMmTOzKF2S1Evf4Z7kbwCfAz5cVd+63K5d2uqShqrdVTVRVROLFi3qtwxJUh/6Cvckr2Mq2D9VVZ9vmk8lWdo8vhQ43bRPAis6Dl8OnBhMuZKkfvRztkyAB4CnqurjHQ/tB7YA9za3D3a0fzrJx4E3A6uBRwdZtKTB6HXG0yMrt424Eg1aP8sPvAP4aeBPkzzetP1LpkJ9X5KtwDFgE0BVHUmyD3iSqTNttlfVuUEXLknqbdpwr6r/Rvd5dID1PY7ZBeyaQ12SpDlw4TBNy4uVpPHj8gOS1EKGuyS1kNMyki7ReyruYyOtQ7PnyF2SWshwl6QWMtwlqYWcc9ervvKRS5puO/bSPBQiaa4cuUtSCxnuktRChrsktZBz7gLgvgPPOr8utYgjd0lqIcNdklrIcJekFjLcJamFDHdJaiHPlrkSeSWqZum+A8/2fOzuO28aYSWajiN3SWqhaUfuSX4LeA9wuqre1rRdC3wWWAW8CLy/ql5uHtsJbAXOAR+qqoeGUrmkkeu2zvsjK7fNQyWaTj/TMr8D/BrwyY62HcDBqro3yY7m/j1JbgY2A2uANwNfTnJTVZ0bbNmaLS9W0sh0mf4DYN3O0dZxhZp2Wqaq/hj4i4uaNwJ7mu09wF0d7Xur6pWqegE4CqwdTKmSpH7Nds59SVWdBGhuFzfty4DjHftNNm2SpBEa9Nky6dJWXXdMtgHbAFauXDngMnS5sxqkQfrePPxXrpvfQnSB2Yb7qSRLq+pkkqXA6aZ9EljRsd9y4ES3J6iq3cBugImJia4/ACSNj0PPd/8s5/YbDf35MNtpmf3AlmZ7C/BgR/vmJFcnuQFYDTw6txIlSTPVz6mQnwHuAK5PMgn8G+BeYF+SrcAxYBNAVR1Jsg94EjgLbPdMmRG56MwEz4iRrmzThntVfaDHQ+t77L8L2DWXoiRJc+PyA5KG6uK5+EfOTn3Y73IFw2W4j5teF4ZIUgfXlpGkFjLcJamFDHdJaiHn3MdcrwtHJF3ZHLlLUgsZ7pLUQk7LjInzC4F55amkfhjukhaUXiuaetHTzBjukkbq/BLBhx64sN0/1zdYhvs8cb11ScPkB6qS1EKO3Beobn9lXmqzXl/z56drnIufGUfuktRCjtwlLWjTjejVneEuaSxNd9bNlT5d47SMJLWQI/d55genkobBcB+0Pv9SkssISMPRa7rmvNtvvO7ChnU7h1zR/BhauCfZAHwCuAr4zaq6d1ivNS/6DHGX5JU0H4YS7kmuAn4duBOYBL6WZH9VPTmM1xuVzvNsHXlLLdFroNaM6Mf1/PphjdzXAker6nmAJHuBjcBwwr35z+lnlNx5+tQF/zl9jMQNdGn89f3b9PO/BMBtvZ6nx7RPp555MwKpqsE/afI+YENV/ePm/k8Df6+qfr5jn23A+Xf+FuCZgRfS3fXAN0f0WuPEfunNvunOfultVH3zt6pqUbcHhjVyT5e2C36KVNVuYOSniiQ5XFUTo37dhc5+6c2+6c5+6W0h9M2wznOfBFZ03F8OnBjSa0mSLjKscP8asDrJDUleD2wG9g/ptSRJFxnKtExVnU3y88BDTJ0K+VtVdWQYrzULXjXUnf3Sm33Tnf3S27z3zVA+UJUkzS/XlpGkFjLcJamFxjrck2xI8kySo0l2XGa/v5vkXHP+/fm2X0zyRJIjST7c0X5rkkeSPJ7kcJK1Q34bQzGkvrklyaEkf5rkPyd545DfxsBN1y9J7kjyv5r//8eT/Ovpjk1ybZIDSZ5rbq8Z1fsZlCH1y6bma+i7Scb2lMkh9c1Hkzyd5E+SfCHJmwZeeFWN5T+mPqj9M+BG4PXAN4Cbe+z3R8AfAO9r2t4GPAG8gakPlb8MrG4e+xLwo832jwEPz/d7XUB98zXg7zfbHwT+3Xy/10H3C3AH8PszORb4FWBHs70D+OX5fq8LpF/eytQFig8DE/P9PhdY37wLeG2z/cvD+JoZ55H795Y4qKrvAOeXOLjYLwCfA053tL0VeKSqvl1VZ4H/Cvx481gB50ekf5PxPD9/WH3zFuCPm+0DwE8Mo/gh6rdfZnrsRmBPs70HuGtwJY/EUPqlqp6qqlFdeT4sw+qbLzXfXwCPMHUt0ECNc7gvA4533J9s2r4nyTKmguk/XHTsE8A7k1yX5A1MjdDPX3T1YeCjSY4DHwPGcT3QYfXNE8B7m+1NXHih2jiYtl8atyf5RpI/TLKmj2OXVNVJgOZ28WDLHrph9UsbjKJvPgj84SCK7TTO4T7tEgfArwL3VNW5C3aqeoqpX4UOAF9k6tel8z9Ffw64u6pWAHcDfSwPtOAMq28+CGxP8hjwg8B3BljzKPTTL19nar2OW4B/D/ynGRw7ruyX3obaN0n+FVPfX5+aW5mXGudw72eJgwlgb5IXgfcB9ye5C6CqHqiqH66qdwJ/ATzXHLMF+Hyz/btM/Wo1bobSN1X1dFW9q6p+BPgMU/OJ42Tafqmqb1XVXzfbfwC8Lsn10xx7KslSgOa2c5prHAyrX9pgaH2TZAvwHuAnq5l8H6j5/sBitv+Y+rDveeAGXv2wYs1l9v8dmg8Nm/uLm9uVwNPANc39p4A7mu31wGPz/V4XUN+cb38N8Engg/P9XgfdL8AP8erFfWuBY0yNwHoeC3yUCz9Q/ZX5fq8LoV86jn2Y8f1AdVhfMxuYWgJ90bBqH9s/s1c9ljhI8rPN4xfPJV/sc0muA/4fsL2qXm7a/wnwiSSvBf4vry5LPDaG2DcfSLK92f488NtDKH9o+uyX9wE/l+Qs8H+AzTX13Xi5JTXuBfYl2crUN/amkb6xORpWvyT5caamKRYB/yXJ41X17lG/v7kY4tfMrwFXAweSwNRJDD87yNpdfkCSWmic59wlST0Y7pLUQoa7JLWQ4S5JLWS4S1ILGe6S1EKGuyS10P8HSVpnR5JFUlIAAAAASUVORK5CYII=\n",
"text/plain": [
""
]
},
"metadata": {
"needs_background": "light"
},
"output_type": "display_data"
}
],
"source": [
"show(c=0.99)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We see that there is very little difference between the two sides. So the conclusion is: when there is a lot of common value, the Gale-Shapley Matching Algorithm is almost fair: the proposers have an advantage, but it is minimal. So it is probably okay to use the algorithm for matching medical residents, because there is a lot of common value in the perception of the quality of hospitals, and likewise for the quality of students.\n",
"\n",
"But when there is mostly private value, the algorithm is unfair, favoring the proposers over the acceptors."
]
}
],
"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.9.12"
}
},
"nbformat": 4,
"nbformat_minor": 4
}