Mechanism Design without Money Lecture 12 1 Individual rationality and efficiency: an impossibility theorem with a (discouraging) worstcase bound For every k> 3, there exists a compatibility graph such that no k-maximum allocation which is also individually rational matches more than 1/(k-1) of the number of nodes matched by a k-efficient allocation. 2

Proof (for k=3) a3 a1 e 3 a2 c b d

Cost of IR is very small - Simulations No. of Hospitals IR,k=3 2 4 6 8 10

12 14 16 18 20 22 18.3 35.4 63.6 81.4 97.8 109.0 121.8 144.0 160.7 6.8 7 2 49.3 8

3 2 1 1 9 4 6.8 18.6 35.9 49.7 64.3 81.8 98.0 109.4 144.3 161.0 Efficient, k=3 9 7 7 5 4 3 7

1 122.1 5 7 4 But the cost of not having IR could be very high if it causes centralized matching to break down 5 But current mechanisms arent IR for hospitals Current mechanisms: Choose (~randomly) an efficient allocation. Proposition: Withholding internal exchanges can (often) be strictly better off (non negligible) for a hospital regardless

of the number of hospitals that participate. A-O O-A And hospitals can withhold individual overdemanded pairs 6 What if we have a prior? Infinite horizon In each timestep, a hospital samples its patients from some known distribution Then there exists a truthful mechanism with efficiency 1 o(1)

7 Matching Initially the hospital has zero credits In the beginning of the round, if the hospital has zero credits, each patients enters the match with probability 1 1/k1/6 For each positive credit, the hospital increases this probability by 1/k2/3 and the credit is gone For each negative credit, the hospital decreases this probability by 1/k2/3 and the credit is gone. The probability is always > 8 Gaining credit

For each patient over k, the hospital gets 1 credit For each patient below k, the hospital looses 1 credit These credits only affect the next rounds 9 Proof idea Hiding a patient can give an additive advantage, but causes a multiplicative loss Number of credit doesnt matter you always care about the future Can work for every distribution of patients 10

Voting 11 Terminology Agent Voting rule Social Sometimes choice: assume mapping oddofnumber

a profile ofonto agents a winner(s) to reduce ties Social welfare: mapping of a profile onto a total ordering Vote Total order over outcomes Profile Vote for each agent , Extensions include indifference incomparability, incompleteness Voting rules: plurality

Otherwise known as majority or first past the post Candidate with most votes wins With just 2 candidates, this is a very good rule to use (See Mays theorem) Voting rules: plurality Some criticisms Ignores preferences other than favourite Similar candidates can split the vote Encourages voters to vote tactically My candidate cannot win so Ill vote for my second favourite

Voting rules: plurality with runoff Consider Two rounds 25 votes: A>B>C Eliminate all but the 2 candidates with most votes 24 votes: Then

holdB>C>A a majority election between these 2 candidates 46 votes: C>A>B 1st round: B knocked out 2nd round: C>A by 70:25 C wins Voting rules: plurality with runoff Some criticisms Requires voters to list all preferences or to vote twice Moving a candidate up your ballot may not help them (monotonicity) It can even pay not to vote! (see next slide)

Voting rules: plurality with runoff Two voters dont vote Consider again 23 25 votes: votes: A>B>C

A>B>C 24 24 votes: votes: B>C>A B>C>A 46 votes: C>A>B 46 votes: C>A>B Different result C wins easily 1st round: A knocked out 2nd round: B>C by 47:46 B wins Voting rules: single transferable vote

STV Example: If candidate has >50% 39one votes: A>B>C>D

vote then they are 20 votes: B>A>C>D elected 20 votes: B>C>A>D Otherwise candidate with 11 votes: least votesC>B>A>D is eliminated Their votes transferred

10 votes: D>A>B>C (2nd placed candidate becomes 1st, etc.) Result: B wins! Identical to plurality with runoff for 3 candidates Voting rules: Borda Given m candidates ith ranked candidate score m-i Candidate with greatest sum of scores wins

Example 42 votes: A>B>C>D 26 votes: B>C>D>A 15 votes: C>D>B>A 17 votes: D>C>B>A B wins Jean Charles de Borda, 1733-1799 Voting rules: positional rules

Given vector of weights, Candidate scores si for each vote in ith position Candidate with greatest score wins Generalizes number of rules Borda is Plurality is <1,0,..,0> Voting rules: approval Each voters approves between 1 and m-1 candidates Candidate with most votes of approval wins Some criticisms Elects lowest common denominator? Two similar candidates do not divide vote, but can introduce problems when we are electing multiple

winners Voting rules: other Cup (aka knockout) Tree of pairwise majority elections Copeland Candidate that wins the most pairwise competitions Bucklin If one candidate has a majority, they win Else 1st and 2nd choices are combined, and we repeat Voting rules: other

Coombs method If one candidate has a majority, they win Else candidate ranked last by most is eliminated, and we repeat Range voting Each voter gives a score in given range to each candidate Candidate with highest sum of scores wins Approval is range voting where range is {0,1} Voting rules: other Maximin (Simpson) Score = Number of voters who prefer candidate in worst pairwise election Candidate with highest score wins

Veto rule Each agent can veto up to m-1 candidates Candidate with fewest vetoes wins Inverse plurality Each agent casts one vetor Candidate with fewest vetoes wins Voting rules: other Dodgson Proposed by Lewis Carroll in 1876 Candidate who with the fewest swaps of adjacent preferences beats all other candidates in pairwise elections NP-hard to compute winner!

Random Winner is that of a random ballot Voting rules So many voting rules to choose from .. Which is best? Social choice theory looks at the (desirable and undesirable) properties they possess For instance, is the rule monotonic? Bottom line: with more than 2 candidates, there is no best voting rule Axiomatic approach

Define desired properties E.g. monotonicity: improving votes for a candidate can only help them win Prove whether voting rule has this property In some cases, as we shall see, well be able to prove impossibility results (no voting rule has this combination of desirable properties) Mays theorem Some desirable properties of voting rule Anonymous: names of voters irrelevant Neutral: name of candidates irrelevant

Mays theorem Another desirable property of a voting rule Monotonic: if a particular candidate wins, and a voter improves their vote in favour of this candidate, then they still win Non-monotonicity for plurality with runoff 27 votes: A>B>C 42 votes: C>A>B 24 votes: B>C>A Suppose 4 voters in 1st group move C up to top 23 votes: A>B>C 46 votes: C>A>B 24 votes: B>C>A

Mays theorem Thm: With 2 candidates, a voting rule is anonymous, neutral and monotonic iff it is the plurality rule May, Kenneth. 1952. "A set of independent necessary and sufficient conditions for simple majority decisions", Econometrica, Vol. 20, pp. 68068 Since these properties are uncontroversial, this about decides what to do with 2 candidates! Mays theorem Thm: With 2 candidates, a voting rule is anonymous, neutral and monotonic iff it is the plurality rule Proof: Plurality rule is clearly anonymous, neutral and monotonic Other direction is more interesting

Mays theorem Thm: With 2 candidates, a voting rule is anonymous, neutral and monotonic iff it is the plurality rule Proof: Anonymous and neutral implies only number of votes matters Two cases: N(A>B) = N(B>A)+1 and A wins. By monotonicity, A wins whenever N(A>B) > N(B>A) Mays theorem Thm: With 2 candidates, a voting rule is anonymous, neutral and monotonic iff it is the plurality rule Proof: Anonymous and neutral implies only number of votes matters Two cases:

N(A>B) = N(B>A)+1 and A wins. By monotonicity, A wins whenever N(A>B) > N(B>A) N(A>B) = N(B>A)+1 and B wins Swap one vote A>B to B>A. By monotonicity, B still wins. But now N(B>A) = N(A>B)+1. By neutrality, A wins. This is a contradiction. Condorcets paradox Collective preference may be cyclic Even when individual preferences are not Consider 3 votes A>B>C

B>C>A C>A>B Majority prefer A to B, and prefer B to C, and prefer C to A! , Marie Jean Antoine Nicolas de Caritat marquis de Condorcet (1743 1794) Condorcet principle Turn this on its head Condorcet winner Candidate that beats every other in pairwise elections In general, Condorcet winner may not exist When they exist, must be unique

Condorcet consistent Voting rule that elects Condorcet winner when they exist (e.g. Copeland rule) Condorcet principle Plurality rule is not Condorcet consistent 35 votes: A>B>C 34 votes: C>B>A 31 votes: B>C>A B is easily the Condorcet winner, but plurality elects A Condorcet principle Thm. No positional rule with strict ordering of weights is Condorcet consistent Proof: Consider

3 votes: A>B>C 2 votes: B>C>A 1 vote: B>A>C 1 vote: C>A>B A is Condorcet winner Condorcet principle Thm. No positional rule with strict ordering of weights is Condorcet consistent Proof: Consider

3 votes: A>B>C 2 votes: B>C>A 1 vote: B>A>C 1 vote: C>A>B Scoring rule with s1 > s2 > s3

Score(B) = 3.s1+3.s2+1.s3 Score(A) = 3.s1+2.s2+2.s3 Score(C) = 1.s1+2.s2+4.s4 Hence: Score(B)>Score(A)>Score(C) Arrows theorem We have to break Condorcet cycles How we do this, inevitably leads to trouble A genius observation Led to the Nobel prize in economics Arrows theorem

Free Every result is possible Unanimous If every votes for one candidate, they win Independent to irrelevant alternatives Result between A and B only depends on how agents preferences between A and B Monotonic Arrows theorem Non-dictatorial Dictator is voter whose vote is the result

Not generally considered to be desirable! Arrows theorem Thm: If there are at least two voters and three or more candidates, then it is impossible for any voting rule to be: Free Unanimous Independent to irrelevant alternatives Monotonic Non-dictatorial Proof of Arrows theorem If all voters put B at top or bottom then result can only have B at top or bottom

Suppose not the case and result has A>B>C By IIA, this would not change if every voter moved C above A: B>A>C => B>C>A B>C>A => B>C>A A>C>B => C>A>B C>A>B => C>A>B Each AB and BC vote the same! Proof of Arrows theorem

If all voters put B at top or bottom then result can only have B at top or bottom Suppose not the case and result has A>B>C By IIA, this would not change if every voter moved C above A By transitivity A>C in result But by unanimity C>A B>A>C => B>C>A B>C>A => B>C>A A>C>B => C>A>B C>A>B => C>A>B

Proof of Arrows theorem If all voters put B at top or bottom then result can only have B at top or bottom Suppose not the case and result has A>B>C A>C and C>A in result This is a contradiction B can only be top or bottom in result Proof of Arrows theorem If all voters put B at top or bottom then result can only have B at top or bottom Suppose voters in turn move B from bottom to top Exists pivotal voter from whom result changes from B at bottom to B at top

Proof of Arrows theorem If all voters put B at top or bottom then result can only have B at top or bottom Suppose voters in turn move B from bottom to top Exists pivotal voter from whom result changes from B at bottom to B at top B all at bottom. By unanimity, B at bottom in result B all at top. By unanimity, B at top in result By monotonicity, B moves to top and stays there when some particular voter moves B up Proof of Arrows theorem If all voters put B at top or bottom then result can only have B at top or bottom

Suppose voters in turn move B from bottom to top Exists pivotal voter from whom result changes from B at bottom to B at top Pivotal voter is dictator (need to show) Proof of Arrows theorem Pivotal voter is dictator between A and C Consider profile when pivotal voter has just moved B to top (and B has moved to top of result) For any AC, let pivotal voter have A>B>C By IIA, A>B in result as AB votes are identical to profile just before pivotal vote moves B (and result has B at bottom) By IIA, B>C in result as BC votes are unchanged Hence, A>C by transitivity

Proof of Arrows theorem Each two alternatives {A,C} have a voter which dictates which one of them will be higher. Let i be the dictator for {A,C} Let j be the dictator for {A,B} Let k be the dictator for {B,C} If ij and jk and ik we can create a cycle: i prefers A to C k prefers C to B j prefers B to A Similar argument for ij=k, i=j k, ji=k 53 Arrows theorem

How do we get around this impossibility Limit domain Only two candidates Limit votes Single peaked votes Limit properties Drop IIA Single peaked votes In many domains, natural order Preferences single peaked with respect to this order

Examples Left-right in politics Cost (not necessarily cheapest!) Size Single peaked votes There are never Condorcet cycles Arrows theorem is escaped There exists a rule that is Pareto Independent to irrelevant alternatives Non-dictatorial Median rule: elect median candidate Candidate for whom 50% of peaks are to left/right

What about dynamics? What is the tradeoff between waiting and number of matches? Dynamic matching in dense graphs (Unver, ReStud,2010). Matching over time *Simulation results using 2 year data from NKR Matches 550 500 450 2-ways

3-ways 2-ways & chain 3-ways & chain 400 350 300 1 5 10 20

32 64 100 260 520 1041 Waiting period between match runs In order to gain in current pools, we need to wait probably too long On average 1 pair every 2 days arrived over the two years*

59 Matching over time *Simulation results using 2 year data from NKR Matches high PRA 230 210 190 2-ways 3-ways 2-ways & chain 3-ways & chain 170 150 130

110 90 1 5 10 20 32 64 100

260 520 1041 In order to gain in current pools, we need to wait probably too long On average 1 pair every 2 days arrived over the two years* 60 Matching over time *Simulation results using 2 year data from NKR Matches 295 290

285 280 275 270 265 260 255 250 Waiting Time 240 220 200 180 160 140

120 1D 1W 2W 1M 3M 6M 1Y

100 1D 1W 2W 1M 3M In order to gain in current pools, we need to wait probably too long On average 1 pair every 2 days arrived over the two years* 61

6M 1Y ?Match the pair right away Online ::Online A H-node forms an edge with each remove cycles when formed match the the arrived arrived node node to to aa neighbor; neighbor; ..match

remove cycles when formed node u of U with probability /n. A L-node forms an edge with each Lemma: the online algorithm matches node u of Uwhen with probability almost all pairs p is a constant and n is large enough (even with just 2way cycles) Either a sparse finite horizon model or an infinite horizon model and analyze steady state

62 Arriving pair Dynamic matching in dense-sparse graphs n nodes. Each node is L w.p. q<1/2 and H w.p. 1-q . incoming edges to L are drawn w.p . incoming edges to L are drawn w.p L H 63 Dynamic matching in dense-sparse graphs

n nodes. Each node is L w.p. q<1/2 and H w.p. 1-q . incoming edges to L are drawn w.p . incoming edges to L are drawn w.p . At each time step 1,2,, n, one node arrives L H 64 Heterogeneous Dynamic Model (PRA). PRA determines the likelihood that a patient cannot receive a kidney from a blood-type compatible donor. PRA < 79: Low sensitivity patients (L-patients).

80 < PRA < 100: High sensitivity patients (H-patients). Most blood-type compatible pairs that join the pool have H-patients. pc/n Distribution of High PRA patients in the pool is different from the population PRA. 2 65 Chunk Matching in a heterogeneous graph :At time steps , 2, , n .Find maximum matching in H-L; remove the matched nodes

.Find maximum matching in L-L; remove the matched nodes 66 Chunk Matching in a heterogeneous graph .Chunk matching finds a maximum matching at time steps , 2, , n M() - expected number of matched pairs at time n . Theorem (Ashlagi, Jalliet and Manshadi): When matching only 2way cycles: 1. If = o(n), M() = M(1) + o(n) 2. = n, then n, then M() = M(1) + f(q,p)n for strictly increasing f()>0.

67 Chunk Matching in a heterogeneous graph When matching 2 and 3-way cycles: 1. If = () M() = M(1) + f(q,p) (n) (formally this is still a conjecture) 68 Denser Pools : :Theorem /, If < 1. 1 M() = M(1) + o(n)

/If = n, then . 2 M() = M(1) + f(q)n .for strictly increasing f()>0 Need to wait less time to gain If the graph is dense (large) no need to wait at all 69 Proof Ideas Special structure: Sparse H-L and dense L-L. (PRA). PRA determines the likelihood that a patient cannot receive a kidney from a blood-type compatible donor. PRA < 79:p/n Low sensitivity patients (L-patients). 80 < PRA < 100: High sensitivity patients (H-patients).

Most blood-type compatible pairs that join the pool have H-patients. Distribution of High PRA patients in the pool is different from the population PRA. 2 Compare the number of H-L matchings. 70 Proof Ideas In H-L graph, = o(n): No edge in the residual graph. arrived chunk

Tissue-type compatibility: Percentage Reactive Antibodies (PRA). PRA determines the likelihood that a patient cannot receive a kidney from a blood-type compatible donor. PRA < 79: Low sensitivity patients (L-patients). 80 < PRA < 100: High sensitivity patients (H-patients). residual graph Most blood-type compatible pairs that join the pool have H-patients. Distribution of High PRA patients in the pool is different from the population PRA. Decision of online and chunk matching are the same on depth-one trees. M() = M(1) + o(n).

71 Proof Ideas In H-L graph, = n:n: Find f(n, then )n augmenting paths to the matching obtained by online. Given M the matching of the online scheme: h1 l1 l2 Chunk matching would choose (l1,h1) and (l2,h2). M() = M(1) + f(n, then )n,

72 h2 Chunk Matching in a heterogeneous graph M() - expected number of matches using only 2-ways MC() - expected number of using 2-ways and allowing an unbounded chain . Theorem (Ashlagi, Jalliet and Manshadi): MC(1) = M(1) + f(q)n 73