China
Africa
Explore chapters and articles related to this topic
Game Theory
Published in Albert G. Holzman, Mathematical Programming, 2020
An n-person game in extensive form can be described by a "rooted tree, " that is, a connected graph in the plane with no loops and with a distinguished vertex or node. The distinguished or initial vertex (root) and each additional interior vertex (point, node, locus) corresponds either to one of the n players or to the "chance player." The arcs (edges, lines) ascending from a vertex correspond to the alternate choices this player can make if a play of a game leads to this point. To each terminal vertex there is associated an n-dimensional vector in which the components represent the payoffs to the respective players. For each node belonging to the chance player there is a probability distribution over the ascending arcs. The state of a player's information at any stage can be described by certain types of subsets of the set of all his vertices which are called information sets. The extensive form usually gives the most complete description of a game and is used to model many game-like situations. However, it has not yet proved to be the most suitable form for handling the computational problems involved in actually solving games, except for very simple cases.
Game Theory
Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012
Erik G. Larsson, Eduard Jorswiec
Another interesting interpretation is the following: Normal form games with incomplete information from Section 19.6 can be described in extensive form with information sets. Consider that the nature moves first and determines the types of the players. The uncertainty about the types of the other players is modeled by corresponding information sets. Let us revise the Cournot-Nash-equilibrium example with incomplete information from Section 19.6. Two firms with two possible cost types play for maximizing their revenue. Assume that the production amounts are chosen from a discrete set with two possible amounts. One high and one small production, say xh = 15 and xl = 5. The resulting tree representation is shown in Figure 19.11.
Enhancing cyber-physical security in manufacturing through game-theoretic analysis
Published in Cyber-Physical Systems, 2018
Zach DeSmit, Aditya U. Kulkarni, Christian Wernz
To solve the attacker–defender game in extensive form with perfect information, we use backward induction [60]. Assume that the two decision epochs of the defender and the first decision epoch of the attacker have passed, and it is now the final decision epoch where the attacker has to choose between attacking the computer or the lathe. There are eight possible decision nodes in which the attacker can be. Although the choices available to the attacker are the same for each of the eight nodes, due to perfect information, the attacker knows exactly which node they are at. That is, the attacker knows the past actions of both players. For such scenarios, we say that the information set for both players consists of a single node at all points in the game. An information set for a player is a collection of nodes at a particular decision epoch for the player such that the player has the same information available for all nodes in the same information set. Thus, in games of perfect information, each player’s information set consists of a single node at all of their decision epochs; the number of information sets for a player at a decision epoch equals the number of nodes at the same epoch. While in games of imperfect information, there can be multiple nodes in the same information set for the player, which means that the player cannot deduce the exact node they are at.