Topic 2

Question 1

Blocking Pair

Answer 1

A pair of a leader and follow who are not currently matched but would each prefer each other over their assigned partners

Question 2

Stable Matching

Answer 2

A matching with no blocking pair

Question 3

Gale-Shapley Algorithm

Answer 3

Always finds a stable matching in polynomial time

Question 4

Candidates

Answer 4

The agents on the other side of markets
- Followers are the candidates to leaders
- Leaders are the candidates to followers

Question 5

Achievable Candidates

Answer 5

Two candidates are achievable if their exists a stable matching in which they are matched

Question 6

Best Achievable Partner

Answer 6

The most preferred candidate from all those who are achievable

Question 7

Optimal Matching

Answer 7

A matching where everyone gets their best achievable partner

Question 8

Pessimal Matching

Answer 8

A matching where everyone gets their worst achievable partner

Question 9

Preference Truncating

Answer 9

Falsely declare an acceptable partner as unacceptable to achieve a better matching

Question 10

Preference Permuting

Answer 10

Misreporting preference order

Question 11

Approximate Truthfulness

Answer 11

In practice, very few agents can benefit from submitting false benefits