# Duke CPS 296.1 - Homework 2 (4 pages)

Previewing page 1 of 4 page document
View Full Document

## Homework 2

Previewing page 1 of actual document.

View Full Document
View Full Document

## Homework 2

73 views

Problems/Exams

Pages:
4
School:
Duke University
Course:
Cps 296.1 - Introduction to Computer Vision
##### Introduction to Computer Vision Documents
• 10 pages

• 7 pages

• 15 pages

• 18 pages

• 6 pages

• 4 pages

• 4 pages

• 6 pages

• 2 pages

• 31 pages

• 17 pages

• 6 pages

• 10 pages

• 54 pages

• 11 pages

• 5 pages

• 4 pages

• 11 pages

• 38 pages

• 5 pages

• 18 pages

• 23 pages

• 28 pages

• 18 pages

• 9 pages

• 15 pages

• 2 pages

• 6 pages

• 3 pages

• 6 pages

• 16 pages

• 63 pages

• 6 pages

• 30 pages

• 7 pages

• 6 pages

• 5 pages

• 12 pages

• 7 pages

• 16 pages

• 13 pages

• 3 pages

• 4 pages

• 3 pages

• 7 pages

• 17 pages

• 4 pages

• 5 pages

• 8 pages

• 10 pages

• 6 pages

• 2 pages

• 12 pages

• 8 pages

• 41 pages

• 5 pages

• 16 pages

• 17 pages

• 6 pages

• 17 pages

• 7 pages

• 7 pages

Unformatted text preview:

CPS 296 1 Computational Microeconomics Game Theory Social Choice and Mechanism Design Homework 2 due 10 14 Note the rules for assignments on the course web page Show all your work but circle your final answer Contact Vince conitzer cs duke edu with any questions 1 Properties of voting rules Alice likes to analyze the outcomes of elections specifically she is interested in the different outcomes that different voting rules produce on the same votes To do so she executes many different rules on the same set of votes a painstaking process She likes knowing about properties of voting rules that ease her task For example she likes to know which voting rules satisfy the Condorcet criterion so that if there is a Condorcet winner she immediately knows that that will be the winner for those rules without having to go through the trouble of executing each rule individually Recently Alice has become interested in the phenomenon of votes cancelling out Let us say that a set1 S of votes cancels out with respect to voting rule r if for every set T of votes the winner2 that r produces for T is the same as the winner that r produces for S T For example the set of votes a b c b a c c a b cancels out with respect to the plurality rule each candidate is ranked first once in this set of votes so it has no net effect on the outcome of the election The same set does not cancel out with respect to Borda though because from these votes a gets 4 points b gets 3 and c gets 2 which may affect the outcome of the election Alice likes to know when a set of votes cancels out with respect to a rule so that she can just ignore these votes easing her computation of the winner Define a pair of opposite votes to be a pair of votes with completely opposite rankings of the candidates i e the votes can be written as c1 c2 cm and cm cm 1 c1 Let us say that a voting rule r satisfies the Opposites Cancel Out OCO criterion if every pair of opposite votes cancels out with respect to r 1a 12 points From among

View Full Document

Unlocking...