Multi-Agent Systems

These are notes taken in Multiagent Systems class (AE4M36MAS) taught at CTU FEE.

Multiagent system

is a collection of multiple autonomous agents, each acting towards its objectives while all interacting in a shared environment, being able to communicate and possibly coordinate their actions.

Agent

[Russell & Norvig] An agent is anything that can perceive its environment (through its sensors) and act upon that environment (through its effectors).
[Wooldridge & Jennings] An agent is a computer system that is situated in some environment, and that is capable of autonomous action in this environment in order to meet its design objectives/delegated goals.

Autonomous Agent Properties

autonomous

the agent is self goal-directed and acts without requiring user initiation and guidance; it can choose its own goal and the way to achieve it; its behavior is determined by its experience; we have no direct control over it

reactive

the agent maintains an ongoing interaction with its environment, and responds to changes that occur in it

proactive

the agent generates and attempts to achieve goals; it is not driven solely by events but takes the initiative

sociable

the agent interacts with other agents (and possibly humans) via cooperation, coordination, and negotiation; it is aware and able to reason about other agents and how they can help it achieve its own goals

coordination

is managing the interdependencies between actions of multiple agents (not necessarily cooperative)

cooperation

is working together as a team to achieve a shared goal

negotiation

is the ability to reach agreements on matters of common interest

An agent has unpredictable behaviour as observed from the outside, unless its simple reflexive agent.
An agent is situated in the environment.
Agent communication model is asynchronous.
Objects do it for free; agents do it because they want to.

Types of Agent Systems

single-agent
multi-agent
- cooperative - single shared utility
- competetive - multiple different utilities

Agent Behavior

Agent function

Agent’s behavior is described by the agent function that maps percept sequences to actions.

Agent program

runs on a physical architecture to produce agent function.

Rational agent

chooses whichever action maximizes the expected value of the performance measure given the percept sequence to date and whatever bulit-in knowledge the agent has.

To design a rational agent, we must specify the task environment (PEAS).

Task environment (PEAS)

Performance measure, Environment, Actuators, Sensors

Properties of Environments

Fully observable vs. partially observable

can agents obtain complete and correct information about the state of the world?

Deterministic vs. stochastic

Do actions have guaranteed and uniquely defined effects?

Episodic vs. sequential

Can agents decisions be made for different, independent episodes?

Static vs. dynamic

Does the environment change by processes beyond agent control?

Discrete vs. continuous

Is the number of actions and percepts fixed and finite?

Single-agent vs. multi-agent

Does the behavior of one agent depends on the behavior of other agents?

Hierarchy of Agents

There is a link between the complexity of the task and the minimum agent architecture required to implement a rational agent.

Basic types of agents in the order of increasing capability:

simple reflex agents
model-based agents with state
goal-based agents
utility-based agents
(learning agents)

Simple Reflex Agents

chooses the next action on the basis of the current percept only.

Reflex agents are simple but of limited intelligence – they only work if

the environment is fully observable and
the decision can be made based solely on the current percept

If the above not the case => suboptimal action choices, infinite loops.

Model-based Reflex Agent

Keeps track of the world by extracting relevant information from percepts and storing it in its memory.

whats and hows tightly coupled (impossible to tell the agent what to do)
the agent does not anticipate the effects of its actions (only finds out the result after having executed the action)

Goal-based Agents

Goal-based agents are more flexible, they use search and planning.

Goals alone are not sufficient for decision making:

there may be multiple ways of achieving them;
agents may have several conflicting goals that cannot be achieved simultaneously.

Utility-based Agents

use the utility function to choose the most desirable action/course of actions to take.

Uses optimizing planning - searches for the plan that leads to the maximum utility. There are still issues:

irreducible preference orderings
non-deterministic environment (Markov decision processes)

Utility

is a function that maps a state onto a real number; it captures “quality” of a state. If an agent prefers one world state to another state then the former state has higher utility for the agent.

Utility can be used for:

choosing the best plan
resolving conflicts among goals
estimating the successfulness of an agent if the outcomes of actions are uncertain.

Summary

Intelligent agent

is autonomous, proactive, reactive and sociable.

Agents can be cooperative or competitive (or combination thereof).

There are different agent architectures with different capabilities and complexity.

Auctions

Auction

mechanism for allocating resource among self-interested agents
[Shoham & Leyton-Brown 2009] An auction is a protocol that allows agents (=bidders) to indicate their interests in one or more resources and that uses these indications of interest to determine both an allocation of resources and a set of payments by the agents.

Auctions Rules

Auction mechanism is specified by auction rules.

Bidding rules

How offers are made: by whom, when, what their content is

Clearing rules

Who gets which goods (allocation) and what money changes hands (payment).

Information rules

What information about the state of the negotiation is revealed to whom and when.

Valuation Models

Common value

the good has the same value to all agents example: a 100 dollar note

Private value

an agent A’s valuation of the good is independent from other agent’s valuation of the good example: a painting, John Lennon’s last dollar bill

Correlated value

valuations of the good are related, i.e. the more other agents are prepared to pay, the more agent A prepared to pay. example: purchase of items for later resale

Agent’s payoff from participating in an auction

if winner: payoff = item’s valuation – price paid for the item; if not winner: payoff = zero

Auction types

Single Good Auctions

auction of one item

Multi-Unit Auctions

multiple units of the same item are available for auction

Multi-Item Auctions

bidding for multiple items grouped together

Reverse Auctions

The buyer issues a request for bids to his providers.

Multi-Attribute Auctions

Negotiation over further attributes beyond price, e.g. color, weight, or delivery time

Single-Item Auctions - Basic Auction Mechanisms

English Japanese Dutch First-Price Second-Price

English Auction

Auctioneer starts the bidding at some reservation price. Bidders then shout out ascending prices (minimum increments). Once bidders stop shouting, the high bidder gets the good at that price.

Japanese Auction

Same as an English auction except that the auctioneer calls out the prices
All bidders start out standing. When the price reaches a level that a bidder is not willing to pay, that bidder sits down. Once a bidder sits down, they can't get back up the last person standing gets the good.

Dutch Auction

The auctioneer starts ahigh value; it descends clock at some. At some point, a bidder shouts “mine!" and gets the good at the price shown on the clock. Good when items need to be sold quickly (similar to Japanese auction) No information is given away during auction.

First-price sealed bid auction

Bidders write down bids on pieces of paper. Suctioneer awards the good to the bidder with the highest bid. That bidder pays the amount of his bid.

Second-price sealed bid auction

Same as First-price sealed bid auction except winner pays the amount bid by the second-highest bidder alias: Vickerey auction

Analysing Auctions

(Desired) Properties

Strategy: existence of dominant strategy

Truthfulness: bidders are incentivized to bid their true valuations

Efficiency (Pareto-optimality): the aggregated utility, measured as the sum of valuations, is maximized

Optimality: maximization of seller’s revenue

Manipulation vulnerability: Lying auctioner, Shills, Bidder collusion

Other consideration: communication complexity, private information revelation, ...

Dutch and First-price Sealed Bid

Strategically equivalent: an agent bids without knowing about the other agents’ bids - a bidder must decide on the amount he's willing to pay, conditional on having placed the highest bid

Differences

First-price auctions can be held asynchronously
Dutch auctions are fast, and require minimal communication