No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation
Authors: Per Kristian Lehre
Shishen Lin
Venue: NeurIPS 2024 poster (2024)
Keywords: No Free Lunch Theorem
Black-Box Optimisation
Black-Box Complexity Analysis
Zero-Sum Games
Primary area: algorithmic_game_theory

Abstract: Black-box optimisation is one of the important areas in optimisation. The original No Free Lunch (NFL) theorems highlight the limitations of traditional black-box optimisation and learning algorithms, serving as a theoretical foundation for traditional optimisation. No Free Lunch Analysis in adversarial (also called maximin) optimisation is a long-standing problem [45 , 46]. This paper first rigorously proves a (NFL) Theorem for general black-box adversarial optimisation when considering Pure Strategy Nash Equilibrium (NE) as the solution concept. We emphasise the solution concept (i.e. define the optimality in adversarial optimisation) as the key in our NFL theorem. In particular, if Nash Equilibrium is considered as the solution concept and the cost of the algorithm is measured in terms of the number of columns and rows queried in the payoff matrix, then the average performance of all black-box adversarial optimisation algorithms is the same. Moreover, we first introduce black-box complexity to analyse the black-box adversarial optimisation algorithm. We employ Yao’s Principle and our new NFL Theorem to provide general lower bounds for the query complexity of finding a Nash Equilibrium in adversarial optimisation. Finally, we illustrate the practical ramifications of our results on simple two-player zero-sum games. More specifically, no black-box optimisation algorithm for finding the unique Nash equilibrium in two-player zero-sum games can exceed logarithmic complexity relative to search space size. Meanwhile, no black-box algorithm can solve any bimatrix game with unique NE with fewer than a linear number of queries in the size of the payoff matrix.

No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation
Per Kristian Lehre
Shishen Lin'
School of Computer Science University of Birmingham Birmingham, United Kingdom p.k. www.eeeberaam..... ac.
School of Computer Science University of Birmingham Birmingham, United Kingdom sxl 121222studdnt bham. ac.
Abstract
Black-box optimisation is one of the important areas in optimisation. The original No Free Lunch (NFL) theorems highlight the limitations of traditional black-box optimisation and learning algorithms, serving as a theoretical foundation for tradi- tional optimisation. No Free Lunch Analysis in adversarial (also called maximin) optimisation a long-standing problem [45] (6). This paper first rigorously proves (NFL) Theorem for general black-box adversarial optimisation when considering Pure Strategy Nash Equilibrium (NE) as the solution concept. We emphasise the the
solution concept (i.e. define the optimality in adversarial optimisation) key in our NFL. theorem. In particular, if Nash Equilibrium is considered as the solution concept and the cost of the algorithm measured in terms of the number of columns and rows queried in the payoff matrix, then the average performance of all black-box adversarial optimisation algorithms is the same. Moreover, we first introduce black-bor box complexity to analyse the black-box adversaris optimisation algorithm. We employ Yao's Principle and our new NFL Theorem provide general lower bounds for the query complexity of finding Nash Equilibrium in adversarial optimisation. Finally, we illustrate the practical ramifications of our results on simple two-player zero-sum games. More specifically, no black-box opti- misation algorithm for finding the unique Nash equilibrium in two-player zero-sum games can exceed logarithmic complexity relative to search space size. Meanwhile, no black-box algorithm can solve any bimatrix game with unique NE with fewer than a linear number of queries in the size of the payoff matrix.
1 Introduction
1.1 Black-Box Optimisation and the No Free Lunch Theorem
Black-Box Optimisation (BBO) is crucial for optimising complex, unknown, or expensive-t--evalute functions in real-world scenarios, such as aerodynamic design and hyperparameter tuning, where only input-output observations are available. Formally, BBO is the task of optimising objective functions from some function class f where F consists of f X' - IR, where the algorithm limited to making queries to f [1] 14 36). In this case, the algorithm is only able to sample and query the function value f(x) of search points x E X' from "black-box" or "oracle" without access to any description of the objective functions f. A similar framework can be extended game-thcoree theoretic BBO, namely adversarial BBO. Specifically, adversarial BBO is the task that optimising payoff functions from some payoff function class & where G consists of black-box functions g X ) + R. with a limited budget of function evaluations. Additionally, two players E X and E y form
Authors are listed in alphahetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

maximin optimisation (as presented in Figure D. The original No Free Lunch Theorems for traditional optimisation can be summarised as follows:
"For all possible metrics, no search algorithm or supervised learning algorithm is better than another when its performance averaged over all possible problem instances 445 44
y Input
f(x)
g(x, y)
X
Black Box
X
Black
Input
Output
Input
Box
Output
Comparison between traditional black-boo optimisation and maximin black-box optimi- sation. Instead of querying in traditional optimisation, maximin optimisation queries (x, y) include both strategy x and the best response y from the opponent, i.e. max mingey g(2, y). Their interaction is converted to the payoff g(;; y) in the given black-box model.
Figure 1:
Wolpert and Macready 45 and Wolpert 44 have revealed the underlying facts about the usefulness
of traditional black-box optimisation algorithms, including various randomised search heuristics (such evolutionary algorithms and simulated annealing) and machine learning algorithms (such as supervised learning). In particular, it shows that the performance of all black-box optimisation algorithms 45 and learning algorithms 44,, when averaged over all problem instances, is the same for any maximisation or minimisation tasks. Droste et al. [ has provided generalised NFL theorem with more realistic scenarios by relaxing NFL theorem holds from all problem instances to problem instances closed under permutation. Another seminal work by Schaffer [37] also showed conservation law for the generalised performance of learning algorithms classification problems.
Adversarial optimisation tasks, such as maximin optimisation, are more complex and often counter- intuitive compared traditional optimisation problems. In adversarial settings, defining solution concepts, or establishing what is meant by optimality, is essential. Common solution concepts include 'Maximisation Over All Test Cases', 'maximin' and Nash Equilibrium. 'free lunch' in adversarial optimisation implies that, for a given solution concept, some algorithms consistently outperform others when averaged across all possible problem instances. This phenomenon
demonstrated by Wolpert and Macready (46) for adversarial optimisation with respect to the 'maximin' solution concept (Definition I0). Similarly, Service and Tauritz (39 established 'free lunch' result for the 'Maximisation Over All Test Cases' concept (Definition 9).
Beyond 'maximin' and 'Maximisation Over All Test Cases', Nash Equilibrium is another widely studied solution concept in adversarial learning and maximin optimisation. This concept is central to various applications, including adversarial learning models such as GANs [15] 20) and spatial games 19 26 32). While previous studies by Wolpert and Macready [46] and Service and Tauritz
39 have demonstrated the existence of 'free lunches' in adversarial optimisation, the following key questions remain open:
(1) Does adversarial optimisation exhibit a 'free lunch' for all possible solution concepts?
(2) If use Nash Equilibrium as the solution concept, how can characterise the difficulty of black-box adversarial optimisation problems for problem-independen,, possibly randomised, search heuristies?
In this paper, we answer Question (1) in the negative by showing No Free Lunch theorem for Nash Equilibrium solution concept and address Question (2) by introducing black-box complexity tools.
1.2 Challenges and Technical Overview of the NFL and BBC Results
There are several challenges in showing the NFL and BBC results. First, we highlight the challenges and our technical details the derivation process compared previous NFL work. The classical No Free Lunch theorem applies proof by induction with respect to the size of the function domain. A natural idea is to extend the previous mrof-by--ndducton method in our NFL proof. However, one of the most challenging aspects of deriving NFL for Nash Equilibrium (NE) is that the adversarial

---

setting significantly increases the difficulty since the problem depends on the performances of both the player and the opponents. To address this, we introduce two technical lemmas from game theory (i.e. Lemma 3 and Lemma and help to construct the isomorphism between two different problem classes (i.e. Corollary | and Lemma 2). which is an essential step in the proof of the original NFL. theorem for traditional optimisation (see Section B for more details). Another significant challenge is that we start with a very weak assumption: we only allow access to the payoff function and make no assumptions about its properties, such as convexity, continuity, or differentiability. In fact, no gradients, continuity, or differentiability make the NFL and black box results easier to prove (i.e., the function class lacks a specific structure). On the other hand, it makes it more diffieult for the algorithm. Consequently, we have limited analytical tools to proceed. To analyse the black-bor complexity of adversarial optimisation, we introduce Yao's minimax principle and apply our new NFL result. Please consult the proof of Theorem 4.2 for more details.
1.3
Contribution
We prove new impossibility result black-box adversarial optimisation. In two-player zero- sum game setting, there is no free lunch with respect to an approximation of the real cost model when regarding the unique Nash Equilibrium as the solution concept. In other words, all black-box adversarial optimisation algorithms have the same expected performance over a uniform distribution of all possible problem instances with the unique Nash Equilibrium as the solution concept. It is the first step to resolve this long- long-standing open research problem about NFL in general black-box adversarial optimisation since 45] 46]. Our results highlight the significance of the choice of solution concepts and the limitation of general black-box adversarial optimisation. Additionally, we introduce the first general black-box model and the notion of black-box complexity for adversarial optimisation. Under this general black-box model, we provide the general lower bounds for query complexity of computing Nash Equilibrium in adversarial optimisation. Finally, we illustrate our results on examples of computing unique Nash Equilibrium in two wwo-player zero-sum games.
2 Preliminaries
2.1 Notation
Given n E N. [n] = (1,2 ,n). Given a finite set X, we denote the permutation group by 6(X) = fo x X' 1 is permutation of 23. For any R let SUPP(c) == (i E [n] 4 0}. We refer to query complexity or runtime as the number of payoff function evaluations until the given algorithm finds the optimum. We consider the search space X' x V, where X' and y are finite and denote the cardinality of a set by | For any bitstring z, |z|1 denotes the number of 1-bits in z. X = Y denotes the isomorphism between X and Y. X Y if there exists a one-to-one correspondence map from X to Y.
Let f X Y be function from a set X to set Y. If A is subset of X, then the restriction Y be any function and A and B be sets such that X C A and Y B. An extension of f to A is a function g f(x) = g(x) for all x E X. Alternatively, g is an extension of f to A if f is a restriction of g to X.
of f to A is the function: fla A + Y f()). Let f = X +
B such that
In this paper, we assume that the black-box optimisation algorithms do not make the same query twice. This can be achieved by memorising the outcome of previous queries.
2.2 Solution Concepts
Solution concepts for classical function optimisation are not directly applicable to adversarial op-
timisation in general-sum or zero-sum game settings [3] 24 35). Each agent or player's payoff depends on not only its action but also the response from its opponents, and thus, we need to introduce different solution concepts to specify what kind of optimum we look for.
Pure Strategy Nash equilibrium is considered as our solution concept in this work. We are interested in whether the black-box adversarial optimisation can efficiently find any given game's 's Nash equilibrium. We use the formulation in (30 to define Nash equilibrium rigorously. In this paper, we only focus on Pure Strategy Nash Equilibrium (abbrev. NE).
3

---

Definition 1. (Nash) Consider a two-player game. Given strategy spaces X' x ) and payoff functions g. h X x y + O, where O an ordered set which determines the outcome of candidate solution X' on test V, (x", .y) is a Nash equilibrium if for all (z, v) E X x }/ o(x""y" 2 g(r, y²) and h(x=.,""""00n" _y"= 2 h(r", ())
partieular, if the two-player game is zero-sum 0 for all (x, E X' x 3), then (x", yy) is Nash equilibrium if for g(x", .e"""") S g(x",))) ,2). The solution concept is defined by
(that is. if g(r, u) + h(x, v) all (x, v) E X ), D(g
S = {(==''")) ,"") E X x x v(r,y) E X x (z, v²) S g(0" vy) S ()))
We also defer other solution concepts for comparison in the appendix. We use the formulation in 46 39]
No Free Lunch Theorem for Computing Nash Equilibrium in Adversarial Optimisation
In this section, we prove a No Free Lunch Theorem for black-box adversarial optimisation. As a first step toward the No Free Lunch Theorem, we consider two-player zero-sum games with the unique NE as the same setting in [34], but we relax the restriction from potential games to general two-player zero-sum games. The original NFL theorem for traditional optimisation assumed all problems instances 45 and later, sharpened work also proved that this holds for functions 'closed under permutation' 38 We now explain what 'closed under permutation" means and how it can
be extended to games.
Permutation closure of set of functions means that let X, be two finite sets and f defined by f(x;) = yt. Let a be a permutation a + X and we can permute the function: [(((z)) == o f (zr). Schumacher et al. (38 and Droste et al. [ defined 'closed under permutation (c.u.p.)' with respect to a single search space X. A class of functions F = f X x y - R is called c.u.p. if for all f F and all permutations need to extend this notion to X' y
6(X), for E F. For our adversarial setting,
Definition 2. Given two-player zero-sum games, suppose F a subset of all the payoff functions in these games X' x y + O where O C R. We say F is c.u.p if for any E F and any permutations on X, N. denoted by a E G(X), T E G()), we have (o @ 7) o oggg E (or abbreviated (aT)g) where (a @ T) g(z y) == (a(z), for all (z. E X ).
If set of two-player zero-sum games is c.u.p., will also call it structure-free. In this paper, we restrict to the case that X, V. O are finite sets following the settings in 45 46). The proof of the No Free Lunch theorem for traditional optimisation by Droste et al. [12 by induction, where one assumes that the statement is true for all "smaller problems". Here, a smaller problem refers to the following definition of aub-game or sub-problem class. Next, we define a sub-problem class for two-player zero-sum games.
Definition 3. Given two-player zero-sum games, let O C IR and be any subset of the set of payoff functions in these games g X' x y + O such that F is closed under permutation. For any given (I1, 8/1) E X x V, any function by y + O, and any function by : X + O, we define a sub-problem class F ((x1, 81). ) (bi, b2)) with respect to F follows: f F ((11, V1), (bi, bz)) if and only if there exists E F such that
(1) g( v) = 61 (v) for all E 3: (2) g(x, vn) = (z) for all E X;;
(3) f is restriction of on (X' (a1)) x (2)) (mi)).
Next, before we show that sub-problem class F F((11, 91), (b), b2)) is c.u.p., we need lemma to guarantee that after any permutation, the permuted pavoff function still contains the same unique Nash Equilibriun We provide corollary Lemma We defer all the proofs the appendix due to the page limit.
R} be any set of two-player zero-sum games with unique NE. Assume furthermore that J is c.u.p.. Then, for any game g E F, let
Corollary 1. Let | = | and F C :g:
TThe further explanation for sub sub-problem classes can be found in Section E

---

(x". E X' x y denote the unique Nash Equilibrium of g. For any permutations over X, denoted by T E 6()), (or 7) o gg FF exhibits the same unique Nash Equilibrium (a* y²). Moreover, if for any # x" and yo F y", the restriction of on (X' (xo)) x () {uo)), denoted by (1
exhibits the same unique Nash Equilibrium (x","")
This permutation essentially swaps the rows and columns in the payoff matrix. Corollary I shows that the permutation of rows and columns does not change the optimum (Nash Equilibrium in any given payoff' function). Moreover, if we remove the row and column in the given payoff function, which do not contain the unique Nash Equilibrium, then the unique Nash Equilibrium remains the same in the restricted sub-prot coooproblem.
Next, we prove the sub sub-problem class is closed under permutation.
Lemma 1. If F is c.u.p., then F ((x1, 3n), (b1, b2)) is also c.u.p..
Then, we want to know if we choose different (zr, y) in the sub-problem class, are they still isomorphic (i.e., essentially the same problem for any black-box optimisation algorithm)?
Lemma 2. For all (1), (22, v2) E X y and b, : y + R. b2 X + R. we have the isomorphism 3)
F F(221,11), (61, b2)) = F ((22, 32), (b,, b2)).
Given (Ie, ye) is the search point by Algorithm H on payoff function g at iteration E N and (x", y²) is the unique NE in two-player zero-sum game defined by g : X' x y R. Theorem 3.1 considers the following query complexity: assume the cost C₁ is the unique queries made by Algorithm H,
Tin (H, inf(C, 0 xe x² y y²}
Now, we prove our main theorem.
Theorem 3.1. Given F as subset of all the payaff functions g X' ) - O with unique Nash Equilibrium where S and |X| = Vy). Let be an arbitrary (randomised or deterministic) black-box adversarial optimisation algorithm for any g F where F is closed under permutations. Let r( (H, F) be the average (under the uniform distribution on F) of the expected query complexity of H on g E F (i.e. E(Tis ())))) Then r(H, r(Ht', F) for all algorithms H, Il'.
Proof Sketch. The proof of the main theorem is deferred to the appendix. Briefly, we use proof by induction on the size of the search space. During the inductive hypothesis, problem class is (b), b2)). decreasing the search space from size x N to size -1-1) (N - 1). where |X]
reduced from F to F ((11, v1), :
N. Then using Lemma 2 and inductive step, it follows that r(H,F)= = FF for any two deterministic algorithms H, Hi' and the claim for randomised algorithms quickly follows from the fact that any randomised algorithm can be viewed probability distribution among all deterministic algorithms.
Theorem 3.1 reveals important underlying result: All black-box adversarial algorithms exhibit the same average runtime FH of all possible problem instances (or problem instances c.u.p.) with unique Nash Equilibrium in two-player zero-sum game setting. It is reasonable result since Theorem 3.T tells us that a class of payoff functions with a unique Nash Equilibrium does not change by any permutation or any optimisation algorithm to use and it cannot help to find the Nash Equilibrium. This is also the reason why the original No Free Lunch theorem for traditional optimisation holds 45 44 As concluded by Ho and Pepyne (23] "if anything is possible and occurs with the same probability, then nothing can be expected.
the input space, there is no structure provided for any search heuristic
This result also surprising since Wolpert and Macready [46] and Service and Tauritz 39 both show there exists free lunch with respect to the two solution concepts in Definition 9 and Definition I0 However, our result does contradict the previous result. We consider the performance measure T(H,g) g) and a different query model considered by the previous work. In particular, Definition 9 and Definition only take the player x into account, while the opponent optimum and different query model and performance measures can make difference, resulting in either FL or NFL results. In summary, our new NFL theorem highlights the significance of solution concepts and also reveals that adversarial optimisation can exhibit mnofrreellunch" in particular for NE solution concept.
'Here we define isomorphism following [1I rather than defining it as usual group ring isomorphism since we do not require any group or ring structure of F in the proof.
5

---

Black- Box Complexity of Black-Box Adversarial Optimisation
As shown in the previous NFL theorem, no better universal algorithms exist on structure-fres problems (i.e., only assume the payoff function consists of the unique NE). In order for an algorithm to guarantee good performance, it is necessary to restrict the algorithm to classes of games that possess some structure. To compute the Nash equilibrium certain classes of problems, including Nash equilibrium in black-box setting, there are many works on analysing the computational complexity for black-box algorithms, and researchers aim to minimise the query complexity and provide more efficient algorithms to compute Nash equilibrium in two-player zero-sum game settings 17. 26, measure of an algorithm (like query complexity) depend on the size of the search space, and is there any limitation that these algorithms will reach regardless of the problem g? We answer these questions here using black-box complexity.
3 21 22] The following questions remain under-cxplored: How does the performance
4.1 The Unrestricted Black-Bot Model and the Black-Box Complexity
This section focuses on adversarial black-box optimisation and study the query complexity of learning Nash equilibrium in two-player zero-sum-game setting. We refer to [3 g 10) more detailed introduction to the black-box complexity theory on traditional black-box optimisation. To prove a lower bound that holds for all algorithms, it necessary first formally to define what constitutes an algorithm. Next, we construct an unrestricted black-box model of adversarial optimisation.
Algorithm 1 An Unrestricted Black-Box Model with Unique Query History
Require: Search spaces X.
Require: Payoff functions g X' x 3' + R. x y R; 1: Initialise (Ir,, yo) based on Pa: Initialise Ho 0 and Co - 0.
2: for / 1, ... until the termination criterion met do
3: Choose some probability distribution PI(j). depending only on [(t) where
I(t) == - (mzj Uy g( h(x, v;)) E (X' x y x R x RR)-1
4: Produce a random search point (Fe, Vb.) based on PI(0)-
5: Query the payoffs ga 31, h(=;, y1)
6: if (It, 31) & H1-1 then C. C. 1; 1; H U ((()
7:
else C. = 12-1; H. He-1-
Algorithm [ defines class of algorithms subject to various probability distributions and samples the new strategy pair based on previous pairs and their payoffs. The initial search point (ro. yo) is independent of the problem, so we can choose any probability distribution Po to initialise the algorithm. Subsequent strategy pairs are obtained by asking the oracle to apply a given variation operator all previously queried search points subject sample probability distribution Pr(j- By specifying different sample probability distribution Pr(e), Algorithm Tepreseenss various black-box optimisation algorithms, including several adversarial search (also called competitive coevolutionary) and randomised algorithms FINDPSNE (designed to learn the NE in bimatrix games) 27 Note that the model only considers the cost of unique queries made by the algorithm (i.e. we check the search point in the previous query history H, in line 6). We assume that an algorithm which makes the same query twice is only charged for the cost of one of the queries.
algorithms 46
32
Now, we define the query complexity (or runtime) of black-box adversarial optimisation algorithms by extending the idea of the traditional single-objective black-box. optimisation algorithm in 13 43 and assuming h = g (i.e. zero-sum game) in this case.
Definition 4. Given any unrestricted black- box algorithm with unique query history A and the payoff function g : X' x y + F. T(A. g) the query complexity of with respect to g and (æt, yc) the search point generated by A if
T(A.g) g) = inf (dC, e eN| (xr, E arg max min g(x,, v)}
neX yE)
where d 21, If the game is zero-sum, then d = 1. Otherwise, d d=3

---

Note that T(A,g) E R u foc) is the number of payoff evaluations until A queries for the first time Now, we can define what black-box complexity means with respect to a given class of adversarial optimisation algorithms and problem classes.
some (x" arg max minyey g(z, y). y).
Definition For class of payoff functions g : X' y + R, the A-black-box complexity of G is defined as 9) := supgeg T(A,g), the runtime of A under the worst-case scenario G. Then, the A- 4-black-box complexity of G is T(A, 9) == inf AE T(A, g) inf AE sup,ec T(A, g): the best or minimum complexity among all A E A with respect to G. If A is the whole class of all black-box algorithms,
denote T(A, 9) the unrestricted black-box complexity of G.
We want to point out the difference between these two definitions. Definition considers the query complexity for particular algorithm and problem instance, and Definition D considers the black-box complexity for the best possible query complexity of all possible given algorithms under the worst- case scenario. The traditional black-box complexity theory characterises the difficulty of a certain class of problems and explores the limitations of the given black- black-box optimisation algorithms. We expect our extension to adversarial optimisation can provide similar insights as well.
4.2 A General Lower Bound for Black-Box Adversarial Optimisation
We first provide lower bound of query complexity for general class of black-box adversarial optimisation problems.
Theorem 4.1. Let X and y be any finite sets. Assume that B R with k: |B] 2 2. Consider any class of two-player zero-sum games 9 C. {g: : X x + B} such that for all (I, y) E X x y, there exists a game 92,9 which has (a, y) as unique, pure Nash Equilibrium. Then, the class & has black box complexity at least [log, X x y/1 1.
4.3 A General Lower Bound for Two-player Zero-Sum Bimatrix Games
In this subsection, employ Yao's Principle and No Free Lunch Theorem to provide general lower bound for query complexity of searching Nash Equilibrium in zero-sum bimatrix games, and this leads to sharper lower bound compared to the previous result in (27].
Theorem 4.2. Let A be the set of all randomised algorithms defined by Algorithm I and T(A, P denote the query complexity of A with respect the impul payoff matrix P for a two-player zero-sum game. Then, there exists an input matrix P E Raxx with unique pure Nash equilibrium (x", ,y""") such that (A, P)) 2 (n + 1)/2. Thus, the black-box complexity with respect to A of the problem class consisting of all bimatrix games with a unique Nash Equilibrium is at least (n 1)/2.
Theorem 4.2 provides sharper lower bound by multiplicative factor 4 compared with the current best bound by [27]. This result also demonstrates that in a two-player zero-sum bimatrix game (with an n payoff matrix), there are complex instances where no randomised algorithm achieve better than Onn) query complexity unless additional problem structure is provided.
4.4 Applications on Two-Player Zero-Sum Games
4.4.1 Introduction to Binary Voting Games
This section provides some example applications of our black-box complexity results. Voting games are popular games studied in game theory, computational social choice theory [6] and Boolean games 18). Voting is considered fundamental tool for analysing multi-agent systems [16] 11. We start with simple binary voting games which the outcome or payoff 0 or (or -1 and 1). These games also play role in the analysis of Boolean functions [11.
Convergence to NE plurality voting has been studied from the perspective of social choice theory and researchers specify certain conditions to guarantee the voting games to converge to NEs (28). Some natural question arises: are there any randomised algorithms that can find these NEs in voting games efficiently? What are the limitations of these black-box optimisation algorithms? Using the black-box complexity analysis, we can answer the questions about the efficiency/ineffccieney of black-box optimisation algorithms on binary voting games.
'Note that T(A, P) = T(A, g) where g(z, v) == e Pew with ex, ey denote the elementary probability distribution over probability simplex [(0.13"
7

---

We formulate binary voting games in the context of adversarial optimisation as follows, Consider two parties represented by vectors z, y E {0. 13" where N. Each group has members that either "in favour" (encoded by 1) or "against" (encoded by 0) a particular proposal or decision. One group seeks a strategy x" that maximises its minimum gains against any strategy of the other group, while the other group seeks strategy y" such that its choice minimises the maximum gains of the first group. It essentially forms a two-player zero-sum game.
Definition 6. For x== = y {0,1)* the payoff function DIAGONAL. X - (-1,1)
DIAGONAL(2,9) : {-1 1
1//1 S | otherwise.
In Definition 6 we present the votes of both groups by binary bitstrings and the payoff g can be viewed as a binary voting game where the payoff only depends on which group has the stronger majority "influence". If one group has stronger 'in favour' "influence" in the sense of the number of the support votes (i.e. the number of in the encoding binary bitstring), then we get a payoff' 1 and -1 otherwise. We interested in computing NE in these two-player zero-sum games, i.e. solving (x" y²) )" E arg m mingey g(,, y). Notice that in DIAGONAL, (In, 9n) = (1", (1",17 1n) is the unique NE optimum. In this optimum, neither of the two groups is willing deviate from affecting their payoff g(xn; Vo) anymore. This exactly coincides with the definition of NE.
Next, we consider different binary voting game, denoted by PLATEAU. To make the binary voting game more challenging, we introduce some plateaus in games.
Definition 7. For X' = y' - {0, 1]",, constant E (0, 1), the payoff function PLATEAU : x 1-1,1} is defined as
if || - 21 6n (g(2,)) otherwise
[f(v]
PLATEAU(I,
where f: 1-1,1 and g: X x + (-,1,1] are any functions such that the NE of PLATEAU is (x", v²) & y) ||||1 21 }
Definition] 7 introdduees plateau when comparing the "influence" between two groups and defines a general class of pseudo-Boolean benchmarks with plateau. Imagine committee deciding new policy where there are two groups with equal voting power. If the votes from group X' are balanced or nearly balanced (within the plateau), then the votes from the second group (J)) come into play. It is like their votes are the tiebreaker. If the second group votes in favour, then the policy passes; they vote against it, then it fails. If the votes from group X' are outside the plateau, then the payoff is not restricted to be determined by E V.
Finally, we define game instances generated by (u, v) where u, v E {0,
Definition 8 ((u, -amm instance). For all u, u E f0, 1)", given f: (0, 1)" x 10, - RR we define the (u, vi-instance of denoted by f(u,,)) as f((,,) v) == f(u (1(0x,
We can see that for any u, E {0, 1)", flaee) generates the same payoff landscape as f. In this paper, will be either DIAGONAL or PLATEAU. We defer more details to Section c
4.4.2 Black-Box Complexity of Learning Nash Equilibrium in Binary Voting Games
First, let us illustrate how Theorem 4.1 and Theorem 4.2 work on these simple examples. If we consider general class of black-box optimisation algorithms defined by Algorithm [ On binary voting games with a unique Nash Equilibrium, then we provide general lower bound black-box complexity as follows.
Theorem 4.3. The black-box complexity with respect to Algorithm of the binary voting games with problem size n. E and a unique Nash Equilibrium is eRs)))
Theorem 4.3 means that there exist no universal good black-box optimisation algorithms defined by Algorithm|] that can solve all binary voting games with unique Nash Equilibrium efficiently, (i.e. with polynomial query complexity of the problem size). To yield better performance of black-box
We defer the definition of xor Section G in the supplementary material.
8

---

optimisation algorithms on binary voting games, we need to specify the problem class we work on. Next. we consider DIAGONAL and explore the black-box complexity with respect to the class of black-box optimisation algorithms A defined by Algorithm [ DIAGONAT. This reveals that DIAGONAL a feasible benchmark problem for black-box adversarial optimisation algorithms.
Theorem 4.4. Given the game class
DIAGONAL, == (DIAGONAL(...) (u, v) E {0.1)" x {0,
the black-box complexity with respect to Algorithm 1 of DIAGONAL, is (()).
Theorem implies that DIAGONAL, is a sensible maximin benchmark for testing black-box optimisation algorithms. It means that if we restrict the problem class to certain class with specific structure, then is possible to solve them in polynomial query complexity.
We have seen the black-box complexity results on DIAGONAL Next, we start to consider more challenging binary voting games, PLATTEAU. We are interested in whether there is any efficient black-box adversarial optimisation that can solve PLATEAU, in polynomial query complexity (i.e. O(n)). To answer this question, need to compute its black-box complexity.
Theorem 4.5. Given the game class,
PLATEAU, == (PLATEAU I (u. E {0,1]" x {0,1)"), the black-box complexity with respect to the class of algorithmms defined by Algorithm Of PLATEAU is e enn)
Theorem 4.3 implies that all black-box adversarial optimisation algorithms defined by unrestricted model (i.e. Algorithm[]] have exponential runtime on PLATEAU,- They need at least an exponentially large query complexity with respect the problem size n. It is evident that PLATEAU is too challenging that it may not be a proper benchmark for black-box adversarial optimisation algorithms.
4.4.3 Summary
Our study introduces the concept of black-box complexity in binary voting games, providing insights into the challenges faced by general black-box adversarial optimisation algorithms. These examples illustrate two kinds of problems within the general class of binary voting games with unique NE: the polynomial-solvahee
class (i.e., there exists an algorithm that can solve all problem instances of this class in polynomial runtime) and the polppooooall-lllaaallllll class (i.e., there exists no algorithm that can solve all problem instances of this class in polynomial runtime).
Theorem rigorously show that no universal algorithm can efficiently learn the unique Nash Equilibrium (NE) in these games due to their structure- free nature, where efficiency means small query complexity. However, when assuming specific problem structures, such DIAGONAL,, it is possible to come up with a better algorithm which achieves better polynomial query complexity shown in Theorem 4.4. DIAGONAL.,
be promising benchmark for evaluating black-box algorithms. Additional assumptions on the payoff function, like those in PLATEAU, problems, proved in Theorem [4.5 do not lower the difficulty of the problems. This emphasises the need for more careful selection of benchmarks. Black-box complexity emerges as a valuable tool for distinguishing between potentially easy and hard problem instances, guiding the design of black-box algorithms.
5
Further Related Work
5.1
Co-evolutionary Search Heuristies
Next, we provide some practical examples of adversarial optimisation. There various adversarial search heuristics, including competitive co-evolutionary algorithms (CoEAs) B3 26]. CoEAs are a class of algorithms applied in game-theoreee and strategic adversarial optimisation scenarios. For example, CoEAs are used to solve maximin optimisation in a cybersecurity context (32 and to enhance GANs by using co-evolutionary approach for image translation [4]. Similarly, the neural architecture search system Lipizzaner employs co-evolutionary adversarial search to find suitable neural architectures for GANs [42).
Although several applications of adversarial (or co-evolutionary) search exist, there limited theo- retical literature this topic. Lehre (26) demonstrated that the running time of the co-evolutionary

---

algorithm PDCoEA on instances of the discrete bilinear problem is polynomial. Later, Hevia Fa- jardo et al. [22 showed a weakness of RLS-PD and the sufficiency of simple archive prevent evolutionary forgetting. On the other hand, regarding the general black-box optimisation framework, Wolpert and Macready [46] showed there exists "free lunch" in such adversarial (or co-evolutionary) optimisation setting there exist some algorithms have better performance than others averaged across all possible problem instances in adversarial optimisation with respect to the maximin solution concept (see Definition IOP.
5.2 Query Complexity of Learning in Games
The query complexity of various solution concepts in zero-sum and general-sum multi-player games has been well studied (for an overview, see [2 27)). It is well-known that converging to an exact (mixed strategy) Nash Equilibrium in general-sum matrix games is PPAD-complete 77]. Chen and Deng [6] provide simplified proof of the computational complexity of Nash Equilibrium in two- player games. Significant focus has also been placed on how the game dynamics converge to the Nash equilibrium or approximate it [7
Panageas et al. (34) considered the complexity of fictitious play in two-player potential games with unique Nash Equilibrium (NE). They proved the existence of hard instance which requires query complexity Ω 44th ((n/2-2)!)) 2)1)*) where refers to the number of actions. They showed that fictitious play can take exponential time (in the number of strategies) to reach a unique Nash Equilibrium, even when the game is restricted to two agents and arbitrary tie-breaking rules, by constructing a two-player coordination game with a unique Nash Equilibrium. Unlike previous work, our paper focuses more general class of games: the entire class of two-player zero-sum games with a unique NE rather than just potential games. We show that all black-box -ox adversarial algorithms, including fictitious play, exhibit the same average performance across all problem instances in terms of query complexity.
6 Conclusion and Discussion
Utilising the tools from game theory and Yao's principle, rigorously prove the impossibility results for a universally effective adversarial algorithm applicable across various problem classes in black-box adversarial optimisation. We emphasise the impact of solution concept selection on the feasibility of a "free lunch" in adversarial optimisation. Additionally, we introduce the notion of black-box complexity in black-box adversarial optimisation and characterise the difficulty of learning the unique optimum in adversarial optimisation and solving two-player zero-sum games.
The results from this paper build up foundation for future studies on the strengths and limitations of adversarial optimisation. More specifically. it highlights the need for more comprehensive benchmarks and careful selections of solution concepts when using any black-box adversarial optimisation algorithms. Moreover, no black-box optimisation algorithm for learning the Nash equilibrium in two-player zero-sum games Meanwhile, no algorithm can solve any bimatrix game with unique NE faster than the linear query complexity in terms of the size of input payoff matrices.
exceed the logarithmic complexity relative to search space size.
Although our work makes a first step towards the new NFL and BBC results on black-box adversarial optimisation, we want to point out some limitations of our current work and list them as our future work. Firstly, our theoretical results build on discrete exponential large search spaces rather than countably infinite (e.g. N) uncountable infinite (e.g. IR) sets. To generalise results to infinite sets, we might require further assumptions on our search spaces. Secondly, our NFL focuses on two-player zero-sum games with unique NE.
Future direction of our work includes extending Theorem 3.1 to other solution concepts like mixed strategy Nash Equilibrium or exploring different possible solution concepts which may exhibit free lunch or not. Additionally,
interesting to generalise NFL and BBC analysis to zero-sum games with multiple NEs and more general search spaces. Finally, it is interesting to analyse other black-box models, such as unbiased black-box complexity models, to characterise the difficulty of adversarial problems that different classes of search heuristics can solve.
10

---

Acknowledgements
We would like thank Dr Alistair Benford and Dr Mario Alejandro Hevia Fajardo for the fruitful discussion and comments on an earlier draft of this paper. This work was supported by a Turing AI Fellowship (EPSRC grant ref EP/V025522/)..
References
[1] Haris Aziz, Felix Brandt, Edith Elkind, and Piotr Skowron. Computational social choice: The first ten years and beyond. Computing and Software Science: State of the Art and Perspectives, pages 48-65 2019.
[2] Yakov Babichenko. Informational Bounds on Equilibria (a survey). ACM SIGecom Exchanges, 17(2):25-45, 2020.
[3] Alistair Benford and Per Kristian Lehre. Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games. In GECCO'24: Genetic and Evolationary Computation Conference. Association for Computing Machinery (ACM), 2024.
[4] Felix Brandt, Vincent Conitzer, and Ulle Endriss. Computational social choice. Multiagent systems, 2:213-288 2012.
[5] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jéröme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
[6] Xi Chen and Xiaotie Deng. Settling the complexity of two-player Nash equilibrium. In FOCS, volume 6, pages 261-272, 2006.
[7] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing Nash equilibrium. Communications of the ACM, 52(2):89-97, 2009.
[8] Benjamin Doerr, Timo Kötzing, Johannes Lengler, and Carola Winzen. Black-box complexities of combinatorial problems. Theoretical Computer Science, 471:84-106, 2013.
[9] Benjamin Doerr, Carola DoerT, and Franziska Ebel. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 567:87-104, 2015.
[10] Carola Doem. Complexity Theory for Discrete Black-Box Optimization Heuristies. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pages 133-212, 2020.
[11] Stefan Droste, Thomas Jansen, and Ingo Wegener. Optimization with randomized search heuristics -te (A) NFL theorem, realistic scenarios, and difficult functions. Theoretical Computer Science, 281(1)1111-144 2002.
[12] Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276((-2):51188 April 2002.
[13] Stefan Droste, Thomas Jansen, and Ingo Wegener. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory of computing systems, 39(4):225-544, 2006.
[14] Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and David Sculley, Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1487-1495, 2017.
[15] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Nets. Advances in Neural Information Processing systems, 27, 2014.
[16] Umberto Grandi, Davide Grossi, and Paolo Turrini. Equilibrium refinement through negotiation in binary voting. In Proceedings of the 24th International Conference on Artificial Intelligence, IJCAI 15, page 540-546. AAAI Press, 2015.

---

[17] Hedi Hadiji, Sarah Sachs, Tim van Erven, and Wouter M Koolen. Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL. httpp:://openrevie..nettt www.oordddnnnnneeeeeee
[18] Paul Harrenstein, Wiebe van der Hoek, John-Jules Meyer, and Cees Witteveen. Boolean games. In Proceedings of the 8th Conference on Theoretical Aspects of Rationality and Knowledge, TARK '01, page 287-298, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
[19] Erik Hemberg, Jamal Toutouh, Abdullah Al-Dujaili, Tom Schmiedlechner, and Una-May O' O'Reilly. Spatial coevolution for generative adversarial network training. ACM Transactions on Evolutionary Learning and Optimization, 122:1-28, 2021.
[20] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs Trained by Two Time-scale Update Rule Converge to a Local Nash Equilibrium. Advances in Neural Information Processing Systems, 30, 2017.
[21] Mario Alejandro Hevia Fajardo and Per Kristian Lehre. How fitness aggregation methods affect the performance of competitive coeas on bilinear problems. In Proceedings of the Genetic and Evolutionary Computation Conference. GECCO '23, page 1593-1601, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 3798400701199
[22] Mario Alejandro Hevia Fajardo, Per Kristian Lehre, and Shishen Lin. Runtime analysis of co-evolutionary algorithm: Overcoming negative drift in iaximinn-ptiinisaiion In Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA '23, page 73 -3, New York, NY, USA, 2023. Association for Computing Machinery.
[23] Y.C. Ho and D.L., Pepyne. Simple Explanation of the No-Free-Lunch Theorem and Its Im- plications. Journal of Optimization Theory and Applications, 115(3):549-570, December 2002.
[24] Junling Hu, Michael P Wellman, et al. Multiagent reinforcement learning: theoretical framework and an algorithm. In ICML, volume 98, pages 242-250, 1998.
[25] Fivos Kalogiannis and Ioannis Panageas. Zero-sum Polymatrix Markov Games: Equilibrium Collapse and Efficient Computation of Nash Equilibria. In Thirth-seventh Conference on Neural Information Processing Systems, 2023. URL htttpp:///ppereviev..o wtt.eeiiwwweeeeettmiiiiieee.
NGi NCiq8qCQNK
[26] Per Kristian Lehre. Runtime Analysis of Competitive co-Evolutionary Algorithms for Max- imin Optimisation of a Bilinear Function. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '22, page
2022.
[27] Arnab Maiti, Ross Boczar, Kevin Jamieson, and Lillian J Ratliff. Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Wwo-Player Zero-Sum Matrix Game arXiv preprint arXiv:2310. 16236, 2023.
[28] Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R. Jennings, Convergence to equilirria in plurality voting. In Proceedings of the Twenty-Fore Fourth AAAI Conference on Artificial Intelligence, AAAI'10, page 223-828. AAAI Press, 2010.
[29] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge university press, 1995.
[30] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vazirani Vijay V. Algorithmic Game Theory. Cambridge University Press, 2007.
[31] Ryan D'Donell. Some topics in analysis of Boolean functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing (STOC), pages 569-578, 2008
[32] May O' O'Reilly, Per Kristian Lehre, Mario Hevia Fajardo, Jamal Toutouh, and Erik Hemberg. Analysis of pairwise dominance coevolutionary algorithm and defendit. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '23, page 1027-1035, New York, NY, USA, 2023, Association for Computing Machinery.
12

---

[33] Martin Osborne and Ariel Rubinstein. A course in game theory. MIT press, 1994.
[34]
Ioannis Panageas, Nikolas Patris, Stratis Skoulakis, and Volkan Cevher. Exponential Lower Bounds for Fictitious Play Potential Games. In Thirty-seventh Conference on Neural Informa- lion Processing Systems, 2023,
[35] Elena Popovici, Anthony Bucci, R. Paul Wiegand, and Edwin D. De Jong. Coevolutionary Principles. In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, pages 987-1033. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
[36] Elad Sarafian, Mor Sinay, Yoram Louzoun, Noa Agmon, and Sarit Kraus. Explicit gradient learning for black-box optimization. In ICML, pages 8480-8490, 2020.
[37] Cullen Schaffer. A Conservation Law for Generalization Performance. In Proceedings of the Eleventh International Conference on International Conference on Machine Learning, ICMI.'9, '94, page 259-265,, San Francisco, CA, USA, 1994.
[38] C. Schumacher, M. D. Vose, and L. D. Whitley. The No Free Lunch and Problem Description Length. In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO'01, page 565-570, San Francisco, CA, USA. 2001. Morgan Kaufmann Publishers Inc.
[39] Travis C. Service and Daniel R. Tauritz. A No-Freee-uncch Framework for Coevolution. In Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, GECCO '08, page 371-378, New York, NY, USA, 2008. Association for Computing Machinery.
[40] Lloyd Shapley, Samuel Karlin, and HF Bohnenblust. Solutions of discrete, two-person games. Contributions to the Theory of Games, 1950.
[41] Han Shu, Yunhe Wang, Xu Jia, Kai Han, Hanting Chen, Chunjing Xu, Qi Tian, and Chang Xu. Co-evolutionary compression for unpaired image translation, In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 3235-3244, 2019.
[42] Jamal Toutouh, Erik Hemberg, and Una-May O'Reilly. Spatial evolutionary generative adver- sarial networks. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 19, page 472-480, 4800 New York, NY, USA, 2019. Association for Computing Machinery.
[43] Carola Winzen. Toward complexity theory for randomized search heuristics black-box models. Adviser: Mehlhorn, Kurt. PhD thesis. Germany, Germany: Max-Planch Jaa-Planck-Instituu ur Informatik, 2011.
[44] David Wolpert.
The Supervised Learning No-Free-Lunch Theorems. Soft computing and industry: Recent applications, pages 25-42, 2002.
[45] David H Wolpert and William G Macready. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67-82, 1997.
[46] David H Wolpert and William G Macready, Coevolutionary Free Lunches. JEEE Transactions on Evolutionary Computation, 96)721--735 December 2005.
[47] Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222-227, October 1977.
13

---

Appendix / Supplementaryy material
Contents
1 Introduction
Black-Box Optimisation and the No Free Lunch Theorem
Challenges and Technical Overview of the NFL and BBC Results
Contribution
2
Prelininaries
2.1
Notation
2.2 Solution Concepts
3
No Free Lunch Theorem for Computing Nash Equilibrium in Adversarial Optimisation
Black- Box Complexity of Black-Box Adversarial Optimisation
4.1
The Unrestricted Black-Box Model and the Black-Box Complexity
6
4.2
A General Lower Bound for Black Box Adversarial Optimisation
4.3
A General Lower Bound for Two-player Zero-Sum Bimatrix Games
4.4
Applications on Two-Player Zero-Sum Games
4.4.1
Introduction to Binary Voting Games
4.4.2
Black Box Complexity of Learning Nash Equilibrium in Binary Voting Games
4.4.3
Summary
5
Further Related Work
5.1
Co-evolutionary Search Heuristics
5.2
Query Complexity of Learning in Games
10
6
Conclusion and Discussion
10
Two Other Solution Concepts
15
Technical Lemmas for Games with Unique Nash Equilibrium
15
Analytic Tools from Probability Theory and Analysis of Randomised Algorithms
16
C.1 Yao's s Principle
16
Markov's inequality and Chernoff's 's bound
16
D
Omitted Proofs
16
Further Explanations for Sub-Problem Class
21
Further Explanations for the role of Corollary and Lemmal 1 in Theorem 3.1
22
Further Explanations for bitwise exclusive or in Black-Box Complexity Analysis
22
14

---

NeurIPS Paper Checklist
23
A Two Other Solution Concepts
Suppose of candidate solutions, X. and a set test cases, V Given an interaction function or payoff function, x y - O, where O is an ordered set which determines the outcome of candidate solution X' on test ) the solution concept is defined by: S = x E X Vo E X, Vy E V, g0 y) 2 g y)}.
Definition 9 (Maximisation Over All Test Cases 39
Next, we define the Maximin solutions are those solution configurations which maximise the minimum outcome over all test cases.
Definition 10 (Maximin (46]. Suppose a set of candidate solutions, X, and a of test cases, V Given interaction function payoff function, g : X' x y > O, where O is an ordered set which determines the outcome candidate solution X' on test V. the solution concept defined by:
S {x"
X Va X, min g(x", . . 2 min (2, vEy
vEy
Notice that in Definition 9 this solution concept considers the candidate solution r with respect to all test cases Definition 10 considers the candidate solution with respect to the worst-case scenario. y is compact, then these two solution concepts are essentially the same. Compared with Nash Equilibrium in Definition [ these two solution concepts only focus on finding the best candidate solution and the algorithm not required also to produce an opposing "optimal" solution y".
_
B Technical Lemmas for Games with Unique Nash Equilibrium
We adopt the notation 27
Definition 11. Given two-player zero-sum game payoff matrix P E Raxx, Let A, denote the n-dimensional probability simplex (i.e. for E An, E Ps 1 and p: 2 0). A pair (p". ."""") ) is (mixed strategy) Nash Equilibrium of input matrix P E Ruxn if and only the following holds for all (p, q) E An x An:
Pq)) (0" Pq") S Pq).
In this paper, we are only interested in Pure Strategy Nash Equilibrium.
Definition 12. For any payoff matrix P Raxn let V maXpeл, minge4, (p, Pq)- In particular, we say an entry (i* (i*,j") e [n] x [n] is unique pure strategy Nash Equilibrium (e.),ey)) An A, is unique Nash Equilibrium of P where e are the unit probability vector.
We refer to the following lemma from 40
Lemma 3 (Lemma 1 in (27). Consider matrix A E Raxa with unique Nash equilibrium (p",g").
The following conditions hold:
The support sizes of p" and g are equal (i.e., [supp("*) (supp(y"))
2. V (e,,Aq' Ag*) for all supp(r"), ), and Vī > (es, Aq*) for all i & supp(p*).
3. V (p',Ae,) for all j E supp(g"), and VA < (p": Acy) for all j & supp(g").
Lemma alloww us derive the following result, which is proved in Appendix B. in (27].
Lemma (Lemma 2 in (27)) Consider matrix P E Raxx with unique Nash equilibrium (p* g*).
Consider submatrix M of P with row index set Xx and column index set Ty. If SUPP(p") C Tx
and SUPP(q*) C Ty, then (ý, ④) is the unique Nash equilibrium of M where (Ø); = (p"); for all i Ix and (g), (g"), for all j e Iy. Moreover, Vy Ví.
15

---

C Analytic Tools from Probability Theory and Analysis of Randomised Algorithms
C.1 Yao's Principle
In this section, we provide the mathematical tool that use in the rest of the analysis. Yao's Principle 47 can be used to give lower bounds of a class of randomised algorithms.
Theorem C.1 (Yao's Principle [47)). Let II be problem with a finite set I of imput instances (of fixed size) permitting finite set A of deterministic algorithms. Let p be probability distribution over I and q be a probability distribution over A. Then,
min ELp A)) S max ((T(L, AEA
where Ip denotes random input chosen from I according to p. Ag random algorithm chosen from A according to and T(I, A) denote the runtime of algorithm A on input
C.2 Markov's inequality and Chernoff's bound
Theorem C.2 (Markov's inequality). Given a non-negative random variable X and a > 0.
(r a) < B(X)
Theorem C.3 (Chernoff's bound). Given X = Ei= X; where X; Ber(ps) where Ber(p:) is Bernoulli random variable with probability pt and all X; are independent. Let J == E(X)
E. Pt. Then, for 10,1).
Pr μ1 2 5p) 2e 135
D Omitted Proofs
Corollary 2. Let | = | and F x RJ be any set of two-player zero-sum games with unique NE. Assume furthermore that F is c.u.p.. Then, for any game g E F, let (x","") E X x y denote the unique Nash Equilibrium of g. For any permutations over X, denoted by E 6(X),
6()), (o r) gg F exhibits the same unique Nash Equilibrium (x*, y²)) Moreover, if for any To # x and yo # y², the restriction of on (X' {x=o) x () {Bo3), denoted exhibits the same unique Nash Equilibrium (x*, "²))
by g (1
Proof of Lemmal 7 We employ the result in 27 (See Lemma 4 For any permutations on N, denoted by (()), G()), (a @ r) og E F is defined as for any E X,y EV,
(a & g v) = (c(x),
We consider the payoff matrix defined by P p= (pt.) where Pi.j g(z;, Mj) with x; X, yj V. We denote row index set by Ix S N and column index set by Ty S N. Notice that [x| = X = ||]| = | We denote the row index by E Ix and the column index by J E Ty. P R [x] is the payoff matrix of two-player zero-sum game g with unique Nash Equilibrium (x", v²). Let us denote the row index x² in the payoff matrix P by i. and the column index of y by j. in the payoff matrix P. So (ei+, e E An x A, is the unique Nash Equilibrium in the form of probability vector.
Now, given any permutation row index set I'x S N and column index set 1/,- S N. Since a only shuffles around the row indices in Ix. I'2 ~ Ix with the isomorphism a. Similarly, we have I3, ~ Ly with the isomorphism т. Now, we can see that = SUPP(e<-) ) E I'2- and j SuPP(e,-) T5, so (f. () E A, A, the unique Nash Equilibrium of P' (in the form of probability vector) where (p): = (ee-), for all i I'x and ( = (e for all j E 15. In other words, (p, q) (ex-, ). So by using Lemma 4 we can conclude that (x* ,,"" E X y is the unique Nash Equilibrium of (o @ o...
we consider submatrix Pr such that p = (Pa(t).T() with a new
For the second claim, we construct a submatrix Q such that Q = (g.,)) where Ga.j = g(,, Uj) with I, X') {zu). My E (vo). We denote the row index set (x)( (zo) and the column index set Ly) (vo) Since 2o # 2, and yo # ye. it SUpP(e.-) E Lx and j SUPP(e,-) Ly by using
16

---

Lemma agaain, we can conclude that (x","" is the unique Nash Equilibrium of g (2)((0)))x(0(00)) We complete the proof.
Lemma 1. If F is c.u.p. then J ((21, (1), b2)) is also c.u.p..
Proof of Lemmal 7 For any o' E 6(X) (z1 J E G()" ( and any o' E F ((11, ((11,,1), (b,, b2)), we want to show (o'T'g'' E ((x1, (1),,,,)), m, (b,, b2]). We consider the extensions of each permutation. We define a X + X by its restriction on X' {21) as
d dx = o' and (x1) = 21-
We define T y + + its restriction on 3/ {4i} is
<lx(()) = 7' and r (1)) yn-
Now, let g be the extension of g' which satisfies (1), (2) and (3) of Definition 3 (such extension g exists since we take g' E F ((21. 31). (b1, b2)) and follows from the definitonn of sub-prout rub-problem class). As g F, so (ar)g F. Thus, construct (αr)g
extension of (o'r')g' and
(ar)g satisfies (1), (2) and (3) of Definition 3 So (o'r')g E
(b1,b2)) b2)).
Lemma 2. For all (1), (22, v2) E X' x y and b1 y - R. b2 X + R, we have the isomorphism
F F((11,11) (b1, b2)) F ((12, 92), (b1, b2))
Proof of Lemmna 2 To prove the isomorphism, need to find a bijection between these two sets. We consider the tollowing map between sets with defined by:
$ D:F((un) ((x1,,1), (b), b2)) + F ((12, 12), (bi, b2)) where ((g') = ht' such that
for (x. v) (X' (21, x ()) (2)1)
N/(z, v) olg') g (z.8).
For E {12). (((11,)) =(d)),)))('((002)1
g ('(x2,)) y).
For x E y {12), (x, = (z)') U2) = g (zx U2) Let h be the extension of h defined by h(12, y) by (y). M(x y2) = (x() For all (x, E (X) (x2)) x (0) {y2)).
h(2,8) 3) h' (x.
Now, we notice that h (T g where To: Ty are two transpositions in 6(X), 6()) defined by
(x1) 22 n. (x2) .1
Ty (31) = 122 F. (,222) = y1
and for all x' E X {2 22 and for all s/ E y {v1132).
Tx = x m (1') =
Since g E F, so h (ga E F. So ht' has the extension h satisfies (1), (2) in Definition 3 Also, h' = Q(g") ( is uniquely determined by g' and the argument would also hold when swapping h', with the map ø So we prove there exists an isomorphism between these two sub- sub-problem classes.
Theorem 3.1. Given F as subset of all the payoff functions g X y O with unique Nash Equilibrium where C IR and |X| = [V]. Let be an arbitrary (randomised or deterministic) Mlack-box adversarial optimisation algorithm for any g F where F is closed under permutations. Let r( (H, F) be the average (under the uniform distribution on F) of the expected query complexity of H on g E F (i.e. E(TLo (H, 9))). Then r(H, F) r(H', F) for all algorithms H, H'.
'Here we define isomorphism following 111 rather than defining it as usual group ring isomorphism since do not require any group or ring structure of J in the proof.
17

---

Proof of Theorem 3.7 Recall that the query complexity of H on g is (Lu(H.g):=innt) > 0 I :=
x² or J/: = yy where (z+,3) is the search point by Algorithm on payoff function g and (x" yy"))") is the unique Nash Equilibrium in a two-player zero-sum game defined by X x ) + O. We
denote the set of all functions from set X set O by H(X, O) and the set of all well-defined functions from a set Y' to a set O by H()).).
Let F be a class of games with all the payoff functions g X' y - 0 with a unique NE, and assume that F is closed under permutation. For all (To, y0) E X' x 3 define
_ {b) HO),0) there cxists 9 E F s.t. b1 (v) g y) for all y E 3); B {b2 E H O) there exists E F s.t. b2(x) = g(r, vo) for all x E X.
Let (u, v) E R' x y be the first query point that Algorithm makes, we consider b E _! and b2 B!?)
We first prove the claim holds for deterministic heuristics by induction. This is done by induction on the size of search space N |x Suppose for any two deterministic algorithms A, B on F.
If N 1, then means that X' x y only consists of one unique NE and consists of one payoff function g. So for any two deterministic algorithms A, B, r(A,)) = r(B,F) 1.
Next, assume N and r(A, 9) r(B, 9) where is any of payoff functions with unique NE and search space in payoff functions of size N - 1 and G is closed under permutation. Moreover, we assume FF now consists of payoff functions with unique NE and search space in payoff functions of size N. We expand out the average of F).
r(AF)) =
EPr(g
Pr(y is selected from F) -)(A
9EF
we are lucky, then the first point (u, v) EX x Y we query is the optimum (opt.) and (x*, yz" is the NE of the selected g.
= 1. Pr ((u, is the opt. s.t. u = x² or 5²)
+ Pr ((u, v) is not the opt. s.t. u = x² or U = y
x (1 + [A,F F (u, v), (b), b2))))
Notice that after we query (u, v). we can reduce the whole problem class F to F(uu, (),,)), (bi, b2)) with case N where b,, b2 are defined above.
Lemma shows that if F is closed under permutation, then F((u, v), (b), b2)) is closed under permutation. Corollary 1 shows that if we restrict g E F((u, v), (bi, b2)), then all the restriction of g on (X {u)) x (J/) {u}). denoted by g1(2), (x)x) (2)()) exhibits the same unique Nash Equilibrium (e", as g. So F((u,v) v), (b1, 62)) is set of payoff functions with unique NE (x", (x","") and the search space of size N and closed under permutation for all (u, v) in which (u, v) is not the opt. s.t. u x or y²
With the help of Corollary and Lemma I we apply the inductive hypothesis to this sub- oroblero class F(uu, v), (b1, bz) Also note that we consider the uniform distribution on problem class F and thus for any (u',
(u, v), we have
Pr (u,, v) is the opt. s.t. u = x" or v² = Pr ((u', the opt. s.t. u = or or==""" y
Using the inductive hypothesis on the case N with Lemma gives since two sub-problem classes are essentially isomorphic and thus have the same average query complexity from the inductive hypothesis step.
(r,, v²), b2))).
Thus, we can conclude that r r(A, F) = r(B for any deterministic algorithms A, B.
We defer further explanations of the role of Corollary and Lemma | to the supplementary material Section
D.
18

---

Now, we generalise the result to randomised algorithms. Let m denote the number of different deterministic search heuristics. We consider a randomised search strategy to be a probability distri- bution p- (P1, well-known (see detail in (2]] that the expected cost of a randomised search heuristic the weighted average of the cost of the deterministic search heuristics. Since all deterministic search heuristics have the same cost, this should also hold for all randomised search strategies.
Pm) and choose the i-th deterministic search strategy with probability p;. It is
Theorem 4.1. Let X and y be any finite sets. Assume that B C R with k: == |B] 2 2. Consider any class of two-player zero-sum games 9 {g: X x x - B) such that for all (x. y) E X x Y, there exists a game gz.y E 9 which has (x. y) as unique, pure Nash Equilibrium. Then, the class G has black box complexity least [log, X x y/1 1.
The proof which uses Yao's minimax principle is analogous to the proof of Theorem 2 in 13 We need to construct a suitable probability distribution p over the set of games. By assumption, for each (ar, y) E X' Y/ we can associate game Jz.y which has (x, y) as the unique pure NE. We let p be the uniform distribution over the set of the games {0e.s (x, V) E X' x y) S g.
Proof of Theorem
4.7
We now consider the runtime of any deterministic black-box algorithm A E Adet with respect to a random game Ie-,yr which is sampled according to distribution p. The algorithm is a decision tree, where each node is a pair (zt, y) E X' Y corresponding to a query made by algorithm A, and each edge corresponds to one of at most k possible outcomes ((,, y) of this query. The runtime of algorithm A on the random game 9x* .v" corresponds to the depth of (a* yy" in this decision tree. The expected depth is therefore lower bounded by [logæ (1X' x VD1
Hence, we have for all deterministic algorithms A E Adet.
(1d x 21) - 1. E(T A)) 2 logx
This implies that
min E(T 2 log x D1) -1
AEAsu
By Yao's Principle, for any distribution q over the set of deterministic algorithms Adet.
max E(T(L,AALA)) z min
E(T(Ip: 4)) AEAsa
JEz
ス log (IX' x D)) 1.
The proof now follows by noting that any randomised algorithm can be described as sampling a deterministic algorithm according some distribution g. and applying this algorithm.
Theorem 4.2. Let A be the set of all randomised algorithmss defined by Algorithm Aand T(A, P
denote the query complexity of A with respect to the input payoff matrix P for a two-player zero-sum game. Then, there exists an input matrix P E gaxx with unique pure Nash equilibrium (x".y") such that ((T P)) 2 (n + 1)/2. Thus, the black-box complexity with respect to A of the problem class consisting of all bimatrix games with a unique Nash Equilibrium is at least (n + 1)/2.
Proof Theorem 4.2 Given payoff matrix P, recall that for any A E A.
Tis(A, P): inf > 0 2, x" or yt y }: T(A, P): = inf(C, > 0 x, x" and yr = y }
M: = (P E R with a unique PSNE}.
Clearly, T(A, P) 2 [A, We denote M as the set of input instances. Now, we estimate the lower bound by using Yao's minimax principle (we denote the query complexity of specified algorithm namely ALG searching the PSNE of P by T(ALG, P) and the set of all deterministic black-box adversarial optimisation algorithms by Adet): for any randomised algorithm A E A,
max ((T(A, > min PEM
E (T(ALG, P))
ALGEAAm P~
'Note that T(A,P) = T(A, g) where g(2,8) = ey Pe, with ex, ey denote the elementary probability distribution over probability simplex [(0.13"
19

---

Using the definition of (ALG, P) and (ALGA P) gives
2 min ALGE PM))i((
E (TB((AL,,))
Using Theorem 3.1] we know the expected performance of all algorithms on any all problem instance in M is the same with respect to the unique Nash Equilibrium solution concept. So, we define new algorithm AL." such that it a deterministic algorithm starting from = = 1, and makes one query in each iteration. It continues to query Pi,1, P2.,, ... Pa... (i.e. query the entries in the diagonal of the payoff matrix P). ALG" continues the processes until reaches either the column or the row of the position of the unique Nash Equilibrium. So, we derive
R P~)
(Tin(AL.", P))
Note that we consider the uniform distribution on M. It means that the probability that (x", yy) lies in the j-th column of payoff matrix P is 1/n for all j E [n]. Then, the total expected query complexity is 2 1 n+1 So, we derive
2
n+1
2
This completes the proof.
of Theorem 4.3. The black-box complexity with respect to Algorithm of the binary voting games with problem size E N and a unique Nash Equilibrium is eQ(n)
Given an arbitrary binary voting game with problem size n defined by a payoff function {0,1) x 10, - IR, we consider the corresponding payoff matrix P. For each party,
Proof of Theorem 4.3
there are 2n possible strategies encoded by binary bitstring of length n. So P E R²"x2" Using Theorem 4.2 with arbitrary algorithms in the class defined by Algorithm and the payoff matrix P gives us the black-box complexity is at least 2
2(x)
Theorem 4.4. Given the game class
DIAGONAL: == {DIAGONAL(..)) (u, v) E [0, x 13,
the black-box complexity with respect to Algorithm 7 of DIAGONAL, is ((n).
Proof of Theorem 4.4 We consider an algorithm A E A, which operates in two phases. In each itera- tion of Phase 1. the algorithm samples x and uniformly at random, then flips one bit uniformly at ran- dom in æ to obtain x'. It then compares the values of DIAGONALy, (I, y) and DIAGONAL,, (2', y). Phase ends when DIAGONAL knows that Iu ① x| 1
y) o DIAGONALU, ,)). Once Phase I ends, the algorithm [M ④ 1/1-
In Phase 2, Algorithm
sample a bitstring y' by flipping a single bit in If DIAGONAL (x.,0) -1, we set y = y', otherwise we repeatedly sampling new y'. Once we get payoff -1, accept the new search point and then sample x' by flipping a single bit in & until repeat the process until we get payoft This procedure continues until the termination criterion is met.
We now consider how long it takes for Phase to finish (i.e. the search point arrives at the diagonal). Since
using uniformly random initialisation, Z1 := lu O æ/1 and Zg := ly + z/1 subject to two independent binomial random variables Bin (z, 1/2). We first estimate Pr(Zi = Zz). Notice that let Y := Zg and Y is also subject to Bin f2, 1 1/2) Bin(n, 1/2). So the event
{Z, = ] is equivalent to { = Y) = {Zz + Zg = n). Thus, we can derive the following
estimate by using Stirling's 's approximation (i.e. n! ~ v 22m (2T "),
12n
1
1 V
Pr(Z 72) =
2 2n
22n 2
2n
VTn
So the expected runtime for finishing Phase I is O(vn)
Now, we consider how long takes for Phase
reach the optimum. Notice that for each bit, we need query of the payoff function to determine whether it is the correct bit to flip. We need to flip the correct bits for both x and y, Since the maximum Hamming distance to the optimum of DIAGONAL is bounded by 2n, then the overall runtime is bounded above by 2n O(n). Adding the
expected runtime for both Phases gives O(n) + O(vr) = O(n). Together with Theorem 4.1 we can conclude that the black-box complexity of DIAGONAL, is @(n).
20

---

Theorem 4.5. Given the game class.
PLATEAU, {PLATEAU(H.)) (w.e) (u, [0, {0,1)"),
the black-box complexity with respect to the class of algorithms defined by Algorithm 7 of PLATEAU, is e e
Proof of Theorem 4.5
Recall the definition of PLATEAU,, u,e for arbitrary u, c. We call the set {(r y)
I|u @ 1
x-independent, and we call any query this set æ-independent. Note that for any z-independent query has payoff PLATEAU,,, (Z. y) = f(v @ y). i.e., it is independent of x. Furthermore, note that the Nash Equilibrium is not r-independent.
We will apply Yao's 's Principle with respect to the distribution p over instances where u is sampled uniformly at random among all bitstrings of length n. and 0" We consider the average runtime of deterministic algorithms with respect to distribution p. Such algorithms can be modelled binary decision trees: in each node, the algorithm makes query (Ir, y), and for each outgoing edge, the algorithm obtains one of two possible payoff values PLATEAU (3. y) E {-1,1). We call the rr-nndependent path in the decision tree the longest path (x1, 31),............. (Zi, Ue) such that (æ1, y1) is the root node and all nodes (Iz 31) for i E [t] are z-independent. We let t denote the length of the r-independent path. Since the outcome of an x-independent query only depends on @ y which is deterministic, the x-indeppenent path of a decision tree is unique. Furthermore, the length of the r-independent path a lower bound on the runtime of the algorithm since the Nash Equilibrium is not z-independent.
We now lower bound the length of the z-independent path. Let (æ;, y:) be any fixed query in the decision tree, and F; the event that (Ii, is sz-independent. We sample u by picking each bit independently and uniformly random in (0, 1}. This implies that the number of bits for each bit is subject to a Bernoulli random variable (12(1 We therefore have ju @ 24/1 is binomially distributed (n, 1/2). Applying Chernoff's bound, we get
Pr [F)) Pr (Ilu x:li
2
11
S
2e
-2n/6
Let Ej be the complement of the failure events, i.e., En U Fi. Therefore, by a union bound, the zr-independent path has length = 2e 2n/12 with probability
Pr(Ei) = 1 Pr (U F.) 2 t2e 12e - = =1 Q((n)
We then have by the law of total probability
min E(T(Ip, A)) 2 min Pr (Et) E(T(Lp, E1)
AEA
AEA
> - (((n) 12 22/12
2(m)
The proof now follows by Yao's minimax Principle. The expected worst-case runtime of any randomised algorithm is lower bounded by the average case runtime of deterministic algorithms.
max E(T(L,A,) min B(T A)) a((), TEz
AEA
E Further Explanations for Sub-Problem Class
We provide an example to illustrate the concept of the sub-problem class (see Definition B
Figure 2 is an example of a sub-problem class. When querying (Z1,y1), we also check the corre- sponding row and column to verify whether the unique Nash Equilibrium lies on this blue cross or not. If the answer is negative, then restrict to the sub-matrix by removing the blue entries in P.
21

---

P
y%
X1
x
Figure 2: Example of sub-problem class. Given a payoff matrix P. the blue entries mean that the actual values are already assigned to -( ) and g( 91). (x", ,o"""") ) is the Nash Equilibrium we search for. The sub-problent class here means that the problem consists of different payoff matrices with given blue entries.
F Further Explanations for the role of Corollary and Lemma in Theorem 3.1
1
In the main proof of Theorem 3.1 we rely on proof by induction: assume the theorem holds for search space of size N, we want to show it also holds for N +.. Corollary @orollar[[aand Lemmaaaree crucial since they ensure that for every payoff function g E F, there a corresponding function g' where are two permutations on X' respectively) and the NE is still unique in the game defined by g'. This means that the inductive hypothesis can be applied to g' due to the closure under permutation. In short, Corollary I and Lemma establish property of the problems or payoff functions under consideration that is preserved under permutations. This property helps ensure that the induction step can be applied successfully.
the NE (a* yy") is switched to (o(="),T()) (v")) (i.e.
G Further Explanations for bitwise exclusive or in Black-Box Complexity Analysis
We define @ as bitwise exclusive or. means that for any two binary bitstrings
21 ................................ In and u = U1 ... Un. @ == (x1 @ "1, Iy, @ un) where 1 @ 1 = 0, 1 e 0 = 1, + = 1, 1.1e + 1 0. We introduce bitwise exclusive here generate problem instances with the same structure. For example, DIAGONAL y) is only one possible problem instance in binary voting games and to find its optimum, we only need to design the algorithm querying (1", 17) to reach its optimum. And its black-box complexity is trivially (()). Using bitwise exclusive or @ (i.e. DIAGONAL(u x, 2 y) where (u, v) U is sampled uniformly at random), we can generate set of problem instances which have the same structure as DIAGONAL(2,, y) and the goal of black-box algorithms to find (2; y) such that (u @ x, v @ y) = (1"; 1"). (Note that if (u, v) = (0", 0*), then DIAGONAL @ ("" @ y) is reduced to the vanilla DIAGONAL y).) This bitwise exclusive generator can avoid the trivial black-box complexity mentioned above and reflect the true difficulty of the class DIAGONAL. We refer to 13 9 for more detail about black-box complexity theory.
22

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claims made in the abstract and introduction accurately reflect the paper's contributions and scope. The detailed contribution can be checked in Section 1.2 in the main paper. We also provide content list as the roadmap of this paper at the beginning of the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations of our results have been discussed in the conclusion (line 372-384). Moreover, the bounds for the black-box complexity of binary voting games derived in this paper mainly consider the asymptotic order, which is sufficient for benchmark dichotomy. There is room to improve these bounds with respect to the leading coefficients.
Guidelines:
The answer NA means that the paper has no limitation, while the answer No means that the paper has limitations, but those are not discussed the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken low lighting. Or speech-to-text system might not used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable. the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems, formulas, and proofs in the paper numbered and cross- referenced, and all assumptions are clearly stated or referenced in the statement of all theorems.
Due the page limit, we defer all the proofs in the supplementary material (see Section D). We also provide short proof sketch for our main result: Theorem 3.1
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: Our paper purely theory paper, and it does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
If) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
If) the contribution is new model (e.g.. large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)We recognize that reproducibility may be tricky in some cases, in which case authors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines hittps::/nips.cc//pppi
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
wewibbmmsssiooooo ssionnolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the is necessary to appreciate the results and make sense of them.
the paper a level of detail that
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
25

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric eгтоr bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn 't make it into the paper).
Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
This work strictly follows the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts the work performed?
Answer: [Yes]
Justification:
This paper studies NFL analysis and BBC analysis of black-box adversarial opti- misation algorithms. From a theoretical viewpoint, our work rigorously outlines the theoretical limitations of black-box adversarial optimisation algorithms for finding Nash Equilibrium and characterises the general difficulty of different class problems to be solved via the given black-bor box model. From practical viewpoint, in many black-box optimisation applications which solve maximin problems with complicated constraints, e.g. robust optimisation, neuroevolution, bimatrix games, two-player games etc. This work of theoretical nature, and there is no foreseeable negative ethical or societal implication.
careful benchmark selections
suggested for
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there a direct path any negative applications, the authors should point it out. For example, it is legitimate to point
26

---

out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode licenses for some datasets. Their licensing guide can help determine the license of a dataset.
com/datasets has curated
For existing datasets that are re-packaeed both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
27

---

Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
28


Reviews:
[{"review_id": "V8HJC3pvpt", "reviewer": "Reviewer_Xe7y", "summary": "The paper mainly focuses on the analysis of black-box adversarial optimization algorithms with an emphasis on Nash Equilibrium (NE) as the solution concept. It introduces the concept of No Free Lunch (NFL) Theorem for general black-box adversarial optimization, showcasing the equal average performance of all algorithms when NE is the solution concept. The paper also delves into the black-box complexity analysis and provides lower bounds for query complexity in finding NE. Overall, it contributes to the understanding of the limitations and performance evaluation of black-box adversarial optimization algorithms under the Nash Equilibrium solution concept.", "questions": "1. This paper is theoretically comprehensive. However, providing simple empirical verification on binary voting might increase the credibility of the theoretical founding. I am wondering if it is possible to conduct experiments to verify the proposed lower bound. \n2. I am curious about more difficult games than DIAGONAL and PLATEAU that can be solved by Algorithm 1. Can you provide other examples? \n3. Algorithm 1 is still a random search algorithm. Can it be generalized to some real-world games? Please discuss more on different classes of search heuristics rather than random search. How will the results of black-box complexity change?", "limitations": "No potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper provides rigorous analysis and theoretical foundation concerning black-box adversarial optimization algorithms, particularly focusing on the Nash Equilibrium as the solution concept. The paper provides a novel proof of the No Free Lunch Theorem in the context of adversarial optimization, shedding light on the equal performance of algorithms when NE is considered. Additionally, the introduction of black-box complexity analysis adds depth to understanding the query complexity in finding NE. Overall, the paper's strengths include its theoretical contributions, clarity in presentation, and insightful analysis of black-box adversarial optimization in the context of NE.", "weaknesses": "See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**RXe7yQ2 I am curious about more difficult games than DIAGONAL and PLATEAU that can\nbe solved by Algorithm 1. Can you provide other examples?**\n\nA: Before answering the question, we would like to clarify two confusions in the question:\n\n(1) As mentioned in the paper **(lines 223-230)**, Algorithm 1 represents a broad class of algorithms.\nTherefore, we cannot claim that all instances of Algorithm 1 solve Diagonal and Plateau.\n\n(2) While all instances of the Diagonal problem class can be solved by some instance of Algorithm 1\nin polynomial runtime, Plateau is already a challenging problem in terms of polynomial solvability. In\nparticular, we prove that all instances of Algorithm 1 need exponential time to solve Plateau, making\nit inefficient. Hence, we do not consider it significant to find more difficult games than Plateau.\n\n(3) The reason we chose these examples is to illustrate two kinds of problems within the general class of binary voting games with unique NE: the **polynomial-solvable** class (i.e., there exists an algorithm $A \\in \\mathcal{A}$ that can solve all problem instances of this class in polynomial runtime) and the **non-polynomial-solvable** class (i.e., there exists **no** algorithm $A \\in \\mathcal{A}$ that can solve all problem instances of this class in polynomial runtime).\t\n  As mentioned in **Section 4.4.3**, these examples and the general class of binary voting games with unique NE are sufficient to illustrate the use of black-box complexity in black-box adversarial optimisation. \n\n**RXe7yQ3 Algorithm 1 is still a random search algorithm. Can it be generalised to some real-\nworld games? Please discuss more on different classes of search heuristics rather than random\nsearch. How will the results of black-box complexity change?**\n\nA: Before answering the question, we would like to point out another confusion in the\nquestion:\n\nAlthough the algorithm(s) make random decisions, it does not make it a pure random\nsearch (sampling solutions uniformly at random).\nWe would like to clarify that Algorithm 1 is **not** a simple class of random search algorithms but defines a general class of algorithms.  As is well-known in the literature, clever use of\nrandomness can lead to simpler and more robust algorithms. \n\nWe extend our discussion from the original paper **(lines 223-233)** here. Algorithm 1 defines various\nblack-box adversarial algorithms, including coevolutionary heuristics [7 , 6, 1], bandit learning\nalgorithms [10 , 3], and other black-box query-only randomised algorithms like FINDPSNE (designed\nto learn the NE in bimatrix games by querying the payoff matrix) [9], by specifying different\nprobability distributions PI(t) in Line 3 of Algorithm 1. \n\nThe main aim of Section 4 is to provide a general performance measure for such a broad class of black-box models. \nFor other algorithms outside the class defined by Algorithm 1, if in the binary voting games they act like a decision tree\nalgorithm, we conjecture that the black-box complexity (BBC) will remain the same. If not, we may\nneed to examine different classes on a case-by-case basis.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0ypGyMWgFj", "reviewer": "Reviewer_Puqf", "summary": "Black-box optimization is a critical area in the field of optimization. The original No Free Lunch (NFL) theorem highlights the inherent limitations of traditional black-box optimization and learning algorithms, establishing a theoretical basis for these methods. The paper addresses a long-standing problem in NFL analysis for adversarial (maximin) optimization. The authors try to prove a new NFL theorem for general black-box adversarial optimization, specifically when Nash Equilibrium (NE) is used as the solution concept. This implies that when NE is the goal, the average performance of all black-box adversarial optimization algorithms is equivalent. Using Yao’s maximin principle and the new NFL theorem, the paper provides general lower bounds for the query complexity required to find Nash Equilibrium in adversarial optimization.\n\nThe authors prove the theoretical impossibility of a universally effective adversarial optimization algorithm and highlight the impact of solution concept selection. It introduces black-box complexity to assess the difficulty of learning the unique optimum and solving two-player zero-sum games, laying the foundation for future research on adversarial optimization.", "questions": "Please clarify the points in the Weaknesses section.", "limitations": "Yes, the limitations of the proposed method are discussed in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The paper demonstrates a high level of theoretical rigor in proving an NFL Theorem for general black-box adversarial optimization, specifically focusing on Nash Equilibrium as the solution concept. The proofs and technical details are sufficiently detailed.\n\nS2. The paper effectively formulates the problem statement by emphasizing the importance of solution concepts in adversarial optimization. The paper contributes by addressing adversarial optimization and providing a new perspective on the limitations of black-box algorithms in this context.", "weaknesses": "W1. The notations used in the paper are not clear in some places. For example, in line 92, v is introduced as a real number. Then for i in [1,n], what is v_i in line 93? In the double-line equation between line 149 and line 150, the notation is not clear. Terms like 'extension' and 'restriction' of a function should ideally be defined earlier in the paper. Here, it is only somewhat discussed in the appendix.\n\nW2. The paper seems to focus more on theoretical analysis and proofs, lacking empirical validation or practical demonstrations of the proposed concepts and findings. Incorporating experimental results could enhance the credibility and applicability of the research.\n\nW3. For the theoretical analysis discussed in the paper, there is only one practical application provided viz., two-player zero-sum games with a unique Nash Equilibrium (NE). The authors introduce certain complexity in this game by considering plateaus. However, the application is still a trivial one and a study on a broader range of adversarial optimization problems with different solution concepts would have been insightful.\n\nW4. The paper cannot rely on the appendix. The text should be self-contained. The appendix contains many crucial information needed for understanding and judging the paper. I didn't particularly like the current structure of the paper, where related work has ended up in the appendix.\n\nW5. In the checklist, the authors mention that from a practical viewpoint, more careful benchmark selections are suggested for use in many black-box optimization applications that solve maximin problems with complicated constraints. However, an elaborate discussion on the practical applicability is not discussed in the paper. Such a discussion would have been insightful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**PuqfW1. The notations used in the paper are not clear in some places.**\n\nA: We will improve the accessibility of this paper in the updated version.\n    There is a typo here, $v \\in \\mathbb{R}^n$ rather than  $v \\in \\mathbb{R}$ and $v_i$ is the $i$-th opponent of $v$.\n    We refer to $g$ as the extension of $g'$ in line 149 and 150 and it is defined in (1). \n    Note that restrictions and extension are two well-established mathematical terms.\n    We define them separately here and will include these formal definitions in the preliminaries later.\n\nDef (restriction):\n Let $f : X \\to Y$  be a function from a set $X$ to a set $Y$.\nIf $A$ is a subset of  $X$, then the **restriction** of $f$ to $A$ is the function:\n\\begin{align*}\nf|_A : A &\\to Y \\\\\\\\\nx &\\mapsto f(x).\n\\end{align*}\n\nDef (extension):\nLet $f : X \\to Y$ be a function and $A$ and $B$ be sets such that $X \\subseteq A$ and $Y \\subseteq B$. \nAn **extension** of $f$ to $A$ is a function $g : A \\to B$ such that $f(x) = g(x)$ for all  $x \\in X$.\n Alternatively, $g$ is an **extension** of $f$ to $A$ if $f$ is the restriction of $g$ to $X$.\n\n**PuqfW4. The paper cannot rely on the appendix. The text should be self-contained.**\n\nA:  We agree that the appendix is not the appropriate place for related work. In the revised\nversion of the paper, we will move the extra related work from the appendix to the main text where\nnecessary and compress the main text. However, it is not feasible to include all proof details in the\nmain body of any comprehensive theory paper. As is traditional for theoretical papers in AI/ML\nconferences, detailed proofs are deferred to the appendix (e.g., see [11, 5, 3, 4]). We will include\nproof sketches or explanations in the main text, as seen in line 183, to ensure the paper remains\nself-contained.\n\n**PuqfW5. In the checklist, the authors mention that from a practical viewpoint, ... \nHowever, an elaborate discussion on the practical applicability is not discussed in the paper.**\n\nA: As a theory paper, we focus on rigorous proof and analysis of general adversarial\noptimisation problems. For the discussion of careful benchmark selections in black-box adversarial\noptimisation, we have used binary voting games (two-player zero-sum games) as a practical\nillustration of BBC analysis. The detailed discussion of the practical applicability of black-box\ncomplexity analysis can also be checked in **Section 4.4.3**.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hSJYExFgda", "reviewer": "Reviewer_7LPo", "summary": "In this paper, the authors theoretically analyze the query complexity for general black-box Adversarial Optimisation under the \"closed under permutation\" assumption.  A no-free-lunch theorem is proved for all algorithms in achieving the same average performance of all possible problem instances (or problem instances c.u.p.) with a unique Nash Equilibrium in a two-player zero-sum game setting.  Moreover, the authors provide Lower Bounds for General Black-Box Adversarial Optimisation (with possible answers assumption ) and Two-player Zero-Sum Bimatrix Games, respectively.", "questions": "1.  What is the key technical challenge for the theoretical analysis of black-box adversarial optimization compared with white-box adversarial optimization?\n\n\n2. What is the key technique employed in this paper to solve the challenge compared with the standard  Nash Equilibrium analysis for two-player zero-sum games or adversarial optimization analysis?", "limitations": "N.A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.  The paper is well-written and well-organized. \n\n\n2.  The theoretical results are general to cover many interesting adversarial optimization cases.  The no-free-lunch theorem shows the difficulty of optimizing the whole family of problem instances in two-player zero-sum games.   The lower bound of query complexity for  General Black-Box Adversarial Optimisation (with possible answers assumption for each query) and Two-player Zero-Sum Bimatrix Games are also interesting.", "weaknesses": "1. The technical challenge of the analysis for black-box adversarial optimization over the standard adversarial optimization analysis is not clearly discussed.   What the key technique employed for the black-box cases compared with the standard  Nash Equilibrium analysis for two-player zero-sum games is not clear. \n\n\n2. The theoretical analysis is restricted to finite (discrete) problems instead of continuous problems.  This restriction may limit the possible application of the theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**7LPoW1+Q1.** \n- **The technical challenge of the analysis for black-box adversarial optimization\nvs the standard adversarial optimization analysis** \n- **The key technique employed for the black-box cases for two-player zero-sum games**\n- **Black-box adversarial optimisation vs white-box adversarial optimisation**\n\n\nA: The detailed discussion of key technical contributions,  challenges and technique can be found in\n**Sections 1.2 and 1.3**. \n\nThere are different definitions of white-box in the literature. To answer\nthe question, it is necessary to define the meaning of white-box adversarial optimisation. For\ncomparison, we need to define white-box adversarial optimisation. We have defined black-box\nadversarial optimisation in **lines 23-30** and **Algorithm 1**. Since the reviewer did not specify which\ninterpretation they had in mind precisely, we consider two possible interpretations:\n\n(1) **White-box adversarial optimisation with full access to the payoff function:** This means the\npayoff matrix in the two-player zero-sum game is given and known. In this case, finding the Nash\nEquilibrium (NE) can be formulated as a linear programming problem, which can be solved in\npolynomial time using algorithms such as the ellipsoid method or interior-point method [2, 9].\n\n(2)**White-box adversarial optimisation with gradient access:** The gradient is accessible if the\npayoff function is differentiable. A well-known method for solving the saddle-point problem is\ngradient descent ascent (GDA) and its variants, including stochastic/optimistic GDA, which have\nbeen extensively studied [8, 4].\n\nCompared with these two types of white-box adversarial optimisation, black-box adversarial optimi-\nsation considered in this paper only allows querying the payoff function in each iteration, and the\npayoff function is usually not explicitly known. The tools used in these two white-box cases are not\napplicable in our scenario. This is why we employ tools from game theory **(see lines 66-69)** and\nintroduce black-box complexity to analyse the black-box adversarial model **(see lines 70-74)**.\n\n\n**7LPoQ2. The key technique employed in this paper to solve the challenge compared\nwith the standard Nash Equilibrium analysis for two-player zero-sum games or adversarial\noptimization analysis**\n\nA: For the standard Nash Equilibrium analysis for two-player zero-sum games, the payoff\nfunction is explicitly known. As mentioned in our response, the tools used in such cases are not\napplicable here. We have also discussed other works, such as the computational complexity of\ncomputing NE in general-sum games being PPAD-complete and the complexity of fictitious play in\ntwo-player potential games with a unique NE, in **lines 568-583**.\n\nThe key technique employed in our paper involves using game-theoretic tools and Yao’s principle to\nanalyse black-box adversarial models. This approach is necessary because, unlike in standard NE\nanalysis, we only have access to the payoff function through queries, and the function is not explicitly\nknown and discrete (hence, no gradient is accessible).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NxLeNGP3Yu", "reviewer": "Reviewer_RwGp", "summary": "This paper considers the complexity of finding (Pure Strategy) Nash Equilibrium in black-box optimization for adversarial optimization.\n\nBy denoting the loss of a learned solution $x\\in X$ on a possible test case $y\\in Y$ as $g(x,y)$, the authors show that no algorithm is on average better than any other in finding a PSNE of $g\\in \\mathcal F$, given that $\\mathcal F$ is closed under permutation, via constructing an isomorphism result which roughly says that if the algorithm doesn't at the first time query the unique PSNE $(x^\\ast,y^\\ast)$, then every possible sub-problem is isomorphic to another. This NFL result distinguishes finding a NE from finding an \"always optimal\" or \"worst-case optimal\" solution.\n\nThe authors then derive the query complexity lower bounds for general black-box adversarial optimization and two-player zero-sum bimatrix games, and also their implications to some two-player zero-sum games.", "questions": "1. In the proof of Theorem 3.1, the authors mentioned \"$b_1$ and $b_2$ are defined in Definition 6\". Is this really correct? I don't feel Definition 6 infers the construction of $b_1$ and $b_2$.\n2. In Theorem 4.1, the condition that \"each query has at most k ≥ 2 possible answers\" seems pretty strong -- what if the noise on $g(x,y)$ is a continuous r.v.?\n3. Can you discuss more regarding the \"always optimal\" solution concept in Definition 2? Is it likely to exist for a general adversarial optimization problem? If not, why did the original authors consider it?", "limitations": "Included in sec. 5", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This NFL-style result distinguishes finding NE from finding an \"always optimal\" or \"worst-case optimal\" solution, which is important towards understanding the various solution concepts in adversarial optimization.\n2. Via the NFL-style result, various query complexity lower bounds are also derived for adversarial optimization and two-player games.", "weaknesses": "1. This paper assumes a unique PSNE in $g$, but it may not be this case in ML (e.g., $X$ corresponds to a set of over-parameterized NN and $y$ is some train/test loss).\n1. While the main text looks pretty technically rigorous, it is a little hard to read. For example, in a sub-problem definition, what does the $b_1,b_2$ usually mean and how are they constructed? The answer to this question doesn't seem to appear anywhere in the main text as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**RwGpW2. While the main text looks pretty technically rigorous, it is a little hard to read ...**\n\nA: We agree with the reviewer that the role of $b_1$ and $b_2$ was not fully explained.\n We will improve this in the final version. In particular, Definition 5 can be improved as follows:\n\nLet $O\\subseteq \\mathbb{R}$.\nLet $\\mathcal{F}$ be any subset of the set of payoff functions $g:\\mathcal{X} \\times \\mathcal{Y} \\rightarrow O$ with a unique Nash Equilibrium and such that $\\mathcal{F}$ is closed under permutation.    For any given $(x_1,y_1) \\in \\mathcal{X} \\times \\mathcal{Y} $, any function $b_1:\\mathcal{Y} \\rightarrow  O$, and any function $b_2:\\mathcal{X} \\rightarrow O$,\n    we define a sub-problem class $\\mathcal{F} \\left((x_1,y_1),(b_1,b_2) \\right)$ with respect to $\\mathcal{F}$ as follows:\n    $f \\in \\mathcal{F} \\left((x_1,y_1),(b_1,b_2) \\right)$ iff there exists a $g \\in \\mathcal{F}$ such that\n\n(1)  $g(x_1,y)=b_1(y)$ for all $y \\in \\mathcal{Y}$;\n\n(2) $g(x,y_1)=b_2(x)$ for all $x \\in \\mathcal{X}$;\n\n(3) $f$ is a restrction of $g$ on $\\left(\\mathcal{X} \\setminus \\\\{x_1\\\\} \\right) \\times \\left( \\mathcal{Y} \\setminus \\\\{y_1\\\\} \\right)$.\n\nThe formal definition of restriction/extension can be found in the response of PuqfQ1.\n\n In terms of the construction of $b_1, b_2$, we explain in detail as follows.\n  To get the intuition of what $b_1,b_2$ means in our analysis, we extend the discussion of **Section E** here.\n  As shown in **Figure 2, Section E, Appendix**, after querying $(x_1,y_1)$, both strategies of $x_1,y_1$ are known.\n  We define $b_1(y):=g(x_1,y)$ for all $y \\in \\mathcal{Y}$ and $b_2(x):=g(x,y_1)$ for all $x \\in \\mathcal{X}$.\n  Note that the definition of $b_1, b_2$ depends on $g \\in \\mathcal{F}$.\n  We consider a black-box model where the algorithm learns all the blue entries in payoff matrix $P$ (Figure 2) when querying the entry ($x_1,y_1)$ (i.e., row $x_1$ and column $y_1$). \n  If there is no Nash equilibrium among the blue entries, we exclude this row and column in the payoff matrix and restrict the problem to a smaller sub-problem.\n  Now, we define $b_1,b_2$ formally:\n\n\n  We denote the set of all functions from a set $\\mathcal{X}$ to a set $O$ by $\\mathcal{H}(\\mathcal{X},O)$ and the set of all well-defined functions from a set $\\mathcal{Y}$ to a set $O$ by $\\mathcal{H}(\\mathcal{Y},O)$.\n\n Given a subset $\\mathcal{F}$ of all the payoff functions $g: \\mathcal{X} \\times \\mathcal{Y} \\rightarrow O$ with a unique NE where $\\mathcal{F}$ is closed under permutation. For all $(x_0,y_0) \\in \\mathcal{X} \\times \\mathcal{Y}$,\n  define \n\n  \\begin{align*}\n        B_{x_0}^{(1)}:&=\n \\\\{b_1 \\in \\mathcal{H}(\\mathcal{Y},O) \\mid \\text{there exists $g \\in \\mathcal{F}$ s.t. } b_1(y)=g(x_0,y) \\text{ for all $y \\in \\mathcal{Y}$} \\\\}; \\\\\\\\\n         B_{y_0}^{(2)}:&=\n  \\\\{b_2 \\in \\mathcal{H}(\\mathcal{X},O) \\mid \\text{there exists $g \\in \\mathcal{F}$ s.t. } b_2(x)=g(x,y_0) \\text{ for all $x \\in \\mathcal{X}$}\\\\}.\n  \\end{align*}\n\n  Let $(x_1,y_1) \\in \\mathcal{X} \\times \\mathcal{Y}$ be the first query point that Algorithm 1 makes,\n  we consider $b_1 \\in B_{x_1}^{(1)}$ and $b_2 \\in B_{y_1}^{(2)}$.\n  Now, they should be well-defined in the proof of Theorem 3.1.\n\n We will include this explanation in the proof to improve the accessibility of our paper. \n\n**RwGpQ1. In the proof of Theorem 3.1, the authors mentioned, \"b1, b2 are defined in Definition\n6\". Is this really correct? I don’t feel Definition 6 infers the construction of b1 and b2.**\n\nA: Yes, you are right. There is a typo; it should be Definition 5 rather than 6. We will correct\nthis in the updated version. The construction part can be checked in the response to RwGpW2.\n\n**RwGpQ3. Can you discuss more regarding the \"always optimal\" solution concept in Definition\n2? Is it likely to exist for a general adversarial optimization problem? If not, why did the\noriginal authors consider it?**\n\nA: Yes, we agree with the reviewer that an \"always optimal\" solution can hardly exist for a\ngeneral adversarial optimisation problem. Even in their previous paper, Service and Tauritz [12]\nacknowledge this by stating:\n\n“in many real-world problems, there are no candidate solutions which perform best over all possible\ntest cases. That is, there is often a trade-off between performance on test cases.”\n\nWe believe they consider this “ideal solution concept\" to theoretically demonstrate the existence of a\n\"free lunch\" with respect to it. While their result and the result of Wolpert and Macready [14] can be\nconsidered worthwhile contributions to No Free Lunch (NFL) in adversarial optimisation, we argue\nthat it is necessary to consider other solution concepts.\n\nIn fact, we are not satisfied with these \"free lunch\" results since an \"always optimal\" solution rarely\nexists in real-world applications, and such a \"free lunch\" result might sometimes be misleading. It is\nimportant to recognise that every approach, including coevolutionary approaches or other black-box\nadversarial optimisation algorithms have limitations. This is one of the key messages of our paper.\n\nWe will extend our discussion in the updated version by including the response above.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their useful and detailed comments.

Due to the space limit, we only keep the reference list in the global response. All the responses will use the **same** reference list.

**Q1 Two-player zero-sum game with a unique NE or PSNE. PuqfW3; RwGpW1**

A: Our current theoretical analysis focuses on two-player zero-sum games with a unique Nash
Equilibrium (NE). We agree that exploring other solution concepts and games would be insightful.
However, we argue that our analysis solves a non-trivial open problem.
Choosing this class of games is reasonable for the following reasons:

(1) The No Free Lunch (NFL) theorem for any solution concept is still a long-standing open problem.
One of the main messages of this paper is that, despite prior work showing the existence of a “free
lunch” in adversarial optimisation (e.g., [13]; [12]), we prove a NFL theorem for the unique Nash
Equilibrium. This uncovers the fact that there is no “silver bullet” in adversarial optimisation for
all solution concepts. To our knowledge, this is the first work to answer this question negatively,
and the unique NE solution concept is sufficient to serve this aim.

(2) The technical level is state-of-the-art within the area. As discussed in Section 1.2, we make only
a very weak assumption: limited query access to the payoff function, with no assumptions about
properties such as convexity, continuity, or differentiability. Therefore, we need to introduce tools
from game theory and Yao’s principle.

(3) Two-player zero-sum games with a unique NE are commonly studied in AI/ML literature. For
instance, (detailed discussion can be found in **Section A** in Appendix), 

(a) Learning in Games:  for example, see [11], [10], [9].

(b) Co-evolutionary Heuristics: for example, see [7],[6],[1].

In summary, two-player zero-sum games with a unique NE represent a broad and meaningful class of
games, providing a reasonable starting point. While it is indeed interesting to generalise the analysis
to more complex solution concepts such as mixed NEs or broader classes of adversarial optimisation
problems, it is a necessary first step in order to be able to analyse more general classes of games.

**Q2 The theoretical analysis is restricted to finite (discrete) problems. 7LPoW2; RwGpQ2.**

A: We agree that the current result is restricted to finite (discrete) problems and only
considers the deterministic case where "each query has at most k ≥ 2 possible answers".
There are two reasons for using this condition:

(1) For consistency with previous literature and a fair comparison, we use the same setting as the previous
NFL/FL results [13, 14, 12] and emphasise that under the same condition, the solution concept
plays a role in the construction of NFL/FL.

(2) The generalisation of such a result is interesting, however, as shown in the paper, under this
condition, the proof/analysis is still challenging and non-trivial. It is necessary to understand the
basic setting before moving to a more general setting.

In conclusion, despite the limitations, this setting provides a clear and rigorous starting point. Future
work can build on these results to explore continuous and more complex scenarios. As mentioned
in **line 384**, we may need further assumptions or use other tools to derive the NFL analysis for
other scenarios. For a broad class of possible applications on two-player zero-sum games with finite
strategies and unique NE, we refer to our response to Q1.

**Q3 Empirical verification of our theoretical result. RXe7yQ1; PuqfW2**

A: It is impossible to verify impossibility results, such as our black-box results, empirically.
In particular, we are proving an impossibility result for an infinitely large class of algorithms and for an infinitely large class of problems (c.f. Definition 7). 
To verify the result empirically, one would
have to try an infinite number of algorithms on an infinite number of problem instances. Clearly, this
is not possible. This paper is theoretical in nature and aims to provide a general understanding of
black-box adversarial optimisation.

**References**

[1] A. Benford, P.K. Lehre. Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games. In GECCO, 2024.

[2] S. Bubeck et al. Convex Optimization: Algorithms and Complexity. Found. Trends Mach. Learn., 2015.

[3] Y. Cai, H. Luo, C.-Y. Wei, W. Zheng. Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback. In NeurIPS, 2023.

[4] C. Daskalakis, I. Panageas. The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization. In NeurIPS, 2018.

[5] A.V. Do, A. Neumann, F. Neumann, A.M. Sutton. Rigorous runtime analysis of MOEA/D for solving multi-objective minimum weight base problems. In NeurIPS, 2023.

[6] M.A. Hevia Fajardo, P.K. Lehre, S. Lin. Runtime analysis of a co-evolutionary algorithm: Overcoming negative drift in maximin-optimisation. In FOGA, 2023.

[7] P.K. Lehre. Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function. In GECCO, 2022.

[8] T. Lin, C. Jin, M. Jordan. On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems. In ICML, 2020.

[9] A. Maiti, R. Boczar, K. Jamieson, L.J. Ratliff. Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Two-Player Zero-Sum Matrix Game. arXiv preprint arXiv:2310.16236, 2023.

[10] B. O’Donoghue, T. Lattimore, I. Osband. Matrix Games with Bandit Feedback. In UAI, 2021.

[11] I. Panageas, N. Patris, S. Skoulakis, V. Cevher. Exponential Lower Bounds for Fictitious Play in Potential Games. In NeurIPS, 2023.

[12] T.C. Service, D.R. Tauritz. A No-Free-Lunch Framework for Coevolution. In GECCO, 2008.

[13] D.H. Wolpert, W.G. Macready. No Free Lunch Theorems for Optimization. TEVC, 1997.

[14] D.H. Wolpert, W.G. Macready. Coevolutionary Free Lunches. TEVC, 2005.

Meta-review: The paper makes a significant theoretical contribution by proving a No Free Lunch (NFL) theorem for black-box adversarial optimization, focusing on Nash Equilibrium (NE). The results are rigorous and provide valuable insights into the limitations of adversarial optimization algorithms. However, concerns were raised about the paper's readability and limited discussion of practical applications. The authors have addressed these concerns in their rebuttal, promising to improve clarity and integrate essential details from the appendix into the main text. Given its theoretical importance and the authors' commitment to revisions, the paper is recommended for acceptance.
Decision: Accept (poster)