# Duke CPS 296.2 - Computational Game Theory and Mechanism Design (4 pages)

Previewing page*1*of 4 page document

**View the full content.**## Computational Game Theory and Mechanism Design

Previewing page *1*
of
actual document.

**View the full content.**View Full Document

## Computational Game Theory and Mechanism Design

0 0 82 views

- Pages:
- 4
- School:
- Duke University
- Course:
- Cps 296.2 - Computational Biology and Biomolecular Computation

**Unformatted text preview: **

CPS 296 2 Computational Game Theory and Mechanism Design Homework 2 due 10 12 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 the reasonable3 voting rules

View Full Document