Agent-based Systems
Paolo Turrini
www.dcs.warwick.ac.uk/~pturrini R p.turrini@warwick.ac.uk
Introduction
Paolo Turrini Introduction Agent-based Systems
Timetable
Asynchronous Videos here
Synchronous Wed 9:00 am
Seminars (f2f) Wed (group dependent)
Seminars (online) Wed from 10:00 am (group dependent)
Paolo Turrini Introduction Agent-based Systems
The module
Seminars nine in total, every week, starting form the next Coursework 50% of the mark (deadline week 12)
Exam 50% of the mark
Paolo Turrini Introduction Agent-based Systems
Lectures
Location Available online. It changes.
Description Syllabus, notes and material on the course webpage
Slides Available (but I would also attend the lectures) Homepage https://warwick.ac.uk/fac/sci/dcs/teaching/
modules/cs404/
Paolo Turrini Introduction Agent-based Systems
Seminars/Labs
Exercises Questions on explained material Labs Programming-based exercises
Previous Papers Some exercises are previous exam papers of mine Solutions Key exercises will come with model answers
Tip 1: go to the seminars/labs and do all the exercises.
Tip 2: write everything down, even when you think it’s trivial.
Paolo Turrini Introduction Agent-based Systems
Tutors
Jack
jack.bara@warwick.ac.uk
Stas
s.zhydkov@warwick.ac.uk
Charlie
charlie.pilgrim@warwick.ac.uk
Paolo Turrini Introduction Agent-based Systems
Coursework
The coursework will be a Python-based implementation of a strategic agent, participating in an auction. The goal is to make money.
You are going to be playing against one other.
It’s not a programming exercise, although it involves programming. The focus is on the strategic behaviour itself.
There will be a coursework handout lecture (week 3), where everything will be explained in details, and a coursework hints lecture (week 10), to discuss some basics, in case you are lost.
Paolo Turrini Introduction Agent-based Systems
Exam
Questions on the material explained.
Focus will be on precise applications of learnt techniques. This means no questions like:
“What’s your view on Artificial Intelligence?” But rather:
“This is the problem: calculate the solution”
It won’t be a memory game.
The goal is to reward the ‘understanding’ of the subject.
Everything I explain is examinable.
Paolo Turrini Introduction Agent-based Systems
Interaction
This is a course on multi-agent interaction, and I like interaction.
The vast majority of the slides will be available before the lecture, but some will not, because I want you to think on the spot.
All the slides will be available after the lecture.
Don’t be scared of saying wrong things (before the exam).
Paolo Turrini Introduction Agent-based Systems
Questions
1 Ask them in class
2 Ask them during seminars
3 Send me an email (p.turrini@warwick.ac.uk)
Paolo Turrini Introduction Agent-based Systems
Artificial Intelligence with many agents
The toolbox for the design of interactive decision-makers
Paolo Turrini Introduction Agent-based Systems
Artificial Intelligence with many agents
AlphaGo
Defeats the World Champion 4-1 (March 2016)
The toolbox for the design of interactive decision-makers
Paolo Turrini Introduction Agent-based Systems
Artificial Intelligence with many agents
Libratus
Wins 1.7M dollars from top players (January 2017)
AlphaGo
Defeats the World Champion 4-1 (March 2016)
The toolbox for the design of interactive decision-makers
Paolo Turrini Introduction Agent-based Systems
Artificial Intelligence with many agents
Libratus
Wins 1.7M dollars from top players (January 2017)
AlphaZero
Defeats the best open source engine 28-0, after 9 hours of self-training (December 2017)
The toolbox for the design of interactive decision-makers
AlphaGo
Defeats the World Champion 4-1 (March 2016)
Paolo Turrini Introduction Agent-based Systems
Connections
Important private investments: Google DeepMind
Paolo Turrini Introduction Agent-based Systems
The starting kit
Helpful background basics
Y. Shoham and K. Leyton-Brown
Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations www.masfoundations.org
Discrete mathematics, probabilities, algorithms, logic.
Paolo Turrini Introduction Agent-based Systems
Other important references
M. Maschler, E. Solan and S. Zamir
Game Theory
Y. Shoham and K. Leyton-Brown
Essentials of Game Theory
S. Russel and P. Norvig
Artificial intelligence: a modern approach
One of the greatest books ever written
It’s very useful to look at different ways of presenting the same topic!
Paolo Turrini Introduction Agent-based Systems
Acknowledgments
This module would not have been possible without:
Ulle Endriss
Institute for Logic, Language and Computation University of Amsterdam
Paolo Turrini Introduction Agent-based Systems
Agents
An agent is a formal model of decision-maker which:
lives in a world, made of states
is goal-oriented (wants to achieve some states, or sequences of states) has a view-point on the world
can take actions to change the world into a different state
AlphaGo is an agent,
You are an agent,
Pretty much everything interesting is an agent.
An abstract comprehensive theory of (rational) decision-making
Paolo Turrini Introduction Agent-based Systems
Humans can be rational
Robert J. Aumann
Nobel Prize in Economics
‘A person’s behaviour is rational if it is in their best interests, given their information.’
Agents (not only humans) can be rational!
Paolo Turrini Introduction Agent-based Systems
Agents can be rational
Robert J. Aumann
Nobel Prize in Economics
‘An agent’s behaviour is rational if it is in their best interests, given their information.’
Agents (not only humans) can be rational!
Paolo Turrini Introduction Agent-based Systems
Multi-agent Systems
A multi-agent system is any situation with more than one agent.
their goals might be interdependent (one against the other, or they
need one another to achieve them)
each have view points on the world, the other agents, and view points about the other agents’ viewpoints!
their choices are interdependent, too: the world state changes as a function of what all agents do.
Paolo Turrini Introduction Agent-based Systems
Kuhn Poker
Two players, Ann and Bob, are dealt one of the following cards: {A, K, Q}.
Ann Bob Ann
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass pass pass bet pass bet bet pass bet bet
pass bet
Players take turns in starting. So cach player can be playing two different games: the one when they start, and the one when they don’t start.
Each of these games is an extensive game of imperfect information.
Although Poker is more complicated, it’s not that much more complicated really.
Harold E. Kuhn
Simplified two-person poker
Contributions to the Theory of Games, 1950
Paolo Turrini Introduction Agent-based Systems
Let’s Play!: Kuhn Poker
Ann Bob Ann
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass pass pass bet pass bet bet pass bet bet
pass bet
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann Bob Ann
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass pass pass bet pass bet bet pass bet bet
pass bet
Scenario 1: You are Bob.
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Bob Ann pass
bet
bet pass bet
dealt Q.
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets.
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do?
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2: You are Bob.
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do?
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q.
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q. Ann passes.
Paolo Turrini
Introduction
Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q. Ann passes. What do you do?
Paolo Turrini
Introduction Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Scenario 3
You are Ann.
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q. Ann passes. What do you do?
Paolo Turrini
Introduction Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Scenario 3
You are Ann. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q. Ann passes. What do you do? dealt A.
Paolo Turrini
Introduction Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Scenario 3
You are Ann. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q. Ann passes. What do you do? dealt A. What do you do?
Paolo Turrini
Introduction Agent-based Systems
Let’s Play!: Kuhn Poker
Ann
pass pass pass bet bet
Scenario 1:
You are Bob. You are
Scenario 2:
You are Bob. You are
Scenario 3
You are Ann. You are
Bob Ann pass
bet
bet pass bet
outcome
+1 to higher card +1 to Bob
+ 2 to higher card + 1 to Ann
+ 2 to higher card
pass bet
dealt Q. Ann bets. What do you do? dealt Q. Ann passes. What do you do? dealt A. What do you do?
Question: What are the objectively bad choices? The good ones?
Paolo Turrini Introduction Agent-based Systems
In a slogan…
Agent-based systems is Artificial Intelligence with many agents.
where…
Artificial means done by a computer. Intelligence means rational.
many agents means many agents.
No magic, no singularity, no spelling the end of the human race. Just computational modelling.
Paolo Turrini Introduction Agent-based Systems
The plan
Logical Agents [Week 1-2]
Knowledge, Preferences, Strategies and how to reason.
Decision-Making Agents [Week 3] Probabilistic Beliefs and Expected Utility.
Strategic Agents [Week 4-5]
Games, Equilibria, Opponent Modelling.
Learning Agents [Week 6-7-8]
Opponent Modelling and (Multi-Agent) Learning.
Social Agents [Week 8-9] Groups and Networks
Paolo Turrini Introduction Agent-based Systems
Week 10: Recap
Coursework hints for those who are hopelessly lost Revision Lectures 1 and 2 (your input matters!)
Paolo Turrini Introduction Agent-based Systems
What we have seen
The course plan
Agents: first definition
Agents and multi-agent systems Rationality
Paolo Turrini Introduction Agent-based Systems
Coming next
Modelling actions, plays and wins Strategies
Paolo Turrini Introduction Agent-based Systems