Víctor Verdugo

Kristóf Bérczi, Vasilis Livanos, José A. Soto et al.

The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. We introduce a bipartite graph framework that unifies and extends several known formulations, including bipartite matching, matroid intersection, and matroid secretary problems. In this model, agents and items form a bipartite graph, and the objective is to select a matching that satisfies independence constraints on both sides. We first study the free-order setting under edge-arrivals. For $k$-matroid intersection, we leverage a core lemma by [FSZ, 2022] to design an $Ω(1/k^2)$-competitive algorithm, extending known results for single matroids. Building on this, we introduce $k$-growth systems -- a new class of independence systems that lie properly between $k$-matchoids and $k$-extendible systems and may be of independent combinatorial interest. We establish a generalized core lemma for $k$-growth systems, showing that a suitably defined set of critical elements retains a $Ω(1/k^2)$ fraction of the optimal weight. Using this lemma, we extend our $Ω(1/k^2)$-competitive algorithm to $k$-growth systems. We then study the agent-arrival model, which presents unique challenges to our framework. We extend the core lemma to this model and then apply it to obtain an $Ω(β/k^2)$-competitive algorithm for $k$-growth systems, where $β$ denotes the competitiveness of an appropriate type of order-oblivious algorithm for the item-side constraint. Finally, we extend our results to the case of multiple item selection, and obtain constant-competitive algorithms for fundamental cases such as partition matroids and $k$-matching constraints. We also study the closure properties and structural role and of $k$-growth systems within the hierarchy of $k$-systems.

Jasper van Doornmalen, Mathieu Molina, Victor Verdugo et al.

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform $L_\infty$-error guarantees rather than the usual $L_2$-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most $d$ on $n$ variables, the sample complexity scales as $n^{d+1}$. Second, for $s$-sparse Fourier-Walsh polynomials with $s \leq n$, it scales as $ns^2$. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as $n^d$ and $ns$, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the $L_2$-norm do not naturally extend to the $L_\infty$-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the $L_\infty$-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.

Alejandro Jofré, Angel Pardo, David Salas et al.

Understanding the strategic behavior of miners in a blockchain is of great importance for its proper operation. A common model for mining games considers an infinite time horizon, with players optimizing asymptotic average objectives. Implicitly, this assumes that the asymptotic behaviors are realized at human-scale times, otherwise invalidating current models. We study the mining game utilizing Markov Decision Processes. Our approach allows us to describe the asymptotic behavior of the game in terms of the stationary distribution of the induced Markov chain. We focus on a model with two players under immediate release, assuming two different objectives: the (asymptotic) average reward per turn and the (asymptotic) percentage of obtained blocks. Using tools from Markov chain analysis, we show the existence of a strategy achieving slow mixing times, exponential in the policy parameters. This result emphasizes the imperative need to understand convergence rates in mining games, validating the standard models. Towards this end, we provide upper bounds for the mixing time of certain meaningful classes of strategies. This result yields criteria for establishing that long-term averaged functions are coherent as payoff functions. Moreover, by studying hitting times, we provide a criterion to validate the common simplification of considering finite states models. For both considered objectives functions, we provide explicit formulae depending on the stationary distribution of the underlying Markov chain. In particular, this shows that both mentioned objectives are not equivalent. Finally, we perform a market share case study in a particular regime of the game. More precisely, we show that an strategic player with a sufficiently large processing power can impose negative revenue on honest players.