4期

最新文章

• The Privacy Paradox and Optimal Bias-Variance Trade-offs in Data Acquisition AI翻译
  作者：Liao, Guocheng; Su, Yu; Ziani, Juba; Wierman, Adam; Huang, Jianwei
  作者单位：Sun Yat Sen University; California Institute of Technology; University System of Georgia; Georgia Institute of Technology; The Chinese University of Hong Kong, Shenzhen; Shenzhen Institute of Artificial Intelligence & Robotics for Society
  摘要：Whereas users claim to be concerned about privacy, often they do little to protect their privacy in their online actions. One prominent explanation for this privacy paradox is that, when an individual shares data, it is not just the individual's privacy that is compromised; the privacy of other individuals with correlated data is also compromised. This information leakage encourages oversharing of data and significantly impacts the incentives of individuals in online platforms. In this paper, ...
• Fair-Share Allocations for Agents with Arbitrary Entitlements AI翻译
  作者：Babaioff, Moshe; Ezra, Tomer; Feige, Uriel
  作者单位：Hebrew University of Jerusalem; Sapienza University Rome; Weizmann Institute of Science
  摘要：We consider the problem of fair allocation of indivisible goods to n agents with no transfers. When agents have equal entitlements, the well-established notion of the maxi min share (MMS) serves as an attractive fairness criterion for which, to qualify as fair, an allocation needs to give every agent at least a substantial fraction of the agent's MMS. In this paper, we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to une...
• Finding Hall Blockers by Matrix Scaling AI翻译
  作者：Hayashi, Koyo; Hirai, Hiroshi; Sakabe, Keiya
  作者单位：University of Tokyo; Nagoya University; University of Tokyo
  摘要：Given a nonnegative matrix A=(A(ij))=, the matrix scaling problem asks whether A can be scaled to a doubly stochastic matrix D1AD2 for some positive diagonal matrices D-1, D-2. The Sinkhorn algorithm is a simple iterative algorithm, which repeats row-normalization A(ij )<- A(ij)/& sum;(i)A(ij) and column-normalization A(ij )<- A(ij)/& sum;(i)A(ij) alternatively. By this algorithm, A converges to a doubly stochastic matrix in limit if and only if the bipartite graph associated with A has a perf...
• A Class of Dissimilarity Semimetrics for Preference Relations AI翻译
  作者：Nishimura, Hiroki; Ok, Efe A.
  作者单位：University of California System; University of California Riverside; New York University; New York University
  摘要：We propose a class of semimetrics for acyclic preference relations, any one of which is an alternative to the classical Kemeny-Snell-Bogart metric. These semimetrics are based solely on the implications of preferences for choice behavior and thus appear more suitable in economic contexts and choice experiments. We obtain a fairly simple axiomatic characterization for the class we propose. The apparently most important member of this class, which we dub the top-difference semimetric, is charact...
• Fluid Limits for Longest Remaining Time First Queues AI翻译
  作者：Kruk, Lukasz
  作者单位：Maria Curie-Sklodowska University
  摘要：A single-server queue with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served using the longest remaining time first scheduling algorithm. In case of a tie, processor sharing is utilized. We introduce a fluid model for the evolution of a measure-valued state descriptor of this queue, and we investigate its properties. We also prove a fluid limit theorem justifying our fluid model as the first-order approximation ...
• A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond AI翻译
  作者：Naegele, Martin; Zenklusen, Rico
  作者单位：University of Bonn; Swiss Federal Institutes of Technology Domain; ETH Zurich
  摘要：Short spanning trees subject to additional constraints are important building blocks in various approximation algorithms, and moreover, they capture interesting problem settings on their own. Especially in the context of the traveling salesman problem (TSP), new techniques for finding spanning trees with well-defined properties have been crucial in recent progress. We consider the problem of finding a spanning tree subject to constraints on the edges in a family of cuts forming a laminar famil...
• Convergence Analysis of Accelerated Stochastic Gradient Descent Under the Growth Condition AI翻译
  作者：Chen, You-Lin; Na, Sen; Kolar, Mladen
  作者单位：University of Chicago; University of California System; University of California Berkeley; University of Chicago
  摘要：We study the convergence of accelerated stochastic gradient descent (SGD) for strongly convex objectives under the growth condition, which states that the variance of stochastic gradient is bounded by a multiplicative part that grows with the full gradient and a constant additive part. Through the lens of the growth condition, we investigate four widely used accelerated methods: Nesterov's accelerated method (NAM), robust momentum method (RMM), accelerated dual averaging method (DAM+), and imp...
• Quantitative Convergence for Displacement Monotone Mean Field Games with Controlled Volatility AI翻译
  作者：Jackson, Joe; Tangpib, Ludovic
  作者单位：University of Chicago; Princeton University
  摘要：We study the convergence problem for mean field games with common noise and controlled volatility. We adopt the strategy recently put forth by Laurie re and the second author, using the maximum principle to recast the convergence problem as a question of forward-backward propagation of chaos (i.e., (conditional) propagation of chaos for systems of particles evolving forward and backward in time). Our main results show that displacement monotonicity can be used to obtain this propagation of c...
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness AI翻译
  作者：Amanatidis, Georgios; Birmpas, Georgios; Fusco, Federico; Lazos, Philip; Leonardi, Stefano; Reiffenhauser, Rebecca
  作者单位：University of Essex; University of Liverpool; Sapienza University Rome; University of Amsterdam
  摘要：We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers, and therefore, a mechanism in our setting is an algorithm that takes as input the reported- rather than the true-values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspon...
• Worst-Case Iteration Bounds for Log Barrier Methods on Problems with Nonconvex Constraints AI翻译
  作者：Hinder, Oliver; Ye, Yinyu
  作者单位：Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Stanford University
  摘要：Interior point methods (IPMs) that handle nonconvex constraints such as IPOPT, KNITRO and LOQO have had enormous practical success. We consider IPMs in the setting where the objective and constraints are thrice differentiable, and have Lipschitz first and second derivatives on the feasible region. We provide an IPM that, starting from a strictly feasible point, finds a mu-approximate Fritz John point by solving O(mu-7=4) trustregion subproblems. For IPMs that handle nonlinear constraints, this...