mgss {HyRiM}

compute a multi-goal security strategy

Description

Finds security strategy that assures a maximal loss w.r.t. all goals of the given game, delivering a Pareto-efficient loss bound. Internally, it constructs an auxiliary one-against-all game and uses a sequence of linear programs to compute a lexicographic Nash equilibrium therein (Rass et al., 2022), using the methods described by (Lozovanu et al 2005; Rass, Wiegele & König 2020).

Usage

mgss(G, weights, cutOff, ord = 5, fbr = FALSE, points = 512, tol = 0.0)

Arguments

G

a multi-objective game constructed using mosg

weights

each goal in G can be assigned a weight to reflect its priority. If missing, the weights default to be all equal. The weights do not need to sum up to 1 (and are normalized towards a unit sum otherweise), but need to be all non-negative.

cutOff

(only used for continuous loss distributions) the maximal loss for which no events are expected or otherwise the risk of exceeding cutOff are accepted. If missing, this value defaults to the maximal observation on which the loss distributions were constructed (equivalently, the right end of their common support).

ord

the order up to which a continuous loss distribution shall be approximated. This value may be set to high orders when it is necessary to distinguish distributions that are similar at the tails.

fbr

if set to TRUE, instruct the function to additionally compute the best replies regarding each goal individually, assuming that defender plays optimalDefense as a leader, and the attacker per goal follows (follower's best reply). These replies are always pure strategies.

points

the number of points at which the resulting equilibrium loss distributions are evaluated numerically.

tol

occasionally, it was observed that the internal linear programs failed due to roundoff errors; in these cases, the function reported an "internal error" on the LP failure. In that case, one can supply a tolerance to go into the optimization to avoid such roundoff problems. By default, the tolerance is set to zero, to search for an "exact" solution, though. The GLPK status given in the error message refers to the codes for the GNU Linear Programming Kit, given at https://rdrr.io/cran/glpkAPI/man/glpkConstants.html.

Details

For continuous loss distributions, the function uses a Gaussian kernel density approximation (constructed using the function lossDistribution), and computes a Taylor-polynomial approximation at the x equal to cutOff for each distribution up to order ord. Preferences are decided using the methods described by (Rass, König and Schauer; 2022), and (Rass, König, Schauer, Bürgin, Epperlein and Wirth; 2021), using sign-alternating derivatives, representing a distribution by a vector with ord elements. Categorical distributions are represented likewise directly by the vector of their probability masses. In both cases, preferences are decided by a lexicographic comparison of vector-representations. The returned optima are Nash equilibria for single-goal games, and lexicographic Nash equilibria for multi-goal games. Constructing a game using mosg with vectors in the payoff description can, consequently, allows to use mgss to compute optimal results with explicit goal priorities in multi-criteria games.

Value

An object of class mosg.equilibrium, containing the following fields:

optimalDefense

a discrete probability distribution over the action space of player 1 (defender)

optimalAttacks

a discrete probability distribution over the action space of player 2 (attacker). Note that this is not a best-response to the player 1's optimalDefense, but rather the best that the attacker could do if the game were just about the particular goal that the attacker refers to. This worst-case scenario assumes that the defender would focus all its efforts to that single goal.

assurances

a list of loss distributions valid under the assumption that player 1 adheres to the optimalDefense distribution in its randomized action choices, while the opponent plays its own zero-sum equilibrium strategy in the game that is only (and exclusively) about this particular goal. This value has to be interpreted with care, as it assumes that player 1 would put all efforts into a defense for the particular goal, but in reality, will have multiple criteria to simultaneously optimize. This means that the attacker, in turn, could adapt to the optimalDefense of player 1, to cause more damage. The given assurance is thus only an upper bound of the worst-possible damage, under the assumption that player 1 would focus only on this particular goal.

The list can be accessed by the names for each goal as specified through the input mosg object G. Each distribution within assurances is a mixed loss distribution constructed using lossDistribution

br_to_optimalDefense

This is a vector of best replies per goal for a leading defender playing the fixed strategy optimalDefense, and letting the adversary (player 2) follow. It is the (stochastically largest) damage among optimalDefense^T\cdot A_p, when A_p is the game structure for the p-th goal; the vector br_to_optimalDefense contains the indices of the individually best replies, pointing into the list of attack strategies.

Note

The output loss distributions (accessible by the list assurances) cannot be used to construct a subsequent game (see mosg), since continuous distributions are represented as a sequence of points, rather than raw data or probability masses.

As of version 2.0.0 of the package, this function is no longer downwards compatible to earlier versions of itself, since the method of computation (formerly fictitious play) was replaced by linear programming to give exact solutions rather than approximations. Consequently, the parameters T (iteration count) and eps (accuracy) have become useless and have been removed after version 1.0.4.

Author(s)

Sandra Koenig, Stefan Rass

References

S. Rass, S. König, S. Schauer: Games over Probability Distributions Revisited: New Equilibrium Models and Refinements, MDPI Games 2022, 13(6), 80; DOI: https://doi.org/10.3390/g13060080, online: https://www.mdpi.com/2073-4336/13/6/80

S. Rass, S. König, S. Schauer, V. Bürgin, J. Epperlein, F. Wirth: On Game Theory Using Stochastic Tail Orders, arXiv:2108.00680v1 [math.PR], 2021

S. Rass, A. Wiegele, S. König: Security Games over Lexicographic Orders, in: Decision and Game Theory for Security, 11th International Conference, GameSec 2020, College Park, MD, USA, October 28–30, 2020, Proceedings, Springer LNCS 12513, ISBN 978-3-030-64792-6

S. Rass, S. König, S. Schauer. Decisions with Uncertain Consequences-A Total Ordering on Loss-Distributions. PLoS ONE 11, e0168583. 2016, https://doi.org/10.1371/journal.pone.0168583

S. Rass. On Game-Theoretic Risk Management (Part One). Towards a Theory of Games with Payoffs that are Probability-Distributions. June 2015. http://arxiv.org/abs/1506.07368.

S. Rass. On Game-Theoretic Risk Management (Part Two). Algorithms to Compute Nash-Equilibria in Games with Distributions as Payoffs, 2015, arXiv:1511.08591v1 [q-fin.EC].

D. Lozovanu, D. Solomon, and A. Zelikovsky. Multiobjective games and determining pareto-nash equilibria. Buletinul Academiei de Stiinte a Republicii Moldova Matematica, 3(49):115-122, 2005. ISSN 1024-7696.

See Also

A brief info on the results can be obtained by print.mosg.equilibrium, and a more detailed summary (showing all loss distributions in detail) is obtained by summary.mosg.equilibrium.

Examples

## raw data (PURELY ARTIFICIAL, for demo purposes only)
# N=100 observations in each category
obs111<-c(rep(1,40),rep(3,20),rep(5,10),rep(7,20),rep(9,10));
obs112<-c(rep(1,50),rep(2,10),rep(4,10),rep(6,20),rep(8,10));
obs121<-c(rep(1,20),rep(4,30),rep(6,20),rep(8,10),rep(10,20));
obs122<-c(rep(1,40),rep(2.5,20),rep(5,20),rep(7.5,10),rep(9,10));
obs211<-c(rep(1,30),rep(2,30),rep(5,10),rep(8,10),rep(10,20));
obs212<-c(rep(1,10),rep(2,10),rep(4,20),rep(7,20),rep(10,40));
obs221<-c(rep(1,30),rep(3,30),rep(4,10),rep(7,20),rep(9,10));
obs222<-c(rep(1,10),rep(3,10),rep(5,50),rep(8,20),rep(10,10));
obs311<-c(rep(1,40),rep(2,30),rep(4,10),rep(7,10),rep(9,10));
obs312<-c(rep(1,20),rep(3,20),rep(4,20),rep(7,20),rep(10,20));
obs321<-c(rep(1,10),rep(3,40),rep(4,30),rep(7,10),rep(9,10));
obs322<-c(rep(1,10),rep(4,30),rep(5,30),rep(7,10),rep(10,20));

## compute payoff densities
f111<-lossDistribution(obs111)
f112<-lossDistribution(obs112)
f121<-lossDistribution(obs121)
f122<-lossDistribution(obs122)
f211<-lossDistribution(obs211)
f212<-lossDistribution(obs212)
f221<-lossDistribution(obs221)
f222<-lossDistribution(obs222)
f311<-lossDistribution(obs311)
f312<-lossDistribution(obs312)
f321<-lossDistribution(obs321)
f322<-lossDistribution(obs322)

payoffs<-list(f111,f112,f121, f122,f211,f212,f221,f222, f311,f312,f321,f322)
G <- mosg( n=2,
            m=2,
            payoffs,
            goals=3,
            goalDescriptions=c("g1", "g2", "g3"),
            defensesDescr = c("d1", "d2"),
            attacksDescr = c("a1", "a2"))
eq <- mgss(G,weights=c(0.25,0.5,0.25))
print(eq)
summary(eq)

# construct another loss distribution from a given behavior in the game G
suboptimal <- lossDistribution.mosg(G, c(0.1,0.1,0.8), c(0.2,0.3,0.5))
plot(suboptimal)

# compute an equilibrium in a standard matrix game
#     [,1] [,2]
#[1,]    3    4
#[2,]    6    1
G <- mosg(n = 2, m = 2, goals = 1,
          losses = list(3,6,4,1), byrow=FALSE,
          attacksDescr = c("a1", "a2"))
mgss(G, fbr=TRUE)  # compute an equilibrium, including best replies if the adversary is a follower

# get best replies if there would be a following
# adversary per goal (taking the defender as a leader)
G$attacksDescriptions[eq$br_to_optimalDefense]