Knowledge that Transforms

Data envelopment analysis (DEA) is an optimization-based methodology used for the assessment of efficiency of organizations. Traditional DEA models are based on the vectors of inputs (resources) and outputs (products or services) of the observed organizations. DEA models are often enhanced by additional value judgements stated as tradeoffs between inputs and outputs or as dual weight restrictions. In the paper “Proper and consistent production trade-offs in models of data envelopment analysis”, Podinovski and Papaioannou showed that such additional value judgments may be contradictory (not proper) and develop analytical and computational tests for their identification. Any value judgments that are not proper indicate an error in their assessment. The developed approach is equally applicable in multicriteria decision analysis in which the tradeoffs between criteria are specified imprecisely by a set of linear inequalities stated in terms of criterion weights. Not proper tradeoffs result in the weights of some criteria (identifiable by the developed computational approach) being equal to zero, which effectively excludes such criteria from the analysis.

Epidemic Forecasting on Networks: Bridging Local Samples with Global Outcomes Forecasting how an epidemic will unfold, its trajectory and eventual size, usually presumes access to the full contact network. In practice, no one ever has the full mapping of networks. New research shows that full mapping is unnecessary. By observing only the local neighborhoods around a small number of individuals, the kind of partial data that can actually be collected during an epidemic, the authors prove that global outcomes, such as the eventual size of an epidemic, can be predicted with rigorous accuracy guarantees. The work formally connects what public health planners can observe locally—for example, connections revealed by contact tracing and similar methods—to how an epidemic behaves globally, giving them a principled way to turn limited, realistic data into reliable forecasts.

Novel Insights on Robust Markov decision Processes with Average Reward and Blackwell Optimality Criteria Robust Markov decision processes (RMDPs) have been studied extensively when the objective is the discounted return, but little is known for average optimality and Blackwell optimality. We show that average optimal policies can be chosen stationary and deterministic for sa-rectangular RMDPs, but perhaps surprisingly, we show that for s-rectangular RMDPs average optimal policies may not exist, and if they do exist, they may not be stationary. We also study Blackwell optimality for sa-rectangular RMDPs, where we show that approximately Blackwell optimal policies always exist, although exact Blackwell optimal policies may not exist. We provide a general sufficient condition for their existence. We then discuss the connection between average and Blackwell optimality, and we describe several algorithms to compute the optimal average return. Interestingly, our approach leverages the connections between RMDPs and stochastic games. Overall, our paper emphasizes the superior practical properties of distance-based sa-rectangular models over s-rectangular models for average and Blackwell optimality.

On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

Diagnosing Why Models Fail Under Distribution Shift and What to Do Next Predictive models often perform worse when deployed in a new target setting, but it is rarely clear why. In “Diagnosing Model Performance Under Distribution Shift,” Cai, Namkoong, and Yadlowsky introduce a diagnostic, distribution shift decomposition (DISDE), that attributes the change in performance from the training to target distributions into terms for (i) an increase in harder but previously seen inputs from training, (ii) changes in how outcomes relate to inputs, and (iii) poor performance on new input regions absent from the training data. Applications to employment prediction demonstrate how this decomposition can inform potential modeling improvements, guiding whether to use domain adaptation techniques, adjust model covariates, or collect new samples. Additionally, DISDE is used to help explain why certain domain adaptation methods fail to improve model performance for satellite image classification.

Certifying Submodularity with Algebraic Techniques Submodularity is a structural property encoding the notion of diminishing returns, that is, the benefits one gets from an additional element decrease when many elements have been chosen. This property appears in many applications, from operations research to machine learning and economics. Unfortunately, testing whether a set function is submodular is computationally intractable for set functions of degree 4 or higher. In “Sum of Squares Submodularity,” Anna Deza and Georgina Hall introduce the notion of t-sum of squares submodularity, a hierarchy of algebraic certificates that provides tractable sufficient conditions for submodularity. For each fixed level t, membership in the hierarchy can be checked through semidefinite programming. The paper develops equivalent characterizations of the hierarchy, identifies operations that preserve it, and clarifies when it coincides with submodularity. It also demonstrates practical value in three settings: submodular regression, bounding submodularity ratios for approximate maximization, and constructing improved difference of submodular decompositions.

Nature Doesn’t Play Dice, It Plays to Win Decision making under uncertainty can be brittle, often failing when real-world data deviates from training assumptions. This study frames this problem as a game between a decision maker and an adversary, nature, who strategically corrupts the data distribution to create a worst case scenario with the cost of these changes defined by optimal transport theory. The authors establish conditions under which a stable outcome, a Nash equilibrium, exists and provide efficient methods to compute it. A key insight is that nature’s optimal strategy corresponds to generating remarkably deceptive adversarial examples; in an image classification task, this strategy can transform an image of an “8” into a convincing “3.” This work provides a powerful framework for developing more reliable models by understanding and countering worst case data perturbations.

Randomized Apportionment: A Fairer Distribution of Seats The question of how to apportion the seats of the U.S. House of Representatives to states has fueled century-long political debates and sparked mathematical theory. Traditional deterministic methods, such as the Hamilton method or the currently used Huntington–Hill method, may result in paradoxes or substantially deviate from proportionality. In their paper “In This Apportionment Lottery, the House Always Wins,” Gölz, Peters, and Procaccia propose a randomized approach that ensures each state receives its exact proportional share of seats in expectation and its proportional share, up to rounding, ex post. By incorporating randomization, the authors argue, the system can better adhere to the principle of proportional representation, minimizing the impact of small counting errors and ensuring fairness over time. In addition, their approach achieves house monotonicity, a property that prevents counterintuitive outcomes when the total number of seats changes. This is achieved through a novel cumulative rounding technique, a generalization of dependent rounding on bipartite graphs with potential applications beyond apportionment, including EU commission nominations and resource allocation.

Day-ahead electricity auctions allow market participants to trade power for delivery the following day. In Europe, these auctions are designed as combinatorial auctions, enabling agents to submit package bids (“block bids”) that span multiple time periods rather than bidding separately for each hour. However, power exchanges impose limits on the number of package bids an agent can submit, creating a complex decision problem: Which packages should an agent bid on to best represent their preferences? In “Package Bids in Combinatorial Electricity Auctions: Selection, Welfare Losses, and Alternatives,” Hübner and Hug study this selection problem and propose decision-support algorithms that optimize bid choice under uncertainty. They provide theoretical bounds on welfare loss due to bid limits and validate their methods with simulations involving generators, storage systems, and flexible demand. Their findings offer actionable insights for both auctioneers and bidders.

Performance of a queueing system with scheduled arrivals A scheduled arrival sequence is one in which customers are scheduled to arrive at constant interarrival times, but each customer’s actual arrival time is perturbed from her scheduled arrival time by a random perturbation. In “Stability of a Queue Fed by Scheduled Traffic at Critical Loading”, V.F. Araman and P.W. Glynn consider a single server queue with deterministic service times in which customers arrive following a scheduled arrival process. Unlike a queue fed by renewal traffic, this queue is shown to be stable even when the utilization is equal to one. It is also shown that for finite mean perturbations, a necessary and sufficient condition for stability is when the positive part of the perturbation has bounded support, with no requirement on the negative part of the perturbation. Perhaps surprisingly, this criterion is not reversible, in the sense that such a queue can be stable for a scheduled traffic process in forward time, but unstable for the time-reversal of the same traffic process.