生活中的机制设计学习重点

1、VotingThe point is that whether a voting rule is immune to a paradox or not.The outcome is a social ranking (or a winner) of the candidates.u Important voting rulesØ Condorcet Rule: A candidate who defeats every competitor in one-to-one confrontations.Ø Plurality Rule: The candidate who is

2、 ranked first by the voters the most times is the winner.The Plurality rule may select a Condorcet loserØ Instant Runoff Rule: (1) Run a plurality vote. If a candidate receives a majority, then he is the winner. Otherwise, move to the second round. (2) A runoff between the top two candidates fr

3、om the first round.The Instant Runoff rule never selects a Condorcet loser. While it may not select the Condorcet winner.Ø Sequential Runoff Rule: (1) Run a plurality vote. If a candidate receives a majority, then he is the winner. Otherwise, eliminate the candidate who is ranked first the leas

4、t times and move to the next round. (2) Repeat the process.The Sequential Runoff rule never selects a Condorcet loser. While it may not select the Condorcet winner.Ø Borda Rule: Suppose that there are m candidates. A candidate gets m k points from a voter if he is ranked k-th by the voter. The

5、candidate with the highest total number of points is the winner.Borda Rule never selects a Condorcet loser. While it may not select the Condorcet winner.Ø Black Rule: (1) If there is a candidate who is a Condorcet winner, then he wins. (2) If not, the candidate with the highest Borda score wins

6、.Ø Copeland Rule: The candidate who beats the highest number of other candidates in one-to-one confrontations is the winner.Black Rule and Copeland Rule can always selects the Condorcet winner when one existsØ Approval Rule: Each voter divides the candidates into two categories, good and b

7、ad, and casts a vote for each good candidate. The candidate with the most votes is the winner.u Voting paradox is where the outcome is not what we think it should be. A “good” voting rule should be immune to voting paradoxes.Ø Condorcet winner paradox: There exists a Condorcet winner, but a dif

8、ferent candidate is declared the winner.Ø Absolute majority paradox: There is a candidate who is ranked first by a majority, but a different candidate is declared the winner.If a voting rule is immune to the Condorcet winner paradox, then it is immune to the absolute majority paradox.Ø Con

9、dorcet loser paradox: There exists a Condorcet loser, and he is declared the winner.Ø Absolute loser paradox: There is a candidate who is ranked last by a majority, and he is declared the winner.If a voting rule is immune to the Condorcet loser paradox, then it is immune to the absolute loser p

10、aradox.Ø Lack of monotonicity paradox: (1) Initially, candidate a is the winner. (2) If some voters move candidate a to a higher position in their rankings, a different candidate is now declared the winner.Ø No-show paradox: (1) Initially, candidate a is the winner. (2) If some voters who

11、ranked candidate b higher than candidate a quit, candidate b is now declared the winner.Ø Multiple-districts paradox: (1) Initially, the voters are divided into two distinct districts. Candidate a is the winner for both districts. (2) If the two districts are combined, a different candidate is

12、now declared the winner for the entire population of voters.u Strategic manipulationØ Strategy-Proofness: A voting rule is strategy-proof if no voter can ever benefit from lying (a more preferred candidate is selected) about his ranking of the candidates.Ø Group strategy-proofness: A votin

13、g rule is group strategy-proof if no group of voters can ever benefit from jointly lying about their rankings of the candidates.For the case of two candidates, there is some democratic voting rule that is strategy-proof. Unfortunately, for the case of three or more candidates, there is not.u Gibbard

14、-Satterthwaite theoremØ Ontoness: A voting rule is onto if it is possible for any of the candidate to win, given the right ranking profile. (If a candidate is top-ranked by all the voters, he/she should be the winner.)Ø Dictatorship: A voting rule is dictatorial if there is a voter whose m

15、ost preferred candidate is always the winner. In other words, only one voters opinion matters.Ø Theorem 1: If there are at least three candidates, any strategy-proof and onto voting rule is dictatorial.Ø Corollary 2: If there are at least three candidates, any onto and non-dictatorial voti

16、ng rule is manipulable.PluralityInstant RunoffSequential RunoffBorderBlackCopelandApprovalCondorcet winner paradox(4)-+-Absolute majority paradox(4)+-+-Condorcet loser paradox(4)-+-Absolute loser paradox(4)-+-Lack of monotonicity paradox(5)+-+No-show paradox(4)+-+-+Multiple-districts paradox（4）+-+-+

17、Special solution:3.84 1 1 1A b c dB c b b5.24 2 3 1A b c dB c d cC d b dD a a aMarriage ProblemThe point is Deferred Acceptance, stability and strategy-proofness.An outcome is a match of men and women, such that each person is matched to a person of the opposite gender or a man is matched to a woman

18、 only if she is also matched to him. Two sides have preferences over each other.u StablityØ A blocking pair for a match is a pair of man and woman such that they prefer each other to their current partners.Ø A match is stable if there is no blocking pair for the match.Ø A stable match

19、 always exist.Ø We can find a stable match with deferred acceptance mechanism.Ø The stable match is not unique because there may be several stable matches.Ø Starting from an arbitrary match, there exists a path to stability by satisfying blocking pairs. Although not every path works,

20、there exists at least one path that works. And depending on the path, the final match could be any stable match.u Men-proposing deferred acceptance mechanismØ Theorem 1: The men-proposing deferred acceptance mechanism always produces a stable match.u Strategy-proofnessØ A matching mechanis

21、m is strategy-proof is no one can ever benefit from lying (be matched to a more preferred partner) about his/her preferences.Ø Theorem 2: The men-proposing deferred acceptance mechanism is strategy-proof for men, but is not strategy-proof for women. Because whichever side we discuss from, the o

22、ther side always can benefit from lying.Ø Theorem 3: There is NO matching mechanism that is both stable and strategy-proof.House Allocation and Housing MarketThe point is mechanisms, core, efficiency, and strategy-proofnessu House AllocationØ In house allocation, the houses are publicly ow

23、ned and only one side has preferences. So envy is inevitable. However, no person can firmly justify his/her envy. Therefore, fairness (stability) is less relevant in this context. Then in this case, we are interested in two properties: Efficiency and Strategy-proofness.Ø Sequential priority rul

24、esProposition 1: The sequential priority rules are efficient and strategy-proof.u Housing marketØ In housing market, the houses are privately owned. We are interested in two properties: Strategy-proofness and core² Core: there exists no group of people that blocks the assignment. (Blocking

25、: from their initial endowments, there is an assignment among themselves that they prefer to the current assignment. Proposition 2: If an assignment is in the core, then it is efficientØ Top trading cycles mechanism² Theorem 1: For each problem, there is a unique core assignment. The top t

26、rading cycles mechanism always selects it.² Proposition 3: The top trading cycles mechanism is strategy-proof.u House allocation with money transferØ We study two properties: efficiency and envy-freeness - no person envies another person (prefers another persons assignment to his/her own a

27、ssignment).² Proposition 4: If an assignment is envy-free, then it is efficient.² Theorem 2: There always exists an envy-free assignment.Ø Permutation and sidepayment algorithmu House Allocation with Existing TenantsØ We are interested in three properties: efficiency, strategy-pr

28、oofness and respecting private ownership: each existing tenant should be assigned a house at least as good as his/her current house.Ø Sequential priority rules are efficient and strategy-proof, but fail to respect private ownership; Ø Sequential priority rules with incumbency is uncertaint

29、y for existing tenants, as they are not guaranteed to be assigned a house at least as good as their current houses. Whats more, there might be an efficiency loss if some tenants choose to avoid the lottery; Ø Top trading cycles with pre-assignment is efficient and strategy-proof, and respects p

30、rivate ownership;Ø You request my house, I get your turn is efficient and strategy-proof, and respects private ownership. In fact, it is a combination of Sequential Priority and Top Trading Cycles.School Choice and College AdmissionsThe point is differences and similarities of the two models, t

31、hree mechanisms, stability, efciency, and strategy-proofnessu StablityA match is stable if there is no blocking pair for the match.u EfciencyThere is no other match in which students are better off.u Strategy-proofnessNo student can ever benet from lying about his/her preferences.u School ChoiceRema

32、rk 1: We focus on the student side since school only have priorities, but not preferences.Ø Three Mechanisms² Immediate acceptance (Boston) mechanismProposition 1: The Immediate Acceptance mechanism is not stable, not strategy-proof, but is efcient.² Deferred acceptance mechanismThe D

33、eferred Acceptance mechanism is stable, strategy-proof, but is not efcient.² Top trading cycles mechanismThe Top Trading Cycles mechanism is not stable, but is efcient and strategy-proof.u College AdmissionsØ Differences and similarities of the two models² School Choice:1. Students ar

34、e strategic agents; school seats are objects to be consumed.2. Stability is very desirable, but not a must.3. For efciency and strategy-proofness, only one side matters.² College Admissions:1. Both students and colleges are strategic agents.2. Stability is the central notion.3. For efciency and

35、 strategy-proofness, both sides matter.Marriage Problem is a special case of College Admissions.Proposition 10: In College Admissions, stability implies efciency.Remark 1: The two denitions of stability in these two models are mathematically identical.Ø Three Mechanisms² Immediate acceptan

36、ce (Boston) mechanismThe Immediate Acceptance mechanism is not stable, not strategy-proof, but is efcient.² Deferred acceptance mechanismThe Deferred Acceptance mechanism is stable, efcient, but is not strategy-proof.Remark 3: When both sides are strategic agents, it is harder to prevent manipu

37、lations. Thus, the strategy-proofness requirement is stronger in College Admissions than in School Choice.² Top trading cycles mechanismThe Top Trading Cycles mechanism is not stable, not strategy-proof but is efcient.Ø Parallel Mechanism in ChinaKidney ExchangeThe point is Top Trading Cyc

38、les and Chains and the effects of different chain selection rules.u Some assumptionsØ Assumption 1: The survival rate increases as the HLA type mismatch decreases. It is the European view.Ø Assumption 2: There is no constraint on the number of transplants that can be simultaneously carried

39、 out.Ø Assumption 3: Indirect exchanges are feasible.u Top Trading Cycles and ChainsØ Efciency: there is no other assignment in which patients are better off.Ø Strategy-proofness: no patient can ever benet from lying about his/her preferences.u Chain selection rulesØ Choose minimal wchains and remove them.Ø A minimal wchai