-
作者：Vardi, Shai; Haskell, William
作者单位：Purdue University System; Purdue University
摘要：Scarce resources are often shared between different stakeholders and need to be scheduled fairly among them. In this paper, we study the utility loss resulting from requiring the schedule to be fair, using the price of fairness-the ratio of the utility attainable with and without fairness restrictions. We focus on envy-freeness, an intuitive and well-studied fairness notion. We derive tight bounds on the price of fairness as a function of the problem parameters: the number of agents, the time ...
-
作者：Bai, Yicheng; Feldman, Jacob; Topaloglu, Huseyin; Wagner, Laura
作者单位：Washington University (WUSTL); University of Navarra; IESE Business School
摘要：We study assortment optimization problems under a natural variant of the multinomial logit model where the customers are willing to focus only on a certain number of products that provide the largest utilities. In particular, each customer has a rank cutoff, characterizing the number of products that she will focus on during the course of her choice process. Given that we offer a certain assortment of products, the choice process of a customer with rank cutoff k proceeds as follows. The custom...
-
作者：Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis
作者单位：University of Washington; University of Washington Seattle
摘要：For some epsilon > 10(-36), we give a randomized 3/2 - epsilon approximation algorithm for metric TSP.
-
作者：Li, Gen; Wei, Yuting; Chi, Yuejie; Chen, Yuxin
作者单位：University of Pennsylvania; Carnegie Mellon University; University of Pennsylvania
摘要：This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator). We first consider gamma-discounted infinite-horizon Markov decision processes (MDPs) with state space S and action space A. Despite a number of prior works tackling this problem, a complete picture of the trade-offs between sample complexity and statistical accuracy has yet to be determined. In particular, all prior results suffer from a severe sample size barrier...
-
作者：Adler, Nicole; Olesen, Ole Bent; Volta, Nicola
作者单位：Hebrew University of Jerusalem; University of Southern Denmark; Cranfield University
摘要：Horizontal mergers and acquisitions offer firms the means to grow. However, forecasting these actions' potential effects on the market is not a simple task. We propose a model that identifies optimal horizontal merger configurations for an industry. The model endogenizes the merger choice by maximizing the overall potential efficiency gain at the level of an industry or firm with multiple branches. We further extend the model to consider mergers that create contiguous firms, should network eff...
-
作者：Lo, Andrew W.; Wu, Lan; Zhang, Ruixun; Zhao, Chaoyi
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); The Santa Fe Institute; Peking University; Peking University; Peking University; Peking University
摘要：We develop a mathematical framework for constructing optimal impact portfolios and quantifying their financial performance by characterizing the returns of impactranked assets using induced order statistics and copulas. The distribution of induced order statistics can be represented by a mixture of order statistics and uniformly distributed random variables, where the mixture function is determined by the dependence structure between residual returns and impact factors-characterized by copulas...
-
作者：Light, Bar; Johari, Ramesh; Weintraub, Gabriel
作者单位：Tel Aviv University; Stanford University; Stanford University
摘要：Online platforms collect rich information about participants and then share some of this information back with them to improve market outcomes. In this paper, we study the following information disclosure problem in two-sided markets: if a platform wants to maximize revenue, which sellers should the platform allow to participate, and how much of its available information about participating sellers' quality should the platform share with buyers? We study this information disclosure problem in ...
-
作者：Chen, Zhi; Hu, Zhenyu; Wang, Ruiqin
作者单位：Chinese University of Hong Kong; National University of Singapore; National University of Singapore
摘要：Consider a seller seeking a selling mechanism to maximize the worst-case revenue obtained from a buyer whose valuation distribution lies in a certain ambiguity set. Such a mechanism design problem with one product and one buyer is known as the screening problem. For a generic convex ambiguity set, we show via the minimax theorem that strong duality holds between the problem of finding the optimal robust mechanism and a minimax pricing problem where the adversary first chooses a worst-case dist...
-
作者：Perakis, Georgia; Singhvi, Divya
作者单位：Massachusetts Institute of Technology (MIT); New York University
摘要：We consider the dynamic pricing problem of a retailer who does not have any information on the underlying demand for a product. The retailer aims to maximize cumulative revenue collected over a finite time horizon by balancing two objectives: learning demand and maximizing revenue. The retailer also seeks to reduce the amount of price experimentation because of the potential costs associated with price changes. Existing literature solves this problem in the case where the unknown demand is par...
-
作者：Li, Yongchun; Xie, Weijun
摘要：This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to develop a sampling algorithm and derive its approximation bound for MESP, which improves the best know...
