3期

最新文章

• The Running Intersection Relaxation of the Multilinear Polytope AI翻译
  作者：Del Pia, Alberto; Khajavirad, Aida
  作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University
  摘要：The multilinear polytope of a hypergraph is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acy...
• Fair Allocation of Indivisible Goods: Improvement AI翻译
  作者：Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi
  作者单位：Sharif University of Technology; Institute for Research in Fundamental Sciences IPM; University System of Maryland; University of Maryland College Park
  摘要：We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061-1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive sett...
• 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...
• 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.
• 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...
• Shapley-Snow Kernels, Multiparameter Eigenvalue Problems, and Stochastic Games AI翻译
  作者：Attia, Luc; Oliu-Barton, Miquel
  作者单位：Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS)
  摘要：We propose a connection between matrix games, finite zero-sum stochastic games (henceforth stochastic games) and multiparameter eigenvalue problems. From this connection, we derive a handful of new results for stochastic games.