Lecturer: Ralf Möller
Content
- Introduction
Terminology, 4-phase model(s), agents, rational behavior, goals, utilities, PEAS, environment types - Adversarial Agent Cooperation
Agents with complete access to the state(s) of the environment, games, Minimax algorithm, alpha-beta pruning, elements of chance - Uncertainty
Motivation: agents with no direct access to the state(s) of the environment, probabilities, conditional probabilities, product rule, Bayes rule, full joint probability distribution, marginalization, summing out, answering queries, complexity, independence assumptions, naive Bayes, conditional independence assumptions - Bayesian networks
Syntax and semantics of Bayesian networks, answering queries revised (inference by enumeration), typical-case complexity, pragmatics: reasoning from effect (that can be perceived by an agent) to cause (that cannot be directly perceived). - Probabilistic reasoning over time (1)
Motivation: environmental state may change even without the agent performing actions, dynamic Bayesian networks, Markov assumption, transition model, sensor model, inference problems: filtering, prediction, smoothing, most-likely explanation - Probabilistic reasoning over time (2)
Special cases: hidden Markov models, Kalman filters, Exact inferences and approximations - Decision making under uncertainty (1): Simple decisions
Utility theory, multivariate utility functions, dominance, decision networks, value of information - Decision making under uncertainty (2): Complex decisions
Sequential decision problems, value iteration, policy iteration, MDPs - Decision making under uncertainty (3): Decision-theoretic agents
POMDPs, Reduction to multidimensional continuous MDPs, Dynamic Decision Networks - Game
theory (Golden Balls: Split or Share)
Decisions with multiple agents, Nash equilibrium, Bayes-Nash equilibrium - Social Choice
Voting protocols, preferences, paradoxes, Arrow's Theorem, - Mechanism Design
Fundamentals, dominant strategy implementation, Revelation Principle, Gibbard-Satterthwaite Impossibility Theorem, Direct mechanisms, incentive compatibility, strategy-proofness, Vickrey-Groves-Clarke mechanisms, expected externality mechanisms, participation constraints, individual rationality, budget balancedness, bilateral trade, Myerson-Satterthwaite Theorem
Acknowledgments:
Numerous lecturers have made available material for teaching chapters of the AIMA book [1]. Some of this material has been integrated into this lecture. Since it is hard to trace back the original contributors of particular slides, I would like to thank all authors who provided their slides and made them available on the web. See also the site of the AIMA book for further references. Special acknowledgments for Kate Larson who made their slides on electronic market design available on the web.Literature:
- Artificial Intelligence: A Modern Approach (Second Edition), Stuart Russell, Peter Norvig, Prentice Hall, 2003
Chapters 2, 6, 13-17, 10.6 - Multiagent Systems -- Algorithmic, Game-Theoretic, and Logical Foundations, Yoav Shoham, Kevin Leyton-Brown, Cambridge University Press, 2009.
Old Exams:
Can be found here.Ralf Möller