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

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 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 from 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 least 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 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. 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 bad, 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 different 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. Condorcet 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 paradox. 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 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 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 voting 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-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 most 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 voting 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）+-+-+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 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 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, 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 mechanism 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 other 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 owned 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 rulesProposition 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: 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 trading 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 assignment). 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-proofness 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 uncertainty 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 private 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, three 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 ChoiceRemark 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 Deferred 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 are 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 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 acceptance (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 manipulations. 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 Cycles 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 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 mini