Hi there!
Welcome to the Appendix of the Algorithmic Game Theory notes.
This is a place for me to put proofs, examples, and interesting non-examinable stuff that would otherwise bloat the notes.
The things here aren’t needed, but useful for further insight, and guaranteeing that first!

Examples

Gale-Shapley Algorithm Example

	Behold! Our example of matching lecturers (leaders) to ANAC winners (followers). Let me introduce you to: AgentGG: Winner of Automated Agents League, Individual Utility of ANAC2019 AgentHerb: Winner of Repeated Multilateral Negotiation League, Social Welfare of ANAC2018 ParsCat2: Winner of Repeated Multilateral Negotiation League, Nash Product Category of ANAC2017 Everyone’s preferences are listed beneath them.
	This is a leader-oriented example, so the leaders propose. We’ll start with the top-most leader, Enrico. His first choice of follower is AgentHerb, so Enrico will propose to AgentHerb.
	AgentHerb doesn’t have any pairing yet, so AgentHerb accepts Enrico’s proposition and pairs with Enrico! Now, Enrico scratches AgentHerb from his list and AgentHerb scratches Enrico off their list. We move on to the next leader: Bahar. Her first choice of follower is AgentGG, so she proposes to them.
	AgentHerb also doesn’t have a pairing, so AgentHerb forms a matching with Bahar and they scratch each other off their lists. Lastly, we move on to Jie. His first choice of follower is also AgentGG, so he proposes to them.
	Awkward 😳 AgentGG actually prefers Jie to Bahar, but AgentGG is already matched with Bahar. What is an ANAC winner to do? In this case, AgentGG breaks up with Bahar and instead forms a match with Jie (and scratches the other off their lists). Poor Bahar! I suppose this is payback for outbidding Jie on that Greggs veggie bake? In any case, Bahar now doesn’t have a matching; she is free.
	Bahar, now being the only one without a matching, gets to go next. The next follower on her list is AgentHerb, so she proposes to them.
	Oh no! When will the tragedy end? AgentHerb preferred Bahar to Enrico, so they split up with Enrico and matched with Bahar! Now Enrico is the ‘free’ one!
	Enrico proposes to the next follower in his list, AgentGG. Unfortunately, AgentGG prefers their own matching, Jie, to Enrico, so no dice.
	Enrico proposes to the last follower on his list, ParsCat2. ParsCat2, being the lonely, unwanted cat that they are, has no matching currently, so they accept Enrico’s proposal. Now we have a stable matching! If you ask me, I don’t know why everyone preferred ParsCat2 last. I’d like a robot cat.

RGS Algorithm Example

	We have 6 residents, and 3 hospitals. Each resident gives preferences for two hospitals they like, and the hospitals give preferences for the residents they like.
	First, r1 applies to h2, and a match is made. h2 isn’t over-subscribed or full, so we move on.
	r2 applies to h1, and a match is made. Again, h1 isn’t over-subscribed or full, so we move on.
	r3 applies to h1, and a match is made. Now, h1 is full, so h1 scratches off all residents on their list that are less desirable than the assigned r3 and r2, and h1 is also removed from r5 and r6’s lists.
	r4 applies to h2, and a match is made. h2 is now full, so the residents less desirable than r1 and r4 are scratched off (r5), and h2 is removed from r5’s list. r5 no longer has any hospitals on their list! r5 will not have any matchings.
	r6 applies to h2, who is over-subscribed. Therefore, the worst resident on h2’s list is scratched off and replaced with r6. r4, now without a hospital, has their turn next.
	r4 applies to the next hospital on their list, h3. They have no residents, so h3 accepts r4. h3 isn’t full or over-subscribed, so that’s the end of that. Now, all residents are either allocated or have no hospitals left to apply to! This is our resident-optimal stable matching.

HGS Algorithm Example

	We have the same setting as the previous example.
	First, we start with h1. It has two available seats, so we look at the first two residents in our preference list, r1 and r3. They’re both free, so we assign r1 and r3 with h1. r1 and r3 are now no longer free. This means we need to scratch off the hospitals they prefer less than h1. r1 doesn’t have any hospitals they like less than h1, but r3 does: h3. So h3 is scratched off r3’s list, and vice versa on h3’s list.
	h2 also has two available seats, so we look at the first two residents of h2’s preference list, r2 and r6. They’re also both free, so we assign r2 and r6 to h2. r2 and r6 are no longer free, but they don’t have any hospitals they desire less to scratch off.
	h3 has two available seats, but only one (available) resident on their list, so they can only propose to r4. r4, being free, accepts h3 and makes a matching. There we have it! All hospitals are now fully subscribed, or have no more residents to propose to. This is our hospital-optimal stable matching.

Irving’s Algorithm Phase 1 Example

	We have the same setting as the previous example.
	Let’s start at the top, with A. A proposes to C, and a matching is made. Now, we go through the successors of A on C’s list (which is just F), and we remove the matching (C,F).
	Now, B proposes to F, and a matching is made between B and F.
	This could go on for a while, so let’s speed this up: C proposes to B, they are semi-engaged D proposes to E, they are semi-engaged (F,E) was removed, as F is a successor to D in E’s list.
	Now, E tries to propose to C. C actually prefers E to A, so C lets E semi-engage with them, and ditches A! A is no longer semi-engaged with anyone.
	Let’s try and find someone for A again. A proposes to D, and accepts; now A is semi-engaged to D.
	Lastly, F proposes to A, and A accepts. E is a successor to F in A’s list, so (A,E) is removed. All the crossed out agents are simply removed in the picture.

Irving’s Algorithm Phase 2 Example

Let’s find a rotation! Starting with A...

A’s second agent is B
B’s last agent is C
C’s second agent is D
D’s last agent is A

p: A C A

q: B D

Boom: a rotation. Now we must remove pairs (B,C) and (A,D).

Time to find another rotation, starting with A:

A’s second agent is F
F’s last agent is B
B’s second agent is E
E’s last agent is D
D’s second agent is B
B’s last agent is A

p: A B D A

q: F E B

Now we remove pairs (B,F), (D,E) and (A,B).

Let’s find another, but this time we must start with B, because A has no second agent:

B’s second agent is D
D’s last agent is F
F’s second agent is D
D’s last agent is F

p: B F F

q: D D

Oops! We repeated ourselves a bit there. No matter, let’s just remove the pair (D,F).

Again, starting with B:

B’s second agent is D
D’s last agent is C
C’s second agent is E
E’s last agent is B

p: B C B

q: D E

Let’s remove pairs (C,D) and (B,E).

Each preference list only has one agent on them!

So, our final stable matching for this SR problem is:

(A,F)
(B,D)
(C,E)

YRMH-IGYT Example

Grab some popcorn 🍿 because you’re gonna be here for a while.
Don’t worry, it’s not hard; it’s just long.

I am once again using examples from the slides, because sod making my own ones.

Let be the set of existing tenants.

Let be the set of newcomers.

Let be the set of occupied houses.

Let be the set of vacant houses.

The image above is everyone’s preferences.

The priority order is as follows:

We start with our first student: a13!

According to the preferences, a13 likes h6, hence the arrow from a13 to h6.

However, we can’t give h6 to a13, because it’s already owned by a6. What are we to do?

Remember the name of the algorithm? “You Request My House, I Get Your Turn”? a6 gets a13’s turn! By that, I mean we put a6 to the front of the priority list and continue, hence the blue arrow from a6 to the start.

Now, a6 is at the start, so we take a6’s turn.

a6 likes h6, giving us a cycle: h6 → a6 → h6 → ...

When we have a cycle, we do the same thing that we do in TTC: assign each agent the house they’re pointing at in the cycle. So, we give h6 to a6.

Now that h6 is gone, a13 can’t point to it anymore.

So, we make a13 point to its next favourite house: h13.

Nobody owns h13, so a13 is free to claim it: we allocate a13 with h13.

a13 → h13

Next is a15. They like h1, but a1 already owns it, so a1 takes a15’s turn and goes to the front of the priority list.

Now it’s a1’s turn. a1 actually likes a completely different house: h15.

Nobody owns that, so a1 is free to take it. Since h1 will be free after a1 moves out, a15 is free to take h1!

Effectively, we’re giving the students what they’re pointing towards. It works like a chain, you see? Or one of those cycles, but without the... cycle.

a1 → h15

a15 → h1

Now, it’s a11’s turn. a11 likes h2, which a2 owns, so a2 is put to the front of the priority list.

a2’s turn is next, and they like h3. a3 already owns that, so a3 is put to the priority list. This ‘combo’ is getting bigger!

a3 actually likes their own home, h3. That creates a cycle: h3 → a3 → h3 → ..., so a3 gets to keep h3.

a2 can’t point to h3 anymore, so it must point to its next favourite: h4. But that’s already owned by a4, who takes a2’s turn! Can’t a2 ever catch a break?

a4, surprisingly, likes h2. Now we have a proper cycle!

h2 → a2 → h4 → a4 → h2 → ...

So, we can make the following assignments:

a2 → h4

a4 → h2

a11 can’t point to h2 anymore, so they point to their next favourite, h16. Nobody owns that, so a11 is free to take it.

a11 → h16

a14, who is next, likes h8. That’s owned by a8, so they go in front.

a8 likes h12, which is free, so they get it. Now that h8is free, a14 can get h8. This is just like that chain from earlier.

a8 → h12

a14 → h8

a12 likes h14, which is free, so they can just take it.

a12 → h14

a16 likes h5, which is owned by a5, so a5 goes to the front of the priority list.

a5 likes h9, which is owned by a9, so a9 now goes to the front of the priority list.

a9 actually likes h11, which is free. That’s a big chain! All students get the houses they point at.

a9 → h11

a5 → h9

a16 → h5

Almost there! a10 likes h7, which is owned by a7, so a7 goes in-front of a10.

a7 actually likes their own home, forming a small cycle, so a7 gets to keep h7.

a7 → h7

Come on. Do you really need an explanation for this?

a10 → h10

Here’s the outcome of the algorithm! Phew... that took a while.

It should be called “You Waste Your Time, You Get The Same Thing As TTC”.

Random Serial Dictatorship Example

	Since this is the teachers allocation problem, why don’t we use the lecturers for this example? Enrico, Bahar, and Jie need to split the teaching load of their new module, Advanced Advanced Intelligent Agents, a.k.a Advanced Game Theory. They need to decide who teaches Nash Equilibria, Prisoners Dilemma, and Auctions. In Random Serial Dictatorship, we’d scramble the order of the lecturers, but for simplicity’s sake we’ll just use this order.
	First up is Enrico! His first choice is Prisoner’s Dilemma, so he is assigned to that. It’s scratched off everyone’s list, so nobody else can claim it.
	Next is Bahar! She can’t pick her favourite, Prisoner’s Dilemma, because it’s taken by Enrico. So, she’ll have to pick her next best, which is free: Nash Equilibria.
	Lastly, it’s Jie! He’d like Nash Equilibria, but it’s taken by Bahar. Next, he’d like Prisoner’s Dilemma, but that’s taken by Enrico. The only thing he can take is Auctions, so Jie is assigned to Auctions. That concludes this algorithm!

This is nice and all, but this is only one possible allocation out of many that RSD could possibly pick.
What’s the probability distribution of lecturers to subjects?
There’s 3 teachers, so there’s different orderings.
I’ve done the hard work for you and calculated the allocation matrices of each:

Enrico, Bahar, Jie

	sN	sP	sA
tE	0	1	0
tB	1	0	0
tJ	0	0	1

Enrico, Jie, Bahar

	sN	sP	sA
tE	0	1	0
tB	0	0	1
tJ	1	0	0

Bahar, Enrico, Jie

	sN	sP	sA
tE	1	0	0
tB	0	1	0
tJ	0	0	1

Bahar, Jie, Enrico

	sN	sP	sA
tE	0	0	1
tB	0	1	0
tJ	1	0	0

Jie, Enrico, Bahar

	sN	sP	sA
tE	0	1	0
tB	0	0	1
tJ	1	0	0

Jie, Bahar, Enrico

	sN	sP	sA
tE	0	1	0
tB	0	0	1
tJ	1	0	0

Now, we sum all the matrices up, and divide by how many there are: 6.

	s1	s2	s3
t1	1/6	4/6	1/6
t2	1/6	2/6	3/6
t3	4/6	0/6	2/6

Boom! We have our probability distribution of lecturers to subjects!

Simultaneous Eating Algorithm Example

Please welcome back our esteemed guests: Enrico, Bahar, and Jie, for their participation in this Simultaneous Eating Algorithm example.

The flight here was a long one, and now they’re hungry hungry! Luckily, we have some food for them. We have a Greggs veggie bake, a grilled cheese sandwich, and some onigiri (not jelly-filled doughnuts).

Everyone has preferences over these lovely dishes, and we want to split them up between everyone. We do this through an ‘eating’ algorithm. The proportion of food items everyone manages to eat is their allocation.

A few things before we start:

Each food item takes the same amount of time to eat
Everyone eats at the same rate
Below everyone is a timeline, which may help to visualise what’s going on. Red is Enrico, Blue is Bahar, and Green is Jie.

What are you all waiting for? Tuck in!

In this algorithm, everybody starts eating their favourite foods first. This means Enrico and Bahar start with the veggie bake, and Jie starts with the grilled cheese sandwich.

Time goes on, until Enrico and Bahar finish their veggie bake. Since they were both eating the same one (and, as I said before, everyone eats at the same rate), they both ate half each. That means Enrico is allocated 0.5 of the veggie bake, and Bahar is also allocated 0.5 of the veggie bake.

Jie is not done yet. He’s only eaten 0.5 of the sandwich, so he’s allocated 0.5 of the sandwich so far, but that may increase.

Since Enrico and Bahar are finished, they’ll move on to their next favourite food. Enrico will start eating the sandwich with Jie, and Bahar will start eating the onigiri on her own.

Before Enrico started eating the sandwich, Jie had already eaten 0.5 of it. That means Enrico and Jie had to share the other half of the sandwich between themselves.

Because of this, it took Jie and Enrico 0.25 time units to eat the rest of the sandwich. This means Enrico is allocated 0.25 for the sandwich, because he only managed to eat 25% of the whole thing, and Jie is allocated 0.75 for the sandwich, because he ate the first half (0.5) and the other 0.25 alongside Enrico.

While all of this is happening, Bahar is still happily eating her onigiri, and has gotten through 0.25 of it.

Enrico is now finished, so he’ll start eating the last item on his list: the onigiri. Jie will do the same, since Enrico and Bahar already polished off the veggie bake from before.

Before everyone started eating the onigiri, Bahar had already eaten 0.25 of it. So, that leaves 0.75 of the onigiri to pass around now. There’s three people eating it now, so everyone evenly eats 0.75 / 3 = 0.25 onigiri.

Bahar is allocated 0.5 onigiri, because she ate 0.25 before and 0.25 now. Enrico and Jie are allocated 0.25 onigiri, because they ate 0.25 while sharing with everyone.

The final allocations are as follows:

	fV	fS	fO
aE	2/4	1/4	1/4
aB	2/4	0/4	2/4
aJ	0/4	3/4	1/4

Proofs

Expected Minimum Valuation

So, you also want to know why the expected minimum valuation when two bidders’ valuations are drawn above is as well?
Bahar said it was easy, but I found it anything but.
Not even the Game Theory youtube guy gave a proper answer (not MatPat, the other one).
I searched for hours, and I finally found the answer.
Credit to Alex G. for his epic answer on the maths stack exchange, which really helped to understand this.

In general, to calculate the expected value in a continuous setting, you’d need to use a probability density function (PDF) :

But to get the expected value of the minimum valuation, we need a PDF of the minimum valuation.
What’s the PDF of the minimum valuation?
It’s a function that, given a possible minimum value, returns the relative likelihood that two valuations drawn will have that minimum value.
If that doesn’t make much sense, don’t worry, it’s not too important.
How do we get a PDF?
No... please don’t say File > Download > PDF document (.pdf).

A PDF is just the derivative of a corresponding cumulative distribution function (CDF) .
So to get the PDF of the minimum valuation, we need the CDF of the minimum valuation.
What’s the CDF of the minimum valuation?
It’s a function that, given a possible minimum value, returns the probability that a randomly drawn pair of valuations will have that minimum value or lower.
How do we get a CDF?
Luckily, it’s a bit easier to “get” a CDF than a PDF:

If you’re confused what this is, that’s a minimum value gotten from drawing two random valuations. This represents the probability that a minimum value gotten from two random valuations is less than or equal to our given value .
Now that we have a function to work with, let’s toy around with this:

Since and are drawn independently, we can split them up here:

Because and are drawn in the exact same range with the same distribution, these two probabilities here are actually the same, so let’s collect them:

and are uniformly distributed on , so we can rewrite this function as:

=		if
		if
	1	if

Now we can find the derivative of this function and get the PDF:

=		if
		otherwise

Now we can finally get the expected minimum value using our PDF!
Remember, it looks like this:

I’m not going to do the integral here, so I’ll let Mathway take over:

Hmm. It didn’t simplify fully. Awkward 😳

Boom! Now you know why the expected minimum valuation is .
Get ready to ace the AGT exam!
... or just the Optimal Auctions part of it.

Impossibility of DS Truthfulness Proof for SM

We have the following matchings:

There are two stable matchings: and .
Every stable matching mechanism must pick from either or .

Let’s say that the mechanism picks .
If declares that she prefers instead of , the mechanism will now only pick .

Therefore, will get matched with instead of and get a better matching!

Let’s cover the other case, where the mechanism picks .
If declares that she prefers instead of , the mechanism will now only pick .

Therefore, will get matched with instead of and get a better matching!

In either scenario, at least one agent can benefit by not reporting truthfully.
Hence, no stable matching mechanism exists for which truth-telling is a dominant strategy.

Not Examinable Stuff

Extensions of Stable Roommate (SR)

What if you have an odd number of agents, ?
In any matching, at least one agent has to go unmatched.
Even so, you could still get a stable matching! So long as there aren’t any blocking pairs.

If all lists in your phase-1 table are non-empty, then there are no stable matchings.
Why?

Proof by contradiction: let’s say that everyone’s list is non-empty in the phase-1 table, and there’s a stable matching to be found in phase 2.
Since everyone is taking part in phase 2, in the stable matching we find, everyone must have matchings.
However, there’s an odd number of agents: at least one person must go unmatched.
There is a contradiction! Therefore, if everyone’s preferences in the phase-1 table is non-empty, there cannot be any stable matchings.

If exactly one agent’s, say , preference list is empty in the phase-1 table, then:

cannot be matched in any stable matching
If there is a stable matching, nobody other than is unmatched
To check for stable matches, run phase 2 without .

What if some agents find others unacceptable?
This is the Stable Roommates with Incomplete Lists (SRI) problem.
After phase-1, there may be one or more agents with an empty preference list.

Any agent with an empty list cannot be matched in any stable matching.
Any agent with a non-empty list must be matched in every stable matching.

To check for stable matches, run phase 2 without the empty list agents.

What if we have ties?
This is the Stable Roommates with Ties (SRT) problem.
Like in SMT, we can define three different kinds of blocking pairs.
Again, we’ll focus on the definition where both agents must strictly prefer each other.
Unfortunately...

Theorem

(Ronn, 1990)

Deciding whether a stable matching exists, given an instance of SRT, is NP-complete.

Even if each preference list is:

strictly ordered, or
contains a tie of length 2 at the head

Size vs Stability

This isn’t examinable, so I’m going to skim the content here.
If you want to go into more detail, read the slides.

In SMTI, stable matchings can have different sizes.
The maximum-size stable matching can be, at most, twice the size of the minimum-size one (Manlove et al, 2002).
The problem of finding the maximum stable matching is called MAX SMTI, and it’s NP-hard (Iwama, Manlove et al, 1999).
MAX HRT is also NP-hard.
Minimisation problems are also NP-hard.

Given two functions and , if there are positive constants and such that for all .
An approximation algorithm has a performance guarantee , for some , if:

for any instance for minimisation problems, and
for any instance for maximisation problems.

... where is the measure of an optimal solution, and is the size of the solution produced by .

MAX HRT is not approximable within unless P = NP
MAX HRT is not approximable within assuming the Unique Games Conjecture.

It is approximable within though, which is what Kiraly’s 3/2 approximation algorithm does.

Summary of Kiraly’s algorithm

When a man is rejected by all women in his list, he is given a second chance and can propose to women on his list again one more time.

Preferences

For a man , and for two women and , we say that prefers to if:

either he prefers in the usual sense
or he is indifferent between the two, is engaged and is free

For a woman , and for two men and , we say that prefers to if:

either she prefers in the usual sense
or she is indifferent between the two, has a second chance (he is proposing to the women in his list for the 2nd time) and does not (he is proposing to the women in his list for the 1st time).

Proposals and rejections

An assigned woman accepts a new proposal from a man , and rejects her current partner , if:

either she prefers to her current partner, according to his new definition of prefers
or her current partner prefers some woman to , again according to his new definition of prefers (in this case, we call precarious)

When a woman rejects a man , and she is not precarious, and are deleted from each other’s lists.

For an example of this algorithm, see the slides.

Kiraly’s algorithm is not DS truthful.
The man-oriented Kiraly is not DS truthful for men.
We cannot achieve 3/2 approximation with another mechanism that is DS for men.
We can achieve 3/2 approximation with another mechanism that is DS for men and ties are only on one side of the market, but only if the ties are on the men’s side.

MAX SIZE MIN BP SMI is the problem of finding the matching with the minimum number of blocking pairs.

It’s NP-hard, even if every preference list is of length <= 3.
It’s not approximable within , for any , unless P = NP.
Solvable in polynomial time if each woman’s list is of length .

There’s even more problems, if you’re really interested:

Stable Marriage problem with Forbidden pairs and/or Forced pairs.
Balanced Stable Matchings
Stronger forms of stability when ties are allowed

Strong stability
Super stability
Social stability
...

My Matching Subset Tree

To conclude the matching algorithms section, I created a tree showing the relationships of all the matching algorithms talked about so far!
Each node is the set of all problems for that particular type.
Each filled arrow means “subset of”.
Each dotted arrow means “can be transformed to” (not all possible dotted lines are added; this is done to save space).

For example, “SM → SRI” means “SM is a subset of SRI”.

Here’s a cool little theorem: none of the stable matching mechanisms for any superset of SM or SR are DS truthful.
How do I know? We can prove this using proof by induction:

1. First, we define our base case.

We already know SM mechanisms are not DS truthful.
SR mechanisms are also not DS truthful because:

Proof by contradiction: Let’s say you have a DS truthful mechanism for SR.
SM problems can be transformed to SR.
We can construct a DS truthful SM mechanism by transforming it to an SR problem and running the DS truthful SR mechanism.
We know that there are no DS truthful SM mechanisms, so there is a contradiction!
Therefore, SR mechanisms can’t be DS truthful.

2. Now, our inductive step. Let’s define some problem X, where X mechanisms are not DS truthful.
Given some problem XY, Y mechanisms are not DS truthful:

Proof by contradiction: Let’s say there is a DS truthful Y mechanism.
Then we could construct a DS truthful X mechanism that just runs the DS truthful Y mechanism on the X problem.
We know that X mechanisms are not DS truthful, so there is a contradiction!
Therefore, Y mechanisms are not DS truthful.

Since both the base case and inductive step are proven to be true, by mathematical induction every superset of SM and SR do not have stable matching DS truthful mechanisms.

Let’s say that an exam question defines some new problem that SMTI is a subset of.
I don’t know... SMTIC, which is SMTI but with couples.
According to the above theorem, you already know it’s not DS truthful!

Secretary Problem with Dynamic Programming

The algorithm explained in this section is from this video and this paper.

Algorithm

For this example, we’ll set .
In this algorithm, we start by constructing a table:

1	2	3	4	5	6	7	8

The numbers on the top are the numbered candidates that we’re interviewing, from to .
The red row represents the probability that we’ll find the best candidate if we skip the column’s candidate.
The blue row represents the probability that this column’s candidate is the best candidate out of everyone, assuming it’s better than everyone we’ve seen before.
The green row is just the max value of the red and blue rows.

So, how do we fill in all these rows?
Let’s start with the blue row, because it’s the easiest.
The probability that a candidate is the best out of everyone, assuming they’re better than everyone before them, is .
Filling that out, we get:

1	2	3	4	5	6	7	8

0.125	0.25	0.375	0.5	0.625	0.75	0.875	1

Next, let’s do the red row.
The probability that we’ll find the best candidate if we skip this column’s candidate is split into two:

The next candidate is the best, and we either pick them or skip them, depending on which has higher probability of getting the best candidate (green row):
OR (plus)
The next candidate is not as good as ones we’ve seen, and we skip them: .

To calculate the red row, we need to do the green row at the same time. That’s easy though; it’s just the bigger value of the blue and red rows.

Thing is, the green row and the red row depend on each other. How are we going to calculate them?
As you can see, the red row depends on the row values to its right.
So if we set a ‘base case’ at the far right, we should be good!
When , it’s obvious that the probability of finding the best candidate when skipping should be 0, because if we skip the last candidate, we won’t get a candidate.
So we can set a base case like this:

1	2	3	4	5	6	7	8
							0
0.125	0.25	0.375	0.5	0.625	0.75	0.875	1
							1

Then, the red and green rows can be calculated:

1	2	3	4	5	6	7	8
0.410	0.410	0.410	0.380	0.318	0.232	0.125	0
0.125	0.25	0.375	0.5	0.625	0.75	0.875	1
0.410	0.410	0.410	0.5	0.625	0.75	0.875	1

As you can see, starting from , the green row picks the red values.
However, there reaches a ‘turning point’ where the green row starts picking the blue values.
That point is where our optimal lies!
The turning point is from to .
Therefore, the optimal is 3.

Pseudocode

This algorithm can be implemented using recursion, as can be seen in this pastebin.

The keep_going function is the red row.
The max_of function is the green row.
This program is used as follows:

$ python secretary.py [N]

If we cache the values of the red and green rows in dictionaries, we can use DP to make this more efficient, as can be seen in this pastebin.

Time Complexities

In the main notes, I said this algorithm has a exponential time complexity without DP.
Why?

For each call of optimal_k_with_i, we are calling keep_going.
So, what’s the time complexity of keep_going?
keep_going calls itself with i + 1, and max_of with i + 1.
max_of simply calls another keep_going with the same ‘i’ it was given it.
So, our execution tree looks kind of like:

You can kind of see that the number of keep_going (KG) nodes and max_of (MO) nodes increases exponentially with N (more specifically, a pattern).
Therefore, we’ve already got an time complexity for this one sub-tree of optimal_k_with_i.
Remember that we’re calling optimal_k_with_i N times, so our overall exponential time complexity is , which can be simplified to .

I also said this algorithm has a linear time complexity with DP.
Why?

We’re caching our values, so our trees don’t have to expand so much:

Each green node represents a function call that just uses the cached calculations.
The tree structure is no more! Now, at the start, we calculate all needed results of our two functions from to .
Since we’re calling two functions for each , this has a time complexity of .
Don’t forget that we’re calling optimal_k_with_i N times, so our overall time complexity is a linear , or .

Bipartite Matching

In bipartite matching, we have two sets: L and R.
Each node L is compatible with some nodes R, meaning L can be matched to compatible nodes, but not incompatible ones.
A matching is a subset of the edges, such that every node is connected to at most one edge.


A matching	Not a matching

There’s different definitions:

Maximal matching:

A matching that cannot be made larger by adding another edge

Maximum matching:

A matching that contains the largest possible number of edges

Perfect matching:

A matching that matches all vertices
Must have an even number of total vertices (L + R)

Maximum matchings are maximal...
... but maximal matchings are not maximum.

Red: maximum, green: maximal

Great! So, we have a bipartite graph, some constraints, and we want to find a maximum matching for it.
There’s a really nice polynomial time algorithm by Hopcroft and Karp 1973, using the concept of augmenting path?
It’s .

Wait! What if this problem was online?

What if we didn’t have the entire graph upfront?
We know L, but we don’t know R.
Each round, a new node in R is revealed, along with its neighbours in L (nodes in L that are compatible with v).
When we see a node , we have to either:

Pair with a node in
Don’t pair at all

Again, this decision cannot be cancelled or revoked later.

Our goal is still to construct the largest matching as possible.
To tie this in with our ad space problem, the L nodes are advertisers and the R nodes are keywords.

A Brief History of Bipartite Matching

Online bipartite matching was first studied in 1990, when online algorithms first became popular.

In the 21st century, web advertising became popular and proved to be a huge revenue generator.

Interests in online bipartite matching was rekindled: a lot of results were discovered and published within the last decade or so.

Did you find that interesting?

Eh, me neither.

We need some way of benchmarking these algorithms; some sort of quantisation.

Remember in the main notes when I said our greedy algorithm was ½ as good as the optimal one?
Let’s define a formal notion of that.
We could say an algorithm ALG is c-competitive if:

So our quantisation is the algorithm’s competitive ratio , or “the fraction of the number of matched nodes yielded by the optimal algorithm that our compared algorithm could achieve”.

Greedy Algorithm

For a quick refresher, the greedy algorithm assigns to any compatible node in as soon as it appears.
It’s equivalent to the greedy algorithm we used in the main notes.

Don’t let this algorithm anywhere

near the Food Allocation problem!

How good is it?

Competitive ratio,
It is ½-competitive.

Is that good?
Considering any deterministic algorithm is at least , we could do better.

Water Level Algorithm

When we match a node , we don’t have to fully match it.
We could partially match with many nodes in !
Decisions are no longer so discrete!
This is called Online Fractional Bipartite Matching.

The algorithm for this is the Water Level (WL) Algorithm.
Water level is a physical metaphor:

Each vertex is a container with capacity 1
Each vertex is a source of 1 unit of water

It works like this:

When a node arrives, drain water from to , always preferring the neighbour with the lowest current water level, until either:

All is full, or
is empty

Here’s a brief example:

Our first node arrives!

It’s neighbouring three L nodes, so we distribute water to each evenly.

Another node arrives!

It’s neighbouring an empty L node, and an L node we’ve already filled.

First, it fills the top node to 33%, then it fills the top and middle nodes evenly, until our R node runs out of water and both L nodes are 67%.

We keep going until everyone is full.
You get the idea.

How good is this algorithm?
It’s -competitive.
That’s not bad! That’s around .
It’s tight, meaning there really exists an instance of WL that returns a fractional matching of size times the maximum possible.
Do you want to see a proof of this?
Me neither, but it’s here, if you change your mind.

RANKING Algorithm

But what if we can’t give a fraction of an allocation?
Well, instead of the fraction being a portion of the allocation...
... what if the fraction was simply the ‘chance’ that the R node is allocated to that L node?
Introducing Online Randomised Bipartite Matching!

The RANKING algorithm [Karp, Vazirani, Vazirani, 1990] is a special transformation from WL, where the probability that a given edge is included in the matching plays the same role as its fractional value in the WL algorithm.
So, just think of it as the WL algorithm, but instead of fractionally partitioning the allocation between L nodes, those ‘fractions’ are probabilities of including that edge, and one of the possible edges are ‘drawn’ from those probabilities.

Well? How good is this?
It’s tightly -competitive.
So, it’s the same as WL, but it solves a different problem.

Can we get any higher than -competitive?
Alas, no...
No online algorithm, deterministic or randomised, has a competitive ratio better than for maximum bipartite matching.

BALANCE Algorithm

Let’s extend our problem a bit more.
Online b-matching: every node in L can be matched for at most times.

You can think of as like a “capacity” for L nodes.
You can also think of it like ‘budget’, but if everyone bid either:

£1 if they’re interested or ‘compatible’, or
£0 if they’re not interested

... for all keywords.

There’s a deterministic algorithm BALANCE [Kalyanasundaram and Pruhs, 2000] with competitive ratio for online b-matching.
Actually, it’s but it converges to for really large values of b.

Basically, when a node arrives, match it with a neighbour in with the highest remaining match “allowance” (the most free capacity).
If there’s more than one such node, pick any arbitrarily.

If we applied this algorithm to our example from the main notes, but tweaked slightly:

When the first 100 users send Nintendo queries, they are evenly distributed to Amazon and eBay, because they’re both interested and had nothing before.
When the next 100 users send PlayStation queries, they are only allocated to Amazon, because eBay has shown their disinterest by bidding £0.

The competitive ratio here was ¾, but the competitive ratio in general is 1-1/e.
So don’t expect this too often!

Factor-revealing LP Algorithm

BALANCE is cool, but what if we consider both our allowance AND our bid?
What is the best trade-off between the two for the best competitive ratio?
... huh? You think I know?
I don’t know. I just write the notes.
Luckily, there was some very smart people back in 2005 who do know:

The factor-revealing LP algorithm says that:

When a query arrives, allocate it to the bidder maximising:
Where:

is bidder ’s bid
is the fraction of ’s budget that has been spent so far

In other words, , where:

is the amount of money spent
is the total budget of

Theorem

Mehta, Saberi, Vazirani, Vazirani, FOCS 2005

The competitive ratio of the factor-revealing LP algorithm is , and it is optimal.

Fair Division

In Fair division, we have a cake that can be cut into slices.
We have agents, who want bits of the cake, and prefer certain parts of the cake more than others.
How do we split the cake so that we can distribute it fairly between everyone?

Mmmm cake

First up, we need a way of representing utility...

Utility Representation

Let’s say we have a rectangular cake, and we can split it at any length, from 0 to 1.

We can split this cake up by defining a range.
For example, if we wanted half of this cake starting from the beginning, we could do:

Where ‘S’ is our ‘segment’.

Each agent has a valuation function, , that represents how much the agent likes each part of the cake.

For example, if our agent likes parts of the cake near the end better than near the start:

Or, if our agent likes parts near the start than near the end:

Or, if our agent likes all parts of the cake equally:

To calculate the actual utility, , we need to find the integral of our valuation function, :

For example, using our first valuation function, if we wanted to find the utility of our agent for a slice between positions 0.4 and 0.6, we’d need to find the area under the graph:

The utility of an agent getting nothing is 0:

... and the utility of an agent getting everything is 1:

So, everything is normalised!

Fairness

What do we mean by a ‘fair’ assignment?
Here’s some properties we could strive for:

Proportionality

Everyone gets at least of the entire cake, according to their own utility / opinion.
for any agent

Envy-freeness

Everyone gets the largest (according to utility) piece of cake amongst pieces.
Equivalently, nobody wants to switch its own cake with others’ cake.
for any agent

Equitability

Everyone gets exactly the same utility as others, according to their own utility / opinion.
for any agent

Envy-freeness implies proportionality.

To prove this, we will use a proof by contradiction.
We’ll assume , but not .
So, these two equations must be true at the same time:

for all
for any

Let’s give this proof a setting: , and this is :

The segments go as follows:

Now, because this is envy-free, these two conditions hold:

In addition, the sum of the utility of agent 1 with all segments is 1:

Because that’s effectively like saying agent 1 is getting all the cake segments, which is the whole cake.
So, let’s split up the utilities evenly for now:

If all the utilities are thirds, they’ll all add up to 1.
However, we just said that is false for all agents, and .
So let’s try lowering and adjusting the values to make this right:

Wait! This breaks our assumption that , because now .
We can’t make both these two conditions true. Quite a contradiction!
We can do the same thing for .
Therefore, envy-freeness implies proportionality.

When , proportionality is equivalent to envy-freeness.

We already know that envy-freeness implies proportionality.
So, if we prove that proportionality implies envy-freeness, then we know that proportionality is equivalent to envy-freeness, too.
To prove this, we’ll use a proof by contradiction.
We’ll assume , but not .
Therefore, both of these must be true at the same time:

for all
for any

Like the previous proof, we’ll set up the sum to 1 equality, except here, :

We can get proportionality to work, but not not-envy-freeness.
It’s because both utilities are the same; the left one has to be smaller than the right one!
Let’s shift it down then:

Oh, man! Now our left utility isn’t greater than .
There’s no way to make agent 1 envious for S2 without lowering their utility for their own segment lower than a half.
There’s a contradiction!
We can do the same thing for .
Therefore, when , proportionality implies envy-freeness.
As we said before, envy-freeness implies proportionality.
With these two in mind, proportionality is equivalent to envy-freeness.

Mechanisms

Alright, that’s all cool.
Now we have the setting, and the representation, the only thing missing are the mechanisms.
How do we actually divide the cake and get these cool properties?

When , we can use I Cut, You Choose.
Basically, agent 1 cuts, then agent 2 chooses.
It’s best for agent 1 to cut fairly, because if they don’t cut fairly, agent 2 will choose the bigger share.
This algorithm is envy-free (and therefore, proportional, as you know).
We only need to cut once, and the portions can be continuous.

When , there’s a whole range of protocols we can use.
For when there’s:

Discrete cake cuts

(must cut at certain spaced-out distances)

Continuous cake cuts

(can cut at any arbitrary distance)

Steinhaus 1943

Selfridge-Conway 1960, 1993

Brams-Taylor 1995 (unbounded cuts)

Aziz-Mackenzie 2015 (extendable to any , bounded cuts)

Stromquist 1980

Steinhaus is proportional only, but the rest are envy-free AND proportional.
Also, we’d ideally want to minimise the number of cuts needed.

Does a fair allocation always exist?

Well? Does it?
I’m not quite sure. But you can find out!
Have you ever heard of Sperner’s lemma?

Every triangulation of an n-dimensional simplex satisfying Sperner colouring contains a fully coloured simplex.

Uhhh...
Anyway, we can use Sperner’s lemma and triangulation with our cake-cutting problem.
How?
I won’t go into the full details in these notes, but if you want to know (or if you don’t even know what Sperner’s lemma is), check out this 15-minute video by Mathologer.
In the video, he uses rent instead of cake, but the concepts are still the same.
I recommend it; he’s good!

Let’s look at two of the mechanisms above and see what they do.
In Steinhaus’ algorithm:

Agent 1 cuts the cake into three even pieces.

If there are two parts that are worth at least ⅓ utility to agent 2, then:

All three agents select pieces in the order 3,2,1 (agent 3 picks first, then agent 2, then agent 1).
Otherwise, agent 2 marks the two small pieces as “bad”.

If agent 2 just marked some cakes as bad, then it’s agent 3’s turn:

If two pieces are worth at least ⅓ to agent 3, then they all select pieces in the order 2,3,1.
Otherwise, agent 3 marks two small pieces as “bad”.

If agent 2 and 3 marked cakes as bad, then:

Agent 1 takes the piece that has two “bad” marks.
Other two pieces are merged into one portion, and agents 2 and 3 split it using You Request My Cake, I Get Your Turn I Cut, You Choose.

Remember, this algorithm is proportional, but not envy-free.

In Selfridge-Conway’s algorithm, where :

Agent 1 cuts the cake into three equal pieces.

Agent 2 trims the largest piece to be equal to the 2nd largest (according to their utility, ofc).

Now we have a trimmed piece, and a small trimming piece that we put aside for now.
Agent 3 chooses one piece first, then agent 2, then agent 1.

If agent 3 does not choose the trimmed piece, then agent 2 has to choose it (to ensure agent 1 doesn’t get the trimmed piece).

Now get out that small trimming piece; the one we put aside.
Call the agent (must be either 2 or 3) who chose the trimmed piece T (in the picture examples, it’s 2), and the other one NT.
Ask NT to cut that small trimming piece into three equal pieces (according to their utility again).

T, agent 1, and NT choose in order.

If that was hard to follow, listen to Dr Hannah Fry’s explanation of it on Numberphile.
It’s entertaining, and won’t take long!

We can design either deterministic or randomised cake cutting mechanisms.

For deterministic algorithms:

Assume that the agents have piecewise uniform valuations, then there is a deterministic algorithm that is:

Truthful
Proportional
Envy-free
Polynomial-time.

This relates to the Probabilistic Serial mechanism (which, ironically, uses the eating algorithm).

For randomised algorithms:

Assume that the agents have piecewise uniform valuations, then there is a randomised algorithm that is:

Truthful in expectation
Universally envy-free
Universally propotional