Foundations of AI Multi Agent Systems Course

[CS 329] Foundations of AI: Multi-Agent Systems
P Manisha
[email protected]
Introduction
16 May 2024

[CS 329] Foundations of AI: Multi-Agent Systems
Link to the Course WebsiteGrading pattern
•1 midsem exam (25%)
•1 endsem exam (35%)
•Two assignments (20% each)
1 / 38

Agenda
•What are Multi-Agent Systems (MAS)?
•Real-world examples with agent interactions•Components of MAS•Why Game Theory?•Applications and role of Computer Science•Game Theory and Machine Learning
2 / 38

Mutli-Agent Systems
What is a multi-agent system?
3 / 38

Mutli-Agent Systems
Can you give more examples of multi-agent systems?
•Family - Division of property•Couple - Battle of Sexes•Any organization - Resource Allocation•Sports - Between teams and organizers•Markets - Big Role in shaping the subject
4 / 38

Multi-Agent Systems
What is the most important aspect of any multi-agent system?
•Involves more than one person•They are interacting▶Cooperating▶Conflicting▶Something in between
•System evolves (aka life goes on)
What all can it model?
5 / 38

Multi-Agent Systems
Division of Cake
6 / 38

Demonitization
Demonitization: Success or a Failure?
7 / 38

Braess’s Paradox
On Earth Day, New York City’s
Transportation Commissioner decided to
close 42d Street, one of the most
congested roads.
And the traffic improved!
8 / 38

Elections
Is majority voting the right thing to do?
2000 US Presidential Election in Florida
Democratic (Al Gore)
Votes: x + 64000
Repulican (George Bush)
Votes: x + 537 + 33000Clearly, democrats had the
majority
9 / 38

Elections
Is majority voting really fair?
2000 US Presidential Election in Florida
Democratic (Al Gore)
Votes: x
Republican (George Bush)
Votes: x + 537
The Green Party (Ralph
Nader)Figure:
10 / 38

Multi-Agent Systems
Two parts to it
•Analyzing Agent Interactions▶What do the agents want?▶Can they get what they want?▶What must they do to get it?▶How do they interact with each other?•Analyzing System as a whole▶What is the system and its rules?▶Transparency between agents and the system (Chess vs Cards)▶How does the system interact with the agents?▶What is the overall objective?▶Is it possible to achieve the objective? How?
11 / 38

Game Theory
The foundation of MAS is Game Theory - which analyzes and predicts agent behaviour
•Nobel Memorial Prize for Economics: Samuelson(1970), Arrow (1972), Selten,
Nash, Harsanyi (1994), Vickery (1996), Schelling, Aumann (2005), Maskin,
Myerson, Hurwicz (2007), Shapley, Roth (2012), Paul Milogram, Robert Wilson
(2020)
12 / 38

Game Theory
John Von Neumann
Definition (Game Theory)
Game theory is the study of mathematical models
of conflict and cooperation between intelligent,
rational decision-makers. – Myerson
13 / 38

Game Theory
What is the role of Computer Science in Game Theory?
•How does Google make money?•Selling your attention!
14 / 38

Internet Advertisement
How does Google make money?
15 / 38

Internet Advertisement
Google’s Ad Auctions
•For every search, find ads whose keywords
match
•Remove ads that are not eligible (policy,
location)
•Among the remaining select ones with a high
rank (bids, quality)
Auctions at large scale to maximize revenue!
16 / 38

Markets (e-Commerce)
•Amazon•Uber/Ola•Airbnb/Oyo Hotel room bookings•Resource allocation such as computing power to dynamically arriving requests
17 / 38

Fair Preference Aggregation
•http://robovote.org
RoboVote is a free service that helps users combine their preferences or opinions into
optimal decisions. To do so, RoboVote employs state-of-the-art voting methods
developed in artificial intelligence research.
•http://www.spliddit.org
Spliddit is a not-for-profit academic endeavor. Its mission is twofold:
To provide easy access to carefully designed fair division methods, thereby making the
world a bit fairer. To communicate to the public the beauty and value of theoretical
research in computer science, mathematics, and economics, from an unusual
perspective.
18 / 38

Surveillance
PROTECTPAWS
https://teamcore.seas.harvard.edu/
19 / 38

Machine Learning in Game Theory
•Designing Mechanisms
•Preference Learning - Multi-Armed Bandit
•Designing systems where agents are strategic and learning preferences
•Fair Allocation
20 / 38

Designing Mechanisms
What is a mechanism?
A social planner designs the rules of a game in a way that strategic and intelligent
agents interact but the planner’s objective is achieved.
•Auctions
•Voting
•Crowdfunding
•Crowdsourcing
21 / 38

Designing Mechanisms
Revenue Optimal Auctions
22 / 38

Designing Mechanisms
Redistribution Mechanisms
23 / 38

Designing Mechanisms
Price prediction in Agriculture
24 / 38

Designing Mechanisms
Fair Resource Allocation
25 / 38

Designing Mechanisms
What if the agents do not even know the value?
26 / 38

Designing Mechanisms
Multi-Armed Bandit-based Mechanism Design - Preference Learning
27 / 38

Preference Learning
Agent preferences are not very simple to extract!
28 / 38

Preference Learning
Agent preferences are not very simple to extract!
29 / 38

Game Theory in Machine Learning
•Feature Selection
•Explainability
•Generative Adversarial Networks
•Strategic Data Classification
•Strategic Agents and Private ML
•Recommendation Systems - two-sided matching
•Multi-Agent RL
30 / 38

Feature Selection
•Which features are important for classification/mining?
1
1
Feature evaluation and selection with cooperative game theory by X Sunet.al., Pattern
Recognition, 2012
31 / 38

Explanability
Neural Networks are black-box models!
32 / 38

GANs
Figure:
33 / 38

Strategic Data Classification
Build classifiers robust to manipulations
34 / 38

Private Data Acquisition
Data in exchange for a monetary reward
35 / 38

Recommendation System as Two Sided Matching
Congestions
36 / 38

Multi-Agent RL
•Typical Reinforcement Learning models single agent
•Many real-world situations need multiple agents
▶The agents jointly decide the actions▶The agents are non-cooperative▶Agents are adversarial
37 / 38

Summary
•Agent interactions at the core of multi-agent systems
•Game Theory models agent interactions
•Role of Computer science
•ML and Game Theory
38 / 38

Foundations of AI Multi Agent Systems Course

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Foundations of AI Multi Agent Systems Course

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 4

Slide 5

Slide 6

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77