3期

最新文章

• Multiunit Facility Location Games AI翻译
  作者：Ben-Porat, Omer; Tennenholtz, Moshe
  作者单位：Technion Israel Institute of Technology
  摘要：Facility location games have been a topic of major interest in economics, operations research, and computer science, starting from the seminal work by Hotelling [Hotelling H (1929) Stability in competition. Econom. J. 39(153):41-57]. In the classical pure location Hotelling game, businesses compete for maximizing customer attraction by strategically locating their facilities, assuming no price competition, and customers are attracted to their closest facilities. Surprisingly, very little rigor...
• Revisiting Stochastic Loss Networks: Structures and Approximations AI翻译
  作者：Jung, Kyomin; Lu, Yingdong; Shah, Devavrat; Sharma, Mayank; Squillante, Mark S.
  作者单位：Seoul National University (SNU); International Business Machines (IBM); IBM USA; Massachusetts Institute of Technology (MIT); International Business Machines (IBM); IBM USA
  摘要：We consider fundamental properties of stochastic loss networks, seeking to improve on the so-called Erlang fixed-point approximation. We propose a family of mathematical approximations for estimating the stationary loss probabilities and show that they always converge exponentially fast, provide asymptotically exact results, and yield greater accuracy than the Erlang fixed-point approximation. We further derive structural properties of the inverse of the classical Erlang loss function that cha...
• On the Role of a Market Maker in Networked Cournot Competition AI翻译
  作者：Cai, Desmond; Bose, Subhonmesh; Wierman, Adam
  作者单位：California Institute of Technology; University of Illinois System; University of Illinois Urbana-Champaign; California Institute of Technology
  摘要：We study Cournot competition among firms in a networked marketplace that is centrally managed by a market maker. In particular, we study a situation in which a market maker facilitates trade between geographically separate markets via a constrained transport network. Our focus is on understanding the consequences of the design of the market maker and providing tools for optimal design. To that end, we provide a characterization of the equilibrium outcomes of the game between the firms and the ...
• The Exact Computational Complexity of Evolutionarily Stable Strategies AI翻译
  作者：Conitzer, Vincent
  作者单位：Duke University
  摘要：While the computational complexity of many game-theoretic solution concepts, notably Nash equilibrium, has now been settled, the question of determining the exact complexity of computing an evolutionarily stable strategy has resisted solution since attention was drawn to it in 2004. In this paper, I settle this question by proving that deciding the existence of an evolutionarily stable strategy is Sigma(p)(2) complete.
• Constrained Submodular Maximization via a Nonsymmetric Technique AI翻译
  作者：Buchbinder, Niv; Feldman, Moran
  作者单位：Tel Aviv University; Open University Israel
  摘要：The study of combinatorial optimization problems with submodular objectives has attracted much attention in recent years. Such problems are important in both theory and practice because their objective functions are very general. Obtaining further improvements for many submodular maximization problems boils down to finding better algorithms for optimizing a relaxation of them known as the multilinear extension. In this work, we present an algorithm for optimizing the multilinear relaxation who...
• Efficient Computation of Optimal Auctions via Reduced Forms AI翻译
  作者：Alaei, Saeed; Fu, Hu; Haghpanah, Nima; Hartline, Jason; Malekian, Azarakhsh
  作者单位：Alphabet Inc.; Google Incorporated; University of British Columbia; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Northwestern University; University of Toronto
  摘要：We study an optimal auction problem for selecting a subset of agents to receive an item or service, whereby each agent's service can be configured, the agent has multidimensional preferences over configurations, and there is a limit on the number of agents that can be simultaneously served. We give a polynomial time reduction from the multiagent problem to appropriately defined single-agent problems. We further generalize the setting to matroid feasibility constraints and obtain exact and appr...
• A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints AI翻译
  作者：Huchette, Joey; Vielma, Juan Pablo
  作者单位：Rice University; Massachusetts Institute of Technology (MIT)
  摘要：A framework is presented for constructing strong mixed-integer programming formulations for logical disjunctive constraints. This approach is a generalization of the logarithmically sized formulations of Vielma and Nemhauser for special ordered sets of type 2 (SOS2) constraints, and a complete characterization of its expressive power is offered. The framework is applied to a variety of disjunctive constraints, producing novel small and strong formulations for outer approximations of multilinea...
• Approximate Nash Equilibria in Partially Observed Stochastic Games with Mean-Field Interactions AI翻译
  作者：Saldi, Naci; Basar, Tamer; Raginsky, Maxim
  作者单位：Ozyegin University; University of Illinois System; University of Illinois Urbana-Champaign
  摘要：Establishing the existence of Nash equilibria for partially observed stochastic dynamic games is known to be quite challenging, with the difficulties stemming from the noisy nature of the measurements available to individual players (agents) and the decentralized nature of this information. When the number of players is sufficiently large and the interactions among agents is of the mean-field type, one way to overcome this challenge is to investigate the infinite-population limit of the proble...
• Continuous-Time Portfolio Choice Under Monotone Mean-Variance Preferences-Stochastic Factor Case AI翻译
  作者：Trybula, Jakub; Zawisza, Dariusz
  作者单位：Cracow University of Economics; Jagiellonian University
  摘要：We consider an incomplete market with a nontradable stochastic factor and a continuous-time investment problem with an optimality criterion based on monotone mean-variance preferences. We formulate it as a stochastic differential game problem and use Hamilton-Jacobi-Bellman-Isaacs equations to find an optimal investment strategy and the value function. What is more, we show that our solution is also optimal for the classical Markowitz problem, and every optimal solution for the classical Marko...
• Completely Positive Binary Tensors AI翻译
  作者：Fan, Jinyan; Nie, Jiawang; Zhou, Anwa
  作者单位：Shanghai Jiao Tong University; Shanghai Jiao Tong University; University of California System; University of California San Diego; Shanghai University
  摘要：A symmetric tensor is completely positive (CP) if it is a sum of tensor powers of nonnegative vectors. This paper characterizes completely positive binary tensors. We show that a binary tensor is completely positive if and only if it satisfies two linear matrix inequalities. This result can be used to determine whether a binary tensor is completely positive or not. When it is, we give an algorithm for computing its cp-rank and the decomposition. When the order is odd, we show that the cp-rank ...