11 | Multiagent systems

Question 1

What are the two extremes we study in the multiagent systems?

Answer 1

fully cooperative, where the agents share the same utility function, and

fully competitive, when one agent can only win when another loses; in zero-sum games, for every outcome, the sum of the utilities for the agents is zero.

Question 2

What does a normal form game consist of?

Answer 2

a finite set I of agents, typically identified with the integers I={1,…,n}

a set of actions Ai for each agent i∈I. An action profile is a tuple ⟨a1,…,an⟩, which specifies that agent i∈I carries out action ai, where ai∈Ai

a utility function ui for each agent i∈I that, given an action profile, returns the expected utility for agent i given the action profile.

Question 3

What does a perfect-information game in extensive form consist of?

Answer 3

Each internal node is labeled with an agent (or with nature). The agent is said to control the node.

Each arc out of a node labeled with agent i
corresponds to an action for agent i

Each internal node labeled with nature has a probability distribution over its children.

The leaves represent final outcomes and are labeled with a utility for each agent.

The extensive form of a game specifies a particular unfolding of the game. Each path to a leaf, called a run, specifies one particular way that the game could proceed depending on the choices of the agents and nature.

Question 4

What is a game tree?

Answer 4

a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position