-
作者：Flesch, Janos; Solan, Eilon
作者单位：Maastricht University; Tel Aviv University
摘要：We consider multiplayer stochastic games with finitely many players and actions, and countably many states, in which the payoff of each player is a bounded and Borelmeasurable function of the infinite play. By using a generalization of the technique of Martin [Martin DA (1998) The determinacy of Blackwell games. J. Symb. Log. 63(4):1565-1581] and Maitra and Sudderth [Maitra A, Sudderth W (1998) Finitely additive stochastic games with Borel measurable payoffs. Internat. J. Game Theory 27:257-26...
-
作者：Papadimitriou, Christos; Pollner, Tristan; Saberi, Amin; Wajc, David
作者单位：Columbia University; Stanford University; Alphabet Inc.; Google Incorporated
摘要：The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a prophet who knows the future. An equally natural, though significantly less wellstudied, benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally unbounded), but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it? M...
-
作者：Liang, Ling; Sun, Defeng; Toh, Kim-Chuan
作者单位：University System of Maryland; University of Maryland College Park; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore
摘要：This paper proposes a squared smoothing Newton method via the Huber smoothing function for solving semidefinite programming problems (SDPs). We first study the fundamental properties of the matrix-valued mapping defined upon the Huber function. Using these results and existing ones in the literature, we then conduct rigorous convergence analysis and establish convergence properties for the proposed algorithm. In particular, we show that the proposed method is well-defined and admits global con...
-
作者：Vera, Alberto; Arlotto, Alessandro; Gurvich, Itai; Levin, Eli
作者单位：Cornell University; Duke University
摘要：We study a family of dynamic resource allocation problems, wherein requests of different types arrive over time and are accepted or rejected. Each request type is characterized by its reward, arrival probability, and resource consumption. An upper bound for the collected reward is given by a linear optimization problem with a random righthand side. This type of problem, known as packing linear program (LP), is ubiquitous in resource allocation. We provide a detailed characterization of the par...
-
作者：Ankirchner, Stefan; Kazi-Tani, Nabil; Wendt, Julian; Zhou, Chao
作者单位：Friedrich Schiller University of Jena; Universite de Lorraine; National University of Singapore; National University of Singapore
摘要：We consider a symmetric stochastic differential game where each player can control the diffusion intensity of an individual dynamic state process, and the players whose states at a deterministic finite time horizon are among the best alpha is an element of (0, 1)of all states receive a fixed prize. Within the mean field limit version of the game, we compute an explicit equilibrium, a threshold strategy that consists of choosing the maximal fluctuation intensity when the state is below a given ...
-
作者：Kushnir, Alexey; Krishnamoorthy, Vinod
作者单位：Carnegie Mellon University; Carnegie Mellon University
摘要：We prove that supply correspondences are characterized by two properties: the law of supply and being homogeneous of degree zero.
-
作者：Klaus, Bettina; Klijn, Flip
作者单位：University of Lausanne; Consejo Superior de Investigaciones Cientificas (CSIC); CSIC - Institut d'Analisi Economica (IAE); Barcelona School of Economics
摘要：A classical school choice problem consists of a set of schools with priorities over students and a set of students with preferences over schools. Schools' priorities are often based on multiple criteria, for example, merit-based test scores as well as minimal-access rights (siblings attending the school, students' proximity to the school, etc.). Traditionally, minimal-access rights are incorporated into priorities by always giving minimal-access students higher priority over non-minimal-access...
-
作者：Bauschke, Heinz H.; Moursi, Walaa M.
作者单位：University of British Columbia; University of Waterloo; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：More than 40 years ago, Lions and Mercier introduced in a seminal paper the Douglas-Rachford algorithm. Today, this method is well-recognized as a classic and highly successful splitting method to find minimizers of the sum of two (not necessarily smooth) convex functions. Whereas the underlying theory has matured, one case remains a mystery: the behavior of the shadow sequence when the given functions have disjoint domains. Building on previous work, we establish for the first time weak and v...
-
作者：Nie, Jiawang; Yang, Zi
作者单位：University of California System; University of California San Diego; State University of New York (SUNY) System; University at Albany, SUNY
摘要：The multi-objective optimization is to optimize several objective functions over a common feasible set. Because the objectives usually do not share a common optimizer, people often consider (weakly) Pareto points. This paper studies multi-objective optimization problems that are given by polynomial functions. First, we study the geometry for (weakly) Pareto values and represent Pareto front as the boundary of a convex set. Linear scalarization problems (LSPs) and Chebyshev scalarization proble...
-
作者：Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems, namely, HYPERGRAPH-k-CUT and MINMAX-HYPERGRAPH-k-PARTITION. The input in hypergraph k-partitioning problems is a hypergraph G = (V, E) with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k nonempty parts (V1, V2, ..., Vk)-known as a k-partition-so as to minimize an objective of interest. (1) If the objective of interest is the maximum c...
