No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation

Authors: kristian  per
  lehre
shishen  lin
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:36:02

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.

Main paper: 
 introduction 1.black-box optimisation and the no free lunch theorem: 
 Black-Box Optimisation (BBO) is crucial for optimising complex, unknown, or expensive-to-evaluate 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 → R, where the algorithm is limited to making queries to f [11, 14, 36] . In this case, the algorithm is only able to sample and query the function value f (x) of search points x ∈ X from a "black-box" or "oracle" without access to any description of the objective functions f . A similar framework can be extended to game-theoretic BBO, namely adversarial BBO. Specifically, adversarial BBO is the task that optimising payoff functions from some payoff function class G where G consists of black-box functions g : X × Y → R, with a limited budget of function evaluations. Additionally, two players x ∈ X and y ∈ Y form a maximin optimisation (as presented in Figure 1 ). 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 is averaged over all possible problem instances [45, 44] ." Instead of querying at x in traditional optimisation, maximin optimisation queries at (x, y) include both strategy x and the best response y from the opponent, i.e. max x∈X min y∈Y g(x, y). Their interaction is converted to the payoff g(x, y) in the given black-box model.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 as 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. [11] has provided a 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 a conservation law for the generalised performance of learning algorithms in classification problems.Adversarial optimisation tasks, such as maximin optimisation, are more complex and often counterintuitive compared to 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. A '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 was demonstrated by Wolpert and Macready [46] for adversarial optimisation with respect to the 'maximin' solution concept (Definition 10). Similarly, Service and Tauritz [39] established a '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 we use Nash Equilibrium as the solution concept, how can we characterise the difficulty of black-box adversarial optimisation problems for problem-independent, possibly randomised, search heuristics?In this paper, we answer Question (1) in the negative by showing a No Free Lunch theorem for Nash Equilibrium solution concept and address Question (2) by introducing black-box complexity tools.There are several challenges in showing the NFL and BBC results. First, we highlight the challenges and our technical details in the derivation process compared to 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 proof-by-induction 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 4) and help to construct the isomorphism between two different problem classes (i.e. Corollary 1 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 difficult for the algorithm. Consequently, we have limited analytical tools to proceed. To analyse the black-box 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.We prove a new impossibility result on black-box adversarial optimisation. In a two-player zerosum 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-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-player zero-sum games.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 a 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 contributions made in the paper and important assumptions and limitations. A No or 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. 
notation: 
 Given n ∈ N, [n] := {1, 2, • • • , n}. Given a finite set X , we denote the permutation group byS(X ) := {σ : X → X | σ is a permutation of X }. For any v ∈ R n , let SUPP(v) := {i ∈ [n] | v i ̸ = 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 × Y, where X and Y are finite and denote the cardinality of a set by |X |. 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 a function from a set X to a set Y . If A is a subset of X, then the restriction of f to A is the function:f | A : A → Y ; x → f (x).Let f : X → Y be any function and A and B be sets such thatX ⊆ A and Y ⊆ B. An extension of f to A is a function g : A → B such that f (x) = g(x) for all x ∈ X. Alternatively, g is an extension of f to A if f is a restriction of g to X.Solution concepts for classical function optimisation are not directly applicable to adversarial optimisation in general-sum or zero-sum game settings [33, 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 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). Definition 1. (Nash) Consider a two-player game. Given strategy spaces X × Y and payoff functions g, h : X × Y → O, where O is an ordered set which determines the outcome of candidate solution X on test Y, (x * , y * ) is a Nash equilibrium if for all (x, y) ∈ X × Y, g(x * , y * ) ≥ g(x, y * ) and h(x * , y * ) ≥ h(x * , y). In particular, if the two-player game is zero-sum (that is, if g(x, y) + h(x, y) = 0 for all (x, y) ∈ X × Y), then (x * , y * ) is a Nash equilibrium if for all (x, y) ∈ X × Y, g(x, y * ) ≤ g(x * , y * ) ≤ g(x * , y). The solution concept is defined byS = {(x * , y * ) ∈ X × Y | ∀(x, y) ∈ X × Y, g(x, y * ) ≤ g(x * , y * ) ≤ g(x * , y)}.We also defer other solution concepts for comparison in the appendix. We use the formulation in [46, 39] .3 No Free Lunch Theorem for Computing Nash Equilibrium in Adversarial OptimisationIn 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, 11] . We now explain what 'closed under permutation' means and how it can be extended to games.Permutation closure of a set of functions means that let X , Y be two finite sets and f : X → Y defined by f (x i ) = y i . Let σ be a permutation σ : X → X and we can permute the function:f (σ(x)) := σ • f (x).Schumacher et al. [38] and Droste et al. [11] defined 'closed under permutation (c.u.p.)' with respect to a single search space X . A class of functionsF = f : X × Y → R is called c.u.p. if for all f ∈ F and all permutations σ ∈ S(X ), f • σ ∈ F.For our adversarial setting, we need to extend this notion to X × Y. Definition 2. Given two-player zero-sum games, suppose F as a subset of all the payoff functions in these games g : X × Y → O where O ⊆ R. We say F is c.u.p if for any g ∈ F and any permutations on X , Y denoted by σ ∈ S(X ), τ ∈ S(Y), we have(σ ⊗ τ ) • g ∈ F (or abbreviated (στ )g) where (σ ⊗ τ ) • g(x, y) := g (σ(x), τ (y)) for all (x, y) ∈ X × Y.If a set of two-player zero-sum games is c.u.p., we will also call it structure-free. In this paper, we restrict to the case that X , Y, 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] is by induction, where one assumes that the statement is true for all "smaller problems". Here, a smaller problem refers to the following definition of a sub-game or a 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 ⊆ R and F be any subset of the set of payoff functions in these games g : X × Y → O such that F is closed under permutation. For any given (2) g(x, y 1 ) = b 2 (x) for all x ∈ X ;(x 1 , y 1 ) ∈ X × Y,(3) f is a restriction of g on (X \ {x 1 }) × (Y \ {y 1 }).Next, before we show that a sub-problem class F ((x 1 , y 1 ), (b 1 , b 2 )) is c.u.p., we need a lemma to guarantee that after any permutation, the permuted payoff function still contains the same unique Nash Equilibrium2 . We provide a corollary to Lemma 4. We defer all the proofs to the appendix due to the page limit. Corollary 1. Let |X | = |Y| and F ⊆ {g : X × Y → R} be any set of two-player zero-sum games with a unique NE. Assume furthermore that F is c.u.p.. Then, for any game g ∈ F, let (x * , y * ) ∈ X × Y denote the unique Nash Equilibrium of g. For any permutations over X , Y denoted by σ ∈ S(X ), τ ∈ S(Y), (σ ⊗ τ ) • g ∈ F exhibits the same unique Nash Equilibrium (x * , y * ). Moreover, if for any x 0 ̸ = x * and y 0 ̸ = y * , the restriction of g on (X \ {x 0 }) × (Y \ {y 0 }), denoted by g| (X \{x0})×(Y\{y0}) , exhibits the same unique Nash Equilibrium (x * , y * ).This permutation essentially swaps the rows and columns in the payoff matrix. Corollary 1 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-problem.Next, we prove the sub-problem class is closed under permutation.Lemma 1. If F is c.u.p., then F ((x 1 , y 1 ), (b 1 , b 2 )) is also c.u.p.. Then, we want to know if we choose different (x, 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 (x 1 , y 1 ), (x 2 , y 2 ) ∈ X × Y and b 1 : Y → R, b 2 : X → R, we have the isomorphism 3 :F ((x 1 , y 1 ), (b 1 , b 2 )) ≃ F ((x 2 , y 2 ), (b 1 , b 2 )) .Given (x t , y t ) is the search point by Algorithm H on payoff function g at iteration t ∈ N and (x * , y * ) is the unique NE in a two-player zero-sum game defined by g : X × Y → R, Theorem 3.1 considers the following query complexity:T LB (H, g) := inf{t > 0 | x t = x * or y t = y * }Now, we prove our main theorem. )), decreasing the search space from size N × N to size (N -1) × (N -1), where |X | := N . Then using Lemma 2 and inductive step, it follows that r(H, F) = r(H ′ , F) for any two deterministic algorithms H, H ′ , and the claim for randomised algorithms quickly follows from the fact that any randomised algorithm can be viewed as a probability distribution among all deterministic algorithms. Theorem 3.1 reveals an important underlying result: All black-box adversarial algorithms can exhibit the same average runtime r(H, F) of all possible problem instances (or problem instances c.u.p.) with a unique Nash Equilibrium in a two-player zero-sum game setting. It is a reasonable result since Theorem 3.1 tells us that if a class of payoff functions with a unique Nash Equilibrium does not change by any permutation on the input space, there is no structure provided for any search heuristic 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.This result is 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 10. However, our result does contradict the previous result. We consider the performance measure T (H, g) and a different query model considered by the previous work. In particular, Definition 9 and Definition 10 only take the player x into account, while the opponent optimum and different query model and performance measures can make a 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 "no-free-lunch", in particular for NE solution concept.A = ⟨e i , Aq ⋆ ⟩ for all i ∈ supp(p ⋆ ), and V ⋆ A > ⟨e i , Aq ⋆ ⟩ for all i / ∈ supp(p ⋆ ).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 in 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-specification, 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 was 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 in low lighting. Or a speech-to-text system might not be 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: All the theorems, formulas, and proofs in the paper are numbered and crossreferenced, and all assumptions are clearly stated or referenced in the statement of all theorems. Due to the page limit, we defer all the proofs in the supplementary material (see Section D). We also provide a 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 or 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 a 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 or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
black-box complexity of black-box adversarial optimisation: 
 As shown in the previous NFL theorem, no better universal algorithms exist on structure-free 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 of certain classes of problems, including Nash equilibrium in a 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 [27, 26, 3, 21, 22] The following questions remain under-explored: How does the performance 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.This section focuses on adversarial black-box optimisation and study the query complexity of learning Nash equilibrium in a two-player zero-sum-game setting. We refer to [13, 8, 10] Choose some probability distribution P I(t) , depending only on I(t) where I(t) := Π t-1 j=1 (x j , y j , g(x j , y j ), h(x j , y j ))∈ (X × Y × R × R) t-1 4:Produce a random search point (x t , y t ) based on P I(t) .5:Query g(x t , y t ), h(x t , y t )Algorithm 1 defines a 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 (x 0 , y 0 ) is independent of the problem, so we can choose any probability distribution P ∅ to initialise the algorithm. Subsequent strategy pairs are obtained by asking the oracle to apply a given variation operator to all previously queried search points subject to sample probability distribution P I(t) . By specifying different sample probability distribution P I(t) , Algorithm 1 represents various black-box optimisation algorithms, including several adversarial search (also called competitive coevolutionary) algorithms [46, 32] and randomised algorithms FINDPSNE (designed to learn the NE in bimatrix games) [27] . 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 algorithm A and the payoff function g : X × Y → R, T (A, g) is the query complexity of A with respect to g and (x t , y t ) is the search point generated by A if Then, theT (A, g) := inf{ct ∈ N | (x t , y t ) ∈ arg maxA-black-box complexity of G is T (A, G) := inf A∈A T (A, G) = inf A∈A sup g∈G T (A, g);the best or minimum complexity among all A ∈ A with respect to G. If A is the whole class of all black-box algorithms, we denote T (A, G) the unrestricted black-box complexity of G.We want to point out the difference between these two definitions. Definition 4 considers the query complexity for a particular algorithm and problem instance, and Definition 5 considers the black-box complexity for the best possible query complexity of all possible given algorithms under the worstcase scenario. The traditional black-box complexity theory characterises the difficulty of a certain class of problems and explores the limitations of the given black-box optimisation algorithms. We expect our extension to adversarial optimisation can provide similar insights as well.We first provide a lower bound of query complexity for a 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. Consider any class of two-player zero-sum games G ⊂ {g : X × Y → B} such that for all (x, y) ∈ X × Y, there exists a game g x,y ∈ G which has (x, y) as unique, pure Nash Equilibrium. Then, the class G has black box complexity at least ⌈log k |X × Y|⌉ -1.In this subsection, we employ Yao's Principle and No Free Lunch Theorem to provide a general lower bound for query complexity of searching Nash Equilibrium in zero-sum bimatrix games, and this leads to a 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 1 and T (A, P )4 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 ∈ R n×n with a unique pure Nash equilibrium (x * , y * ) such that E(T (A, P )) ≥ (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 a sharper lower bound by a 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 × n payoff matrix), there are complex instances where no randomised algorithm can achieve better than O(n) query complexity unless additional problem structure is provided.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 [5, 4, 16] and Boolean games [18] . Voting is considered a fundamental tool for analysing multi-agent systems [16, 1] . We start with simple binary voting games in which the outcome or payoff is 0 or 1 (or -1 and 1). These games also play a role in the analysis of Boolean functions [31] .Convergence to NE in 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/inefficiency of black-box optimisation algorithms on binary voting games.We formulate binary voting games in the context of adversarial optimisation as follows. Consider two parties represented by vectors x, y ∈ {0, 1} n where n ∈ N. Each group has n 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 a 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} n , the payoff function DIAGONAL : X × Y → {-1, 1} is DIAGONAL(x, y) := 1 |y| 1 ≤ |x| 1 -1 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 a stronger 'in favour' "influence" in the sense of the number of the support votes (i.e. the number of 1 in the encoding binary bitstring), then we get a payoff 1 and -1 otherwise. We are interested in computing NE in these two-player zero-sum games, i.e. solving (x * , y * ) ∈ arg max x∈X min y∈Y g(x, y). Notice that in DIAGONAL, (x n , y n ) = (1 n , 1 n ) is the unique NE optimum. In this optimum, neither of the two groups is willing to deviate from affecting their payoff g(x n , y n ) anymore. This exactly coincides with the definition of NE.Next, we consider a 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} n , a constant δ ∈ (0, 1), the payoff function PLATEAU : X × Y → {-1, 1} is defined as PLATEAU(x, y) := f (y) if ||x| 1 -n 2 | < δn 2 g(x, y) otherwise where f : Y → {-1, 1} and g : X × Y → {-1, 1} are any functions such that the NE of PLATEAU is (x * , y * ) ̸ ∈ {(x, y) | ||x| 1 -n 2 | < δn 2 }.Definition 7 introduces a plateau when comparing the "influence" between two groups and defines a general class of pseudo-Boolean benchmarks with a plateau. Imagine a committee deciding on a 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 (Y) come into play. It is like their votes are the tiebreaker. If the second group votes in favour, then the policy passes; if 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 y ∈ Y.Finally, we define game instances generated by (u, v) where u, v ∈ {0, 1} n . Definition 8 ((u, v)-game instance). For all u, v ∈ {0, 1} n , given f : {0, 1} n × {0, 1} n → R, we define the (u, v)-instance of f , denoted by f (u,v) , asf (u,v) (x, y) := f (u ⊕ x, v ⊕ v).We can see that for any u, v ∈ {0, 1} n , f (u,v) generates the same payoff landscape as f . In this paper, f will be either DIAGONAL or PLATEAU. We defer more details to Section G5 .First, let us illustrate how Theorem 4.1 and Theorem 4.2 work on these simple examples. If we consider a general class of black-box optimisation algorithms defined by Algorithm 1 on binary voting games with a unique Nash Equilibrium, then we provide a general lower bound of black-box complexity as follows. Theorem 4.3. The black-box complexity with respect to Algorithm 1 of the binary voting games with problem size n ∈ N and a unique Nash Equilibrium is e Ω(n) . Theorem 4.3 means that there exist no universal good black-box optimisation algorithms defined by Algorithm 1 that can solve all binary voting games with unique Nash Equilibrium efficiently, (i.e. with polynomial query complexity of the problem size). To yield a better performance of black-box 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 1 of DIAGONAL. This reveals that DIAGONAL is a feasible benchmark problem for black-box adversarial optimisation algorithms. DIAGONAL n := {DIAGONAL (u,v) | (u, v) ∈ {0, 1} n × {0, 1} n }, the black-box complexity with respect to Algorithm 1 of DIAGONAL n is Θ(n).Theorem 4.4 implies that DIAGONAL n is a sensible maximin benchmark for testing black-box optimisation algorithms. It means that if we restrict the problem class to a certain class with a specific structure, then it is possible to solve them in polynomial query complexity.We have seen the black-box complexity results on DIAGONAL n . Next, we start to consider more challenging binary voting games, PLATEAU. We are interested in whether there is any efficient black-box adversarial optimisation that can solve PLATEAU n in polynomial query complexity (i.e.). To answer this question, we need to compute its black-box complexity. Theorem 4.5. Given the game class,PLATEAU n := {PLATEAU (u,v) | (u, v) ∈ {0, 1} n × {0, 1} n },the black-box complexity with respect to the class of algorithms defined by Algorithm 1 of PLATEAU n is e Ω(n) . Theorem 4.5 implies that all black-box adversarial optimisation algorithms defined by unrestricted model (i.e. Algorithm 1) have exponential runtime on PLATEAU n . They need at least an exponentially large query complexity with respect to 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.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-solvable class (i.e., there exists an algorithm that can solve all problem instances of this class in polynomial runtime) and the non-polynomial-solvable class (i.e., there exists no algorithm that can solve all problem instances of this class in polynomial runtime). Theorem 4.3 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 as DIAGONAL n , it is possible to come up with a better algorithm which achieves better polynomial query complexity as shown in Theorem 4.4. DIAGONAL n can be a promising benchmark for evaluating black-box algorithms. Additional assumptions on the payoff function, like those in PLATEAU n problems, proved in Theorem 4.5, do not lower the difficulty of the problems. This emphasises the need for a 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 WorkQuestion: Does the paper fully disclose all the information needed to 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 or not)?Answer: [NA] Justification: Our paper is purely a theory paper, and it does not include experiments. 
co-evolutionary search heuristics: 
 Next, we provide some practical examples of adversarial optimisation. There are various adversarial search heuristics, including competitive co-evolutionary algorithms (CoEAs) [35, 26] . CoEAs are a class of algorithms applied in game-theoretic 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 a co-evolutionary approach for image translation [41] . 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 is limited theoretical literature on 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 Fajardo et al. [22] showed a weakness of RLS-PD and the sufficiency of a simple archive to prevent evolutionary forgetting. On the other hand, regarding the general black-box optimisation framework, Wolpert and Macready [46] showed there exists a "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 10).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 [7] . Chen and Deng [6] provide a simplified proof of the computational complexity of Nash Equilibrium in twoplayer games. Significant focus has also been placed on how the game dynamics converge to the Nash equilibrium or approximate it [27, 25, 17, 34] .Panageas et al. [34] considered the complexity of fictitious play in two-player potential games with a unique Nash Equilibrium (NE). They proved the existence of a hard instance which requires query complexity Ω 4 n ((n/2 -2)!) 4 where n 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 on a 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 adversarial algorithms, including fictitious play, exhibit the same average performance across all problem instances in terms of query complexity. 
conclusion and discussion: 
 Utilising the tools from game theory and Yao's principle, we 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 a 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 can exceed the logarithmic complexity relative to search space size. 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.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) or uncountable infinite (e.g. R) sets. To generalise our 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. A Two Other Solution Concepts Definition 9 (Maximisation Over All Test Cases [39] ). Suppose a set of candidate solutions, X , and a set of test cases, Y. Given an interaction function or payoff function, g : X × Y → O, where O is an ordered set which determines the outcome of candidate solution X on test Y, the solution concept is defined by: S = {x * ∈ X | ∀x ∈ X , ∀y ∈ Y, g(x * , y) ≥ g(x, y)}.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 set of test cases, Y.Given an interaction function or payoff function, g : X × Y → O, where O is an ordered set which determines the outcome of candidate solution X on test Y, the solution concept is defined by:S = {x * ∈ X | ∀x ∈ X , min y∈Y g(x * , y) ≥ min y∈Y g(x, y)}.Notice that in Definition 9, this solution concept considers the candidate solution x with respect to all test cases y. Definition 10 considers the candidate solution with respect to the worst-case scenario.If Y is compact, then these two solution concepts are essentially the same. Compared with Nash Equilibrium in Definition 1, these two solution concepts only focus on finding the best candidate solution and the algorithm is not required also to produce an opposing "optimal" solution y * . 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 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 to 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 a 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.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, 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. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [NA]  
 
 Appendix: We adopt the notation in [27] .Definition 11. Given a two-player zero-sum game on a payoff matrix P ∈ R n×n . Let ∆ n denote the n-dimensional probability simplex (i.e. for p ∈ ∆ n , n i=1 p i = 1 and p i ≥ 0). A pair (p * , q * ) is a (mixed strategy) Nash Equilibrium of an input matrix P ∈ R n×n if and only if the following holds for all (p, q) ∈ ∆ n × ∆ n : ⟨p, P q * ⟩ ≤ ⟨p * , P q * ⟩ ≤ ⟨p * , P q⟩.In this paper, we are only interested in Pure Strategy Nash Equilibrium. Definition 12. For any payoff matrix P ∈ R n×n , let V ⋆ P := max p∈∆n min q∈∆n ⟨p, P q⟩. In particular, we say an entry (i * , j * ) ∈ [n] × [n] is a unique pure strategy Nash Equilibrium if (e i * , e j * ) ∈ ∆ n × ∆ n is a unique Nash Equilibrium of P where e i * , e j * are the unit probability vector.We refer to the following lemma from [40] .Lemma 3 (Lemma 1 in [27] ). Consider a matrix A ∈ R n×n with a unique Nash equilibrium (p ⋆ , q ⋆ ). The following conditions hold:1. The support sizes of p ⋆ and q ⋆ are equal (i.e., |supp(p ⋆ )| = |supp(q ⋆ )|).V ⋆ A = ⟨p ⋆ , Ae j ⟩ for all j ∈ supp(q ⋆ ), and V ⋆ A < ⟨p ⋆ , Ae j ⟩ for all j / ∈ supp(q ⋆ ).Lemma 3 allows us to derive the following result, which is proved in Appendix B.1 in [27] .Lemma 4 (Lemma 2 in [27] ). Consider a matrix P ∈ R n×n with a unique Nash equilibrium (p ⋆ , q ⋆ ).Consider a submatrix M of P with row index set I X and column index set I Y . If SUPP(p ⋆ ) ⊆ I X and SUPP(q ⋆ ) ⊆ I Y , then (p, q) is the unique Nash equilibrium of M where (p) i = (p ⋆ ) i for all i ∈ I X and (q) j = (q ⋆ ) j for all j ∈ I Y . Moreover, V ⋆ M = V ⋆ P .In this section, we provide the mathematical tool that we 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 Π be a problem with a finite set I of input instances (of a fixed size) permitting a finite set A of deterministic algorithms. Let p be a probability distribution over I and q be a probability distribution over A. Then,min A∈A E(T (I p , A)) ≤ max I∈I E(T (I, A q ))where I p denotes a random input chosen from I according to p, A q a random algorithm chosen from A according to q and T (I, A) denote the runtime of algorithm A on input I.Theorem C.2. (Markov's inequality) Given a non-negative random variable X and a > 0, Pr (X ≥ a) ≤ E(X) a . Theorem C.3. (Chernoff's bound) Given X := n i=1 X i where X i ∼ Ber(p i ) where Ber(p i ) is a Bernoulli random variable with probability p i and all X i are independent. Let µ := E(X) = n i=1 p i . Then, for δ ∈ (0, 1),Pr (|X -µ| ≥ δµ) ≤ 2e -µδ 2 /3 .Corollary 2. Let |X | = |Y| and F ⊆ {g : X × Y → R} be any set of two-player zero-sum games with a unique NE. Assume furthermore that F is c.u.p.. Then, for any game g ∈ F, let (x * , y * ) ∈ X × Y denote the unique Nash Equilibrium of g. For any permutations over X , Y denoted by σ ∈ S(X ), τ ∈ S(Y), (σ ⊗ τ ) • g ∈ F exhibits the same unique Nash Equilibrium (x * , y * ). Moreover, if for any x 0 ̸ = x * and y 0 ̸ = y * , the restriction of g on (X \ {x 0 }) × (Y \ {y 0 }), denoted by g| (X \{x0})×(Y\{y0}) , exhibits the same unique Nash Equilibrium (x * , y * ).Proof of Lemma 1. We employ the result in [27] (See Lemma 4). For any permutations on X , Y denoted by σ ∈ S(X ), τ ∈ S(Y), (σ ⊗ τ ) • g ∈ F is defined as for any x ∈ X, y ∈ Y,(σ ⊗ τ ) • g(x, y) = g (σ(x), τ (y)) .We consider the payoff matrix defined by P = (p i,j ) where p i,j = g(x i , y j ) with x i ∈ X , y j ∈ Y. We denote row index set by I X ⊆ N and column index set byI Y ⊆ N. Notice that |I X | = |X | = |Y| = |I Y |.We denote the row index by i ∈ I X and the column index by j ∈ I Y . P ∈ R |I X |×|I Y | is the payoff matrix of two-player zero-sum game g with a unique Nash Equilibrium (x * , y * ). Let us denote the row index of x * in the payoff matrix P by i * and the column index of y * by j * in the payoff matrix P . So (e i * , e j * ) ∈ ∆ n × ∆ n is the unique Nash Equilibrium in the form of probability vector. Now, given any permutation σ, τ , we consider a submatrix P ′ such that P ′ = (p σ(i),τ (j) ) with a new row index set I ′ X ⊆ N and column index set I ′ Y ⊆ N. Since σ only shuffles around the row indices in I X , I ′ X ≃ I X with the isomorphism σ. Similarly, we have I ′ Y ≃ I Y with the isomorphism τ . Now, we can see that i * = SUPP(e i * ) ∈ I ′ X and j * = SUPP(e j * ) ∈ I ′ Y , so (p, q) ∈ ∆ n × ∆ n is the unique Nash Equilibrium of P ′ (in the form of a probability vector) where (p) i = (e i * ) i for all i ∈ I ′ X and (q) j = (e j * ) j for all j ∈ I ′ Y . In other words, (p, q) = (e i * , e j * ). So by using Lemma 4, we can conclude that (x * , y * ) ∈ X × Y is the unique Nash Equilibrium of (σ ⊗ τ ) • g.For the second claim, we construct a submatrix Q such that Q = (q i,j ) where q i,j = g(x i , y j ) with x i ∈ X \{x 0 }, y j ∈ Y \{y 0 }. We denote the row index set I X \{x0} and the column index set I Y\{y0} . Since x 0 ̸ = x * and y 0 ̸ = y * , i * = SUPP(e i * ) ∈ I X \{x0} and j * = SUPP(e j * ) ∈ I Y\{y0} , by using Lemma 4 again, we can conclude that (x * , y * ) is the unique Nash Equilibrium of g| (X \{x0})×(Y\{y0}) . We complete the proof. Lemma 1. If F is c.u.p., then F ((x 1 , y 1 ), (b 1 , b 2 )) is also c.u.p.. Proof of Lemma 1. For any σ ′ ∈ S(X \{x 1 }), τ ′ ∈ S(Y \{y 1 }) and any g ′ ∈ F ((x 1 , y 1 ), (b 1 , b 2 )), we want to show (σ ′ τ ′ )g ′ ∈ F ((x 1 , y 1 ), (b 1 , b 2 )). We consider the extensions of each permutation. We define σ : X → X by its restriction on X \ {x 1 } as σ| X \{x1} = σ ′ and σ(x 1 ) = x 1 .We define τ : Y → Y by its restriction on Y \ {y 1 } is τ | X \{y1} = τ ′ and τ (y 1 ) = y 1 . Now, let g be the extension of g ′ which satisfies (1), ( 2) and (3) of Definition 3 (such an extension g exists since we take g ′ ∈ F ((x 1 , y 1 ), (b 1 , b 2 )) and it follows from the definition of sub-problem class). As g ∈ F, so are (στ )g ∈ F. Thus, we construct (στ )g as an extension of (σ ′ τ ′ )g ′ and (στ )g satisfies ( 1), ( 2) and (3) of Definition 3. So(σ ′ τ ′ )g ′ ∈ F ((x 1 , y 1 ), (b 1 , b 2 )).Lemma 2. For all (x 1 , y 1 ), (x 2 , y 2 ) ∈ X × Y and b 1 : Y → R, b 2 : X → R, we have the isomorphism 6 :F ((x 1 , y 1 ), (b 1 , b 2 )) ≃ F ((x 2 , y 2 ), (b 1 , b 2 )) .Proof of Lemma 2. To prove the isomorphism, we need to find a bijection between these two sets. We consider the following map between sets with , defined by:ϕ : F ((x 1 , y 1 ), (b 1 , b 2 )) → F ((x 2 , y 2 ), (b 1 , b 2 )) where ϕ(g ′ ) = h ′ such that for (x, y) ∈ (X \ {x 1 , x 2 }) × (Y \ {y 1 , y 2 }), h ′ (x, y) = ϕ(g ′ )(x, y) = g ′ (x, y). For y ∈ Y \ {y 2 }, h ′ (x 1 , y) = ϕ(g ′ )(x 2 , y) = g ′ (x 2 , y). For x ∈ Y \ {x 2 }, h ′ (x, y 1 ) = ϕ(g ′ )(x, y 2 ) = g ′ (x, y 2 ) Let h be the extension of h ′ defined by h(x 2 , y) = b 1 (y), h(x, y 2 ) = b 2 (x) For all (x, y) ∈ (X \ {x 2 }) × (Y \ {y 2 }), h(x, y) = h ′ (x, y)Now, we notice that h = (π x π y )g where π x , π y are two transpositions in S(X ), S(Y) defined byπ x (x 1 ) = x 2 , π x (x 2 ) = x 1 π y (y 1 ) = y 2 , π y (y 2 ) = y 1and for all x ′ ∈ X \ {x 1 , x 2 } and for all y ′ ∈ Y \ {y 1 , y 2 },π x (x ′ ) = x ′ , π y (y ′ ) = y ′ Since g ∈ F, so is h = (π x π y )g ∈ F.So h ′ has the extension h satisfies (1), (2) in Definition 3. Also, h ′ = ϕ(g ′ ) is uniquely determined by g ′ and the argument would also hold when swapping h ′ , g ′ with the map ϕ -1 . So we prove there exists an isomorphism between these two sub-problem classes.Theorem 3.1. Given F as a subset of all the payoff functions g : X × Y → O with a unique Nash Equilibrium where O ⊆ R and |X | = |Y|. Let H 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 ∈ F (i.e. E(T LB (H, g))). Then r(H, F) = r(H ′ , F) for all algorithms H, H ′ . Proof of Theorem 3.1. Recall that the query complexity of H on g is T LB (H, g) := inf{t > 0 | x t = x * or y t = y * } where (x t , y t ) is the search point by Algorithm H on payoff function g and (x * , y * ) is the unique Nash Equilibrium in a two-player zero-sum game defined by g : X × Y → O. We denote the set of all functions from a set X to a set O by H(X , O) and the set of all well-defined functions from a set Y to a set O by H(Y, O).Let F be a class of games with all the payoff functions g : X × Y → O with a unique NE, and assume that F is closed under permutation. For all (x 0 , y 0 ) ∈ X × Y, define B (1) x0 : = {b 1 ∈ H(Y, O) | there exists g ∈ F s.t. b 1 (y) = g(x 0 , y) for all y ∈ Y}; B (2) y0 : = {b 2 ∈ H(X , O) | there exists g ∈ F s.t. b 2 (x) = g(x, y 0 ) for all x ∈ X }.Let (u, v) ∈ X × Y be the first query point that Algorithm 1 makes, we consider b 1 ∈ B(1)u and b 2 ∈ B (2) v .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 it means that X × Y only consists of one unique NE and F consists of one payoff function g. So for any two deterministic algorithms A, B, r(A, F) = r(B, F) = 1.Next, assume N ≥ 2 and r(A, G) = r(B, G) where G is any set 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 F now consists of payoff functions with unique NE and search space in payoff functions of size N . We expand out the average of r(A, F).r(A, F) = g∈F Pr(g is selected from F) • T (A, g)If we are lucky, then the first point (u, v) ∈ X × Y we query is the optimum (opt.) and (x * , y * ) is the NE of the selected g. With the help of Corollary 1 and Lemma 1, we apply the inductive hypothesis to this sub-problem class F((u, v), (b 1 , b 2 )) 7 . Also note that we consider the uniform distribution on problem class F and thus for any(u ′ , v ′ ) ̸ = (u, v), we have Pr ((u, v) is the opt. s.t. u = x * or v = y * ) = Pr ((u ′ , v ′ ) is the opt. s.t. u = x * or v = y * ) .Using the inductive hypothesis on the case N -1 with Lemma 2 gives since two sub-problem classes are essentially isomorphic and thus have the same average query complexity from the inductive hypothesis step.r (A, F((u, v), (b 1 , b 2 ))) = r (B, F((u ′ , v ′ ), (b 1 , b 2 ))) .Thus, we can conclude that r(A, F) = r(B, F) for any deterministic algorithms A, B. 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 distribution p = (p 1 , • • • , p m ) and choose the i-th deterministic search strategy with probability p i . It is well-known (see detail in [29] ) that the expected cost of a randomised search heuristic is 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. Proof of Theorem 4.1. The proof which uses Yao's minmax 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 (x, y) ∈ X × Y, we can associate one game g x,y which has (x, y) as the unique pure NE. We let p be the uniform distribution over the set of the games {g x,y | (x, y) ∈ X × Y} ⊆ G.We now consider the runtime of any deterministic black-box algorithm A ∈ A det with respect to a random game g x * ,y * which is sampled according to distribution p. The algorithm is a decision tree, where each node is a pair (x, y) ∈ X × Y corresponding to a query made by algorithm A, and each edge corresponds to one of at most k possible outcomes g(x, y) of this query. The runtime of algorithm A on the random game g x * ,y * corresponds to the depth of (x * , y * ) in this decision tree. The expected depth is therefore lower bounded by ⌈log k (|X × Y|)⌉ -1.A ∈ A det , E(T (I p , A)) ≥ log k (|X × Y|) -1.This implies that minA∈A det E(T (I p , A)) ≥ log k (|X × Y|) -1.By Yao's Principle, for any distribution q over the set of deterministic algorithms A det , max I∈I E(T (I, A q )) ≥ minA∈A det E(T (I p , A)) ≥ log k (|X × Y|) -1.The proof now follows by noting that any randomised algorithm can be described as sampling a deterministic algorithm according some distribution q, and applying this algorithm.Theorem 4.2. Let A be the set of all randomised algorithms defined by Algorithm 1 and T (A, P )8 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 ∈ R n×n with a unique pure Nash equilibrium (x * , y * ) such that E(T (A, P )) ≥ (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 of Theorem 4.2. Given payoff matrix P , recall that for any A ∈ A,T LB (A, P ) : = inf{t > 0 | x t = x * or y t = y * }; T (A, P ) : = inf{t > 0 | x t = x * and y t = y * }; M : = {P ∈ R n×n with a unique PSNE}.Clearly, T (A, P ) ≥ T LB (A, P ). 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 a 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 A det ): for any randomised algorithm A ∈ A,max P ∈M E(T (A, P )) ≥ min ALG∈A det E P ∼Unif(M) (T (ALG, P ))Using the definition of T (ALG, P ) and T LB (ALG, P ) gives ≥ minALG∈A det E P ∼Unif(M)(T LB (ALG, P ))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 a new algorithm ALG * such that it is a deterministic algorithm starting from i = j = 1, and it makes one query in each iteration. It continues to query P 1,1 , P 2,2 , • • • P n,n (i.e. query the entries in the diagonal of the payoff matrix P ). ALG * continues the processes until it reaches either the column or the row of the position of the unique Nash Equilibrium. So, we derive= E P ∼Unif(M) (T LB (ALG * , P ))Note that we consider the uniform distribution on M. It means that the probability that (x * , y * ) lies in the j-th column of payoff matrix P is 1/n for all j ∈ [n]. Then, the total expected query complexity isn j=1 j 1 n = n+1 2 . So, we derive ≥ n + 1 2 .This completes the proof.Theorem 4.3. The black-box complexity with respect to Algorithm 1 of the binary voting games with problem size n ∈ N and a unique Nash Equilibrium is e Ω(n) .Proof of Theorem 4.3. Given an arbitrary binary voting game with problem size n defined by a payoff function g : {0, 1} n × {0, 1} n → R, we consider the corresponding payoff matrix P . For each party, there are 2 n possible strategies encoded by a binary bitstring of length n. So P ∈ R 2 n ×2 n . Using Theorem 4.2 with arbitrary algorithms in the class defined by Algorithm 1 and the payoff matrix P gives us the black-box complexity is at least2 n +1 2 = e Ω(n) .Theorem 4.4. Given the game classDIAGONAL n := {DIAGONAL (u,v) | (u, v) ∈ {0, 1} n × {0, 1} n },the black-box complexity with respect to Algorithm 1 of DIAGONAL n is Θ(n).Proof of Theorem 4.4. We consider an algorithm A ∈ A, which operates in two phases. In each iteration of Phase 1, the algorithm samples x and y uniformly at random, then flips one bit uniformly at random in x to obtain x ′ . It then compares the values of DIAGONAL u,v (x, y) and DIAGONAL u,v (x ′ , y). Phase 1 ends when DIAGONAL u,v (x, y) ̸ = DIAGONAL u,v (x ′ , y). Once Phase 1 ends, the algorithm knows that |u ⊕ x| 1 = |v ⊕ y| 1 .In Phase 2, Algorithm A sample a bitstring y ′ by flipping a single bit in y. If DIAGONAL u,v (x, y ′ ) = -1, we set y = y ′ , otherwise we repeatedly sampling a new y ′ . Once we get payoff -1, we accept the new search point and then sample x ′ by flipping a single bit in x until repeat the process until we get payoff 1. This procedure continues until the termination criterion is met.We now consider how long it takes for Phase 1 to finish (i.e. the search point arrives at the diagonal). Since we are using uniformly at random initialisation, so Z 1 := |u ⊕ x| 1 and Z 2 := |v ⊕ x| 1 are subject to two independent binomial random variables Bin(n, 1/2). We first estimate Pr(Z 1 = Z 2 ). Notice that let Y := n -Z 2 and Y is also subject to Bin(n, 1 -1/2) = Bin(n, 1/2). So the event {Z 1 = Z 2 } is equivalent to {Z 1 = Y } = {Z 1 + Z 2 = n}.Thus, we can derive the following estimate by using Stirling's approximation (i.e. n! ∼ √ 2πn( n e ) n ),Pr(Z 1 = Z 2 ) = 2n n 2 -2n ∼ 1 √ πn 2 2n • 2 -2n = 1 √ πn .So the expected runtime for finishing Phase1 is O( √ n).Now, we consider how long it takes for Phase 2 to reach the optimum. Notice that for each bit, we need 1 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 givesO(n) + O( √ n) = O(n).Together with Theorem 4.1, we can conclude that the black-box complexity of DIAGONAL n is Θ(n). PLATEAU n := {PLATEAU (u,v) | (u, v) ∈ {0, 1} n × {0, 1} n },the black-box complexity with respect to the class of algorithms defined by Algorithm 1 of PLATEAU n is e Ω(n) .Proof of Theorem 4.5. Recall the definition of PLATEAU u,v for arbitrary u, v. We call the set {(x, y)| ||u ⊕ x| 1 -n 2 | ≤ εn 2 }x-independent, and we call any query to this set x-independent. Note that for any x-independent query has payoff PLATEAU u,v (x, y) = f (v ⊕ y), i.e., it is independent of x. Furthermore, note that the Nash Equilibrium is not x-independent.We will apply Yao's Principle with respect to the distribution p over instances where u is sampled uniformly at random among all bitstrings of length n, and v = 0 n . We consider the average case runtime of deterministic algorithms with respect to distribution p. Such algorithms can be modelled as binary decision trees: in each node, the algorithm makes a query (x, y), and for each outgoing edge, the algorithm obtains one of two possible payoff values PLATEAU u,v (x, y) ∈ {-1, 1}. We call the x-independent path in the decision tree the longest path (x 1 , y 1 ), . . . , (x t , y t ) such that (x 1 , y 1 ) is the root node and all nodes (x i , y i ) for i ∈ [t] are x-independent. We let t denote the length of the x-independent path. Since the outcome of an x-independent query only depends on v ⊕ y which is deterministic, the x-independent path of a decision tree is unique. Furthermore, the length of the x-independent path is a lower bound on the runtime of the algorithm since the Nash Equilibrium is not x-independent.We now lower bound the length of the x-independent path. Let (x i , y i ) be any fixed query in the decision tree, and F i the event that (x i , y i ) is x-independent. We sample u by picking each bit independently and uniformly at random in {0, 1}. This implies that the number of 1 bits for each bit is subject to a Bernoulli random variable Bin(1/2). We therefore have |u ⊕ x i | 1 is binomially distributed Bin(n, 1/2). Applying Chernoff's bound, we getEQUATIONLet E 1 be the complement of all the failure events, i.e., E 1 = ∪ t i=1 F i . Therefore, by a union bound, the x-independent path has length t = 2e ε 2 n/12 with probabilityPr(E 1 ) = 1 -Pr ∪ t i=1 F i ≥ 1 -t2e -ε 2 n/6 = 1 -e -Ω(n) .We then have by the law of total probabilitymin A∈A E(T (I p , A)) ≥ min A∈A Pr (E 1 ) E(T (I p , A) | E 1 ) ≥ (1 -e -Ω(n) )2e ε 2 n/12= e Ω(n) .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. We provide an example to illustrate the concept of the sub-problem class (see Definition 3). Figure 2 is an example of a sub-problem class. When querying (x 1 , y 1 ), we also check the corresponding row and column to verify whether the unique Nash Equilibrium lies on this blue cross or not. If the answer is negative, then we restrict to the sub-matrix by removing the blue entries in P . F Further Explanations for the role of Corollary 1 and Lemma 1 in Theorem 3.1In the main proof of Theorem 3.1, we rely on proof by induction: assume the theorem holds for a search space of size N , we want to show it also holds for N + 1. Corollary 1 and Lemma 1 are crucial since they ensure that for every payoff function g ∈ F, there is a corresponding function g ′ where the NE (x * , y * ) is switched to (σ(x * ), τ (y * )) (i.e. σ, τ are two permutations on X , Y 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 1 and Lemma 1 establish a property of the problems or payoff functions under consideration that is preserved under permutations. This property helps to ensure that the induction step can be applied successfully.We define ⊕ as bitwise exclusive or. ⊕ means that for any two binary bitstringsx = x 1 • • • x n and u = u 1 • • • u n , x ⊕ u := (x 1 ⊕ u 1 , • • • , x n ⊕ u n ) where 1 ⊕ 1 = 0, 1 ⊕ 0 = 1, 0 ⊕ 1 = 1, 1 ⊕ 1 = 0.We introduce bitwise exclusive or here to generate problem instances with the same structure. For example, DIAGONAL(x, 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 n , 1 n ) to reach its optimum. And its black-box complexity is trivially Θ(1). Using bitwise exclusive or ⊕ (i.e. DIAGONAL(u ⊕ x, v ⊕ y) where (u, v) ∈ U × V is sampled uniformly at random), we can generate a set of problem instances which have the same structure as DIAGONAL(x, y) and the goal of black-box algorithms is to find (x, y) such that (u ⊕ x, v ⊕ y) = (1 n , 1 n ). (Note that if (u, v) = (0 n , 0 n ), then DIAGONAL(0 n ⊕ x, 0 n ⊕ y) is reduced to the vanilla DIAGONAL(x, 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.NeurIPS Paper Checklist• 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 a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not 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. , 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 are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it 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. Guidelines:• The answer NA means that there is 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point 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 a 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 are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).The further explanation for sub-problem classes can be found in Section E.Here we define isomorphism following[11] rather than defining it as a usual group or ring isomorphism since we do not require any group or ring structure of F in the proof.Note that T (A, P ) = T (A, g) where g(x, y) := e T y P ex with ex, ey denote the elementary probability distribution over probability simplex ∆ {0,1} nWe defer the definition of xor ⊕ to Section G in the supplementary material.Here we define isomorphism following[11] rather than defining it as a usual group or ring isomorphism since we do not require any group or ring structure of F in the proof.We defer further explanations of the role of Corollary 1 and Lemma 1 to the supplementary material Section D.Note that T (A, P ) = T (A, g) where g(x, y) := e T y P ex with ex, ey denote the elementary probability distribution over probability simplex ∆ {0,1} n 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: See questions below.
questions: 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. 
2. I am curious about more difficult games than DIAGONAL and PLATEAU that can be solved by Algorithm 1. Can you provide other examples? 
3. 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: limitations: No potential negative societal impact.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: 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.

W2. 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.

W3. 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.

W4. 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.

W5. 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.
questions: questions: Please clarify the points in the Weaknesses section.
limitations: limitations: Yes, the limitations of the proposed method are discussed in the paper.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 


2. The theoretical analysis is restricted to finite (discrete) problems instead of continuous problems.  This restriction may limit the possible application of the theoretical results.
questions: questions: 1.  What is the key technical challenge for the theoretical analysis of black-box adversarial optimization compared with white-box adversarial optimization?


2. 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: limitations: N.A.
paper_summary: paper_summary: This paper considers the complexity of finding (Pure Strategy) Nash Equilibrium in black-box optimization for adversarial optimization.

By 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.

The 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.
strength_weakness: strength_weakness: 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).
1. 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.
questions: 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$.
2. 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.?
3. 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: limitations: Included in sec. 5

Comments: title: Thank-you Message from Anonymous Authors
Acknowledgement of reading the authors' responses
comment: Dear Reviewers and Area Chair,

Thank you for your feedback and efforts during the rebuttal phase. We have received the responses from all the reviewers now. We appreciate your time and comments, which have helped us improve our work.

Best Regard, Anonymous Authors
Thank you for your response and for acknowledging the contribution of our work in laying the foundation for black-box adversarial optimisation. We provide a brief explanation here:

**(1) Readability and Notation Discrepancies:**

Precise mathematical definitions and notations are essential for rigorous theoretical research. However, we also understand the importance of clarity and accessibility. To address this, we will put extra emphasis on accessibility in the revised version, including more explanations in plain English and ensuring consistent use of notations throughout the text.

We have already **clarified** definitions as requested by Reviewer **RwGp** and included explanations of well-established terms like "restriction" and "extension," as suggested by Reviewer Puqf. 

These efforts will be extended in the revised version to make the paper more accessible without compromising its rigour.

**(2) Practical Applicability:**

As noted in our global response to Q3, our results focus on theoretical impossibility results, which in nature usually do not have immediate practical applications. 

However, this **does not lower** their value  (see NFL for traditional black-box optimisation [13] or Arrow's impossibility theorem [15]). As a key message of our paper, theoretical impossibility results are crucial for understanding the limitations of black-box adversarial optimisation. 

We have discussed the usage of black-box complexity analysis in Section 4.4.3 and will include the discussion of theoretical impossibility results in our revised version as well. Future work could explore the potential practical implications of these theoretical findings, which might eventually inform the design and evaluation of black-box optimisation algorithms in applied settings like binary voting games discussed in this paper.



Above all, we will include all the discussion in our revised version.  Moreover, we are pleased to note that the other reviewers are **satisfied** with our responses and responded **positively** with no further questions.  We appreciate your detailed feedback and hope our explanations help resolve your concerns.


**Reference**

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

[15] Kenneth J Arrow. A difficulty in the concept of social welfare. Journal of political economy, 1950.
I thank the authors for their detailed response. I understand that this work is mostly theoretical and this paper has the potential to set the foundation in this domain. However, I am still concerned that: (a) the main text is hard to read (which is agreed upon by Reviewer RwGp) + there are some discrepancies in the notations and (b) practical applicability is not sufficiently discussed (even in Section 4.4.3, as suggested by the authors). So, I have decided to keep my score.
Thanks for the authors' detailed response.  My concern has been well addressed.  I have no further questions.
I would like to thank the authors for clarifying my doubts. The responses provided by the authors adequately addressed my concerns.
Reviewer Puqf, 

Since you gave a borderline score for this paper, please engage in discussions with the authors and see if the rebuttal addressed your concerns. 

Thanks, 

AC
Reviewer Xe7y, 

Since you gave a borderline score for this paper, please engage in discussions with the authors and see if the rebuttal addressed your concerns. 

Thanks, 

AC
Thanks for your detailed responses. I appreciate that.