-
作者：Lim, Tongseok; McCann, Robert J.
作者单位：Purdue University System; Purdue University; University of Toronto
摘要：We bound the variance and other moments of a random vector based on the range of its realizations, thus generalizing inequalities of Popoviciu and of Bhatia and Davis concerning measures on the line to several dimensions. This is done using convex duality and (infinite-dimensional) linear programming. The following consequence of our bounds exhibits symmetry breaking, provides a new proof of Jung's theorem, and turns out to have applications to the aggregation dynamics modelling attractive-rep...
-
作者：Dahan, Mathieu; Amin, Saurabh; Jaillet, Patrick
作者单位：University System of Georgia; Georgia Institute of Technology; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：This article poses the following problem: Does there exist a probability distribution over subsets of a finite partially ordered set (poset), such that a set of constraints involving marginal probabilities of the poset's elements and maximal chains is satisfied? We present a combinatorial algorithm to positively resolve this question. The algorithm can be implemented in polynomial time in the special case where maximal chain probabilities are affine functions of their elements. This existence ...
-
作者：Goldenshluger, Alexander; Zeevi, Assaf
作者单位：University of Haifa; Columbia University
摘要：The subject of this paper is the problem of optimal stopping of a sequence of independent and identically distributed random variables with unknown distribution. We propose a stopping rule that is based on relative ranks and study its performance as measured by the maximal relative regret over suitable nonparametric classes of distributions. It is shown that the proposed rule is first-order asymptotically optimal and nearly rate optimal in terms of the rate at which the relative regret converg...
-
作者：Frankowska, Helene; Sagara, Nobusumi
作者单位：Sorbonne Universite; Centre National de la Recherche Scientifique (CNRS); Universite Paris Cite; Hosei University
摘要：We investigate the value function of an infinite horizon variational problem in the infinite-dimensional setting. First, we provide an upper estimate of its Dini-Hadamard subdifferential in terms of the Clarke subdifferential of the Lipschitz continuous integrand and the Clarke normal cone to the graph of the set-valued mapping describing dynamics. Second, we derive a necessary condition for optimality in the form of an adjoint inclusion that grasps a connection between the Euler-Lagrange cond...
-
作者：Koessler, Frederic; Laclau, Marie; Tomala, Tristan
作者单位：Paris School of Economics; Centre National de la Recherche Scientifique (CNRS)
摘要：We study the interaction between multiple information designers who try to influence the behavior of a set of agents. When each designer can choose information policies from a compact set of statistical experiments with countable support, such games always admit subgame-perfect equilibria. When designers produce public information, every equilibrium of the simple game in which the set of messages coincides with the set of states is robust in the sense that it is an equilibrium with larger and ...
-
作者：Kim, Daehyun; Li, Xiaoxi
作者单位：Wuhan University
摘要：This paper defines a general framework to study infinitely repeated games with time-dependent discounting in which we distinguish and discuss both time-consistent and -inconsistent preferences. To study the long-term properties of repeated games, we introduce an asymptotic condition to characterize the fact that players become more and more patient; that is, the discount factors at all stages uniformly converge to one. Two types of folk theorems are proven without the public randomization assu...
-
作者：Gu, Chenlin; Roth, Alvin; Wu, Qingyun
作者单位：Universite PSL; Ecole Normale Superieure (ENS); Stanford University
摘要：Repugnant transactions are sometimes banned, but legal bans sometimes give rise to active black markets that are difficult if not impossible to extinguish. We explore a model in which the probability of extinguishing a black market depends on the extent to which its transactions are regarded as repugnant as measured by the proportion of the population that disapproves of them and the intensity of that repugnance as measured by willingness to punish. Sufficiently repugnant markets can be exting...
-
作者：Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Lazos, Philip
作者单位：University of Liverpool; University of Erlangen Nuremberg; Sapienza University Rome
摘要：We study the trade-off between the price of anarchy (PoA) and the price of stability (PoS) in mechanism design in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to these metrics and observe that two fundamental mechanisms, namely the first price (FP) and the second price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely char...
-
作者：He, Taotao; Tawarmalani, Mohit
作者单位：Shanghai Jiao Tong University; Purdue University System; Purdue University
摘要：In this paper, we introduce new relaxations for the hypograph of composite functions assuming that the outer function is supermodular and concave extendable. Relying on a recently introduced relaxation framework, we devise a separation algorithm for the graph of the outer function over P, where P is a special polytope to capture the structure of each inner function using its finitely many bounded estimators. The separation algorithm takes O(dnlogd) time, where d is the number of inner function...
-
作者：Faenza, Yuri; Kavitha, Telikepalli
作者单位：Columbia University; Tata Institute of Fundamental Research (TIFR)
摘要：Let G be an instance of the stable marriage problem in which every vertex ranks its neighbors in a strict order of preference. A matching M in G is popular if M does not lose a head-to-head election against any matching. Popular matchings generalize stable matchings. Unfortunately, when there are edge costs, to find or even approximate up to any factor a popular matching of minimum cost is NP-hard. Let opt be the cost of a min-cost popular matching. Our goal is to efficiently compute a matchin...
