Games over probability distributions revisited: New equilibrium models and refinements

Rass, Stefan; König, Sandra; Schauer, Stefan Article Games over probability distributions revisited: New equilibrium models and refinements Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Rass, Stefan; König, Sandra; Schauer, Stefan (2022) : Games over probability distributions revisited: New equilibrium models and refinements, Games, ISSN 2073-4336, MDPI, Basel, Vol. 13, Iss. 6, pp. 1-26, https://doi.org/10.3390/g13060080 This Version is available at: https://hdl.handle.net/10419/329991 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Citation: Rass, S.; König, S.; Schauer, S. Games over Probability Distributions Revisited: New Equilibrium Models and Refinements. Games 2022,13, 80. https://doi.org/ 10.3390/g13060080 Academic Editors: Kjell Hausken and Ulrich Berger Received: 25 October 2022 Accepted: 22 November 2022 Published: 1 December 2022 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). games Article Games over Probability Distributions Revisited: New Equilibrium Models and Refinements Stefan Rass 1,2,* , Sandra König 3and Stefan Schauer 3 1LIT Secure and Correct Systems Lab, Johannes Kepler University, 4040 Linz, Austria 2Institute for Artificial Intelligence and Cybersecurity, University of Klagenfurt, 9020 Klagenfurt, Austria 3Austrian Institute of Technology, Center for Digital Safety & Security, Giefinggasse 4, 1210 Vienna, Austria *Correspondence: [email protected] Abstract: This article is an overview of recent progress on a theory of games, whose payoffs are probability distributions rather than real numbers, and which have their equilibria defined and computed over a (suitably restricted yet dense) set of distributions. While the classical method of defining game models with real-valued utility functions has proven strikingly successful in many domains, some use cases from the security area revealed shortcomings of the classical real-valued game models. These issues motivated the use of probability distributions as a more complex object to express revenues. The resulting class of games displays a variety of phenomena not encountered in classical games, such as games that have continuous payoff functions but still no equilibrium, or games that are zero-sum but for which fictitious play does not converge. We discuss suitable restrictions of how such games should be defined to allow the definition of equilibria, and show the notion of a lexicographic Nash equilibrium, as a proposed solution concept in this generalized class of games. Keywords: game theory; security strategy; generalized game; loss distributions; decision making; Nash equilibrium; lexicographic optimization 1. Introduction In the year 2015, a theory of games was proposed that does not use real-valued payoffs, but rather achieves optimization using stochastic orders on rewards that are probability distributions. Ever since, a couple of intricacies—even pathologies—have been found in such generalized games, and this article is a compilation of the recent findings, advantages, but also pitfalls to avoid when working with game theory over the abstract space of probability distributions. The theory was originally motivated by applications of games in security risk management, where payoffs are hardly crisp or accurately quantifiable; thus, there is a desire to include uncertainty in the game model already before computing solutions. This uncertainty is not in the actions, as is the case for refined equilibrium concepts such as trembling hands or perfect equilibria, but rather in the rewards themselves. Reducing the random outcomes to their averages (expectations) or other representative statistics necessarily sacrifices information that is, in security risk management, generally scarce already. This creates an additional desire to use information about possible effects of an action to the maximum extent available. The story behind all our upcoming considerations evolves around a defending player 1 who seeks to guard a system against a rational or irrational attacker from outside. In a typical generic setting, the defender may be the chief security officer (CISO) of some large enterprise, and is committed to business continuity management and the most important line of defense against external competitors and adversaries (hackers, and others). In this situation, the defender often has to consider multiple goals simultaneously, including damage or loss of sensitive data, the possibility of physical damage to equipment Games 2022,13, 80. https://doi.org/10.3390/g13060080 https://www.mdpi.com/journal/games Games 2022,13, 80 2 of 26 and people (for example, if a production line gets hacked and a robot damages goods or hurts a person), up to issues of reputation, damage compensations, and many others. A security game in such contexts is thus generally a multi-criteria optimization problem, with hardly quantifiable losses to be minimized. For example, if a production line stops for some time, we may have an average estimate of how much that costs per hour, but this value is not quantifiable in an exact way, since the duration of the outage remains random. Insurance and actuarial science [ 1 , 2 ] offer lots of probabilistic models to describe extreme events (the whole theory of extreme value distributions, up to catastrophe theory, can be useful here), but game theory can become difficult to apply if we need to define real-valued, and hence exact, utility functions for optimization. Summarizing the challenges, we have the following situation: A player is minimizing losses by taking strategic action. The losses are inherently random, and admit a quantification only up to the point of modeling a probability distribution that is conditional on the other players’ actions. Specifically, we are unable to give an exact valuation of payoffs to a player due to intrinsic uncertainty. We assume, however, that we can reasonably model the players’ random payoff as a (conditional) probability distribution, with loss distribution models that are assumed to exist and be known for the given application context. As an example (taken from [ 3 ]), such a conditional distribution can be the probability to “catch an intruder”, conditional on the (random) location of the security guard to be at the same location (by coincidence). Similar games have been proposed for border protection, airport protection and coast guarding [4]. Besides the problem with uncertain revenues, some additional quantities that are difficult to bring into classical game models may be interesting. For example, since games typically optimize an average (expected) payoff, what are the chances of receiving more or less than this optimal average? This is important to know when buying insurance or building up backup resources, and is non-trivial to handle with classical game models. We discuss this situation as a concrete motivation for the generalized class of games in Section 1.3. 1.1. Our Contribution This study compiles recent work, findings and progress towards a theory of games for strategic decision making in non-cooperative situations, when consequences are intrinsically random and real valued (and hence crisp) payoff values are not available or are unreliable. This is essentially different from situations in which the imprecision is in the gameplay, such as trembling hands or perfect equilibria capture [ 5 , 6 ], and is also different from situations in which the uncertainty is about the adversary, such as Bayesian games [ 7 ] cover by making assumptions about different types of players, e.g., based on levels of rationality [ 8 ]. Defining games with “uncertain opponents” technically leads to uncertain utilities, as we consider, but the optimization itself is generally again over real values being expectations of (conditional) distributions. We intentionally want to avoid derandomization by averaging, since the expectation E(U)∈R contains less information than the random variable U . In situations in which information is notoriously scarce, such as in security, unnecessary loss of information should be avoided. This is a common circumstance in risk management, where qualitative and overly precise valuations of an actions consequence are not only hard, but even explicitly discouraged [ 9 ]. As an illustration, let us consider quantitative risk management in engineering. In this context, a risk manager makes a list of possible threats to its assets (enterprise business values, human beings or similar), where each threat, if it manifests in reality, may have an impact (e.g., monetary losses, reputational damages, etc.), and occurs with a likelihood to be estimated. The term “risk” is defined by a simple formula to be risk =impact ×likelihood, (1) Games 2022,13, 80 3 of 26 and, provided that the risk manager can assign reliable values to both variables, nicely lends itself to optimization and game theory [ 10 ] (indeed (1) is interpretable as “expected damage” and can be taken as an adversary’s expected utility). If the threats are caused by a rational adversary trying to hack or otherwise hit a system, the threat list is nothing else than an action set of a hostile opponent. For the defender, engaging as the other player in the game has its own action set to protect against the possible threats. Risk management standards such as ISO27000 or ISO31000 provide long lists of actions (termed “controls” in this context), which are the defender’s actions to choose from strategically. The above formula can then be operationalized by playing a non-cooperative game between two players, featuring the defender versus the attacker. The player’s expected utility can be taken directly as the risk = impact × likelihood. From the defender’s perspective, the “likelihood” would be the (optimized) probabilities of actions taken by the opponent, which is nothing other than a mixed equilibrium strategy. Likewise, the defender’s equilibrium then becomes an optimal randomized choice of actions to protect against all threats simultaneously. This mixed equilibrium is then convertible into an optimal resource allocation strategy for the defender, thus providing a provably optimal use of (typically scarce) defense budgets, against a rationally and strategically acting adversary. Recent work on game theoretic cyber security has independently pointed out the lack of consensual interpretations of mixed strategies in security, and our work addresses the resource allocation- and mixed strategy interpretation problem, both noted by [ 11 ], on a common ground. Reference [ 3 ] provided an interesting application for security surveillance monitoring, where the optimization must consider multiple criteria, even including the coverage level of the surveillance, but also the level of inconvenience that surveillance may cause to people at work. Game theory offers powerful possibilities in letting us quantify likelihoods for risk management directly as optimal choice rules, for example, or interpreting mixed strategies as optimal resource allocation rules. However, the difficulty of applying games over real values is the need to “accurately quantify” the impact, which some authors even discourage in light of much and reliable data to be available. Reference [ 9 ] explains this recommendation using an example of the decision about whether or not to buy protection against lightning strikes. Based on long-term statistical evidence, the likelihood of a lightning strike is accurately quantifiable (to be ≈ 1.24 × 10 −6 in the region around Munich/Germany), thus providing a seemingly reliable value for the risk Formula (1) . Similarly, the impact of a lightning strike is also not difficult to quantify, since we most likely know how expensive a repair to the facility would be. Thus, despite both values being accurately estimable (e.g., 10,000$), their product numerically evaluates to an expected loss of ≈ 0.124 $ . Basing a decision on this value to not invest in lightning protection is clearly implausible, and this example (among many others that are similar), leads to official recommendations to not estimate probabilities or impacts with seeming precision numerically, where there is no absolute accuracy. The problem appears more widespread than only in the risk-management context, since any strategic decision under uncertain consequences of actions will need a wellfounded account for uncertainty. For example, the effects of fake news spreading over social media certainly call for strategic intervention, but the effect of campaigns against fake news and disinformation are easily quantified in terms of costs, but are almost impossible to quantify in terms of effects. This makes the definition of crisp, i.e., real-valued utilities, generally hard in many practical instances of security management, and creates a need for a more general concept of games that can work with vague, fuzzy or generally uncertain outcomes of strategic actions. This work, and its contributions, are thus motivated by the following five aspects collected from practical project work, which touch upon all of the above points: First, the quantification of impacts for strategic optimization of actions should be avoided by official recommendations [ 9 ]. Our work addresses this by letting games be played over uncertain utility values. Games 2022,13, 80 4 of 26 Second, strategic interventions in non-cooperative situations where the response dynamics is unknown, intrinsically uncertain or simply not describable in precise mathematical terms, such as social risk response—for example, [ 12 , 13 ]—may not lend themselves to the definition of crisp values. Agent-based simulations, as one possibility to anticipate social or community replies to actions of authorities, deliver a multitude of possible scenarios, and compiling a single value as a utility to optimize actions and interventions would be accompanied by a considerable loss of valuable information. Games using probability distributions are “conservative” here in using all information embodied in random simulations (e.g., Monte Carlo) for decision making. This also relates our work to empirical game theory, making statistical models such as those in actuarial science [ 1 , 14 ] useful for strategic decision making using games. Third, optimizing averages offers no information, nor guarantee, about the fluctuations around the optimal mean. If the game is played to minimize the “expected damage”, one may consider buying insurance to cover for such expected losses. However, what if the game overshoots the losses in one or several rounds? How much more than the expected loss should we anticipate to buy insurance for? Real-valued game models are only concerned with optimizing the average, but do not give information about how “stable” this average outcome is. Playing the game over the whole distribution object, we can also consider the variance, skewness and other properties of the distribution in the decision-making process. One such property is the disappointment rate, which would lead to a discontinuous utility function in a real-valued instance of a game, and hence Nash equilibria may no longer exist. A contribution of this work is showing how probability distributions for payoffs in a game model can avoid such existence issues, and how to play games not only for the best outcome, but also for the least disappointment. This is a new form of equilibrium refinement, which much other work (not only in security) approaches by perfect equilibria or other (more technical) means. Fourth, it has long been recognized that the utility maximization paradigm is not necessarily consistent with human decision making [ 15 ]. Procedural theories, prospect theory and many other paradigms of decision making have been proposed ever since. As an example, reference [ 3 ] has proposed a method to define utilities with regard to subjective risk appetite (aversion or affinity to risk). This construction leads to vector-valued utility functions, and recent work [ 16 ] has demonstrated that such games do not necessarily have Nash equilibria. One contribution of this work is showing a proper solution concept in this case. Finally, along the lines of vector-optimization, multi-criteria games are long known, and concepts such as Pareto–Nash equilibria are definable and useful [ 17 ]. However, Pareto optimization needs a weighting among the multitude of criteria to scalarize the utility and thereby reduce the problem to a game with an aggregate, but scalar, utility. Since the lexicographic order is known to not be representable by a continuous real-valued function, this work contributes a method of defining an equilibrium over games with multiple goals in strict priority. A domain of practical application is in robotics, where the first priority is to avoid human coworkers being hurt by a malfunctioning robot, and the cost and functional correctness of the robot come as secondary and ternary goals. The contributions made here, relative to related work, are as follows: • The proposal to model utilities not only as numbers, but whole distributions. This was first proposed in [ 18 ], and applied in [ 3 , 10 , 19 ]. The theoretical pathologies arising with this, however, were not discussed in these past studies, until reference [ 16 ] first identified theoretical difficulties. This prior reference did not provide solutions for some of the issues raised, which our work does. • The use disappointment rates in game theory. Prior work did either not consider disappointment in the context of games [ 20 , 21 ], or focused on the applicability of conventional equilibria by means of approximation or using endogenous sharing [ 22 ]. Our study differs by describing and proving how to make disappointment rates Games 2022,13, 80 5 of 26 continuous, and for the first time, proposes disappointment as a (novel) equilibrium selection criterion. • We show the lexicographic Nash equilibrium as a solution concept that is well defined for vector-valued games that past work has shown to not necessarily have a classical Nash equilibrium [ 16 ]. Our work picks up this past example of a game without an equilibrium and shows how to define and compute a meaningful solution. • We show and explain a case of non-convergence of Fictitious Play (FP) in zero-sum games that has been reported in [ 23 ] but was left unexplained ever since in past research. This phenomenon appears, as so-far known, only in games with distributions as utilities, since FP is known to converge for zero-sum games by classical results [ 24 ]. 1.2. Preliminaries and Notation We let normal font lower-case letters be scalars, and bold-face letters denote vectors. Upper-case letters in normal font denote sets or random variables, and bold print means matrices. The symbol X∼F means that the random variable has the distribution F . For the expectation of X , we write EF(X) or briefly E(X) if the distribution is unambiguous from the context. For a bounded set X , we write 4(X) to mean the set (simplex) of all probability distributions supported on X . If X is finite with cardinality |X|=n , we have 4(X)⊂[ 0, 1 ]n as the set 4(X) = {(p1, . . . , pn)∈[0, 1]n|p1, . . . , pn≥0; ∑n i=1pi=1} . The symbol AS will hereafter mean the “action set” of a player. It contains all pure strategies, and the corresponding set of mixed strategies is denoted as S=4(AS) , with annotations to make the players explicit. That is, ASi , Si are the i -th player’s pure and mixed strategies, whereas AS−i , S−i is the Cartesian product of the strategy spaces of player i ’s opponents. An asterisk annotation denotes an “optimal” value, e.g., an equilibrium or general best response. 1.3. Disappointment Rates The so-called disappointment rate [ 20 – 22 ], is, for a random payoff X , the probability Pr(X>E(X)) , where the expectation is with regard to the equilibrium strategy in the game. That is, a minimizing player may not only be interested in the least possible loss X , but may also seek to minimize chances to suffer more than the expected loss E(X) . In a security application, where the game is used to minimize expected damage, we may thus face the following challenge: • The game is designed to advise the defender to best protect its system against an attacker. The optimization will thus be a minimization of the expected loss Ex,y(L) for the defender, accomplished at the equilibrium strategy x=x∗ and best reply to it y∗ in a security game model. See [25] for a collection of examples. • Knowing that it has to prepare for an expected loss of v=E(L) , the defender may build up backup resources to cover for cases of a loss >v , one way of which is buying insurance for it. However, E(L) is an average, and naturally, there may be infinitely many incidents where the loss overshoots the optimized expectation v that an insurance may cover. Hence, naturally, the defender will strive to minimize the chances for the current loss being >v . This is where disappointment rates come into the game. Modeling payoffs as entire probability distributions put more information into the game model and can help in cases in which additional quantities besides the expected payoff are of interest, such as disappointment events. Adding this optimization goal as a second dimension to the game, however, introduces a discontinuity in the payoff function. For a finite (matrix) two-player game, the defender would optimize the function d(x,y) = n ∑ i=1 n ∑ j=1 xi·I(aij >x>·A·y)·yj, if the loss, i.e., the highest priority goal, is described by the payoff structure A∈Rn×m . The inner indicator function I is a discontinuous part, and as such can render the classical Games 2022,13, 80 6 of 26 equilibrium existence results inapplicable. Nash’s theorem and all theory that builds upon it relies on continuity of payoffs, and [ 26 ] gave an explicit example of a game with discontinuous payoffs that does not have a Nash equilibrium. While games with discontinuous payoffs may not admit equilibria in general, computing the disappointment rate for a fixed equilibrium can be as simple as in Example 1. Example 1. Consider the zero-sum two-player game with payoff structure A=3 4 6 2 whose equilibrium is x∗= ( 0.8, 0.2 ) and y∗= ( 0.4, 0.6 ) for player 1 being a minimizer. The saddle point value is v= (x∗)>·A·y∗= 3.6. For computing player 1’s disappointment rate d , only those entries that are larger than v are relevant; all others count as zero, i.e., we get the matrix of disappointment indicators as D= (I(aij >v))ij=1...2 =0 1 1 0 . The equilibrium average of indicators in D is the equilibrium disappointment, given by d(x∗ , y∗) = (x∗)>Dy∗= 0.56. Thus, when playing the equilibrium strategy, we have a 56% chance that we will “suffer” more than the expected loss v, and hence are “disappointed”. In the simple case of matrix games, Example 1may serve as an equilibrium selection criterion; namely, among several possibilities, a player may choose the equilibrium of smallest disappointment. If both players do this, we are back at a minimax optimization problem, yet only on the disappointment rates instead, and over the equilibria that exist in the original game. If there are finitely many equilibria, and each has its uniquely associated disappointment rate, we arrive at nothing else than another finite game about equilibrium selection in a prior game. Two facts about this observation are important to emphasize: first, the disappointment rate cannot serve as a goal in its own right, since if a player is just seeking to avoid disappointment, the disappointment rate can play towards maximizing the losses to avoid being disappointed (effectively making Pr(X>E(X)) zero and hence minimal). So, disappointments are only meaningful as a secondary goal that depends on a more important utility. This is the second important observation: the idea of first computing an equilibrium in a given game, and then moving on to a secondary game to select from the perhaps many equilibria that we found before, lets us handle multi-criteria decisions with strict priority orders on the goals. In some cases, such as for disappointment rates, the priority ordering is natural, since disappointment can occur about some utility of primary interest. In other cases, however, goals may not sub-quantify other goals, but can be considered on their own and more or less important than other goals (according to a priority ranking). The idea of optimizing lexicographically will hereafter turn out to be fruitful to solve a generalized class of games whose payoffs are more than numbers, and the rewards—not just the mixed strategies—come as whole probability distributions. One motivation for expressing payoffs as entire probability distributions is, in fact, avoiding the discontinuity problem of disappointment rates, as we show in the following section. 1.4. Making the Disappointment Rate a Continuous Function We let X be the random reward from a game in which the players act according to a joint mixed, and hence random, equilibrium strategy s∗ . In this section, we let s∗ be a multivariate probability distribution over the Cartesian product of all strategy spaces of all players (thus, including the case of n -person games with n> 2). How can we optimize the quantity Pr(X>E(X)) = Es∗(X>Es∗(X)) , if it is, by expressing it as an indicator function, essentially discontinuous? Games 2022,13, 80 7 of 26 Several answers are possible, among them the use of more complex methods such as endogenous sharing [ 22 ], or smooth approximations of the disappointment rate, e.g., for twoplayer games, by changing the indicator to a continuous function such as d(x,y) = max0, x>·A·y−v , which is zero if we get less than v , and only has a penalizing effect if more than the expected minimum is paid. An even more straightforward solution is setting up the game with not only a payoff value for each strategy, but instead defining a whole payoff distribution that is conditional on the players’ strategies. That is, for each joint (pure) strategy profile (xi , x−i) of the i -th player and its group of opponents (denoted by −i in the subscript), we would classically define the payoff value ui(xi , x−i) , or its expectation in case of the mixed extension. In both cases, ui is typically a real number. However, if we let ui be a probability distribution over the set of (real-valued) utilities, we may define ui(xi , x−1) = Fi(X|xi , x−i) as the distribution function of the random reward to be obtained if player i picks (pure) strategy i , and the opponents jointly play the strategy profile x−i. Let us illustrate this modeling for the special case of a finite two-player game: we let AS1 , AS2 be finite sets of pure strategies hereafter. If the game matrix is populated with conditional payoff distributions Fij =F(·|i , j) , such that player 1 receives the random payoff X∼Fij whenever it takes action i∈AS1 and Player 2 plays action j∈AS2 , then the overall payoff, by the law of total probability, for player 1 has the distribution Fs(t) = ∑ i,j Pr(L≤t|i,j)·Pr(i,j), (2) where Pr(i , j) is the probability of the action profile (i , j)∈AS1×AS2 chosen at random by the players. Assuming independence of actions, we have Pr(i , j) = Pr(i)·Pr(j) = xi·yj , when x , y denote the mixed strategies. Furthermore, Pr(X≤x|i , j) is exactly a payoff distribution Fij put into the game’s payoff matrix. Thus, we can continue (2) by writing Fs(t) = ∑ i,j xi·xj·Fij =x>·A·y, (3) and we are back at the familiar payoff functional for matrix games, only now having the matrix A= (Fij)n,m i,j=1 defined with all distribution functions for the payoffs, rather than single (crisp) values. The case of modeling with numbers is (only) included as a special case, since we can take the expected value EF(X) of the random variable X∼F(·| · xi , x−i) and receive a classical model that uses only numbers in the payoff structure. If we now add disappointment rates as an equilibrium selection criterion, i.e., a subordinate goal, we can compute its value from the distributions. Letting s∈ 4(∏n i=1ASi) denote the joint mixed strategy space of all players, the disappointment rate for the i -th player is d(s) = Pr(X>Es(X)) = 1−F(u(s)|s), (4) where F is the cumulative distribution function of the random payoff X to player i , and u(s) is the utility function for this player. Since the formula would be the same for all players, we omit the indication of (4) for a (fixed) i-th player in the following. Now, we are interested in how d is depending on the joint mixed strategies embodied in s. For a distribution-valued modeling, the disappointment rate is continuous again: Proposition 1. Let the Cartesian product of all strategies in an n -player game be the set Ω , and let Ω⊂Rn be compact. Moreover, let the utility function u:Ω→R be continuous. Let each player have its own (possibly distinct) function F(·|s) that is a conditional distribution of the random reward X ∼F(·|s)that this player receives when sis the joint action profile of all players. Then, the disappointment function d for each player, as defined in (4) , is continuous in s∈Ω . The proof of Proposition 1is given in Appendix A. Games 2022,13, 80 8 of 26 Modeling games with payoff distributions rather than payoff values naturally raises the question of whether we can carry over the theory of classical games to this generalized setting. In fact, this transfer is possible via a field extension from R to a strict superset of real numbers, in which payoff distributions can be mapped into and totally ordered stochastically. However, the price for this generality is significant, as we discover various unusual, and partly unpleasant, phenomena through this transition. We dedicate the rest of this article to a description thereof. 2. Games with Rewards Expressed as Whole Distributions Following the classical axiomatic construction that von Neuman and Morgenstern have put forth (a very concise and readable account is given in [ 27 ], (Section 2)), it is enough to have a certain ordering ≤ on the reward space R , into which we let all utility functions map. Under certain assumptions on the ordering ≤ , we can define a real-valued utility function u such that a best decision for a player is characterized as carrying the maximum utility value over possible choices in R . This is the von Neumann–Morgenstern construction, which, in the way we state it here, requires R to be a vector space over R , and the ordering ≤ should be (i) complete, meaning that for all ∀r1 , r2∈R , we either have r1≤r2 , r1>r2 or r1=r2 , (ii) transitive, meaning that r1≤r2 and r2≤r3 implies r1≤r3 , (iii) continuous, meaning that if r1≤r2≤r3 , then there is some p∈[ 0, 1 ] , such that p·r1+ ( 1 −p)·r3=r2 , and (iv) independent, meaning that whenever r1≤r2 , then for any s∈Rand p∈[0, 1]we have p·r1+ (1−p)·s≤p·r2+ (1−p)·s. Under these hypotheses, the existence of a (continuous) utility function can be established, such that the utility-maximizing principle to find best decisions becomes applicable. A related similar result is the Debreu representation theorem [ 28 ], which asserts the existence of utility functions under a set of slightly different (yet all topological) assumptions on the space R. It is not difficult to verify that the axioms of von Neumann and Morgenstern all apply to the real numbers R as the reward space, and hence most game models of today are formulated in terms of real numbers. Now, the idea that first appeared in [ 23 ] was to simply replace the space R with the space of hyperreal number ∗R , which is a strict extension field of R to include infinitesimal and infinitely large numbers. It does so by modeling numbers as sequences ˆ a= (an)n∈N∈∗R , with the intuition that an infinitesimally small number would be such that limn→∞an= 0, while an infinitely large number ˆ a= (an)n∈Nhave limn→∞an=∞. Remark 1 (Notation for the hyperreal space and hyperreal numbers) . It is common in the literature to denote the hyperreal space by a superscript ∗ preceding R , i.e., to use the symbol ∗R . The superscripted star is, however, also commonly used to denote optimal strategies in game theory, such as x∗ as the best strategy for some players. To avoid confusion about the rather similar notation here, we therefore write ˆ x to mean a hyperreal element, and reserve the ∗ -annotation for variables to mark them as “optima” for some minimization or maximization problem, with the symbol ∗R being the only exception, but without inducing ambiguities. The space ∗R is actually a quotient structure, with the equivalence ˆ a=ˆ b to hold if and only if certain sets of indices match. The exact information of which indices matter is given by an ultrafilter U over N . This is a filter 1 over N that is maximal with regard to ⊇ . To define ∗R , we additionally require that the intersection of all elements in U is empty (so that U is called free); then ∗R=R∞/U , where the equivalence relation to define this quotient set is (a1 , a2 , . . .) = (b1 , b2 , . . .) if and only if {i∈N|ai=bi}∈ U . In other words, U is a family of subsets that specifies which indices matter for a comparison of two hyperreals ˆ a , ˆ b . Likewise, we can define ≤ , < , ≥ , . . . relations, over ∗R in this form. Moreover, ∗R inherits the field structure from R , so it has a well-defined arithmetic (addition, subtraction, multiplication and division) just as R. Games 2022,13, 80 15 of 26 Proposition 2. Let a finite two-player zero-sum game be given with pure strategy sets AS1 , AS2 and vector-valued payoff functions u mapping into Rd for player 1 and −u for player 2. Furthermore, let the coordinate functions of u be ordered by decreasing priority (i.e., u1 is the most important goals for the players). The correspondence that maps (x , y)∈ 4(AS1)× 4(AS2) to its best reply set BRu1:d(x , y)× BR−u1:d(y,x)has a fixed point. Proof. We need to prove that some (x∗,y∗)is a best-reply to itself, i.e., (x∗,y∗)∈BRu1:d(x∗,y∗)×BR−u1:d(y∗,x∗). The proof is by induction over d : for d= 1, the game is a conventional matrix game in which a fixed point exists by Nash’s classical existence result about equilibria, since the game is finite. For i> 1, (11) prescribes find an optimium over the so-far known set of equilibria, any convex combination of which is again an equilibrium 5 . This set is compact, so the game with (modified) strategy spaces 4(BRu1:i−1) for player 1, and 4(BR−u1:i−1) for player 2, and payoff functions ui , −ui , has again an equilibrium as a fixed point by Glicksberg’s theorem [ 41 ]. Since the equilibrium is a best response to itself, this puts (x∗ i,y∗ i)∈BRu1:i(x∗,y∗)×BR−u1:i(y∗,x∗), and completes the induction step. Formally, we have the following definition appearing in [ 37 ] earlier, but now reframed into a fixed-point formulation: Definition 2 (Lexicographic Nash equilibrium) . Let {Ai∈Rn×m|i=1, 2, . . . , d} be a finite collection of matrices that define payoff functions u in a two-player zero-sum game, all over the same strategy spaces AS1 , AS2 for the players, and listed in descending order of priority (i.e., A1 is the most important, and Ad is the least important goal dimension). We call a strategy profile (x∗ , y∗)∈ 4(AS1)× 4(AS2) alexicographic Nash equilibrium in mixed strategies, if it is best reply to itself, i.e., a fixed point of the best response correspondence (x , y)7→ BRu1:d(x∗ , y∗)× BR−u1:d(y∗,x∗), with BR defined by (11). Proposition 2then establishes the non-emptiness of Definition 2, and can be interpreted as the assertion that a lexicographic Nash equilibrium is indeed a best reply (in the sense of (11)) to itself. By (11), the one-dimensional case is the requirement that (x∗,y∗)∈[argmin x∈4(AS1) u(x,y∗)] ×[argmin y∈4(AS2) −u(x∗,y)], which is equivalent to u(x∗ , y∗)≤u(x , y∗) for all x and u(x∗ , y)≥u(x∗ , y∗) for all y or more compactly, u(x,y∗)≥u(x∗,y∗)≥u(x∗,y), (12) i.e., the usual definition of an equilibrium; cf. (5) . However, as [ 16 ] demonstrated for the game from Equation (10) , we cannot simply rewrite (12) to use ≤lex instead of ≤ , since we may lose the existence of equilibria. The concept of a lexicographic Nash equilibrium from Definition 2, together with Proposition 2provides us with an equilibrium concept that does exist, at least in the zero-sum case. Remark 2. Alternatively to an equilibrium, a player can also look for a security strategy [ 42 , 43 ], which is the best that they can do, presuming any behavior of the opponent. For a general n -person game with strategy space ASi and utility function ui for the i -th player, a (mixed) security strategy is found as the solution to the following optimization problem: a∗ i∈argmin a∈4(ASi) min a−i4(AS−i)ui(a,a−i), (13) Games 2022,13, 80 16 of 26 In two-player games, a security strategy is computable by a player replacing the opponent’s utility function u2 simply by the negative version of its own utility to assume a worst-case behavior. That is, the game may be non-zero sum in allowing the players to have distinct utilities u16=−u2 , and a security strategy for player 1 is simply a Nash equilibrium in the substitute zero-sum game assuming u2:=−u1for player 1, and conversely for the other player. The point made here is that a security strategy is, in some cases, a fixed point of some properly modified best-response correspondence (namely that of the assumed zero-sum game). Proposition 2 makes the same fixed point assertion about lexicographic Nash equilibria, thus establishing a likewise similarity between classical security strategies, and lexicographic security strategies from past literature [39]. As for the computation of equilibria, we may consider direct procedures using linear optimization, but also online learning schemes such as fictitious play. It turns out that the latter, unlike in the classical case, does not necessarily converge, at least not to a Nash equilibrium in the hyperreal space. 4.1. Convergence (Failure) of FP in Zero-Sum Games Returning to the question of whether an online learning process will carry the players to convergence, we discover another unusual behavior of games played over probability distributions: FP does not necessarily converge even for zero-sum games, in contrast to what we would expect according to classical results [24]. This failure of convergence is easily demonstrated by another 2 × 2-game reported in [ 23 ], and given later as Example 2. Before demonstrating the problem, let us briefly recall the idea behind FP: it is essentially an endless repetition of the game in which each player keeps record of the opponent’s moves, and correspondingly plays a best reply to the empirical mixed strategy that was observed so far. We delegate a detailed description to Appendix C. J. Robinson has shown [ 24 ] that this process will always carry to convergence if the game is zero sum. Later, the convergence was also established for various other classes of games, including non-degenerate 2 ×2-games, potential games, games that can be solved by iterated elimination of dominated strategies, 2 ×n -games, and several others. Example 2shows that the convergence no longer holds if the game is played with distributions as rewards instead of numbers, although it is still zero sum. Example 2 (FP not converging to an equilibrium, although the game is zero sum [ 23 ]) . Let the expected payoffs in a hypothetical 2×2-game be given as A=2 5 3 1 (14) and let us assume that uncertainty is to be included here by allowing a bounded random deviation from these means. This variation is describable in various ways, but let us assume that the modeler has collected empirical data to construct a non-parametric estimator using Epanechnikov kernels k(x):=3 4(1−x2),|x|≤1 0, otherwise, (15) and replaces the entry aij by the distribution Fij with mean aij and some small variance. The respective game with distributions as payoffs thus is again a 2 × 2-matrix, but with probability density functions in the cells; see Figure 1. Games 2022,13, 80 17 of 26 12345 0.0 1.0 2.0 3.0 F11 12345 0.0 1.0 2.0 3.0 F12 12345 0.0 1.0 2.0 3.0 F21 12345 0.0 1.0 2.0 3.0 F22 Figure 1. Distribution-valued game as a version of (14) with uncertainty around the expected payoffs (on the abscissa of each probability density). It is easy to compute the Nash equilibrium for the exact matrix A as v(A) = 2.6, obtained by the mixed equilibrium strategies x∗= ( 0.4, 0.6 ) and y∗= ( 0.8, 0.2 ) for both players. Since our setting shall merely capture our uncertainty about the payoffs, we would thus naturally expect a somewhat similar result when working on the payoff distributions in Figure 1. Unfortunately, however, running FP according to the algorithm from Appendix Cdemonstrably fails. After a few iterations, the algorithm gets stuck in always choosing the first row for player 1, since vup is always ≤hr-preferable over u∗/k, which is immediately obvious from plotting the two distributions: 12345 0.0 1.0 2.0 3.0 vup ≤hr (by criterion C2) 12345 0.0 1.0 2.0 u∗/k Observe that choosing the upper row in the payoff structure adds probability mass to lower damages, but leaves the tail of the distribution unchanged. Thus, although the overall damage accumulates, this effect is not noticeable by the stochastic ordering based on the hyperreal ≤hr relation. Consequently, the algorithm will counter-intuitively come to the conclusion that x= ( 0, 1 ) is a pure equilibrium, which is not plausible or meaningful. Where does the process fail? The answer is found by a deeper inspection of Robinson’s proof [ 24 ], bearing in mind that all variables are to be taken as hyperreals. The sequence enters an ˆ ε -neighborhood for ˆ ε> 0 once the iteration count exceeds the lower bound ˆ n0= 8 ˆ aˆ t∗/ˆ ε , where ˆ a is the maximum (hyperreal) absolute value of the entries in the payoff matrix. Since this matrix contains all distributions, the respective k -th order moment sequences diverge towards infinity. Hence, ˆ a is an infinitely large hyperreal, making ˆ n0 itself infinitely large. Hence, no iteration counter from within N can ever exceed ˆ n0 , which rules out convergence towards a Nash equilibrium for any algorithm running on a conventional computer, although the sequence would converge if it runs towards hyperreal infinity. However, if we assume that the distributions all have a common support, i.e., there are no regions with zero probability mass over a whole interval Ω= [a , b]⊂R , then the individual preferences will depend on the values that the density functions in A take on at x=b . That is, if the matrix A= (fij(x):Ω→R)∈ Fn×m is composed from all densities, then running FP boils down to running the iteration on the real-valued matrix Games 2022,13, 80 18 of 26 A(b) = (fij(b)) ∈Rn×m. The game remains zero sum, and hence the process does converge according to [24]. What we have discovered is thus a slightly unexpected case of a sequence (of hyperreal numbers) that is convergent, but nonetheless admits subsequences that do not converge to the limit. Based on the example from Section 3, we may not reliably claim that the limit to which FP converges for a distribution-valued game is a Nash equilibrium, but we can identify it as a lexicographic Nash equilibrium by looking at what the process of online learning does in more detail. 4.2. Online Learning Lexicographic Nash Equilibria in Zero-Sum Games Without loss of generality, let us consider an arbitrary payoff distribution to be represented as a vector of values (p1 , . . . , pd) , which are either direct probability masses for a categorical distribution (see criterion C1 above) or otherwise representative values computable for a continuous distribution (see criterion C2 above). So, the payoff matrix for a game with payoffs represented as full probability distributions is a matrix of vectors A= (Rd)n×m, and in which the payoffs are strictly ordered lexicographically. The matrix A of vectors translates into a total of d real-valued matrices, just as in the setting just described, only that the projected matrices A1 , . . . , Ad corresponding to the respective (d+ 1 −i) -th coordinates of the probability mass vectors appear in reverse order of priority (so that A1 is the matrix of all tail masses pd for each strategy combination i , j , A2 is the matrix of masses pd−1 for each strategy combination, and so on). Letting the players be minimizers, they will, among two choices, prefer the distribution with less tail mass. This means nothing other than letting the FP process initially run on the matrix A1 of last coordinates only, and from there, it will converge to a best reply. Once FP has converged, it will continue by changing strategies again to optimize the value on the second-largest coordinate. However, exactly this update forces the algorithm to then return to the last coordinate again and restore the optimum there. Here, we have another explanation as to why FP cannot converge over a countable sequence of iterations, since it would take a theoretical infinitude of steps to optimize the last coordinate, followed by a single optimization step on the second-to-last coordinate, and then taking the next infinitude of steps to restore optimality on the last coordinate again. Fortunately, we can prevent the computation from having to re-optimize over and over again, if we compute the equilibrium using plain linear programming first, and then add the constraint of not losing the optimal gains on the previous coordinate when moving to the optimization of the next coordinate. 4.3. Exact Computation of Lexicographic Nash Equilibria in Two-Player Zero-Sum Games We can directly translate (11) into a series of optimization problems, with more and more constraints being added: initially, on the first coordinate, we just set up a standard linear program, minimize v subject to v≥∑n i=1(A1)ij ·xi∀j=1, . . . , m; x1+x2+. . . +xn=1; xi≥0∀i=1, 2, . . . , n;        (LP) in which the symbol (A1)ij denotes the ij -th entry of the payoff matrix A1∈Rn×m . To showcase how to proceed to the next coordinate, let us simplify and thereby better distinguish the payoff matrices by putting A:=A1∈Rn×m and writing B:=A2∈Rn×m , to mean the most important (matrix A of tail masses pd ) and second-most important payoff (Bof probability masses pd−1). Games 2022,13, 80 19 of 26 A more compact version of (LP) in matrix form, using the symbols 1p×q to denote (p×q)-matrix of all 1 s, is minimize (1 0)>·(v1,x1)(16) subject to 1m×1−A> 011×n·v1 x1≥0 =1 where we added the subscript “1” as a reminder that v1 is the saddle-point payoff in the (most important) coordinate, and attained by playing the strategy x∗ 1. This corresponds to solving the “i=1”-case of (11). Next, we go for the second (butlast) coordinate with payoff structure B . We end up with the same linear programming problem (LP) as above, but in addition, the strategy x∗ 2 computed in this new LP should, on the payoff structure A , perform at least as well as x∗ 1 so far, meaning that we want all coordinates of x> 2·A≥v1. Intuitively, any behavior different from x06=x∗ 1 would end up with a possibility for the opponent to cause less revenue than v1 for the first player by the equilibrium property (5) , meaning that (x0)>·A·y∗≥(x∗)>·A·y∗, since player 1 is a minimizer. So, among the remaining equilibria, we would pick one that optimizes the second- to-last coordinate, while it retains the performance in the coordinate(s) that we had so far. This solves the “ i= 2”-case of (11) if player 1 adds the constraint (x2)>·A·ei≤v1 for i= 1, 2, . . . , m , in which ei is the i -th unit vector, to the program. The next linear program that player 1 solves is thus minimize (1 0)>·(v2,x2)(17) subject to   1m×1−B> 011×n 0A> ·v2 x2≥0 =1 ≤v1·1m×1 (18) where, likewise, we have the saddle point v2 on the second coordinate, by playing strategy x2 , which remains optimal for the first game due to A>·x2 giving at most the value v1 whatever player 2 does on its m column strategies. Observe that the goals (16) and (17) are only different in terms of the index, which we can safely drop in an implementation; the only change relates to the constraint matrix that grows by yet another block ( 0 A> i) upon moving to the i -th coordinate for i= 2, 3, . . . , d . The additional lines in (18) thus implement the condition to optimize over x∈ 4(BRu1:i−1)in (11). Each of these linear programs remains feasible, since the first solution x1 is trivially feasible for (18) , and so on, so that we will finally obtain an optimum xd=x∗ as one part of the fixed point that Proposition 2guarantees. The complementary other part y∗ is obtained by solving the sequence of dual programs to (16) and (17) . Along these lines, we obtain a sequence of saddle point values v1 , v2 , . . . , vd that are best accomplished under the assumption that player 2 will adapt to a change in behavior observed for player 1. This adaptation is reflected by letting player 1 anticipate it and hence add the constraint to retain its so-far-accomplished saddle point payoffs, appearing as the added constraint in (17) . Without this constraint, player 1 would simply run another equilibrium computation on the second coordinate, but just as Section 3has shown, player 2 can then adapt to it, and reduce the payoffs for player 1 in the first game on A1 . This possibility is removed by the added constraint in (17). This process has been practically implemented in a package for R [ 44 ]. Concerning the complexity, the repeated linear programming has, using interior point methods, an overall polynomial complexity in the size of the game and number of dimensions to optimize. On the contrary, fictitious play has worse complexity than in the classical case (where it is worst-case exponential already), but may take even longer if the process is played over vectors or distributions. For this reason, the practical recommendation and implementation is using linear programming in the finite case. Games 2022,13, 80 20 of 26 Remark 3. Reference [ 37 ] has defined a lexicographic Nash equilibrium as a situation in which an unilateral deviation of player 1 will enable player 2 to adapt to this, and reduce player 1’s revenue accordingly. Prior work has not explained why this can be called an “equilibrium”, since the typical definition of a Nash equilibrium assumes unilateral deviations to be not responded to, i.e., the optimum holds given that all other players keep their strategies (even if mixed) unaltered. In Proposition 2, we have provided an alternative fixed-point characterization of a lexicographic Nash equilibrium, which we believe better justifies the naming as “equilibrium” in the sense of a best reply for all players, than [37] does. 5. Summary Defining games with payoffs that are entire distributions rather than just real numbers has a variety of pitfalls to avoid, but is, to the best of our current knowledge, possible according to the following steps: • Define the payoff distributions over a joint and compact support Ω= [a , b] that is a closed interval over the reals, or a common discrete interval [a , a+ 1, . . . , b− 1, b]⊂N , with a≥1 in both cases. • If the payoff distributions are continuous, they should either have piecewise polynomial density functions, or be approximated by such functions, which is possible up to arbitrary precision by Lemma 1. • The games themselves may not admit Nash equilibria as mixed strategies with realvalued probabilities, but do have lexicographic Nash equilibria that are efficiently computable by a series of linear optimizations (see Section 4.3) using existing software [ 44 ], at least for finite zero-sum games. Care has to be taken to not misinterpret the resulting strategy profiles as conventional Nash equilibria. In particular, the solution does not need to be lexicographically optimal (as shown in Section 3), but is a best reply to itself under an accordingly modified reply-correspondence (11). 6. Outlook Some authors [ 16 ] have argued to leave the route of game theory over hyperreal spaces aside, as it appears to be a dead end due to practical difficulties. We instead propose taking these difficulties as challenges for further research, substantiated by the diverse phenomena encountered along these lines, as there are several interesting things to discover. 6.1. Phenomena That May Merit Future Studies • Convergence failure of FP in the sense that the iteration may converge to an accumulation point that is not an equilibrium, despite the fact that the iteration, when carried out towards hyperreal infinity, would converge to an equilibrium; only it is not reachable from within iterating in N , resp. R . This phenomenon is due to the fact that N is a strict subset of its hyperreal counterpart ∗N , in which FP does converge (by the transfer principle). • Games that lack a classical Nash equilibrium, although they do have continuous payoffs, with the only difference that they are vector valued. In the absence of conventional Nash equilibria, lexicographic optimization and equilibria, as proposed in Definition 2, may be a solution concept to consider. Intuitively, we hereby treat multiple goals as equilibrium selection criteria, signifying one goal as the most important, and using the subordinate goals to merely refine the equilibrium strategies if they are ambiguous. Overall, the study of games with distributions as rewards has led to new thoughts on equilibrium selection, and solution concepts for multi-criteria games up to algorithms to compute them. In addition to the above, we get extended possibilities due to the modeling of payoffs as whole distributions. Concepts such as disappointment rates may be useful, but remain to be studied, as explanatory mechanisms of bounded rationality. Speculating on why people may, in reality, choose to deviate from the utility maximization paradigm [ 15 ], the anticipation of disappointment may be one possible cause. Moreover, also formally, Games 2022,13, 80 21 of 26 disappointment rates are an example of functions that are discontinuous under the classical modeling paradigm, but can be made continuous if the game is defined with distributions (see Section 1.4). The concept of a lexicographic Nash equilibrium is in itself a simple method of equilibrium refinement by tie-breaking using more properties of the payoff distributions that would not be encoded if the game is defined with crisp values. For example, we cannot only optimize the expected revenue, but also the fluctuation (variance) around it to select the “most stable” equilibrium if there are several. 6.2. Conclusions Generalizations of the theory laid out in this work are straightforward and manifold, yet can be expected to be non-trivial. For example, Proposition 2is given for two-player zero-sum games, but open to extend to n -player games and the non-zero-sum case (Note 5 shows the argument that could fail in the more general case). Likewise, the algorithms to compute Nash equilibria (and hence also lexicographic Nash equilibria) are open for extensions to the generalized setting. Given the intricacy of phenomena that occur in hyperreal games, we argue, on the contrary to previous authors (see citations above), that the so-far discovered oddities justify indeed a deeper study of games inside the hyperreal space, even if just for the sake of scientific curiosity. Author Contributions: Validation, S.S.; Formal analysis, S.R. and S.K.; Investigation, S.K. and S.S.; Writing—original draft, S.R. All authors have read and agreed to the published version of the manuscript. Funding: Open Access Funding by the University of Linz. Data Availability Statement: Not applicable. Acknowledgments: We are grateful for many helpful discussions and contributions by Jeremias Epperlein, Vincent Bürgin, Fabian Wirth, Tatjana Cobit, Peter Occil and Jasmin Wachter. A special thanks goes to Paul Schweinzer, for having drawn our attention to subgame perfectness as a concept related to the lexicographic equilibrium notions in this work, and we are also indebted to Ali Alshawish, whose insightful testing and applications of the theory led to invaluable insights and new ideas. The input of the aforementioned people, discussions and deep thinking about the theory of games with distributions as payoffs has been invaluable to improve the theory over earlier publications. Finally, we are indebted to the anonymous reviewers, who gave very good comments and suggestions to improve the manuscript. Conflicts of Interest: The authors declare no conflict of interest. Abbreviations The following abbreviations are used in this manuscript: FP! Fictitious Play. Appendix A. Proof of Proposition 1 The proof given here has been taken from [ 45 ]. Intuition suggests that d is a composition of continuos functions, and as such should be itself continuous. We make this rigorous: take distinct s,s0∈Rn+mand consider d(s0)−d(s), which equals Fs(u(s)) −Fs0(u(s)) = Fs(u(s)) −Fs0(u(s0)) + Fs0(u(s)) −Fs0(u(s)) = [Fs(u(s)) −Fs0(u(s))] | {z } term (I) −[Fs0(u(s0)) −Fs0(u(s))] | {z } term (II) Games 2022,13, 80 22 of 26 We look at the left and right terms in square brackets separately: Term (I): put t=u(s) = EFs(L) and assume ks0−sk∞<δ1 . We have ∑i,jxiyjFij(t)− ∑i,jx0 iy0 iFij(t) = ∑ij(xiyi−x0 iy0 i)Fij(t) and furthermore xiyj−x0 iy0 i=|xiyj−x0 iy0 j− x0 iyj+x0 iyj|≤|yj(xi−x0 i)|+|x0 i(yj−y0 j)| ≤ δ1|yj|+δ1|x0 i| ≤ 2 δ1 , because yj , x0 i≤ 1 for every categorical distribution (to which yj and x0 i are the respective probability masses). Applying this bound on the sum gives ∑ ij xiyjFij(t)−∑ ij x0 iy0 iFij(t) =∑ ij (xiyj−x0 iy0 j)Fij(t) ≤∑ ij |xiyj−x0 iy0 i|Fij(t) ≤2δ1·∑ ij Fij(t)≤2δ1·n·m=:ε, since Fij(t)≤ 1 as Fij is a (cumulative) distribution function. Since n , m are constants, we can require ks0−sk∞<δ1:=ε 2mn to imply |Fs(u(s)) −Fs0(u(s))|<ε for every ε>0. Term (II): the mapping s0= (x0 , y0)7→ F(t) = ∑ij x0 iy0 jFij(t) delivers a function, which is uniformly continuous as a function of ton its entire support, since: • All Fij were assumed to be continuous and compactly supported, • So they are all uniformly continuous, and ε> 0 admits individual values δij > 0, so that |t−t0|<δij implies |F(t)−F(t0)|<εfor all t,t0within the support. • Since the game is finite, we can put δ2:=minδij to conclude that kt−t0k∞< δ2 further implies |Fs0(t)−Fs0(t0)|<ε , i.e., the function F is, independently of s0 continuos with the same ε , δ2 , since: Fs(t) = ∑ij xiyjFij(t) and so |Fs(t)−Fs0(t)|≤ ∑ij x0 iy0 jFij(t)−Fij(t0)<∑ij x0 iy0 i·ε=ε·∑ij x0 iy0 j=ε, as long as |t−t0|<δ2. Hence, the family {Fs(t):s∈∆(AS1)×∆(AS2)} is in fact equicontinous in t (over its support). Now, we can put things together: take any ε> 0 and let ks−s0k∞<min{δ1,δ2} . Then, |Fs(u(s)) −Fs0(u(s0))|< 2 ε·n·m+ε , which can be made as small as desired. Hence, the function dis continuous. Appendix B. Proof of Lemma 1 The proof as appears below is taken from [37]. Pick any δ> 0. It is straightforward to use Weierstraß’ approximation theorem to get a polynomial p that uniformly δ -approximates f on the given interval. The issue is that (i) p may take on negative values, and (ii), p is not necessarily normalized to be a probability distribution. To fix both, we define the sought function g(x):=α·p+(x) with p+(x) = max( 0, f(x)) for x∈[a , b] , with a normalization constant α> 0 chosen to make Rb ag(t)dt = 1. Let us postpone the role of α until a little later, and look at how well the function p+approximates f. By definition, p+ is different from p only at positions x∈[a , b] when p(x)< 0, and otherwise identical. Since f is bounded from below by zero, p+ can only get “closer” to the graph of f , and hence also satisfies kf−p+k∞<δ . We will make use of this later. Now, let us normalize p+ into a probability density, i.e., choose α> 0 such that Rb aα·p+(t)dt = 1, Games 2022,13, 80 23 of 26 and look at the maximal error kf−α·p+k∞ on the interval [a , b] . We apply the triangle inequality twice after expanding the inner difference,  f−α·p+ ∞= f−α·p+−p+p+α·p−α·p ∞ = (f−p) + (αp−αp+) + (p−αp) ∞ ≤kf−pk∞+|α|· p−p+ ∞+kp−αpk∞. Therein, the first term is <δby construction (Weierstraß’ theorem). The second term is the maximum difference between p and p+ , which is also bounded by δ since p cannot fall below −δas fis bounded to be ≥0, and pis “δ-bound” to f. The third term p−αp attains a maximum where its first order derivative p0−α·p0= ( 1 −α)p0 vanishes. Now, if α= 1, then p+ is normalized already and we are finished. Otherwise, α6= 1, and we can just look for a maximum of p . Again, since p is bound to a deviation from f that is smaller than δ , its maximum must be in an δ -neighborhood of the maximum of f , and we can approximately locate the extreme value pmax ∈[kfk∞− δ , kfk∞+δ] . Wherever this maximum is attained, the same position x=xmax will also maximize the deviation α·p(x) . Thus, the maximum possible deviation between pmax and α·pmax is ≤|α(kfk∞+δ)−(kfk∞−δ)|≤|α·kfk∞−kfk∞|+|αδ −δ|=|α−1|· (kfk∞+δ). Combining all three bounds, we find  f−α·p+ ∞≤δ+|α|·δ+|α−1|·(kfk∞+δ)(A1) To exhibit this bound to ultimately become arbitrarily small, let us finally estimate the value α . To this end, we return to our previous observation that f−δ≤p+≤f+δ due to the uniform approximation property. Integrating the inequalities from ato b, we find 1−δ(b−a)≤Zb ap+(t)dt =1 α≤1+δ(b−a) Taking the reciprocal gives us 1 1+δ(b−a)≤α≤1 1−δ(b−a) Letting δ→ 0, will make α→ 1 (sandwich theorem), and thereby also let the bound (A1) become <εultimately (for any ε>0 that we can choose in advance), thus proving the claim. Appendix C. Fictitious Play Algorithm The following algorithm assumes a minimizing first player, and lets all minima, maxima and ≤ -relation between probability distributions be decided according to the hyperreal representation of two random variables (i.e., by their moment sequences), according to criteria C1 and C2 from Section 2.3. It is an adapted version from [23]. Games 2022,13, 80 24 of 26 Algorithm A1 Fictitious Play Require: an (n×m)-matrix Aof payoff distributions A= (Fij) Ensure: an approximation (x , y) of an equilibrium pair (p∗ , q∗) and two distributions vlow , vup so that vlow ≤hr F(p∗,q∗)≤hr vup. Here, F(p∗,q∗)(r) = Pr(R≤r) = ∑i,jFij(r)·p∗ iq∗ j. 1: initialize x←0∈Rn, and y←0∈Rm 2: vlow ←the minimum over all column-maxima 3: r←the row index giving vlow 4: vup ←the maximum over all row-minima 5: c←the column index giving vup 6: u←(F1,c, . . . , Fn,c) 7: yc←yc+1.y= (y1, . . . , ym) 8: v←0.initialize vwith mfunctions that are zero everywhere 9: for k=1, 2, . . . do 10: u∗←the minimum of u 11: r←the index of u∗in u 12: vup ←the maximum of u∗/k,vup.pointwise scaling of the distribution u∗ 13: v←v+ (Fr,1, . . . , Fr,m).pointwise addition of functions 14: xr←xr+1.x= (x1, . . . , xn) 15: v∗←the maximum of v 16: c←the index of v∗in v 17: vlow ←the minimum of {v∗/k,vlow}.pointwise scaling of the distribution v∗ 18: u←u+ (F1,c, . . . , Fn,c).pointwise addition of functions 19: yc←yc+1.y= (y1, . . . , ym) 20: exit the loop upon convergence .concrete condition given below 21: end for 22: Normalize x,yto unit total sum .turn x,yinto probability distributions. 23: return p∗←x,q∗←y, and F(p∗,q∗)←∑i,jFij(r)·xi·yj.≈(p∗)>Aq∗ Notes 1i.e., a set such that ∅/∈ U,N∈ U, closed under ⊇-relation, and closed under finite intersections. 2 The mixed case is discussed in [ 23 ], but was found to be practically not meaningful, since it would be difficult to interpret the semantics of a comparison of categories to real numbers that are not ranks. 3 Inductively, we can define a≤lex b:⇐⇒ a≤b for a , b∈R , and for (an , . . . , a1) , (bn , . . . , b1) we put a≤lex b:⇐⇒ [(an≤ bn)∧(an−1, . . . , a1)≤lex (bn−1, . . . , b1)] 4 Instantly visible by considering any null-sequence 0 <xn→ 0 as n→∞ , satisfying (xn , 0 )>lex ( 0, 1 ) , while limn→∞(xn , 0 ) = (0, 0)≤lex (0, 0). 5 For zero-sum games, two arbitrary equilibria (x∗ , y∗) and (˜ x∗ , ˜y∗) give rise to two more equilibria (x∗ , ˜y∗) and (˜ x∗ , y∗) , which may not be the case for non-zero-sum games. A proof of convexity of the set for zero-sum games is found in [39]. References 1. Herath, H.S.B.; Herath, T.C. Copula-Based Actuarial Model for Pricing Cyber-Insurance Policies. Insur. Mark. Co. 2011,2, 14. 2. Hogg, R.V.; Klugman, S.A. Loss Distributions; Wiley Series in Probability and Mathematical Statistics Applied Probability and Statistics; Wiley: New York, NY, USA, 1984. [CrossRef] 3. AlShawish, A. Risk-Based Security Management in Critical Infrastructure Organizations. Ph.D. Thesis, University of Passau, Passau, Germany, 2021. 4. Tambe, M. Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned; Cambridge University Press: Cambridge, NY, USA, 2012. 5. Pawlick, J.; Zhu, Q. Game Theory for Cyber Deception: From Theory to Applications; Static & Dynamic Game Theory: Foundations & Applications; Springer International Publishing: Cham, Switzerland, 2021. [CrossRef] 6. Nguyen, T.; Xu, H. When Can the Defender Effectively Deceive Attackers in Security Games? In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, Online, 22 February–1 March 2022; pp. 9405–9412. 7. Zhang, M.; Li, N.; Adepu, S.; Kang, E.; Jin, Z. A Game-Theoretical Self-Adaptation Framework for Securing Software-Intensive Systems. arXiv 2021, arXiv:2112.07588. [CrossRef] 8. Nguyen, T.H.; Sinha, A.; He, H. Partial Adversarial Behavior Deception in Security Games. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), Yokohama, Japan, 11–17 July 2020; pp. 283–289. 9. Münch, I. Wege Zur Risikobewertung. In Proceedings of the DACH Security 2012, Graz, Austria, 25 September 2012; Schartner, P., Taeger, J., Eds.; Syssec: Bochum, Germany, 2012; pp. 326–337.