Homework 2
Previewing page 1 of actual document.
View the full content.View Full Document
Homework 2
0 0 73 views
Problems/Exams
 Pages:
 4
 School:
 Duke University
 Course:
 Cps 296.1  Introduction to Computer Vision
Introduction to Computer Vision Documents

introduction to linear and mixed integer programming
10 pages

7 pages

Preference elicitation/ iterative mechanisms
15 pages

Computational problems, algorithms, runtime, hardness
18 pages

6 pages

Easy and Efficient Parallel Processing of Massive Datasets
4 pages

SCOPE: Easy and Efficient Parallel
4 pages

6 pages

2 pages

31 pages

Concise representations of games
17 pages

6 pages

Mining and Monitoring Evolving Data
10 pages

54 pages

Maintenance Over Semistructured Data
11 pages

WebView Materialization and Maintenance
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

Unified Platform for Secure Networked Information Systems
3 pages

6 pages

16 pages

Compiler Transformations for HighPerformance Computing
63 pages

6 pages

Auctions & Combinatorial Auctions
30 pages

7 pages

6 pages

5 pages

An Analysis of Stochastic Game Theory
12 pages

7 pages

16 pages

13 pages

3 pages

Survey of GeneralPurpose Computation on GPU
4 pages

3 pages

7 pages

17 pages

Programming Platform for Sensor Networks: TinyOS
4 pages

:Java database Queries Through Bytecode Rewriting
5 pages

8 pages

A Fast Index for Semistructured Data
10 pages

6 pages

2 pages

Efficient Evaluation of XML Middleware Queries
12 pages

Optimal DecisionMaking With Minimal Waste
8 pages

41 pages

5 pages

16 pages

17 pages

6 pages

Cooperative/coalitional game theory
17 pages

7 pages

7 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
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