These are notes taken in Multiagent Systems class (AE4M36MAS) taught at CTU FEE.
Multiagent systemis 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
autonomousthe 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
reactivethe agent maintains an ongoing interaction with its environment, and responds to changes that occur in it
proactivethe agent generates and attempts to achieve goals; it is not driven solely by events but takes the initiative
sociablethe 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
coordinationis managing the interdependencies between actions of multiple agents (not necessarily cooperative)
cooperationis working together as a team to achieve a shared goal
negotiationis 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
- cooperative - single shared utility
- competetive - multiple different utilities
Agent functionAgent’s behavior is described by the agent function that maps percept sequences to actions.
Agent programruns on a physical architecture to produce agent function.
Rational agentchooses 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 observablecan agents obtain complete and correct information about the state of the world?
Deterministic vs. stochasticDo actions have guaranteed and uniquely defined effects?
Episodic vs. sequentialCan agents decisions be made for different, independent episodes?
Static vs. dynamicDoes the environment change by processes beyond agent control?
Discrete vs. continuousIs the number of actions and percepts fixed and finite?
Single-agent vs. multi-agentDoes 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
Basic types of agents in the order of increasing capability:
Simple Reflex Agentschooses the next action on the basis of the current percept only.
- simple reflex agents
- model-based agents with state
- goal-based agents
- utility-based agents
- (learning agents)
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 AgentKeeps track of the world by extracting relevant information from percepts and storing it in its memory.
Goal-based AgentsGoal-based agents are more flexible, they use search and planning.
- 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)
Goals alone are not sufficient for decision making:
Utility-based Agentsuse the utility function to choose the most desirable action/course of actions to take.
- there may be multiple ways of achieving them;
- agents may have several conflicting goals that cannot be achieved simultaneously.
Uses optimizing planning - searches for the plan that leads to the maximum utility.
There are still issues:
Utilityis 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.
- irreducible preference orderings
- non-deterministic environment (Markov decision processes)
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.
Intelligent agentis autonomous, proactive, reactive and sociable.
Agents can be cooperative or competitive (or combination thereof).
There are different agent architectures with different capabilities and complexity.
Auctionmechanism 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.
Auction mechanism is specified by auction rules.
Bidding rulesHow offers are made: by whom, when, what their content is
Clearing rulesWho gets which goods (allocation) and what money changes hands (payment).
Information rulesWhat information about the state of the negotiation is revealed to whom and when.
Common valuethe good has the same value to all agents example: a 100 dollar note
Private valuean 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
Agent’s payoff from participating in an auctionif winner: payoff = item’s valuation – price paid for the item; if not winner: payoff = zero
Single Good Auctionsauction of one item
Multi-Unit Auctionsmultiple units of the same item are available for auction
Multi-Item Auctionsbidding for multiple items grouped together
Reverse AuctionsThe buyer issues a request for bids to his providers.
Multi-Attribute AuctionsNegotiation over further attributes beyond price, e.g. color, weight, or delivery time
Single-Item Auctions - Basic Auction Mechanisms
English AuctionAuctioneer 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 AuctionSame 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 AuctionThe 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 auctionBidders 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 auctionSame as First-price sealed bid auction except winner pays the amount bid by the second-highest bidder alias: Vickerey auction
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
- First-price auctions can be held asynchronously
- Dutch auctions are fast, and require minimal communication