Nov 2012 University of Santiago

Constraint Based Programming

• lecture notes
• Wed6: Examples of constraint satisfaction problems, Exhaustive search with backtracking, forward checking, arc-consistency, exercices on paper
• search with backtracking
• local search
• Thu7: Dancing Links, Example Sudoku, exercices on computer
• small test, large test with input and output files
• solving sudoku with dancing links

Game Theory and Applications

• Wed14 before coffee: Equilibria repeated games (Chess, chomp), strategic games, pure Nash equilibria, mixed Nash equilibria, Sperner's Lemma, Nash's Theorem, zero sum games
• Wed14 after coffee: Local search polynomial parity argument on directed graphs, polynomial local search, party affiliation, ham sandwich cut, Braess paradox, congestion game, potential game, PLS-completness of computing Nash equilibria for symmetric congestion games
• Thu15 before coffee: Network creation games price of anarchy, proof techniques
• Thu15 after coffee: Mechanism design voting, Condorcet's paradox, Borda's rule, Arrow's theorem, Vickrey,Clarke,Groves mechanisms, Clarke's pivot rule
• slides