Mathematics of Operations Research

最新文章

• Popularity, Mixed Matchings, and Self-Duality AI翻译
  作者：Huang, Chien-Chung; Kavitha, Telikepalli
  作者单位：Universite PSL; Ecole Normale Superieure (ENS); Tata Institute of Fundamental Research (TIFR)
  摘要：Our input instance is a bipartite graph G where each vertex has a preference list ranking its neighbors in a strict order of preference. A matching M is popular if there is no matching N such that the number of vertices that prefer N to M outnumber those that prefer M to N. Each edge is associated with a utility and we consider the problem of matching vertices in a popular and utility-optimal manner. It is known that it is NP-hard to compute a max-utility popular matching. So we consider mixed...
• A General Analysis of Sequential Social Learning AI翻译
  作者：Arieli, Itai; Mueller-Frank, Manuel
  作者单位：Technion Israel Institute of Technology; University of Navarra; IESE Business School
  摘要：This paper analyzes a sequential social learning game with a general utility function, state, and action space. We show that asymptotic learning holds for every utility function if and only if signals are totally unbounded, that is, the support of the private posterior probability of every event contains both zero and one. For the case of finitely many actions, we provide a sufficient condition for asymptotic learning depending on the given utility function. Finally, we establish that for the ...
• 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...