Renata Valieva

David G. Harris, George Z. Li, Nitya Raju et al.

Many optimization and scheduling problems can be abstracted in terms of a bipartite ``assignment graph" $G = (L \cup R, E)$, where the goal is to select exactly one edge for each right-node. For example, a right-node may correspond to a job, and a left-node to a possible machine assignment. A common strategy to solve such problems is to obtain a fractional relaxation $x_e$ for each edge $e$, and then have each right-node independently select an edge with probability $x_e$. However, this may cause the left-nodes to become unevenly loaded, leading to suboptimal solutions for some problems. To address this, a number of algorithms for dependent rounding with strong negative correlation have been developed, e.g. Bansal, Srinivasan & Svensson (2021), Im & Shadloo (2020), Im & Li (2023), Harris (2024), Naor, Srinivasan & Wajc (2025). We introduce a new method for this, which we call the \emph{Dirichlet mechanism}. It is based on having each left-node draw Dirichlet random variables for its edges, and then having each right-node select an edge based on these values. This achieves quantitatively stronger negative correlation than previous algorithms, and is also simpler since it avoids the need for a tie-breaking mechanism. We illustrate the mechanism with improved approximation ratios for two problems. For oblivious online dependent rounding, we achieve a $0.68$-approximation which improves upon the previous $0.652$-approximation of Naor, Srinivasan & Wajc (2025). For the problem of scheduling jobs on unrelated machines to minimize weighted completion time, we achieve a $1.387$-approximation which improves upon the $1.398$-approximation of Harris (2024). (A recent algorithm of Li (2025) based on iterated rounding also provides a $1.36$-approximation if the weights of each job are independent of machine.)

J. M. Diederik Kruijssen, Renata Valieva, Steven N. Longmore

Decentralized learning networks aim to synthesize a single network inference from a set of raw inferences provided by multiple participants. To determine the combined inference, these networks must adopt a mapping from historical participant performance to weights, and to appropriately incentivize contributions they must adopt a mapping from performance to fair rewards. Despite the increased prevalence of decentralized learning networks, there exists no systematic study that performs a calibration of the associated free parameters. Here we present an optimization framework for key parameters governing decentralized online learning in supervised regression and classification problems. These parameters include the slope of the mapping between historical performance and participant weight, the timeframe for performance evaluation, and the slope of the mapping between performance and rewards. These parameters are optimized using a suite of numerical experiments that mimic the design of the Allora Network, but have been extended to handle classification tasks in addition to regression tasks. This setup enables a comparative analysis of parameter tuning and network performance optimization (loss minimization) across both problem types. We demonstrate how the optimal performance-weight mapping, performance timeframe, and performance-reward mapping vary with network composition and problem type. Our findings provide valuable insights for the optimization of decentralized learning protocols, and we discuss how these results can be generalized to optimize any inference synthesis-based, decentralized AI network.

J. M. Diederik Kruijssen, Renata Valieva, Kenneth Peluso et al.

In decentralized systems, it is often necessary to select an 'active' subset of participants from the total participant pool, with the goal of satisfying computational limitations or optimizing resource efficiency. This selection can sometimes be made at random, mirroring the sortition practice invented in classical antiquity aimed at achieving a high degree of statistical representativeness. However, the recent emergence of specialized decentralized networks that solve concrete coordination problems and are characterized by measurable success metrics often requires prioritizing performance optimization over representativeness. We introduce a simple algorithm for 'merit-based sortition', in which the quality of each participant influences its probability of being drafted into the active set, while simultaneously retaining representativeness by allowing inactive participants an infinite number of chances to be drafted into the active set with non-zero probability. Using a suite of numerical experiments, we demonstrate that our algorithm boosts the quality metric describing the performance of the active set by $>2$ times the intrinsic stochasticity. This implies that merit-based sortition ensures a statistically significant performance boost to the drafted, 'active' set, while retaining the property of classical, random sortition that it enables upward mobility from a much larger 'inactive' set. This way, merit-based sortition fulfils a key requirement for decentralized systems in need of performance optimization.