-
作者：Reed, Josh; Shaki, Yair
作者单位：New York University; Technion Israel Institute of Technology
摘要：We consider the G / GI / N queue with multiple server pools, each possessing a pool-specific service time distribution. The class of nonidling routing policies that we consider are referred to as u-greedy policies. These policies route incoming customers to the server pool with the longest weighted cumulative idle time to equitably spread incoming work amongst the server pools in the system. Our first set of results demonstrates that asymptotically in the Halfin-Whitt regime and under any u-gr...
-
作者：Perchet, Vianney; Quincampoix, Marc
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Sorbonne Universite; Universite Paris Cite; Universite de Bretagne Occidentale; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：We represent any repeated game with partial monitoring as an abstract repeated game with full monitoring where outcomes are probability measures, to be interpreted as the maximal information the players can obtain in the original game. One of our objectives is to define and generalize Blackwell's approachability theory in this space of probability measures. We characterize approachable sets with, as usual, a simple and complete formulation for convex sets. Translated back into the original gam...
-
作者：Bhaskar, Umang; Fleischer, Lisa; Hoy, Darrell; Huang, Chien-Chung
作者单位：California Institute of Technology; Dartmouth College; Northwestern University; Chalmers University of Technology
摘要：In routing games with infinitesimal players, it follows from well-known convexity arguments that equilibria exist and are unique. In routing games with atomic players with splittable flow, equilibria exist, but uniqueness of equilibria has been demonstrated only in limited cases: in two-terminal nearly parallel graphs, when all players control the same amount of flow, and when latency functions are polynomials of degree at most three. There are no known examples of multiple equilibria in these...
-
作者：Huynh Van Ngai; Phan Nhat Tinh
作者单位：Hue University
摘要：Metric subregularity and regularity of multifunctions are fundamental notions in variational analysis and optimization. Using the concept of strong slope, in this paper we first establish a criterion for metric subregularity of multifunctions between metric spaces. Next, we use a combination of abstract coderivatives and contingent derivatives to derive verifiable first order conditions ensuring metric subregularity of multifunctions between Banach spaces. Then using second order approximation...
-
作者：Elmachtoub, Adam N.; Levi, Retsef
作者单位：Columbia University; Massachusetts Institute of Technology (MIT)
摘要：We consider a general class of online optimization problems, called online selection problems, where customers arrive sequentially, and one has to decide upon arrival whether to accept or reject each customer. If a customer is rejected, then a rejection cost is incurred. The accepted customers are served with minimum possible cost, either online or after all customers have arrived. The goal is to minimize the total production costs for the accepted customers plus the rejection costs for the re...
-
作者：Bauso, Dario; Lehrer, Ehud; Solan, Eilon; Venel, Xavier
作者单位：University of Palermo; Tel Aviv University; INSEAD Business School
摘要：We introduce the concept of attainable sets of payoffs in two-player repeated games with vector payoffs. A set of payoff vectors is called attainable by a player if there is a positive integer such that the player can guarantee that in all finite game longer than that integer, the distance between the set and the cumulative payoff is arbitrarily small, regardless of the strategy Player 2 is using. We provide a necessary and sufficient condition for the attainability of a convex set, using the ...
-
作者：Braun, Gabor; Fiorini, Samuel; Pokutta, Sebastian; Steurer, David
作者单位：University System of Georgia; Georgia Institute of Technology; Universite Libre de Bruxelles; Cornell University
摘要：We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n(1/2-is an element of))-approximations for CLIQUE require LPs of size 2(n Omega(is an element of)). This lower bound applies to LPs using a certain ...
-
作者：Chen, Xin; Peng, Jiming
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Houston System; University of Houston
摘要：The standard quadratic optimization problem (StQP) refers to the problem of minimizing a quadratic form over the standard simplex. Such a problem arises from numerous applications and is known to be NP-hard. In a recent paper [Chen X, Peng J, Zhang S (2013) Sparse solutions to random standard quadratic optimization problems. Math. Programming 141(1-2): 273-293], Chen, et al. showed that with a high probability close to 1, StQPs with random data have sparse optimal solutions when the associated...
-
作者：Coucheney, Pierre; Gaujal, Bruno; Mertikopoulos, Panayotis
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Saclay; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：Starting from a heuristic learning scheme for strategic N-person games, we derive a new class of continuous-time learning dynamics consisting of a replicator-like drift adjusted by a penalty term that renders the boundary of the game's strategy space repelling. These penalty-regulated dynamics are equivalent to players keeping an exponentially discounted aggregate of their ongoing payoffs and then using a smooth best response to pick an action based on these performance scores. Owing to this i...
-
作者：He, Xue Dong; Jin, Hanqing; Zhou, Xun Yu
作者单位：Columbia University; University of Oxford; University of Oxford; University of Oxford
摘要：We seek to characterize the trading behavior of an agent, in the context of a continuous-time portfolio choice model, if she measures the risk by a so called weighted value-at-risk (VaR), which is a generalization of both VaR and conditional VaR. We show that when bankruptcy is allowed the agent displays extreme risk-taking behaviors, unless the downside risk is significantly penalized, in which case an asymptotically optimal strategy is to invest a very small amount of money in an extremely r...
