CS 670 Exam 2 Review Sheet

11/7/2007

• Social Choice Functions
• Multi-agent choice framework
• Definition of a social choice function (which I sometimes called social welfare function)
• Profiles
• Tables of preferences
• Size of input to social choice function and output from social choice function
  
• Arrow's Impossibility Theorem
• Axioms of fairness
• Pareto optimality theorem
• Decisiveness lemma
• Minimal decisive set: definition, existence, non-emptiness, algorithm
  
• Given three preference patterns, prove the theorem
• Implications
• Mechanism design
• Definition of a mechanism
• Equilibria and strategic dominance flavors for a mechanism to implement a social choice function
• Truth dominance
• Gibbard Satterthwaite theorem
  
• Voting
• Relationship to Arrow's theorem --- where do the protocols break?
• Relationship to the Gibbard-Satterthwaite theorem --- which are truth dominant?
  
• Borda protocol
• Iterated Borda protocol
• Plurality
• Binary protocol
• Auctions
• Types – English, first-price sealed bid, Dutch, Vickrey
• Strategic dominance and Pareto optimality in various auctions
• Truth dominance proof
  
• Problems – collusions, lying auctioneer
• Cost to auctioneer for inducing honesty
  
• Clarke Tax Mechanism
• Goods and numeraires
• Tax formula
• Truth dominance proof
• Example
• Weaknesses
• Bargaining
• Axiomatic versus strategic bargainning
• Nash bargainning solution
• axioms of fairness
• computing
• uniqueness
• Q-learning
• Sequential estimates of a random variable
  
• Credit assignment and discounted utility
  
• Transition probability
• Rewards
• Policies
• Values
• Q-value
• Q-learning algorithm
• Convergence requirements:
1. learning rate gets small fast, but not too fast (formally)
2. try every action from every state infinitely often
• Intuition
• Parameters
• Q-learning and multiple learning agents