Refinement of acyclic-and-asymmetric payoff aggregates of pure strategy efficient Nash equilibria in finite noncooperative games by maximultimin and superoptimality Decision Making: Applications in Management and Engineering Vol. 4, Issue 2, 2021, pp. 178-199. ISSN: 2560-6018 eISSN: 2620-0104 DOI: https://doi.org/10.31181/dmame210402178r * Corresponding author. E-mail address: v.romanuke@amw.gdynia.pl (V. Romanuke) REFINEMENT OF ACYCLIC-AND-ASYMMETRIC PAYOFF AGGREGATES OF PURE STRATEGY EFFICIENT NASH EQUILIBRIA IN FINITE NONCOOPERATIVE GAMES BY MAXIMULTIMIN AND SUPEROPTIMALITY Vadim V. Romanuke 1* 1 Polish Naval Academy, 69 Śmidowicza Street, Gdynia, Poland Received: 25 May 2021; Accepted: 5 July 2021; Available online: 12 July 2021. Original scientific paper Abstract: A theory of refining pure strategy efficient Nash equilibria in finite noncooperative games under uncertainty is outlined. The theory is based on guaranteeing the corresponding payoffs for the players by using maximultimin, which is an expanded version of maximin. If a product of the players’ maximultimin subsets contains more than one efficient Nash equilibrium, a superoptimality rule is attached wherein minimization is substituted with summation. The superoptimality rule stands like a backup plan, and it is enabled if just a single refined efficient equilibrium (a metaequilibrium) cannot be produced by maximultimin. The number of the refinement possible outcomes is 10. There are 3 single-metaequilibrium cases, 3 partial reduction cases, and 4 fail cases. Despite successfulness of refinement drops as the game gets bigger, efficient equilibria in games with no more than four players are successfully refined at no less than a 54 % rate. Key words: Finite noncooperative games, efficient equilibria, refinement, maximultimin, superoptimality, metaequilibrium, uncertainty partial reduction. 1. Introduction Game theory allows making decisions that would be appropriate simultaneously for multiple sides (or players, persons, subjects, etc.). This is achieved by persuading players that holding at the equilibrium is the best rule. There are many types of equilibria but mostly they are modifications of Nash equilibrium. Either in pure or mixed strategies, Nash equilibrium is a stable state, at which the player cannot increase one’s payoff by acting alone. In a finite noncooperative game (FNCG), however, a few Nash equilibria in pure strategies can exist (Harsanyi & Selten, 1988; Osborne, 2003; Vorob’yov, 1984). Such equilibria may be nonequivalent: despite the mailto:v.romanuke@amw.gdynia.pl Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 179 equilibrium stability itself, the players’ payoffs at some equilibrium can be greater that those at other equilibria (Leinfellner & Köhler, 1998; Osborne, 2003; Vorob’yov, 1984). The equilibria which are strictly and non-strictly dominated are out of interest for players. Then, only efficient equilibria remain. A question is how to persuade players to hold at a certain efficient equilibrium, when there are multiple equilibria (two or more)? For FNCGs with two or three players (bimatrix and trimatrix games) this question is yet not trivial (Vorob’yov, 1985; Vorob’yov, 1958). FNCGs with more than three players are rather complicated, so searching for the most efficient equilibrium, if any, in pure strategies requires a non-trivial theoretic basis. In FNCGs having multiple equilibria, the subsequent decision-making problem lies in refining those equilibria. The refinement is required, in the first turn, for real- world practice applications, wherein messing around with multiple equilibria makes no sense. Those applications emerge from economics, ecology, politics, jurisprudence, computer networking, and other related fields, where multiple subjects come to interaction (Harsanyi & Selten, 1988; Leyton-Brown & Shoham, 2008; Myerson, 1997; Romanuke, 2010b; Vorob’yov, 1984). 2. Background and motivation In game theory, the refinement is understood as the selection of a subset of such equilibria, which are believed to be more plausible than other equilibria (Belhaiza et al., 2012; Myerson, 1978; Vorob’yov, 1985). Sometimes, it is called the identification of actualized equilibria (Dopfer & Potts, 2007; Liu & Forrest, 2010). Thus, the refinement does not necessarily imply selecting the best efficient Nash equilibria. Nor does it imply finding a single efficient equilibrium. In a wider sense, the refinement implies narrowing down the game model decisions. Nash equilibria, for instance, are a particular example of a set of such decisions) (Harsanyi & Selten, 1988; Vorob’yov, 1984; Vorob’yov, 1985). The essential obstacle is that the plausibility does not straightforwardly imply profitability. For repeatable FNCGs, it means that the refined equilibrium can be unstable: a player cannot be “captured” on a non-profitable payoff, although such payoff issues from a plausible equilibrium (Belhaiza et al., 2012; Fudenberg & Tirole, 1991; Myerson, 1978). So, in the course of game repetitions, the player may spring off its non-profitable strategy (Leinfellner & Köhler, 1998; Liu & Forrest, 2010; Osborne, 2003; Romanuke, 2010b). Thus, the plausibility determining the refinement without primordial profitability is not stable itself. In particular,  -equilibria are that kind of instability, wherein players may constantly keep searching for profits rather than stop at a moment (Belhaiza et al., 2012; Fudenberg & Tirole, 1991; Vorob’yov, 1984; Vorob’yov, 1985). In non-repeatable FNCGs, profitability mainly defines the plausibility. It simplifies persuasion of selecting definite equilibrium strategies. On the other hand, a great deal of the existing refinements, e. g. Mertens-stable equilibrium (Kohlberg & Mertens, 1986), trembling hand perfect equilibrium (Selten, 1975), proper equilibrium (Myerson, 1978; Van Damme, 1984), sequential equilibrium (Fudenberg & Tirole, 1991; Gerardi & Myerson, 2007), quasi-perfect equilibrium (Bajoori et al., 2013; Mertens, 1995; Van Damme, 1984), become inapplicable due to mixed strategies lose their reason. Strong Nash equilibrium (Suh, 2001; Tian, 2000) remaining as the most remarkable refinement is efficient itself (Romanuke, 2016b; Romanuke, 2016a). Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 180 In practice, the existing approaches to refining rarely provide just a single refined equilibrium. Commonly, there are still multiple (or even a continuum of) equilibria after the refinement (Gerardi & Myerson, 2007; Harsanyi & Selten, 1988; Myerson, 1978; Romanuke, 2018a). Moreover, sometimes equilibria can be just nonrefinable. Such nonrefinability is easily shown and seen by examples of the bimatrix (even 2 2 ) game whose efficient Nash equilibria produce either identical or symmetric payoffs (Myerson, 1997; Osborne, 2003; Romanuke, 2010b; Vorob’yov, 1985; Vorob’yov, 1984). Bigger FNCGs with the nonrefinability are easily built. At that, symmetric equilibria are even worse than identical. In other cases, efficient equilibria are nonrefinable as there is no additional information that could have helped to understand which equilibrium is better and which is worse (Romanuke, 2018a; Suh, 2001; Tian, 2000). This is equivalent to uncertainty of equilibria, where players may not comprehend a distribution of the plausibility over definite equilibria, except for their profitability at one-step action. An effort made in (Romanuke, 2018b) for refining pure strategy efficient Nash equilibria in trimatrix games had been developed on a base of expanding the refinement approach for bimatrix games. For a player, that novel approach exploits the maximin, expanded to the maximinimin principle, and a superoptimality rule using summing over pure strategy subsets of the other players. The maximin rule is intended for guaranteeing payoffs. The superoptimality rule (Romanuke, 2018a) is enabled if just a single refined efficient Nash equilibrium cannot be produced by maximin. So, the present goal is to finalize the theory of refining pure strategy efficient Nash equilibria in FNCGs under uncertainty. 3. Denotations of FNCG and its efficient Nash equilibria We consider a non-repeatable FNCG (1) of players, in which n X is a set of pure strategies of the n -th player, nK is its payoff -matrix by and for the set of indices   1 N i i J j   ,  1,i ij M 1,i N  . (2) The non-repeatability means that FNCG (1) models a process, in which the player upon one’s decision is made is able to implement it only once (or a few times at most). Suppose that, in FNCG (1),   1 Q q q E e   is a set of efficient Nash equilibria in pure strategies, where (a refinement is needless if 1Q  , i. e. there is a single equilibrium): by . (3) Pure strategy efficient Nash equilibrium (3) produces a payoff aggregate (4) Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 181 whose N elements are the respective elements of N payoff matrices . (5) Nash equilibria, which are strictly and non-strictly dominated by other Nash equilibria, bear no utility (in fact, they are inefficient). This is why they are not further considered (Harsanyi & Selten, 1988; Liu & Forrest, 2010; Osborne, 2003; Romanuke, 2018b; Romanuke, 2018a; Vorob’yov, 1985; Vorob’yov, 1984). All pure strategy efficient Nash equilibria in FNCG (1) with payoff matrices (5) constitute a subset of all pure strategy situations which contain equilibrium strategies of every player: (6) by 1,n N  , (7) where the indices’ subsets (8) are such that for every element of set  1,q Q  such that , 1,n N . It should be noted that every element of set is not necessarily an equilibrium point. This means that some aggregates may not be the equilibria – see an example sketch in Figure 1 and also refer to Figure 1 in (Romanuke, 2018b). Theoretically, inefficient equilibria make no sense. A situation producing payoffs 0  by some  1,m N (9) cannot be an efficient Nash equilibrium, whichever situation producing payoffs (4) is. However, if the weak Pareto efficiency is acceptable to supplement the set of the efficient Nash equilibria, then both situations producing payoffs (4) and (9) are efficient, if the situation (4) is an efficient Nash equilibrium. In general, the weak efficiency, if accepted, implies that a situation producing payoffs 0 n    for all    1, \n N m by some  1,m N (10) is efficient as well (Kumano, 2017; Marden, 2017). Nevertheless, if Nash equilibria are weakly efficient in bimatrix games, then they are fairly senseless due to the player whose payoff is decreased by  will avoid one’s weakly efficient strategy. In Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 182 Figure 1. The efficient Nash equilibria set (highlighted via dashed rectangles) and its relation (shown by arrows) to subsets (7) in a trimatrix 7 4 5  game over a player’s payoff three-dimensional matrix of size 7 4 5  (the view is the same for every player); see the similar visualizations in (Romanuke, 2018b; Romanuke, 2018a) trimatrix games, where the situation producing payoffs (11) is an efficient equilibrium, a weakly efficient situation producing payoffs , or , or (12) by pretty great 1  and 2  , or 1  and 3  , or 2  and 3  , respectively, is fairly senseless as well. However, if   3 1r r  are sufficiently (or even negligibly) small, weakly efficient Nash equilibria producing payoffs (11) and (12) may become (more) significant. For FNCGs with four players and more, weak efficiency of Nash equilibria gets more important, especially if payoffs (9) differ from efficient payoffs (4) by a negligible  . 4. Properties of payoff matrices and distinguishability of efficient Nash equilibria First, none of N payoff matrices (5) of FNCG (1) can have elements, whose values are the same. In particular, matrices (5) of FNCG (1) cannot be null matrices. In addition, these matrices cannot contain strictly dominated  1N  -dimensional slices. Otherwise, if there are strictly dominated  1N  -dimensional slices, the slices are deleted. For example, a 3 2 2  game with matrices (a similar example can be found in (Romanuke, 2018b) but matrices’ values here have been slightly changed) Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 183 1 7 4 6 2 5 5 3 6 6 3 5 1                           K , 2 7 6 4 3 7 6 5 7 6 7 9 6                           K , 3 7 6 6 6 4 8 4 8 8 9 7 8                           K (13) is reduced to the 2 2 2  game with payoff 2 2 2  matrices 1 7 4 6 2 5 5 3 6                 K , 2 7 6 4 3 7 6 5 7                 K , 3 7 6 6 6 4 8 4 8                 K . (14) Indeed, the third slice of matrix 1 K in (13) is strictly dominated by its first slice (the first row values are greater than the third row values), and so the first player will never use one’s pure strategy which is strictly dominated. There are two efficient Nash equilibria in the trimatrix game with payoff matrices (14):  1 1 1 1, ,e x y z and  2 2 2 2, ,e x y z . These equilibria produce payoffs  7, 7, 7 and  6, 7, 8 , respectively. Note that the collective payoffs are the same. Meanwhile, payoffs  6, 7, 8 are produced by the situation involving the non-strictly dominated second slice of matrix 3 K (where the left flat submatrix non-strictly dominates the right flat submatrix). Another peculiarity is that the second player does not care about difference of one’s payoffs at these equilibria, whereas equilibrium 2 e imparts a little advantage to the third player (as opposed to the first player). Thus, equilibrium 1 e is more attractive for the first player, and equilibrium 2 e is more attractive for the third player. The strength of the attractiveness is the same. Distinguishability of efficient Nash equilibria is a principally important property before considering possible refinement. Identical payoff aggregates produced in symmetric situations are non-distinguishable. An example is a trimatrix 2 2 2  game with payoffs matrices (Romanuke, 2018b) 0 0 1 0 0                       K and 0 0 2 0 0                       K and 0 0 0 3 0 0 0                       K by 0    , 0   , 0    . (15) Unlike the slices (left and right flat submatrices) of matrices 1 K and 2 K , the slices (left and right ones) of matrix 3 K are different. This game has two efficient Nash equilibria, each of which produces the same payoff triplet  , ,   . Thus, these equilibria are absolutely non-distinguishable. Therefore, cyclicity and symmetry of payoff aggregates (with respect to situations in which they are produced) is opposed to distinguishability of efficient Nash equilibria. So, only refinement based on acyclic- and-asymmetric payoff aggregates is possible. 5. Maximultimin and superoptimality for refining efficient Nash equilibria in FNCGs Considering the inclusion of the set of the efficient Nash equilibria in (6), FNCG can be reduced to an FNCG defined on product . In the reduced FNCG, payoff matrices are Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 184 at (16) by 1,r N  and re-indexing with a set of corresponding indices. If matrices (16), being the corresponding submatrices of matrices (5), still have N dimensions, then they constitute the reduced game by (7) and (8). The uncertainty amongst the equilibria to be refined (or selected) is still the same as it is for the initial FNCG (1). To reduce the uncertainty, the maximin principle can be applied to guarantee the corresponding “no-less-than” payoffs for the players. For games, this principle is the maximultimin being a generalization of maximin and maximinimin by Romanuke (2018a, 2018b): by , 1,r N (17) and re-indexing with a set of corresponding indices. Set (17) guarantees that the r -th player gets a payoff not less than , 1,r N . (18) However, not all situations in the set (19) are efficient Nash equilibria. Moreover, set (19) may not contain any equilibria. If set (20) is nonempty then it contains the refined efficient Nash equilibria. In particular, if set (20) is a singleton (in other words, it contains just a single element), then the refinement is finished, and the single element is the single efficient Nash equilibrium. If R   or 1R  then the superoptimality rule originally introduced to distinguish optimal player strategies (game situations) in matrix games (e. g., see Romanuke, 2010a) can be applied just as well as it is applied for bimatrix and trimatrix games in (Romanuke, 2018a) and (Romanuke, 2018b), respectively. If set R   then using strategies from subsets (17) involves players into an unstable (wandering) process: the players will search for new pure strategies beyond these subsets for every game round (as there is no a single equilibrium). To guarantee the best payoffs for players under uncertainty of the efficient equilibria in this case, one of the best actions is to use strategies from subsets Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 185 by . (21) Subsets (21) are those guarantors. This uncertainty reduction concerns as FNCG (1), as well as the reduced FNCG with payoff matrices (16), whether matrices (16) have N dimensions or fewer. In the case of 1R  there are at least two equilibria in product (19) of maximultimin subsets (17). Thus, we still have an uncertainty of which equilibrium to select. Let (22) by and 1,r N  and the respective indices’ subsets by which . (23) If then, according to superoptimality, by (24) and re-indexing with a set of corresponding indices, 1,r N . Otherwise, if , then and . Note that finding sets (24) does not guarantee that * 1 N r r X R            , (25) where a case * 1 1 N r r X R           (26) is as ideal as the case 1R  . Statement (25) is only assuredly true for a case, when for all    01, \r N r , and or . (27) Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 186 Hence, the refinement is finished by processing the reduced game with payoff matrices (16), wherein primarily maximultimin subsets (17) are found along with maximultimin payoffs (18). The process of refining is continued to payoff aggregate maximizations if 1R  . The refinement is counted perfectly finished when 1R  or (26) is true. If set (19) is a singleton and it contains a single efficient equilibrium, then using strategies from other situations is unreasonable. In this case, it can be said that product (19) of the maximultimin subsets has perfectly responded, and the players will stick to the single efficient equilibrium. However, if there are at least two equilibria with different payoffs, the single efficient equilibrium is simultaneously unprofitable (or disadvantageous) for 0 N players, where  0 1, 1N N  . The non- profitability (disadvantageousness) follows from the Pareto efficiency definition. Suppose that a player, who loses some payoff at the single refined efficient equilibrium, tries to increase one’s payoff. The payoff increment is possible by when other players do not change their strategies (which are still profitable for them) upon the equilibrium is changed. Consequently, the payoff increment is unlikely even for a few rounds of the game. This attitude can be re-formulated in the terms of the noncooperative game equilibrium: while at the Nash equilibrium a player cannot improve one’s payoff by acting oneself, at the single refined efficient equilibrium it is unlikely for a player to increase one’s payoff at least for a few rounds of the game (Barelli & Duggan, 2015; Kumano, 2017; Romanuke, 2010b). Thus the refined efficient equilibrium called the metaequilibrium becomes an attractive point for all the players (Romanuke, 2018b), although with probably different strengths of the attraction. Obviously, there can be a few refined efficient equilibria. Despite such metaequilibria are considered nonrefinable, the refinement may have a positive impact by some conditions that will be explained in the section right below. 6. A generalized algorithm of refinement in FNCGs The stated approach of maximultimin and superoptimality for refining efficient Nash equilibria in FNCGs with subsets (17), (21), or (24) does not guarantee the best outcome, i. e. that there will be a single metaequilibrium. In general, this approach gives us one of the seven possible final outcomes: 1. The refinement is quite impossible (it totally fails) when R   and . (28) Both the maximultimin principle and superoptimality rule miss all the equilibria here. This is the case when both the maximultimin and superoptimality do not work at all. This is the worst case. 2. A few metaequilibria are returned when R   but . (29) This outcome has two mutually exclusive interpretations. If (30) Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 187 then the uncertainty amongst the equilibria is nonetheless partially reduced. Otherwise, if (31) then the superoptimality rule hits the whole set of the equilibria. Clearly, this does not reduce the uncertainty amongst the equilibria as those metaequilibria remain the same as all those efficient equilibria. So, this is a fail of the refinement, where the superoptimality rule works in vain. 3. A few metaequilibria are returned when 1R  and equality (26) is false by * 1 N r r X R            . (32) Such an outcome has two mutually exclusive interpretations. If R E , that is 1 R E  (33) here, then the uncertainty of equilibria is nonetheless partially reduced. Otherwise, if R E by (32), then the superoptimality rule does not hit an equilibrium, whereas the maximultimin hits the whole set of the equilibria (factually, this is a fail of the refinement, where the maximultimin principle works in vain). There are R metaequilibria anyway, found by just subsets (17). 4. A few metaequilibria are returned when 1R  and equality (26) is false by * 1 1 N r r X R           . (34) Such an outcome has two mutually exclusive interpretations also. If * 1 1 N r r X R E            (35) then the uncertainty of equilibria is nonetheless partially reduced (either owing to maximultimin or superoptimality). Otherwise, if * 1 N r r X R E           (36) then both the maximultimin and superoptimality hit the whole set of the equilibria. As those metaequilibria remain the same as all those efficient equilibria, the uncertainty amongst the equilibria is not reduced at all. So, this is a fail of the refinement, where both the maximultimin and superoptimality work in vain. 5. A single metaequilibrium is returned when 1R  by finding just subsets (17). This is the perfect and fastest outcome of the refinement. 6. A single metaequilibrium is returned when 1R  and equality (26) is true. Here, subsets (17) and (24) are involved. This is the perfect refinement outcome as well. 7. A single metaequilibrium is returned when R   but Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 188 . (37) Although the maximultimin principle misses all the efficient equilibria, the superoptimality rule perfectly hits the single metaequilibrium. Therefore, a generalized algorithm of refinement in FNCGs under uncertainty consists of four key branches (Figure 2): 1R  Start Find maximultimin subsets (17) False True Intersection R by (20) contains a single equilibrium False True Find subsets (23) Find subsets (21) The refinement totally fails Return Return A single metaequilibrium is in set (20) False True Intersection (38) is nonempty Find subsets (24) False True Equality (37) holds Return A single metaequilibrium is in set (38) Return Uncertainty of equilibria has been partially reduced: the players’ metaequilibrium strategies are in intersection (38) False True Inequality (30) holds A fail of the refinement Return False True Equality (26) holds Return A single metaequilibrium is in set (39) Return Uncertainty of equilibria has been partially reduced: the players’ metaequilibrium strategies are in intersection (39) False True Inequality (35) holds A fail of the refinement Return False True Intersection (39) is nonempty Return Uncertainty of equilibria has been partially reduced: the players’ metaequilibrium strategies are in intersection R by (20) False True Inequality (33) holds A fail of the refinement Return Figure 2. An algorithmic generalized scheme for the Nash equilibria refinement in FNCGs (Romanuke, 2018b; Romanuke, 2018a) Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 189 1. Find maximultimin subsets (17) over payoff matrices (16). 2. Return a single metaequilibrium if 1R  , i. e. product (19) of maximultimin subsets (17) contains the single equilibrium. 3. If R   then find subsets (21) which maximize the respective players’ payoffs over subsets (7). Finally, return the resulting set , (38) whether containing metaequilibria or not. 4. Otherwise, if 1R  then maximize the respective players’ payoffs over subsets (23), and find those of subsets (24) (by 1,r N ) whose corresponding subsets (23) contain more than one strategy. Finally, determine a set * 1 N r r X R           . (39) If set (39) is not empty, return the resulting metaequilibrium or metaequilibria in set (39). More precisely, if to distinguish the partial equilibrium uncertainty reduction and the refinement fail in outcomes ## 2 – 4, the number of the refinement possible outcomes is 10. They all are highlighted with three different colors in Figure 2. Statistics of those outcomes bear some similarity at least for bimatrix and trimatrix games by increasing the number of players’ pure strategies (Romanuke, 2018b). Statistics for other FNCGs will be revealed in the section right below. 7. Statistics of refinement For getting more real examples, FNCGs are simulated by a pseudorandom matrix generator suggested in (Romanuke, 2018b). According to the generator, we take 1 N r r M   payoff matrix equal to    1 N r r b M     (40) by a function   1 N r r M   returning a pseudorandom 1 N r r M   matrix whose elements are drawn from the standard uniform distribution on the open interval  0; 1 and a function    returning the integer part of number  , where 0b  , 0  . Constants b and  are taken such that the payoffs would be moderately scattered (Leinfellner & Köhler, 1998; Leyton-Brown & Shoham, 2008; Myerson, 1997; Romanuke, 2018b; Vorob’yov, 1985; Vorob’yov, 1984). The purpose is to count statistics of refinement along with how many FNCGs need refinement and need not, having either a single equilibrium or no equilibria at all. For obtaining confident results, each type of FNCG will be generated for 100,000 times. Generator (40) will be used to produce the same number of pure strategies for players. Such simplification does not influence much on common inferences from Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 190 results of the simulation. Bimatrix games are generated by   1 110 , 40M M   for 1 2, 10M  . (41) So, statistics for bimatrix games will be re-examined for 2 2 up to 10 10 games. Trimatrix games are generated in the same way:   1 1 110 , , 40M M M   for 1 2, 10M  . (42) Processing FNCGs with a greater number of players consumes much more resources, so their topmost number of pure strategies is decreased:   1 1 1 110 , , , 40M M M M   , 1 2, 8M  , (43)   1 1 1 1 110 , , , , 40M M M M M   , 1 2, 7M  , (44)   1 1 1 1 1 110 , , , , , 40M M M M M M   , 1 2, 6M  , (45) for FNCGs with  4, 5, 6N  players, respectively. The statistics of refinement should reflect the number of FNCGs which include the following features: 1. Have no Nash equilibria. 2. Have a single equilibrium. 3. Need refinement. 4. A single metaequilibrium is returned by maximultimin in set (20). 5. A single metaequilibrium is returned by superoptimality in set (38). 6. The refinement totally fails. 7. The uncertainty of equilibria is partially reduced owing to superoptimality: a few metaequilibria are returned in set (38). 8. A fail of the refinement: maximultimin does not hit an equilibrium, although superoptimality hits all the equilibria at once. 9. A single metaequilibrium is returned by superoptimality in set (39). 10. The uncertainty of equilibria is partially reduced owing to maximultimin: a few metaequilibria are returned in set (20), whereas superoptimality does not hit an equilibrium. 11. A fail of the refinement: maximultimin hits all the equilibria at once, whereupon superoptimality does not hit an equilibrium. 12. The uncertainty of equilibria is partially reduced: a few metaequilibria are returned in set (39). 13. A fail of the refinement: maximultimin hits all the equilibria at once, as well does superoptimality. Additional commentaries to the list required for unambiguous interpretation are as follows. Those FNCGs counted by feature #3 have two or more efficient equilibria. Feature #5 implies that R   , i. e. maximultimin does not hit an equilibrium. Feature #6 implies that R   and equality (28) holds (maximultimin does not hit an equilibrium, nor does superoptimality as well), so both sets (20) and (38) are empty. Maximultimin does not work in features #7 and #8 (again, R   ). Statistics of refinement for bimatrix games generated by (41) are shown in Figure 3. Whichever the number of pure strategies is, features ## 7 – 12 are statistically negligible. Meanwhile, as this number increases, the number of FNCGs having a single equilibrium decreases (feature #2) along with the increasing number of FNCGs wherein the refinement is needed (feature #3). Fail cases, when both maximultimin and superoptimality do not hit an equilibrium (feature #6), Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 191 considerably increase. Eventually, they constitute a significant part for 10 10 games. The fail of the refinement caused by the opposite event (feature #13) grows but much slower. The superoptimality rule hits the single metaequilibrium quite rarely (feature #5). Nonetheless, maximultimin does that effectively growing up as 1 M increases. The ratio of the single-metaequilibrium cases (features ## 4, 5, 9) to the refinement fail cases (features ## 6, 8, 11, 13) varies from 1.2 to 2.04, where the worst refinable bimatrix games are 9 9 ones (54.6 % of successful refinement into single-metaequilibrium), and the best refinable bimatrix games are 3 3 ones (67.1 %). Considering positively also the partial reduction of the equilibria uncertainty (adding features ## 7, 10, 12), the ratio varies from 1.22 to 2.05: the worst and best refinable 9 9 and 3 3 bimatrix games respectively constitute 55 % and 67.2 % of the successful refinement. Figure 3. Statistics of refinement for bimatrix games generated by (41) Statistics of refinement for trimatrix games generated by (42) and shown in Figure 4 resemble that in Figure 3. However, a few differences are distinctly visible. The increasing number of FNCGs, wherein the refinement is needed (feature #3), is from 30.2 % to 192.6 % greater. Fail cases (feature #6) are stronger, whereas the fail of the refinement caused by the opposite event (feature #13) slowly descends. Maximultimin and superoptimality separately hit the single metaequilibrium (feature #4 and #5) by 61.7 % better. The ratio of the single-metaequilibrium cases (features ## 4, 5, 9) to the refinement fail cases (features ## 6, 8, 11, 13) varies from 1.06 to 2.09, where the worst refinable trimatrix games are 10 10 10  ones (51.5 % of successful refinement into single-metaequilibrium), and the best refinable trimatrix games are 2 2 2  ones (67.7 %). Adding the partial reduction of the equilibria uncertainty (features ## 7, 10, 12), the ratio varies from 1.08 to 2.13: the worst and best refinable 10 10 10  and 2 2 2  trimatrix games respectively constitute 52 % and 68.1 % of the successful refinement. On average, trimatrix games have better refinability (considering features ## 4, 5, 7, 9, 10, 12) by 63.3 %. 1 2 3 4 5 6 7 8 9 10 11 12 13 23 45 67 89 10 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 7 8 9 10 11 12 2 3 4 5 6 7 8 9 10 0 50 100 150 200 250 300 1 M Number of FNCGs Features 1 M Features Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 192 Statistics for FNCGs with four players (Figure 5) much differ from those with five (Figure 6) and six players (Figure 7). FNCGs with 4N  are only 2.87 % refinable better than trimatrix games. Then, nevertheless, refinability of FNCGs worsens from 4N  to 5N  by 29.1 %, and from 5N  to 6N  by 63.5 %. Figure 4. Statistics of refinement for trimatrix games generated by (42) Figure 5. Statistics of refinement for FNCGs with 1 1 1 1 M M M M   payoff matrices generated by (43) 1 2 3 4 5 6 7 8 9 10 11 12 13 23 45 67 8 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 1 M Number of FNCGs Features 1 2 3 4 5 6 7 8 9 10 11 12 13 23 45 67 89 10 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 1 M Number of FNCGs Features 1 M Features 7 8 9 10 11 12 2 3 4 5 6 7 8 9 10 0 50 100 150 200 250 300 350 400 450 500 550 Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 193 Figure 6. Statistics of refinement for FNCGs with 1 1 1 1 1 M M M M M    payoff matrices generated by (44) Figure 7. Statistics of refinement for FNCGs with 1 1 1 1 1 1 M M M M M M     payoff matrices generated by (45) 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 80000 85000 90000 1 M Number of FNCGs Features 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 55000 60000 65000 70000 75000 1 M Number of FNCGs Features Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 194 A conspicuous fact of FNCGs by  4, 5, 6N  is that feature #11 starts badly growing. Finally, 85.5 % of 6 6 6 6 6 6     games needing refinement come with the fail: maximultimin hits all the equilibria at once, whereupon superoptimality does not hit an equilibrium. They have only 10 % successful refinement including the uncertainty partial reduction. Dyadic games with that many players, i. e. 2 2 2 2 2 2     games, have 60.2 % of that measure, though. In general, except for 2 2 bimatrix games, dyadic games are the best refinable. Their ratio of the successful refinement decreases from 68.1 % down to 60.2 %. In total ratio, the part of successful refinement decreases: it is 58.6 %, 57 %, 54.4 %, 39.9 %, 26.1 % for 2, 6N  . 8. Discussion Obviously, the presented theory does not assure a perfect refinement. A total number of fails increases as FNCG (1) gets of a bigger size. The perfect outcome (features ## 4, 5, 9) strongly depends on the key parameters of an FNCG: the number of players and the players’ numbers of pure strategies. That way how payoff matrices are given influences also, but a regular structure of payoff scattering, like the considered (40), is far less influential. If payoffs are non-moderately (illogically) scattered then a single metaequilibrium, if even it exists, may be significantly disadvantageous for one or more players (Romanuke, 2018b). This disadvantage, meaning “someone always has less”, is common for the known refinement concepts. Bimatrix, trimatrix, and 1 2 3 4 M M M M   games are the most widespread ones in practice. And for them the stated approach of maximultimin and superoptimality for refining efficient Nash equilibria works very good. Based on the statistics by generators (41) – (45), the best refinability (considering only features ## 4, 5, 7, 9, 10, 12; do not confuse it with the part of successful refinement) is expected to be a distinctive property of trimatrix games and FNCGs with four players (whose numbers of pure strategies do not differ much from each other). Another merit is a possibility to partially reduce the uncertainty of equilibria by achieving one of conditions (30), (33), (35). However, if payoffs are not scattered illogically, even a partial reduction may lead to an eventually successful single-metaequilibrium refinement. Consider an example of a trimatrix 8 6 3  game (Figure 8) generated by (42). This game has five equilibria, four of which are efficient:   4 1 q q E e            15 26 32 18 21 32 18 26 32 18 23 33, , , , , , , , , , ,x x x x x x x x x x x x and their respective payoff aggregates are  49, 48, 48 ,  49, 47, 49 ,  49, 47, 49 ,  47, 49, 48 . Equilibrium  16 21 34, ,x x x producing payoff aggregate  49, 45, 44 is nonstrictly dominated by equilibria  1 2 3, ,e e e . Subsets (7) are , , . (46) Maximultimin subsets (17) are as follows: Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 195 45 46 40 48 42 42 45 44 46 41 44 42 49 43 42 41 46 48 46 43 48 46 43 49 48 43 44 43 48 47 46 42 41 47 47 41 43 42 40 48 44 48 42 44 40 41 47 47 41 41 45 41 41 41 47 47 46 49 41 43 44 41 42 43 46 46 46 44 49 40 45 46 40 46 46 41 48 49 41 40 44 49 46 42 45 44 44 48 48 46 48 44 41 49 47 45 44 43 42 43 45 42 45 44 40 40 47 41 41 48 47 47 45 49 42 48 41 47 47 43 47 45 47 47 46 40 44 46 40 44 47 49 43 41 46 45 44 44 45 43 44 46 43 47 45 40 45 41 42 49 48 40 41 43 44 40 41 46 42 40 42 42 44 47 43 41 49 41 49 47 42 42 42 41 41 43 48 42 48 42 46 49 49 43 41 40 40 40 46 45 43 44 41 48 47 46 47 41 43 41 47 48 40 44 49 42 49 41 49 45 44 46 48 44 43 49 49 44 49 45 49 49 42 42 47 41 44 40 45 43 48 48 43 43 43 42 41 41 48 48 42 42 44 40 49 42 40 43 46 49 46 40 46 40 43 49 42 48 44 40 45 45 47 41 40 40 42 42 44 45 48 46 43 40 41 45 46 43 41 48 42 43 49 47 48 47 45 45 40 44 44 41 47 40 46 49 43 44 46 48 47 48 49 49 43 48 41 46 47 45 45 47 46 45 48 48 40 45 42 42 43 46 44 44 47 40 47 47 41 42 47 43 46 45 41 45 48 44 40 43 40 44 40 44 41 47 49 42 48 49 49 46 46 43 49 40 43 48 47 46 41 47 44 47 44 45 45 42 40 45 43 48 44 42 40 41 41 49 48 44 47 49 42 41 46 45 46 44 46 40 45 47 44 47 41 41 40 41 43 47 44 44 47 48 49 44 48 43 45 41 40 43 45 41 48 46 41 47 40 43 47 40 45 41 46 45 41 47 41 42 45 47 41 47 43 45 42 48 47 41 48 41 43 45 45 42 48 43 43 46 48 49 46 47 44 42 47 41 40 43 46 47 49 45 49 40 41 49 46 46 49 42 40 47 41 43 47 43 42 46 40 45 47 45 42 40 42 42 43 42 45 49 49 44 47 45 46 43 48 44 49 40 44 45 46 44 48 42 43 45 41 48 46 48 42 48 43 45 45 46 45 48 40 44 48 48 46 40 47 43 41 49 49 42 44 49 44 42 41 46 47 45 42 44 43 40 40 43 43 40 47 48 44 48 48 41 41 43 45 49 41 42 43 46 44 46 41 40 46 40 41 40 46 49 43 42 48 49 44 40 48 46 45 48 40 41 44 41 45 40 42 43 44 40 48 48 48 46 45 45 47 40 43 42 42 47 49 48 45 40 41 48 44 49 43 43 44 48 45 41 42 42 48 41 40 42 45 43 40 47 40 46 48 42 42 46 40 47 47 41 43 45 42 48 42 42 45 43 44 41 40 44 48 49 44 43 47 42 46 42 47 40 41 43 40 43 45 44 44 40 40 48 44 43 41 46 41 44 40 46 49 46 41 44 46 44 42 41 41 45 43 45 45 42 48 43 49 42 43 48 40 49 42 45 48 43 45 41 44 44 43 42 46 48 40 40 42 46 46 40 Figure 8. A stack of three payoff 8 6 3  matrices of a trimatrix 8 6 3  game, where efficient payoffs are highlighted bold (the second and third columns referring to the respective pure strategies of the third player) , , . So, here set (20) is     15 26 32 18 26 32, , , , ,R x x x x x x E  (47) and case (27) is true. Now, by the superoptimality rule, there is a summing over two singletons in (24): , that still gives us two metaequilibria  15 26 32, ,x x x and  18 26 32, ,x x x in set (47) with their respective payoffs  49, 48, 48 and  49, 47, 49 (Figure 9). Consequently, this is outcome #4 and feature #12, wherein inequality (35) is true 3 * 1 1 2 4 r r X R E              . (48) Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 196 Despite the superoptimality rule works here in vain, maximultimin allows to have reduced the uncertainty of equilibria, according to (48), twice as less. 44 40 49 43 46 44 49 49 49 42 47 40 45 40 48 44 40 49 47 40 47 49 49 49 49 45 48 44 43 48 49 43 49 42 48 41 Figure 9. A stack of three 2 3 2  submatrices of matrices in Figure 8, which are defined on a product of subsets (46), where payoffs at metaequilibria are highlighted squared At first view, it seems that the obtained result with two equilibria is not yet perfect refinement. However, the first player will not care of either of those two equilibria. And, nonetheless, the second player is guaranteed a payoff of 47, and the third one is guaranteed a payoff of 48. Furthermore, the second and third players do not have a choice. That is a perfect result of decision-making. While refining, a researcher should be aware of that both numbers of games without pure Nash equilibria and having a single pure Nash equilibrium decrease as FNCG (1) gets of a bigger size. At the same time, the number of games having multiple efficient equilibria (feature #3) increases up to FNCGs with six players. Multiple equilibria are more probable in bigger size games. These factors define necessity of refinement, which strengthens for bigger FNCGs. But despite the refinement statistics by Figures 3 – 7 are still weakly promising, notice that generators (41) – (45) are yet “pessimistic” giving us only integer-valued repetitions of a set of payoffs (for instance, see them in Figure 8). Therefore, those percentages in the range of successful refinement (58.6 %, ..., 26.1 %) are expected to be higher for FNCGs which model real-world practice interactions (such FNCGs have a way less repeating payoffs). 9. Conclusion Finding maximultimin subsets (17) and either superoptimality subsets (21) or (24) constitute the core of the theory of refining pure strategy efficient Nash equilibria in FNCGs under uncertainty. This theory exploits the maximin, expanded via the maximinimin to maximultimin principle, and a superoptimality rule wherein minimization is substituted with summation. The maximultimin rule guarantees definite payoffs for players. The superoptimality rule stands like a backup plan, and it is enabled if maximultimin cannot produce just a single refined efficient Nash equilibrium (now-called a metaequilibrium). An average effectiveness of refinement by maximultimin and superoptimality, which is exemplarily visualized in Figures 3 – 7 (for a pessimistic approach analysis), appears satisfactory. The theory reckons on dealing with efficient equilibria producing acyclic-and- asymmetric payoff aggregates. Non-distinguishable equilibria produce identical payoff aggregates, and also aggregates with mirror-like symmetry and cyclic symmetry. Such equilibria cannot be principally refined. However, this initial nonrefinability is quite rare in practice due to payoff matrices are hardly ever estimated “symmetrically”. Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 197 Nominally, the stated approach to the refinement is a contribution to the field of the equilibria refinement game theory. The contribution still can be advanced for cases when the uncertainty amongst the equilibria is reduced only partially, that is when one of conditions (30), (33), (35) holds. In a way, the reduction can be evaluated as a ratio of the number of initial efficient equilibria to the number of metaequilibria. For instance, this ratio is 2 in the example with inequality (48). If the refinement fails, a method of finding approximate Nash equilibrium situations with possible concessions can be attached and used (Romanuke, 2016b; Romanuke, 2016a) for the case of situations in pure strategies. For this, the smallest possible concessions are to be found to refine equilibria at least partially. At that, both cases of refinement fails and non-distinguishable equilibria may be rectified. Funding: This research received no external funding. Acknowledgments: This work was technically supported by the Faculty of Navigation and Naval Weapons, Polish Naval Academy, Poland. Conflicts of Interest: The author declares no conflicts of interest. References Bajoori, E., Flesch, J., & Vermeulen, D. (2013). Perfect equilibrium in games with compact action spaces. Games and Economic Behavior, 82, 490–502. Barelli, P., & Duggan, J. (2015). Purification of Bayes Nash equilibrium with correlated types and interdependent payoffs. Games and Economic Behavior, 94, 1– 14. Belhaiza, S., Audet, C., & Hansen, P. (2012). On proper refinement of Nash equilibria for bimatrix games. Automatica, 48 (2), 297–303. Dopfer, K., & Potts, J. (2007). The General Theory of Economic Evolution. London: Routledge. Fudenberg, D., & Tirole, J. (1991). Perfect Bayesian equilibrium and sequential equilibrium. Journal of Economic Theory, 53 (2), 236–260. Gerardi, D., & Myerson, R. B. (2007). Sequential equilibria in Bayesian games with communication. Games and Economic Behavior, 60 (1), 104–134. Harsanyi, J. C., & Selten, R. (1988). A general theory of equilibrium selection in games. Cambridge: The MIT Press. Kohlberg, E., & Mertens, J.-F. (1986). On the strategic stability of equilibria. Econometrica, 54 (5), 1003–1037. Kumano, T. (2017). Nash implementation of constrained efficient stable matchings under weak priorities. Games and Economic Behavior, 104, 230–240. Leinfellner, W., & Köhler, E. (1998). Game theory, experience, rationality. Foundations of social sciences, economics and ethics. In honor of John C. Harsanyi. Netherlands: Springer. Leyton-Brown, K., & Shoham, Y. (2008). Essentials of game theory: a concise, multidisciplinary introduction. San Rafael, CA: Morgan & Claypool Publishers. Romanuke/Decis. Mak. Appl. Manag. Eng. 4 (2) (2021) 178-199 198 Liu, S., & Forrest, J. Y. L. (2010). Grey Systems: Theory and Applications. Berlin: Springer. Marden, J. R. (2017). Selecting efficient correlated equilibria through distributed learning. Games and Economic Behavior, 106, 114–133. Mertens, J.-F. (1995). Two examples of strategic equilibrium. Games and Economic Behavior, 8 (2), 378–388. Myerson, R. B. (1978). Refinements of the Nash equilibrium concept. International Journal of Game Theory, 7 (2), 73–80. Myerson, R. B. (1997). Game theory: analysis of conflict. Harvard: Harvard University Press. Osborne, M. J. (2003). An introduction to game theory. Oxford: Oxford University Press. Romanuke, V. V. (2010). Determining and applying the set of superoptimal pure strategies in some antagonistic games with nonempty set of saddle points in pure strategies. Visnyk of Zaporizhzhya National University. Physical and Mathematical Sciences, 2, pp. 120–125. Romanuke, V. V. (2010). Environment guard model as dyadic three-person game with the generalized fine for the reservoir pollution. Ecological Safety and Nature Management, 6, pp. 77–94. Romanuke, V. V. (2016). Sampling individually fundamental simplexes as sets of players’ mixed strategies in finite noncooperative game for applicable approximate Nash equilibrium situations with possible concessions. Journal of Information and Organizational Sciences, 40 (1), 105–143. Romanuke, V. V. (2016). Approximate equilibrium situations with possible concessions in finite noncooperative game by sampling irregularly fundamental simplexes as sets of players’ mixed strategies. Journal of Uncertain Systems, 10 (4), 269–281. Romanuke, V. V. (2018). Pure strategy Nash equilibria refinement in bimatrix games by using domination efficiency along with maximin and the superoptimality rule. Research Bulletin of the National Technical University of Ukraine “Kyiv Polytechnic Institute”, 3, 42–52. Romanuke, V. V. (2018). Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality. KPI Science News, 4, 38–53. Selten, R. (1975). Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4 (1), 25–55. Suh, S.-C. (2001). An algorithm for verifying double implementability in Nash and strong Nash equilibria. Mathematical Social Sciences, 41 (1), 103–110. Tian, G. (2000). Implementation of balanced linear cost share equilibrium solution in Nash and strong Nash equilibria. Journal of Public Economics, 76 (2), 239–261. Refinement of acyclic-and-asymmetric payoff aggregates of pure efficient Nash equilibria 199 Van Damme, E. (1984). A relation between perfect equilibria in extensive form games and proper equilibria in normal form games. International Journal of Game Theory, 13 (1), 1–13. Vorob’yov, N. N. (1958). Situations of equilibrium in bimatrix games. Probability theory and its applications, 3, 318–331. Vorob’yov, N. N. (1984). Game theory fundamentals. Noncooperative games. Moscow: Nauka. Vorob’yov, N. N. (1985). Game theory for economist-cyberneticians. Moscow: Nauka. © 2021 by the authors. Submitted for possible open access publication under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).