2026

最新文章

• Adaptive Learning in Uncertain and Sequential Competition AI翻译
  作者：Li, Shukai; Mehrotra, Sanjay
  作者单位：New York University; NYU Shanghai; Northwestern University
  摘要：We investigate an individual's decision-making problem in a competitive and uncertain environment, where N learners (decision makers) confront unknown objective functions, lack competitor data, and optimize actions over a finite horizon of T epochs. Within a general framework, we explore what conditions ensure good performance of learning policies solely based on individual data. We show that when learner objective functions exhibit a tatonnement stability property and individual data are info...
• Foresee the Next Line: Customer Strategies and Information Disclosure in Tandem Queues AI翻译
  作者：Snitkovsky, Ran; Roet-Green, Ricky; Ji, Jingwei
  作者单位：Tel Aviv University; University of Rochester; Stanford University
  摘要：Many services consist of multiple stages, where each stage requires some waiting before completion. For example, customers who visit the Apple Store join the check-in queue first and then wait in another queue to be served by the Genius Bar technician. In such settings, customers often see the queue directly ahead of them but not the one in the next stage. Our paper aims to examine the impact of queue-length information on customers' strategic behavior in such systems. We assume a two-stage ta...
• A Low-Rank Augmented Lagrangian Method for Doubly Nonnegative Relaxations of Mixed-Binary Quadratic Programs AI翻译
  作者：Hou, Di; Tang, Tianyun; Toh, Kim-Chuan
  作者单位：National University of Singapore; National University of Singapore
  摘要：Doubly nonnegative (DNN) programming problems are challenging to solve because of their huge number of ohm(n2) constraints and ohm(n2) variables. In this work, introduce RiNNAL, a method for solving DNN relaxations of large-scale mixed-binary quadratic programs by leveraging their solutions' possible low-rank property. RiNNAL a globally convergent Riemannian augmented Lagrangian method (ALM) that penalizes the nonnegativity and complementarity constraints while preserving all other constraints...
• Capacity Planning in Stable Matching AI翻译
  作者：Bobbio, Federico; Carvalho, Margarida; Lodi, Andrea; Ricos, Ignacio; Torrico, Alfredo
  作者单位：Universite de Montreal; Universite de Montreal; Technion Israel Institute of Technology; University of Texas System; University of Texas Dallas; Cornell University
  摘要：Motivated by the shortage of seats that the Chilean school choice system is facing, we introduce the problem of jointly increasing school capacities and finding a studentoptimal assignment in the expanded market. Because of the theoretical and practical complexity of the problem, we provide a comprehensive set of tools to solve the problem, including different mathematical programming formulations, a cutting-plane algorithm, and two heuristics that allow obtaining near-optimal solutions quickl...
• Dynamic Pricing for Reusable Resources: The Power of Two Prices AI翻译
  作者：Balseiro, Santiago R.; Ma, Will; Zhang, Wenxin
  作者单位：Columbia University
  摘要：Motivated by real-world applications, such as rental and cloud computing services, we investigate pricing for reusable resources. We consider a system where a single resource with a fixed number of identical copies serves customers with heterogeneous willingness to pay (WTP), and the usage duration distribution is general. Optimal dynamic policies are computationally intractable when usage durations are not memoryless, so the existing literature has focused on static pricing, which incurs a st...
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model AI翻译
  作者：Shi, Laixi; Li, Gen; Wei, Yuting; Chen, Yuxin; Geist, Matthieu; Chi, Yuejie
  作者单位：Johns Hopkins University; Chinese University of Hong Kong; University of Pennsylvania; Yale University
  摘要：This paper investigates model robustness in reinforcement learning (RL) to reduce the sim-to-real gap in practice. We adopt the framework of distributionally robust Markov decision processes (RMDPs), aimed at learning a policy that optimizes the worst-case performance when the deployed environment falls within a prescribed uncertainty set around the nominal Markov decision process (MDP). Despite recent efforts, the sample complexity of RMDPs remained mostly unsettled regardless of the uncertai...
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives AI翻译
  作者：Behdin, Kayhan; Chen, Wenyu; Mazumder, Rahul
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We consider the problem of learning a sparse graph underlying an undirected Gaussian graphical model, which is a key problem in statistical machine learning. Given n samples from a multivariate Gaussian distribution with p variables, the goal is to estimate the p x p inverse covariance matrix (aka precision matrix), assuming it is sparse (i.e., has a few nonzero entries). We propose GraphL0BnB, a new estimator based on an & euro;0-penalized version of the pseudo-likelihood function; most earli...
• On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization AI翻译
  作者：Prokopyev, Oleg A.; Ralphs, Ted K.
  作者单位：University of Zurich; Lehigh University
  摘要：We consider the computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader's perspective. We show that, for any constant c > 0, the problem of finding a leader's solution that is within Euclidean distance c(n) of any locally optimal leader's solution, where n is the total number of variables, is NP-hard. Our derivations exploit techniques similar to those used for the analogous result for quadratic optimization problems (QPs). ...
• Integrated Conditional Estimation-Optimization AI翻译
  作者：Qi, Meng; Grigas, Paul; Shen, Zuo-Jun (max)
  作者单位：Cornell University; University of California System; University of California Berkeley; University of Hong Kong; University of Hong Kong
  摘要：Many real-world optimization problems involve uncertain parameters with probability distributions that can be estimated using contextual feature information. In contrast to the standard approach of first estimating the distribution of uncertain parameters and then optimizing the objective based on the estimation, we propose an integrated conditional estimation-optimization (ICEO) framework that estimates the underlying conditional distribution of the random parameter while considering the stru...
• Combating Gerrymandering with Ranked Choice Voting: An Experimental Analysis of Multimember Districts in the United States AI翻译
  作者：Garg, Nikhil; Gurnee, Wes; Rothschild, David; Shmoys, David B.
  作者单位：Cornell University; Massachusetts Institute of Technology (MIT); Microsoft
  摘要：Every representative democracy must specify a mechanism under which voters choose their representatives. The most common mechanism in the United States-winnertake-all single-member districts-both enables substantial partisan gerrymandering and constrains fair redistricting, preventing proportional representation in legislatures. We study the design of multimember districts (MMDs), in which each district elects multiple representatives, potentially through a non-winner-take-all voting rule. We ...