CS 670 Final Exam Review Sheet

9 December 2009

The final is comprehensive 

Refer to the previous review sheets.

Arrow's Impossibility Theorem

  • Axioms of fairness
  • Pareto optimality theorem
  • Decisiveness lemma
  • Minimal decisive set
  • Using the three preference patterns to conclude dictatorship

Distributed Intelligence

  • Types of goals
  • Awareness of others
  • Actions advance goals of others?
  • Limitations of taxonomy

  • Types of auctions
    • English, Japanese, Dutch, Vickrey
    • Open cry, sealed bid
    • Ascending, descending
  • Gibbard Satterthwaite theorem
    • Three properties
    • Interpretation
  • Truth dominance: theory in auctions
    • Quasi-linear utilities
    • Vickrey auction is truth dominant
    • First price, open cry is not truth dominant
  • You will not be tested on revenue equivalence
  • Parker paper -- taxonomy
  • Gerkey Mataric' paper
    • Task allocation
    • Metrics and bids
  • Jones, Dias, Stentz paper
    • Time-extended task assignment
    • Hierarchical task allocation -- tiered auctions

Bargainning

  • Axiomatic versus strategic bargainning
  • Nash's axioms of a fair bargain
  • Computing the Nash bargainning solution
  • Uniqueness of the Nash bargainning solution

Principal-agent model

  • Adverse selection/asymmetric information
  • Participation contraints
  • Information rent
  • Theoretical results when type is known
  • Theoretical results when types is unknown
  • Model of principal and model of agent