Multi-Fidelity Bayesian Optimization for Nash Equilibria with Black-Box Utilities

Modern open and softwarized systems -- such as O-RAN telecom networks and cloud computing platforms -- host independently developed applications with distinct, and potentially conflicting, objectives. Coordinating the behavior of such applications to ensure stable system operation poses significant challenges, especially when each application's utility is accessible only via costly, black-box evaluations. In this paper, we consider a centralized optimization framework in which a system controller suggests joint configurations to multiple strategic players, representing different applications, with the goal of aligning their incentives toward a stable outcome. This interaction is modeled as a learned optimization with an equilibrium constraint in which the central optimizer learns the utility functions through sequential, multi-fidelity evaluations with the goal of identifying a pure Nash equilibrium (PNE). To address this challenge, we propose MF-UCB-PNE, a novel multi-fidelity Bayesian optimization strategy that leverages a budget-constrained sampling process to approximate PNE solutions. MF-UCB-PNE systematically balances exploration across low-cost approximations with high-fidelity exploitation steps, enabling efficient convergence to incentive-compatible configurations. We provide theoretical and empirical insights into the trade-offs between query cost and equilibrium accuracy, demonstrating the effectiveness of MF-UCB-PNE in identifying effective equilibrium solutions under limited cost budgets.