אחיה אליסף

When solving two-player multi-objective normal-form games (MONFGs) under worst-case considerations, each strategy is naturally represented by multiple payoff vectors, one for each possible interaction with an opponent’s strategy. While it may be simpler to compress these into a single “representative” vector (e.g., a Nadir point), such scalarization may obscure important trade-offs and potentially misidentify solutions when worst-case performance is critical. To address this, recent approaches compare full sets of payoff vectors to accurately capture adversarial behaviors. However, this approach is computationally expensive. We propose a novel two-stage acceleration method that retains the exactness of full set-based worst-case comparisons, yet substantially reduces runtime. First, a computationally inexpensive tuple-based dominance check identifies obviously dominated (and hence irrational) strategies, discarding them without affecting the final worst-case non-dominated set. Second, the remaining pool of strategies is subjected to the more complex set-based dominance check. We prove theoretically that this two-stage procedure yields the same final solutions as a direct set-based approach, but at a fraction of the computational cost—especially in large strategy spaces. We demonstrate the effectiveness of our method in both a full-search scenario (small problem) and a co-evolutionary setting (larger problem), using a two-player competitive Traveling Salesperson Problem framed as a MONFG. Empirical results show consistent alignment with our complexity analysis and reveal considerable speedups, highlighting the approach’s promise for scaling set-based worst-case methods to more complex multi-player decision domains.