Mathematics of Operations Research

最新文章

• Guarantees in Fair Division: General or Monotone Preferences AI翻译
  作者：Bogomolnaia, Anna; Moulin, Herve
  作者单位：University of Glasgow; Centre National de la Recherche Scientifique (CNRS)
  摘要：When dividing a manna Omega of private items (commodities, workloads, land, time slots) between n agents, the individual guarantee is the welfare each agent can secure in the worst case of other agents' preferences and actions. If the manna is nonatomic and utilities are continuous (not necessarily monotone or convex) the minmax utility, that of our agent's best share in the agent's worst partition of the manna, is guaranteed by Kuhn's generalization of divide and choose. The larger maxmin uti...
• Multiagent Online Learning in Time-Varying Games AI翻译
  作者：Duvocelle, Benoit; Mertikopoulos, Panayotis; Staudigl, Mathias; Vermeulen, Dries
  作者单位：Maastricht University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Maastricht University
  摘要：We examine the long-run behavior of multiagent online learning in games that evolve over time. Specifically, we focus on a wide class of policies based on mirror descent, and we show that the induced sequence of play (a) converges to a Nash equilibrium in time-varying games that stabilize in the long run to a strictly monotone limit, and (b) it stays asymptotically close to the evolving equilibrium of the sequence of stage games (assuming they are strongly monotone). Our results apply to both ...
• Optimal Relative Performance Criteria in Mean-Field Contribution Games AI翻译
  作者：Zhou, Zhou
  作者单位：University of Sydney
  摘要：We consider mean-field contribution games, where players in a team choose some effort levels at each time period and the aggregate reward for the team depends on the aggregate cumulative performance of all the players. Each player aims to maximize the expected reward of her own share subject to her cost of effort. To reduce the free-rider issue, we propose some relative performance criteria (RPC), based on which the reward is redistributed to each player. We are interested in those RPCs that i...
• Reduction of Potential-Based Flow Networks AI翻译
  作者：Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin
  作者单位：Technical University of Berlin; Technical University of Darmstadt
  摘要：We consider potential-based flow networks with terminal nodes at which flow can enter or leave the network and physical properties, such as voltages or pressures, are measured and controlled. We study conditions under which such a network can be reduced to a smaller, equivalent network with the same behavior at the terminal nodes. Potential-based flow networks are widely used to model infrastructure networks, such as electricity, gas, or water networks. In contrast to Kron's reduction for elec...
• Robust Markov Decision Processes: Beyond Rectangularity AI翻译
  作者：Goyal, Vineet; Grand-Clement, Julien
  作者单位：Columbia University
  摘要：We consider a robust approach to address uncertainty in model parameters in Markov decision processes (MDPs), which are widely used to model dynamic optimization in many applications. Most prior works consider the case in which the uncertainty on transitions related to different states is uncoupled and the adversary is allowed to select the worst possible realization for each state unrelated to others, potentially leading to highly conservative solutions. On the other hand, the case of general...
• Minimizing Compositions of Differences-of-Convex Functions with Smooth Mappings AI翻译
  作者：Le Thi, Hoai An; Huynh, Van Ngai; Dinh, Tao Pham
  作者单位：Universite de Lorraine; Institut Universitaire de France
  摘要：We address the so-called DC (difference-of-convex functions) composite minimization problems (or DC composite programs) whose objective function is a composition of a DC function with a continuously differentiable mapping. We first develop an algorithm named DC composite algorithm (DCCA in short) for unconstrained DC composite programs and further extend to DC composite programs with constraints of inclusion associated with a smooth mapping and a closed convex set. The convergence analysis of ...
• Large Ranking Games with Diffusion Control AI翻译
  作者：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 ...
• Polynomial Upper Bounds on the Number of Differing Columns of ?-Modular Integer Programs AI翻译
  作者：Lee, Jon; Paat, Joseph; Stallknecht, Ingo; Xu, Luze
  作者单位：University of Michigan System; University of Michigan; University of British Columbia
  摘要：We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IPs) with bounded determinants. For example, an IP can be solved in strongly polynomial time if the constraint matrix is bimodular: that is, the determinants are bounded in absolute value by two. Determinants are also used to bound the euro1 distance between IP solutions and solutions of its linear relaxation. One of the first to quantify the complexity of IPs with bounded determ...
• Convergent Nested Alternating Minimization Algorithms for Nonconvex Optimization Problems AI翻译
  作者：Gur, Eyal; Sabach, Shoham; Shtern, Shimrit
  作者单位：Technion Israel Institute of Technology
  摘要：We introduce a new algorithmic framework for solving nonconvex optimization problems, that is called nested alternating minimization, which aims at combining the classical alternating minimization technique with inner iterations of any optimization method. We provide a global convergence analysis of the new algorithmic framework to critical points of the problem at hand, which to the best of our knowledge, is the first of this kind for nested methods in the nonconvex setting. Central to our gl...
• Nontruthful Position Auctions Are More Robust to Misspecification AI翻译
  作者：Dutting, Paul; Fischer, Felix; Parkes, David C.
  作者单位：Alphabet Inc.; Google Incorporated; University of London; Queen Mary University London; Harvard University
  摘要：We consider the classical model of sponsored search due to Edelman et al. and Varian and examine how robust standard position auctions are to a misspecification of the position-dependent quality factors used by this model. We show that under both complete and incomplete information a nontruthful position auction admits an efficient equilibrium for a strictly broader range of parameter values than the Vickrey-Clarke-Groves (VCG) mechanism, which would be truthful if the parameters were specifie...