-
作者：Huang, Yu-Jui; Zhou, Zhou
作者单位：University of Colorado System; University of Colorado Boulder; University of Sydney
摘要：A new definition of continuous-time equilibrium controls is introduced. As opposed to the standard definition, which involves a derivative-type operation, the new definition parallels how a discrete-time equilibrium is defined and allows for unambiguous economic interpretation. The terms strong equilibria and weak equilibria are coined for controls under the new and standard definitions, respectively. When the state process is a time-homogeneous continuous-time Markov chain, a careful asymptot...
-
作者：Barman, Siddharth; Rathi, Nidhi
作者单位：Indian Institute of Science (IISC) - Bangalore; Indian Institute of Science (IISC) - Bangalore
摘要：This work develops algorithmic results for the classic cake-cutting problem in which a divisible, heterogeneous resource (modeled as a cake) needs to be partitioned among agents with distinct preferences. We focus on a standard formulation of cake cutting wherein each agent must receive a contiguous piece of the cake. Although multiple hardness results exist in this setup for finding fair/efficient cake divisions, we show that, if the value densities of the agents satisfy the monotone likeliho...
-
作者：Zhou, Zhengyuan; Mertikopoulos, Panayotis; Bambos, Nicholas; Glynn, Peter; Ye, Yinyu
作者单位：New York University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Stanford University
摘要：The recent surge of breakthroughs in machine learning and artificial intelligence has sparked renewed interest in large-scale stochastic optimization problems that are universally considered hard. One of the most widely used methods for solving such problems is distributed asynchronous stochastic gradient descent (DASGD), a family of algorithms that result from parallelizing stochastic gradient descent on distributed computing architectures (possibly) asychronously. However, a key obstacle in ...
-
作者：Mehlitz, Patrick; Zemkoho, Alain B.
作者单位：Brandenburg University of Technology Cottbus; University of Southampton
摘要：This paper is concerned with the derivation of first- and second-order sufficient optimality conditions for optimistic bilevel optimization problems involving smooth functions. First-order sufficient optimality conditions are obtained by estimating the tangent cone to the feasible set of the bilevel program in terms of initial problem data. This is done by exploiting several different reformulations of the hierarchical model as a singlelevel problem. To obtain second-order sufficient optimalit...
-
作者：Ramaswamy, Arunselvan; Bhatnagar, Shalabh
作者单位：University of Paderborn; Indian Institute of Science (IISC) - Bangalore; Indian Institute of Science (IISC) - Bangalore
摘要：In this paper, we consider the stochastic iterative counterpart of the value iteration scheme wherein only noisy and possibly biased approximations of the Bellman operator are available. We call this counterpart the approximate value iteration (AVI) scheme. Neural networks are often used as function approximators, in order to counter Bellman's curse of dimensionality. In this paper, they are used to approximate the Bellman operator. Because neural networks are typically trained using sample da...
-
作者：Gamarnik, David; Tsitsiklis, John N.; Zubeldia, Martin
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University System of Georgia; Georgia Institute of Technology
摘要：We consider a heterogeneous distributed service system consisting of n servers with unknown and possibly different processing rates. Jobs with unit mean arrive as a renewal process of rate proportional to n and are immediately dispatched to one of several queues associated with the servers. We assume that the dispatching decisions are made by a central dispatcher with the ability to exchange messages with the servers and endowed with a finite memory used to store information from one decision ...
-
作者：Bramson, Maury; D'Auria, Bernardo; Walton, Neil
作者单位：University of Minnesota System; University of Minnesota Twin Cities; Universidad Carlos III de Madrid; University of Manchester
摘要：Consider a switched queueing network with general routing among its queues. TShe MaxWeight policy assigns available service by maximizing the objective function Sigma(j)Q(j)sigma(j) among the different feasible service options, where Q(j) denotes queue size and sigma(j) denotes the amount of service to be executed at queue j. MaxWeight is a greedy policy that does not depend on knowledge of arrival rates and is straightforward to implement. These properties and its simple formulation suggest M...
-
作者：Soto, Jose A.; Turkieltaub, Abner; Verdugo, Victor
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universidad de Chile; University of British Columbia; Universidad de O'Higgins
摘要：In the ordinal matroid secretary problem (MSP), candidates do not reveal numerical weights, but the decision maker can still discern if a candidate is better than another. An algorithm alpha is probability-competitive if every element from the optimum appears with probability 1/alpha in the output. This measure is stronger than the standard utility competitiveness. Our main result is the introduction of a technique based on forbidden sets to design algorithms with strong probability-competitiv...
-
作者：Crespi, Giovanni Paolo; Hamel, Andreas H.; Rocca, Matteo; Schrage, Carola
作者单位：Universita Carlo Cattaneo - Liuc; Free University of Bozen-Bolzano; University of Insubria
摘要：Via a family of monotone scalar functions, a preorder on a set is extended to its power set and then used to construct a hull operator and a corresponding complete lattice of sets. Functions mapping into the preordered set are extended to complete lattice-valued ones, and concepts for exact and approximate solutions for corresponding set optimization problems are introduced and existence results are given. Well-posedness for complete lattice-valued problems is introduced and characterized. The...
-
作者：Harks, Tobias; Hoefer, Martin; Schedel, Anja; Surek, Manuel
作者单位：University of Augsburg; Goethe University Frankfurt
摘要：In cost-sharing games with delays, a set of agents jointly uses a subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A separable cost-sharing protocol determines cost shares that are budget-balanced, separable, and guarantee existence of pure Nash equilibria (PNE). We provide black-box reductions reducing the design of such a protocol to the design of an approximation algorithm for...
