Transcript Theorem

Mechanism Design without
Money
Lecture 12
1
Individual rationality and efficiency: an
impossibility theorem with a (discouraging)
worst-case 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
6.8 18.37 35.42 49.3 63.68 81.43 97.82 109.01 121.81 144.09 160.74
Efficient, k=3 6.89 18.67 35.97 49.75 64.34 81.83 98.07 109.41 122.1 144.35 161.07
4
But the cost of not having IR could be very high if it
causes centralized matching to break down
5
But current mechanisms aren’t 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 doesn’t matter – you always
care about the future
• Can work for every distribution of patients
10
Voting
11
Terminology
• Agent
– Sometimes assume odd
number of agents to
reduce ties
• Vote
– Total order over
outcomes
• Voting rule
– Social choice: mapping of
a profile onto a winner(s)
– Social welfare: mapping
of a profile onto a total
ordering
• 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 May’s 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 I’ll vote for my second
favourite”
Voting rules: plurality with runoff
• Two rounds
– Eliminate all but the 2
candidates with most
votes
– Then hold a majority
election between these 2
candidates
• Consider
– 25 votes: A>B>C
– 24 votes: B>C>A
– 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
• Consider again
– 25 votes: A>B>C
– 24 votes: B>C>A
– 46 votes: C>A>B
• C wins easily
• Two voters don’t vote
– 23 votes: A>B>C
– 24 votes: B>C>A
– 46 votes: C>A>B
• Different result
– 1st round: A knocked out
– 2nd round: B>C by 47:46
– B wins
Voting rules: single transferable vote
• STV
– If one candidate has >50%
vote then they are
elected
– Otherwise candidate with
least votes is eliminated
– Their votes transferred
(2nd placed candidate
becomes 1st, etc.)
• Identical to plurality
with runoff for 3
candidates
• Example:
–
–
–
–
–
39 votes: A>B>C>D
20 votes: B>A>C>D
20 votes: B>C>A>D
11 votes: C>B>A>D
10 votes: D>A>B>C
– Result: B wins!
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, <s1,..,sm>
– Candidate scores si for each vote in ith position
– Candidate with greatest score wins
• Generalizes number of rules
– Borda is <m-1,m-2,..,0>
– 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
• Coomb’s 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, we’ll be able to
prove impossibility results (no voting rule has this
combination of desirable properties)
May’s theorem
• Some desirable
properties of voting rule
– Anonymous: names of
voters irrelevant
– Neutral: name of
candidates irrelevant
May’s 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
May’s 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.
680–68
– Since these properties are uncontroversial, this
about decides what to do with 2 candidates!
May’s 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
May’s 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)
May’s 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.
Condorcet’s 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)
Arrow’s 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
Arrow’s 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
Arrow’s theorem
• Non-dictatorial
– Dictator is voter whose
vote is the result
– Not generally considered
to be desirable!
Arrow’s 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 Arrow’s 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 Arrow’s 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 Arrow’s 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 Arrow’s 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 Arrow’s 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 Arrow’s 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 Arrow’s 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 Arrow’s 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 ij and jk and ik we can create a cycle:
– i prefers A to C
– k prefers C to B
– j prefers B to A
• Similar argument for ij=k, i=j  k, ji=k
53
Arrow’s 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
• Arrow’s 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
2-ways
450
3-ways
400
2-ways & chain
350
3-ways & chain
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
170
3-ways
150
2-ways & chain
130
3-ways & chain
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
Waiting Time
295
290
285
280
275
270
265
260
255
250
240
220
200
180
160
140
120
100
1D
1W
2W
1M
3M
6M
1Y
1D
1W
2W
1M
3M
6M
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
1Y
Match the pair right away?
Online:
 Amatch
H-node
edge
each remove cycles when formed.
theforms
arrivedan
node
to with
a neighbor;
node u of U with probability ξ/n.
 A L-node forms an edge with each
Lemma: the online algorithm matches
node
of U when
with probability
π
almost
all u
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).


Mostpc/n
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
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
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
𝑝𝐻 = ξ𝑛−1+𝜀 :
Theorem:
1. If Δ ≤ 𝑛1−2𝜀 < 1/𝑝𝐻 ,
M(Δ) = M(1) + o(n)
2. If Δ = α/𝑝𝐻
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:
Low sensitivity patients (L-patients).
pξ/n
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 depthone trees.
M(Δ) = M(1) + o(n).
71
Proof Ideas
In H-L graph, Δ = αn:
 Find f(α)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,
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