1期

最新文章

• Robust Power Management via Learning and Game Design AI翻译
  作者：Zhou, Zhengyuan; Mertikopoulos, Panayotis; Moustakas, Aris L.; Bambos, Nicholas; Glynn, Peter
  作者单位：New York University; Inria; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP); National & Kapodistrian University of Athens; Stanford University
  摘要：We consider the target-rate power management problem for wireless networks; and we propose two simple, distributed power management schemes that regulate power in a provably robust manner by efficiently leveraging past information. Both schemes are obtained via a combined approach of learning and game design where we (1) design a game with suitable payoff functions such that the optimal joint power profile in the original power management problem is the unique Nash equilibrium of the designed ...
• Competitive Equilibrium and Trading Networks: A Network Flow Approach AI翻译
  作者：Candogan, Ozan; Epitropou, Markos; Vohra, Rakesh V.
  作者单位：University of Chicago; University of Pennsylvania; University of Pennsylvania
  摘要：Under full substitutability of preferences, it is known that a competitive equilibrium exists in trading networks and is equivalent to (chain) stable outcomes. In this paper, we formulate the problem of finding an efficient set of trades as a generalized submodular flow problem in a suitable network. Existence of a competitive equilibrium and its equivalence with the seemingly weaker notion of stability follow directly from the optimality conditions of the flow problem. Our formulation enables...
• Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach AI翻译
  作者：Krishnasamy, Subhashini; Sen, Rajat; Johari, Ramesh; Shakkottai, Sanjay
  作者单位：University of Texas System; University of Texas Austin; Stanford University
  摘要：Consider a queueing system consisting of multiple servers. Jobs arrive over time and enter a queue for service; the goal is to minimize the size of this queue. At each opportunity for service, at most one server can be chosen, and at most one job can be served. Service is successful with a probability (the service probability) that is a priori unknown for each server. An algorithm that knows the service probabilities (the genie) can always choose the server of highest service probability. We s...
• Tractable Equilibria in Sponsored Search with Endogenous Budgets AI翻译
  作者：Ciocan, Dragos Florin; Iyer, Krishnamurthy
  作者单位：INSEAD Business School; University of Minnesota System; University of Minnesota Twin Cities
  摘要：We consider an ad network's problem of allocating the auction for each individual impression to an optimal subset of advertisers with the goal of revenue maximization. This is a variant of bipartite matching except that advertisers may strategize by choosing their bidding profiles and their total budget. Because the ad network's allocation rule affects the bidders' strategies, equilibrium analysis is challenging. We show that this analysis is tractable when advertisers face a linear budget cos...
• Preservation of Supermodularity in Parametric Optimization: Necessary and Sufficient Conditions on Constraint Structures AI翻译
  作者：Chen, Xin; Long, Daniel Zhuoyu; Qi, Jin
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Chinese University of Hong Kong; Hong Kong University of Science & Technology
  摘要：This paper presents a systematic study of the preservation of supermodularity under parametric optimization, allowing us to derive complementarity among parameters and monotonic structural properties for optimal policies in many operational models. We introduce the new concepts of mostly sublattice and additive mostly sublattice, which generalize the commonly imposed sublattice condition significantly, and use them to establish the necessary and sufficient conditions for the feasible set so th...
• Technical Note-Understanding the Performance of Capped Base-Stock Policies in Lost-Sales Inventory Models AI翻译
  作者：Xin, Linwei
  作者单位：University of Chicago
  摘要：Single-sourcing lost-sales inventory systems with lead times are notoriously difficult to optimize. In this paper, we propose a new family of capped base-stock policies and provide a new perspective on constructing a practical hybrid policy combining two well-known heuristics: base-stock and constant-order policies. Each capped base-stock policy is associated with two parameters: a base-stock level and an order cap. We prove that for any fixed order cap, the capped base-stock policy converges ...
• The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms AI翻译
  作者：Holzmann, Tim; Smith, J. Cole
  作者单位：United States Department of Defense; United States Air Force; Air Force Institute of Technology (AFIT); Syracuse University
  摘要：Shortest-path interdiction problems involve a leader and a follower playing a zero-sum game over a directed network. The leader interdicts a set of arcs, and arc costs increase as a function of the number of times they are interdicted. The follower observes the leader's actions and selects a shortest path in response. The leader's optimal interdiction strategy maximizes the follower's minimum-cost path. In classic formulations of these problems, the leader's interdiction actions are determinis...
• Targeting, Deployment, and Loss-Tolerance in Lanchester Engagements AI翻译
  作者：Atkinson, Michael P.; Kress, Moshe; MacKay, Niall J.
  作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School; University of York - UK
  摘要：Existing Lanchester combat models focus on two force parameters: numbers (force size) and per-capita effectiveness (attrition rate). Whereas these two parameters are central in projecting a battle's outcome, there are other important factors that affect the battlefield: (1) targeting capability, that is, the capacity to identify live enemy units and not dissipate fire on nontargets; (2) tactical restrictions preventing full deployment of forces; and (3) morale and tolerance of losses, that is,...
• A Simple and Approximately Optimal Mechanism for a Buyer with Complements AI翻译
  作者：Eden, Alon; Feldman, Michal; Friedler, Ophir; Talgam-Cohen, Inbal; Weinberg, S. Matthew
  作者单位：Harvard University; Tel Aviv University; Technion Israel Institute of Technology; Princeton University
  摘要：We consider a revenue-maximizing seller with m heterogeneous items and a single buyer whose valuation for the items may exhibit both substitutes and complements. We show that the better of selling the items separately and bundling them together-guarantees a Theta(d)-fraction of the optimal revenue, where d is a measure of the degree of complementarity; it extends prior work showing that the same simple mechanism achieves a constant-factor approximation when buyer valuations are subadditive (th...
• Nonsparse Learning with Latent Variables AI翻译
  作者：Zheng, Zemin; Lv, Jinchi; Lin, Wei
  作者单位：Chinese Academy of Sciences; University of Science & Technology of China, CAS; University of Southern California; Peking University; Peking University
  摘要：As a popular tool for producing meaningful and interpretable models, large-scale sparse learning works efficiently in many optimization applications when the underlying structures are indeed or close to sparse. However, naively applying the existing regularization methods can result in misleading outcomes because of model mis-specification. In this paper, we consider nonsparse learning under the factors plus sparsity structure, which yields a joint modeling of sparse individual effects and com...