1期

最新文章

• 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...
• On Policies for Single-Leg Revenue Management with Limited Demand Information AI翻译
  作者：Ma, Will; Simchi-Levi, David; Teo, Chung-Piaw
  作者单位：Columbia University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); National University of Singapore
  摘要：In this paper, we study the single-item revenue management problem, with no information given about the demand trajectory over time. When the item is sold through accepting/rejecting different fare classes, the tight competitive ratio for this problem has been established by Ball and Queyranne through booking limit policies, which raise the acceptance threshold as the remaining inventory dwindles. However, when the item is sold through dynamic pricing instead, there is the additional challenge...
• 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...
• Intertemporal Price Discrimination with Time-Varying Valuations AI翻译
  作者：Araman, Victor F.; Fayad, Bassam
  作者单位：American University of Beirut; Sorbonne Universite; Universite Paris Cite
  摘要：A firm that sells a nonperishable product considers intertemporal price discrimination in the objective of maximizing its long-run average revenue. We consider a general model of patient customers with changing valuations. Arriving customers wait for a random but bounded length of time and purchase the product when its price falls below their valuation, which varies following a stochastic process. We show the optimality of a class of cyclic strategies and obtain an algorithm that yields them. ...
• Technical Note-A Stochastic Assignment Problem with Unknown Eligibility Probabilities AI翻译
  作者：Ross, Sheldon M.; Weiss, Gideon; Zhang, Zhengyu
  作者单位：University of Southern California; University of Haifa
  摘要：Consider n initially empty boxes, numbered 1 through n. Balls arrive sequentially. Each ball has a binary n-vector attached to it, with the interpretation that the ball is eligible to be put in box i if component i of its vector is equal to 1. An arriving ball can be put in any empty box for which it is eligible. Assuming that components of the vector are independent Bernoulli random variables with initially unknown probabilities, our primary interest is to compare several policies to determin...
• Technical Note-A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents AI翻译
  作者：Russo, Daniel
  作者单位：Columbia University
  摘要：This note gives a short, self-contained proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. I consider a Gaussian multiarmed bandit problem with discount factor.. The Gittins index of an arm is shown to equal the gamma-quantile of the posterior distribution of the arm's mean plus an error term that vanishes as gamma -> 1. In this sense, for sufficiently patient agents, a Gittins index measures the highest plausible mean-reward of an arm in a mann...
• The Discrete Moment Problem with Nonconvex Shape Constraints AI翻译
  作者：Chen, Xi; He, Simai; Jiang, Bo; Ryan, Christopher Thomas; Zhang, Teng
  作者单位：New York University; Shanghai University of Finance & Economics; University of British Columbia; Stanford University
  摘要：The discrete moment problem is a foundational problem in distribution-free robust optimization, where the goal is to find a worst-case distribution that satisfies a given set of moments. This paper studies the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC), has an increasing failure rate (IFR), or increasing generalized failure rate (IGFR). These classes of shape constraints have not previously been studied in th...
• Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions AI翻译
  作者：Golrezaei, Negin; Javanmard, Adel; Mirrokni, Vahab
  作者单位：Massachusetts Institute of Technology (MIT); University of Southern California; Alphabet Inc.; Google Incorporated
  摘要：Motivated by pricing in ad exchange markets, we consider the problem of robust learning of reserve prices against strategic buyers in repeated contextual second-price auctions. Buyers' valuations for an item depend on the context that describes the item. However, the seller is not aware of the relationship between the context and buyers' valuations (i.e., buyers' preferences). The seller's goal is to design a learning policy to set reserve prices via observing the past sales data, and her obje...
• 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...
• Robust Power Management via Learning and Game Design AI翻译
  作者：Zhou, Zhengyuan; Mertikopoulos, Panayotis; Moustakas, Aris L.; Bambos, Nicholas; Glynn, Peter
  作者单位：New York University; 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); Inria; 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 ...