Multi-Agent Systems Final Summary

Introduction to MAS

Agent
- Sensors (to perceive)  policy (agent program)  actuators (to act)
- Autonomous  Decision making relying on own perception instead of prior knowledge
- Rational  optimize appropriate performance measures

Multi-agent system = ABM = Distributed AI
- Agents + environment
- Collective behavior > sum of individual behaviors

Characteristics of MAS
1. Agent design  physical vs programmatic, heterogeneous vs homogeneous
2. Environment  dynamic vs static
3. Perception  distributed (spatially, temporally or semantically), partial observability,
sensor fusion
4. Control  decentralized (efficient + robust), some coordination still needed
5. Knowledge  different levels of common knowledge for different agetns
6. Communication  two-way, can be coordination among cooperative agents/negotiation
among self-interested agents, what network protocols and language to use

Agent types
- Simple reflex agents
- Model-based reflex agents
- Goal-based agents
- Utility-based agents
- Learning agents

Why MAS in social science?
- Society as dynamical and complex system  Behavior of the system as a whole cannot
be determined by decomposing the system and understanding the behavior of each part of
it
- Path dependence + non-linear interactions of individuals  emergence (social
institutions and phenomena at a system level that arise from but are not specifically
encoded in the units of society at an individual level)
- Deductive approach  6 cost of data collection
- Impossible/unethical social stimulation

How to develop good ABM
- Validation  parameters reflect statistical properties of observed behaviors
- Workflow: setting objective / RQ  building a simple model  conducting theoretical
research & making assumptions, designing stimulation by defining objects, attributes,
environment & dynamics  setting up user interface  unit testing & debugging

, Agent Decisions; Modelling social sciences

Policy
- Memory-expensive
 memory space + computational cost (intractability)
- Memoryless policy  reflex agent
 Markov property: the world for the current state provides a complete characterization of
the history before the current time, i.e. predictions based on current state only
 Rational decision in a Markov world  maximize expected utility/get optimal Q-value
 Utility =/= payoff




Factors:
- Fully vs partially observable  noise, perceptual aliasing (e.g. two doors in the same
corridor look the same to a sensor)
- Deterministic vs stochastic  state-action pairs to single new states vs probability
distribution over states | goals & planning vs utilities and preferences

Game Theory

Premises:
1. Rational agents
2. Strategic reasoning  also consider other agents’ decisions

Strategic game
- Single-shot game  act simultaneously and independently
- Strictly competitive, zero-sum
- Fixed, fully observable world state  common knowledge shared by all agents
(know the existence, action sets and payoffs of each other)

Extensive game (⨉ discussed in this course)
- Can change their actions throughout the game

Principles for strategic games:
1. Iterated Elimination of Strictly Dominated Actions (IESDA)
- ai is strictly dominated by ai’: if a-i = cooperate / defect  u(ai’,a-i) > u(ai,a-i)?
- Eliminate strictly dominated actions until no more actions are strictly dominated 
consider one agent at a time