-
作者：Chan, Timothy C. Y.; Mahmood, Rafid; Zhu, Ian Yihang
作者单位：University of Toronto; University of Ottawa; National University of Singapore
摘要：Inverse optimization describes a process that is the reverse of traditional mathematical optimization. Unlike traditional optimization, which seeks to compute optimal decisions given an objective and constraints, inverse optimization takes decisions as input and determines objective and/or constraint parameters that render these decisions approximately or exactly optimal. In recent years, there has been an explosion of interest in the mathematics and applications of inverse optimization. This ...
-
作者：Shahmizad, Maral; Buchanan, Austin
作者单位：Oklahoma State University System; Oklahoma State University - Stillwater
摘要：When partitioning a state into political districts, a common criterion is that political subdivisions, like counties, should not be split across multiple districts. This criterion is encoded into most state constitutions and is sometimes enforced quite strictly by the courts. However, map drawers, courts, and the public typically do not know what amount of splitting is truly necessary, even to satisfy basic criteria, like contiguity and population balance. In this paper, we provide answers for...
-
作者：Cai, Jun; Li, Jonathan Yu-Meng; Mao, Tiantian
作者单位：University of Waterloo; University of Ottawa; Chinese Academy of Sciences; University of Science & Technology of China, CAS
摘要：Distributionally robust optimization (DRO) has arisen as an important paradigm for addressing the issue of distributional ambiguity in decision optimization. In the case in which a decision maker is not risk neutral, the most common scheme applied in DRO for capturing the risk attitude is to employ an expected utility functional. In this paper, we propose to address a decision maker's risk attitude in DRO by following an alternative scheme known as dual expected utility. In this scheme, a dist...
-
作者：Xu, Guanglin; Hanasusanto, Grani A.
作者单位：University of North Carolina; University of North Carolina Charlotte; University of Minnesota System; University of Minnesota Twin Cities; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We study decision rule approximations for generic multistage robust linear optimization problems. We examine linear decision rules for the case when the objective coefficients, the recourse matrices, and the right-hand sides are uncertain, and we explore quadratic decision rules for the case when only the right-hand sides are uncertain. The resulting optimization problems are NP hard but amenable to copositive programming reformulations that give rise to tight, tractable semidefinite programmi...
-
作者：Feng, Qing; Zhu, Ruihao; Jasin, Stefanus
作者单位：Cornell University; Cornell University; University of Michigan System; University of Michigan
摘要：Motivated by the prevalence of price protection guarantee which helps to promote temporal fairness in dynamic pricing, we study the impact of such policy on the design of online learning algorithms for data-driven dynamic pricing with initially unknown customer demand. Under the price protection guarantee, a customer who purchased a product in the past can receive a refund from the seller during the so-called price protection period (typically defined as a certain time window after the purchas...
-
作者：Mueller, Alfred; Scarsini, Marco; Tsetlin, Ilia; Winkler, Robert L.
作者单位：Universitat Siegen; Luiss Guido Carli University; INSEAD Business School; Duke University
摘要：Most often, important decisions involve several unknown attributes. This produces a double challenge in the sense that both assessing the individual multiattribute preferences and assessing the joint distribution of the attributes can be extremely hard. To handle the first challenge, we suggest multivariate almost stochastic dominance, a relation based on bounding marginal utilities. We provide necessary and sufficient characterizations in terms of simple transfers, which are easily communicat...
-
作者：Akrami, Hannaneh; Alon, Noga; Chaudhury, Bhaskar Ray; Garg, Jugal; Mehlhorn, Kurt; Mehta, Ruta
作者单位：Max Planck Society; Saarland University; Princeton University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：The existence of envy-freeness up to any good (EFX) allocations is a fundamental open problem in discrete fair division. The goal is to determine the existence of an allocation of a set of indivisible goods among n agents for which no agent envies another, following the removal of any single good from the other agent's bundle. Because the general problem has been elusive, progress is made on two fronts: (i) proving existence when n is small and (ii) proving the existence of relaxations of EFX....
-
作者：Alpern, Steve; Lidbetter, Thomas
作者单位：University of Warwick; Rutgers University System; Rutgers University Newark; Rutgers University New Brunswick
摘要：Adversarial search of a network for an immobile Hider (or target) was introduced and solved for rooted trees by Shmuel Gal in 1979. In this zero-sum game, a Hider picks a point to hide on the tree and a Searcher picks a unit speed trajectory starting at the root. The payoff (to the Hider) is the search time. In Gal's model (and many subsequent investigations), the Searcher receives no additional information after the Hider chooses his location. In reality, the Searcher will often receive such ...
-
作者：MacRury, Calum; Ma, Will; Grammel, Nathaniel
作者单位：Columbia University; Columbia University; University System of Maryland; University of Maryland College Park
摘要：Online Contention Resolution Schemes (OCRSs) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRSs have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions-accept/reject, probing, pricing-in a unified manner. This paper analyzes OCRSs for resource constraints defined by matchings...
-
作者：Brubach, Brian; Grammel, Nathaniel; Ma, Will; Srinivasan, Aravind
作者单位：Wellesley College; University System of Maryland; University of Maryland College Park; Columbia University; Columbia University
摘要：We study generalizations of online bipartite matching in which each arriving vertex (customer) views a ranked list of offline vertices (products) and matches to (purchases) the first one they deem acceptable. The number of products that the customer has patience to view can be stochastic and dependent on the products seen. We develop a framework that views the interaction with each customer as an abstract resource consumption process and derive new results for these online matching problems un...
