Mathematics of Operations Research

最新文章

• Risk Sharing with Lambda Value at Risk AI翻译
  作者：Liu, Peng
  作者单位：University of Essex
  摘要：In this paper, we study the risk-sharing problem among multiple agents using lambda value at risk (AVaR) as their preferences via the tool of inf-convolution, where AVaR is an extension of value at risk (VaR). We obtain explicit formulas of the infconvolution of multiple AVaR with monotone A and explicit forms of the corresponding optimal allocations, extending the results of the inf-convolution of VaR. It turns out that the inf-convolution of several AVaR is still a AVaR under some mild condi...
• Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation AI翻译
  作者：Zhang, Brian Hu; Farina, Gabriele; Celli, Andrea; Sandholm, Tuomas
  作者单位：Carnegie Mellon University; Massachusetts Institute of Technology (MIT); Bocconi University
  摘要：We study the problem of finding optimal correlated equilibria of various sorts in extensive-form games: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarse correlated equilibrium (EFCCE), and extensive-form correlated equilibrium (EFCE). We make two primary contributions. First, we introduce a new algorithm for computing optimal equilibria in all three notions. Its runtime depends exponentially only on a parameter related to the information structure of the game. We also p...
• Envy-Free Division of Multilayered Cakes AI翻译
  作者：Igarashi, Ayumi; Meunier, Frederic
  作者单位：University of Tokyo; Institut Polytechnique de Paris; Ecole des Ponts ParisTech
  摘要：Dividing a multilayered cake under nonoverlapping constraints captures several scenarios (e.g., allocating multiple facilities over time where each agent can utilize at most one facility simultaneously). We establish the existence of an envy-free multi-division that is nonoverlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. [Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake...
• Risk-Averse Markov Decision Processes Through a Distributional Lens AI翻译
  作者：Cheng, Ziteng; Jaimungal, Stian
  作者单位：University of Toronto
  摘要：By adopting a distributional viewpoint on law-invariant convex risk measures, we construct dynamic risk measures (DRMs) at the distributional level. We then apply these DRMs to investigate Markov decision processes, incorporating latent costs, random actions, and weakly continuous transition kernels. Furthermore, the proposed DRMs allow risk aversion to change dynamically. Under mild assumptions, we derive a dynamic programming principle and show the existence of an optimal policy in both fini...
• Confidence Intervals for Piecewise Normal Distributions and Stochastic Variational Inequalities AI翻译
  作者：Lu, Shu
  摘要：In this paper, we first show how to obtain easy -to -compute confidence intervals for the center of a piecewise normal distribution given a sample from this distribution (assuming that the center belongs to a known affine set parallel to the common lineality space of all cones defining the piecewise normal distribution) by using certain skewed projectors on that space. We then extend this method to an asymptotic setting. Next, we apply this method to compute confidence intervals for the true s...
• Liquid Welfare Guarantees for No-Regret Learning in Sequential Budgeted Auctions AI翻译
  作者：Fikioris, Giannis; Tardos, Eva
  作者单位：Cornell University
  摘要：We study the liquid welfare in sequential first-price auctions with budgeted buyers. We use a behavioral model for the buyers, assuming a learning style guarantee: the utility of each buyer is within a gamma factor (gamma >_ 1) of the utility achievable by shading their value with the same factor at each iteration. We show a gamma + 1/2 + O(1/gamma) price of anarchy for liquid welfare when valuations are additive. This is in stark contrast to sequential second-price auctions, where the resulti...
• Many-Server Asymptotics for Join-the-Shortest-Queue in the Super-Halfin-Whitt Scaling Window AI翻译
  作者：Zhao, Zhisheng; Banerjee, Sayan; Mukherjee, Debankur
  作者单位：University System of Georgia; Georgia Institute of Technology; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
  摘要：Join-the-shortest queue (JSQ) is a classical benchmark for the performance of parallel-server queueing systems because of its strong optimality properties. Recently, there has been significant progress in understanding its large-system asymptotic behavior. In this paper, we analyze the JSQ policy in the super-Halfin-Whitt scaling window when load per server scales with the system size N as lim(->infinity) (1 - ) = for is an element of (1/2, 1) and > 0. We establish that the centered and scaled...
• Improved Bounds for Single-Nomination Impartial Selection AI翻译
  作者：Cembrano, Javier; Fischer, Felix; Klimm, Max
  作者单位：Max Planck Society; Technical University of Berlin; University of London; Queen Mary University London
  摘要：A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and alpha-optimal if the expected number of nominations received by the selected individual is always at least alpha times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is 1/2-optimal, and this is the bes...
• Tightness Without Counterexamples: A New Approach and New Results for Prophet Inequalities AI翻译
  作者：Jiang, Jiashuo; Ma, Will; Zhang, Jiawei
  作者单位：Hong Kong University of Science & Technology; Columbia University; New York University
  摘要：Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some ingenuity. In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds ...
• Upper Bounds for All and Max-Gain Policy Iteration Algorithms on Deterministic MDPs AI翻译
  作者：Goenka, Ritesh; Gupta, Eashan; Khyalia, Sushil; Kalyanakrishnan, Shivaram
  作者单位：University of Oxford; University of Illinois System; University of Illinois Urbana-Champaign; Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
  摘要：Policy iteration (PI) is a widely used family of algorithms to compute optimal policies for Markov decision problems (MDPs). Howard's [Howard RA (1960) Dynamic Programming and Markov Processes (MIT Press, Cambridge, MA)] PI is one of the most commonly used algorithms from this family. Despite its popularity, theoretical analysis of the running-time complexity of Howard's PI has remained elusive. For n-state, two-action MDPs, the best known lower and upper bounds are ohm(n) and O(2n/n) iteratio...