-
作者：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...
-
作者：Frank, Andras; Murota, Kazuo
作者单位：Eotvos Lorand University; Tokyo Metropolitan University
摘要：A min-max formula is proved for the minimum of an integer-valued separable discrete convex function in which the minimum is taken over the set of integral elements of a box total dual integral polyhedron. One variant of the theorem uses the notion of conjugate function (a fundamental concept in nonlinear optimization), but we also provide another version that avoids conjugates, and its spirit is conceptually closer to the standard form of classic min-max theorems in combinatorial optimization....
-
作者：Carmona, Rene; Cooney, Daniel B.; Graves, Christy, V; Lauriere, Mathieu
作者单位：Princeton University; University of Pennsylvania
摘要：We consider static finite-player network games and their continuum analogs graphon games. Existence and uniqueness results are provided as well as convergence of the finite-player network game optimal strategy profiles to their analogs for the graphon games. We also show that equilibrium strategy profiles of a graphon game provide approximate Nash equilibria for the finite-player games. Connections with mean field games are discussed. A motivating application of Cournot competition is presente...
