-
作者：Chen, Xi; Miao, Sentao; Wang, Yining
作者单位：New York University; McGill University; University of Texas System; University of Texas Dallas
摘要：In recent decades, the advance of information technology and abundant personal data facilitate the application of algorithmic personalized pricing. However, this leads to the growing concern of potential violation of privacy because of adversarial attack. To address the privacy issue, this paper studies a dynamic personalized pricing problem with unknown nonparametric demand models under data privacy protection. Two concepts of data privacy, which have been widely applied in practices, are int...
-
作者：Goyal, Vineet; Udwani, Rajan
作者单位：Columbia University; University of California System; University of California Berkeley
摘要：The problem of online matching with stochastic rewards is a generalization of the online bipartitematching problemwhere each edge has a probability of success. When a match is made it succeeds with the probability of the corresponding edge. We consider the more general vertex-weighted version of the problem and give two new results. First, we show that a natural generalization of the perturbed-greedy algorithm is (1 - 1/e) competitive when probabilities decompose as a product of two factors, o...
-
作者：Swamy, Rahul; King, Douglas M.; Jacobson, Sheldon H.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Political districting in the United States is a decennial process of redrawing the boundaries of congressional and state legislative districts. The notion of fairness in political districting has been an important topic of subjective debate, with district plans affecting a wide range of stakeholders, including the voters, candidates, and political parties. Even though districting as an optimization problem has been well studied, existing models primarily rely on nonpolitical fairness measures ...
-
作者：Goyal, Vineet; Grand-Clement, Julien
作者单位：Columbia University
摘要：Markov decision processes (MDPs) are used to model stochastic systems in many applications. Several efficient algorithms to compute optimal policies have been studied in the literature, including value iteration (VI) and policy iteration. However, these do not scale well, especially when the discount factor for the infinite horizon discounted reward, lambda, gets close to one. In particular, the running time scales as O (1=(1 - lambda)) for these algorithms. In this paper, our goal is to desig...
-
作者：Behnezhad, Soheil; Dehghani, Sina; Derakhshan, Mahsa; Hajiaghayi, Mohammedtaghi; Seddighin, Saeed
作者单位：University System of Maryland; University of Maryland College Park
摘要：In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each battlefield is determined independently by a winner-takes-all rule. The ultimate payoff for each colonel is the number of battlefields won. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S. Presidential election to innovative technology competitions to advertising, sport...
-
作者：Rostami, Borzou; Errico, Fausto; Lodi, Andrea
作者单位：Wilfrid Laurier University; Universite de Montreal; Polytechnique Montreal; University of Quebec; Ecole de Technologie Superieure - Canada; Cornell University
摘要：In this paper, we propose a general modeling and solving framework for a large class of binary quadratic programs subject to variable partitioning constraints. Problems in this class have a wide range of applications as many binary quadratic programs with linear constraints can be represented in this form. By exploiting the structure of the partitioning constraints, we propose mixed-integer nonlinear programming (MINLP) and mixedinteger linear programming (MILP) reformulations and show the rel...
-
作者：Garg, Jugal; Vegh, Laszlo A.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of London; London School Economics & Political Science
摘要：We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly polynomial Duan-Mehlhorn (DM) algorithm. We use the DMalgorithm as a subroutine to identify revealed edges-that is, pairs of agents and goods that must correspond to the best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if ther...
-
作者：Nakahira, Yorie; Ferragut, Andres; Wierman, Adam
作者单位：Carnegie Mellon University; University ORT Uruguay; California Institute of Technology
摘要：Many modern schedulers can dynamically adjust their service capacity to match the incoming workload. At the same time, however, unpredictability and instability in service capacity often incur operational and infrastructural costs. In this paper, we seek to characterize optimal distributed algorithms that maximize the predictability, stability, or both when scheduling jobs with deadlines. Specifically, we show that Exact Scheduling minimizes both the stationary mean and variance of the service...
-
作者：Hmedi, Hassan; Arapostathis, Ari; Pang, Guodong
作者单位：University of Texas System; University of Texas Austin; Rice University
摘要：We introduce a system-wide safety staffing (SWSS) parameter for multiclass multipool networks of any tree topology, Markovian or non-Markovian, in the Halfin-Whitt regime. This parameter can be regarded as the optimal reallocation of the capacity fluctuations (positive or negative) of order root n when each server pool uses a square-root staffing rule. We provide an explicit formof the SWSS as a function of the systemparameters, which is derived using a graph theoretic approach based on Gaussi...
-
作者：Liu, Junyi; Pang, Jong-Shi
作者单位：Tsinghua University; University of Southern California
摘要：This paper proposes the use of a variant of the conditional value-at-risk (CVaR) risk measure, called the interval conditional value-at-risk (In-CVaR), for the treatment of outliers in statistical learning by excluding the risks associated with the left and right tails of the loss. The risk-based robust learning task is to minimize the In-CVaR risk measure of a random functional that is the composite of a piecewise affine loss function with a potentially nonsmooth difference-of-convex statisti...
