-
作者：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...
-
作者：Fujii, Kaito; Yoshida, Yuichi
作者单位：Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions of candidate values are provided in advance. We propose an algorithm that achieves a nearly optimal value if the predictions are accurate and results in a constant-factor competitive ratio otherwise. We also show that the worst-case competitive ratio of an algorithm cannot be hig...
-
作者：Garg, Jugal; Hoefer, Martin; Mehlhorn, Kurt
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Goethe University Frankfurt; Max Planck Society
摘要：We study linear Fisher markets with satiation. In these markets, sellers have earning limits, and buyers have utility limits. Beyond applications in economics, they arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not...
-
作者：Kong, Siyu; Lewis, A. S.
作者单位：Cornell University
摘要：We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a 2020 black-box algorithm of Zhang-Lin-Jegelka-Sra-Jadbabaie that approximates an e-stationary point of any directionally differentiable Lipschitz objective using O(e-4) calls to a specialized subgradient oracle and a randomized line search. Seeking by contras...
-
作者：Chen, Xi; Kroer, Christian; Kumar, Rachitesh
作者单位：Columbia University
摘要：Budget constraints are ubiquitous in online advertisement auctions. To manage these constraints and smooth out the expenditure across auctions, the bidders (or the platform on behalf of them) often employ pacing: each bidder is assigned a pacing multiplier between zero and one, and her bid on each item is multiplicatively scaled down by the pacing multiplier. This naturally gives rise to a game in which each bidder strategically selects a multiplier. The appropriate notion of equilibrium in th...
