MA279 Review
Voting
Vocabulary
- candidate
- ballot
- election
- preference schedule
Methods
- plurality
- borda count
- plurality with instant run off
- pairwise comparison
Criteria
- majority
- condorcet
- monotonicity
- independence of irrelevant alternatives
Arrows Theorem
- all methods must fail at least one criterion
Ranking
- extension of voting methods
- recursive (repeat voting methods)
Weighted Voting
Vocabulary
- players, weights, quote, dictator, veto power, unsuspecting dummy
Banzhaf Power Index
Vocabulary
- coalition, winning coalition, grand coalition, critical players
Shapley-shubik index
- sequential coalition
- mult. rule for counting indep xxxx
Division
Vocabulary
- players
- goods
- value system
- fair share
- continuous/discrete division
Assumptions
- rational players
- preferences are private
Methods
Continuous
- divider-choose
- lone divider
- lone chooser
- last diminisher
Discrete
Apportionment
Vocabulary
- states, seats, populations, upper/lower standard quote
Methods
- hamilton, jefferson, adams
- webster
Paradoxes
- alabama
- new state
- population
Graphs
Euler circuits
Vocabulary
- graph, vertex, edge, loop, degree, path, circuit
Types
- complete, bipartite
- bridge, adjacency matrix
- wedding theorem, euler's theorem
Fleury, Hierholzer
Hamilton circuits
- hamilton circuit, hamilton path
- np hard to test
Traveling salesman
Methods
- nearest neighbor, cheapest link
Spanning trees
- counting number in complete graph
- prufer sequence
Networks
vocabulary
Characteristics
- E+I = V, only bridges, no loops - all equivalent
- Shortest networks: steiner points