2021

最新文章

• Feasible Bases for a Polytope Related to the Hamilton Cycle Problem AI翻译
  作者：Kalinowski, Thomas; Mohammadian, Sogol
  作者单位：University of New England; University of Newcastle
  摘要：We study a certain polytope depending on a graph G and a parameter beta is an element of(0,1) that arises from embedding the Hamiltonian cycle problem in a discounted Markov decision process. Literature suggests a conjecture a lower bound on the proportion of feasible bases corresponding to Hamiltonian cycles in the set of all feasible bases. We make progress toward a proof of the conjecture by proving results about the structure of feasible bases. In particular, we prove three main results: (...
• Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach AI翻译
  作者：Duchi, John C.; Glynn, Peter W.; Namkoong, Hongseok
  作者单位：Stanford University; Stanford University; Columbia University
  摘要：We study statistical inference and distributionally robust solution methods for stochastic optimization problems, focusing on confidence intervals for optimal values and solutions that achieve exact coverage asymptotically. We develop a generalized empirical likelihood framework-based on distributional uncertainty sets constructed from nonparametric f-divergence balls-for Hadamard differentiable functionals, and in particular, stochastic optimization problems. As consequences of this theory, w...
• From Monetary to Nonmonetary Mechanism Design via Artificial Currencies AI翻译
  作者：Gorokh, Artur; Banerjee, Siddhartha; Iyer, Krishnamurthy
  作者单位：Cornell University; Cornell University; University of Minnesota System; University of Minnesota Twin Cities
  摘要：Nonmonetary mechanisms for repeated allocation and decision making are gaining widespread use in many real-world settings. Our aim in this work is to study the performance and incentive properties of simple mechanisms based on artificial currencies in such settings. To this end, we make the following contributions: For a general allocation setting, we provide two black-box approaches to convert any one-shot monetary mechanism to a dynamic nonmonetary mechanism using an artificial currency that...
• Game of Thrones: Fully Distributed Learning for Multiplayer Bandits AI翻译
  作者：Bistritz, Ilai; Leshem, Amir
  作者单位：Stanford University; Bar Ilan University
  摘要：We consider an N-player multiarmed bandit game in which each player chooses one out of M arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed or Markovian. When two or more players choose the same arm, they all receive zero reward. Performance is measured using the expected sum of regrets compared with optimal assignment of arms to players that maximizes the sum of expected rewards. We assume that e...
• Distributionally Robust Markov Decision Processes and Their Connection to Risk Measures AI翻译
  作者：Baeuerle, Nicole; Glauner, Alexander
  作者单位：Helmholtz Association; Karlsruhe Institute of Technology
  摘要：We consider robust Markov decision processes with Borel state and action spaces, unbounded cost, and finite time horizon. Our formulation leads to a Stackelberg game against nature. Under integrability, continuity, and compactness assumptions, we derive a robust cost iteration for a fixed policy of the decision maker and a value iteration for the robust optimization problem. Moreover, we show the existence of deterministic optimal policies for both players. This is in contrast to classical zer...
• Universal Barrier Is n-Self-Concordant AI翻译
  作者：Lee, Yin Tat; Yue, Man-Chung
  作者单位：University of Washington; University of Washington Seattle; Hong Kong Polytechnic University
  摘要：This paper shows that the self-concordance parameter of the universal barrier on any n-dimensional proper convex domain is upper bounded by n. This bound is tight and improves the previous O(n) bound by Nesterov and Nemirovski. The key to our main result is a pair of new, sharp moment inequalities for s-concave distributions, which could be of independent interest.
• Stochastic Load Balancing on Unrelated Machines AI翻译
  作者：Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun
  作者单位：Carnegie Mellon University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; University of Michigan System; University of Michigan
  摘要：We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identicalmachines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated m...
• Simplex Transformations and the Multiway Cut Problem AI翻译
  作者：Buchbinder, Niv; Schwartz, Roy; Weizman, Baruch
  作者单位：Tel Aviv University; Technion Israel Institute of Technology; Tel Aviv University
  摘要：We consider multiway cut, a basic graph partitioning problem in which the goal is to find the minimum weight collection of edges disconnecting a given set of special vertices called terminals. Multiway cut admits a well-known simplex embedding relaxation, where rounding this embedding is equivalent to partitioning the simplex. Current best-known solutions to the problem are comprised of a mix of several different ingredients, resulting in intricate algorithms. Moreover, the best of these algor...
• Equilibria and Systemic Risk in Saturated Networks AI翻译
  作者：Massai, Leonardo; Como, Giacomo; Fagnani, Fabio
  作者单位：Polytechnic University of Turin; Lund University
  摘要：We undertake a fundamental study of network equilibria modeled as solutions of fixed-point equations for monotone linear functions with saturation nonlinearities. The considered model extends one originally proposed to study systemic risk in networks of financial institutions interconnected by mutual obligations. It is one of the simplest continuous models accounting for shock propagation phenomena and cascading failure effects. This model also characterizes Nash equilibria of constrained quad...
• Data Exploration by Representative Region Selection: Axioms and Convergence AI翻译
  作者：Estes, Alexander S.; Ball, Michael O.; Lovell, David J.
  作者单位：University of Minnesota System; University of Minnesota Twin Cities; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
  摘要：We present a new type of unsupervised learning problem in which we find a small set of representative regions that approximates a larger data set. These regions may be presented to a practitioner along with additional information in order to help the practitioner explore the data set. An advantage of this approach is that it does not rely on cluster structure of the data. We formally define this problem, and we present axioms that should be satisfied by functions that measure the quality of re...