More Like this

1. Online revenue maximization for server pricing

   https://doi.org/10.1007/s10458-022-09544-y  

   Boodaghians, Shant ; Fusco, Federico ; Leonardi, Stefano ; Mansour, Yishay ; Mehta, Ruta ( April 2022 , Autonomous Agents and Multi-Agent Systems)

   Abstract Efficient and truthful mechanisms to price resources on servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers revenue maximization in the online stochastic setting with non-preemptive jobs and a unit capacity server. One agent/job arrives at every time step, with parameters drawn from the underlying distribution. We design a posted-price mechanism which can be efficiently computed and is revenue-optimal in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent’s type, and the computed pricing scheme is deterministic, depending only on the length of the allotted time interval and on the earliest time the server is available. We also prove that the proposed pricing strategy is robust to imprecise knowledge of the job distribution and that a distribution learned from polynomially many samples is sufficient to obtain a near-optimal truthful pricing strategy. 

   more » « less
2. Efficient Algorithms for Learning Revenue-Maximizing Two-Part Tariffs

   https://doi.org/10.24963/ijcai.2020/47  

   Balcan, Maria-Florina ; Prasad, Siddharth ; Sandholm, Tuomas ( July 2020 , Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI-20})

   null (Ed.)

   A two-part tariff is a pricing scheme that consists of an up-front lump sum fee and a per unit fee. Various products in the real world are sold via a menu, or list, of two-part tariffs---for example gym memberships, cell phone data plans, etc. We study learning high-revenue menus of two-part tariffs from buyer valuation data, in the setting where the mechanism designer has access to samples from the distribution over buyers' values rather than an explicit description thereof. Our algorithms have clear direct uses, and provide the missing piece for the recent generalization theory of two-part tariffs. We present a polynomial time algorithm for optimizing one two-part tariff. We also present an algorithm for optimizing a length-L menu of two-part tariffs with run time exponential in L but polynomial in all other problem parameters. We then generalize the problem to multiple markets. We prove how many samples suffice to guarantee that a two-part tariff scheme that is feasible on the samples is also feasible on a new problem instance with high probability. We then show that computing revenue-maximizing feasible prices is hard even for buyers with additive valuations. Then, for buyers with identical valuation distributions, we present a condition that is sufficient for the two-part tariff scheme from the unsegmented setting to be optimal for the market-segmented setting. Finally, we prove a generalization result that states how many samples suffice so that we can compute the unsegmented solution on the samples and still be guaranteed that we get a near-optimal solution for the market-segmented setting with high probability.

    

   more » « less
3. Robust Auctions for Revenue via Enhanced Competition

   https://doi.org/10.1287/opre.2019.1929  

   Roughgarden, Tim ; Talgam-Cohen, Inbal ; Yan, Qiqi ( July 2020 , Operations Research)

   Most results in revenue-maximizing mechanism design hinge on “getting the price right”—selling goods to bidders at prices low enough to encourage a sale but high enough to garner nontrivial revenue. This approach is difficult to implement when the seller has little or no a priori information about bidder valuations or when the setting is sufficiently complex, such as matching markets with heterogeneous goods. In this paper, we apply a robust approach to designing auctions for revenue. Instead of relying on prior knowledge regarding bidder valuations, we “let the market do the work” and let prices emerge from competition for scarce goods. We analyze the revenue guarantees of one of the simplest imaginable implementations of this idea: first, we enhance competition in the market by increasing demand (or alternatively, by limiting supply), and second, we run a standard second price (Vickrey) auction. In their renowned work from 1996 , Bulow and Klemperer [Bulow J, Klemperer P (1996) Auctions vs. negotiations. Amer. Econom. Rev. 86(1):180–194.] apply this method to markets with single goods. As our main result, we give the first application beyond single-parameter settings, proving that, simultaneously for many valuation distributions, this method achieves expected revenue at least as good as the optimal revenue in the original market. Our robust and simple approach provides a handle on the elusive optimal revenue in multiitem matching markets and shows when the use of welfare-maximizing Vickrey auctions is justified, even if revenue is a priority. By establishing quantitative tradeoffs, our work provides guidelines for a seller in choosing among two different revenue-extracting strategies: sophisticated pricing based on market research or advertising to draw additional bidders. 

   more » « less
4. Pricing Multi-Interval Dispatch under Uncertainty Part I: Dispatch-Following Incentives

   https://doi.org/10.1109/TPWRS.2021.3055730  

   Guo, Ye ; Chen, Cong ; Tong, Lang ( January 2021 , IEEE Transactions on Power Systems)

   null (Ed.)

   Pricing multi-interval economic dispatch of electric power under operational uncertainty is considered in this two- part paper. Part I investigates dispatch-following incentives of profit-maximizing generators and shows that, under mild conditions, no uniform-pricing scheme for the rolling-window economic dispatch provides dispatch-following incentives that avoid discriminative out-of-the-market uplifts. A nonuniform pricing mechanism, referred to as the temporal locational marginal pricing (TLMP), is proposed. As an extension of the standard locational marginal pricing (LMP), TLMP takes into account both generation and ramping-induced opportunity costs. It eliminates the need for the out-of-the-market uplifts and guarantees full dispatch-following incentives regardless of the accuracy of the demand forecasts used in the dispatch. It is also shown that, under TLMP, a price-taking market participant has incentives to bid truthfully with its marginal cost of generation. Part II of the paper extends the theoretical results developed in Part I to more general network settings. It investigates a broader set of performance measures, including the incentives of the truthful revelation of ramping limits, revenue adequacy of the operator, consumer payments, generator profits, and price volatility under the rolling-window dispatch model with demand forecast errors. 

   more » « less
5. Privacy-Preserving Dynamic Personalized Pricing with Demand Learning

   https://doi.org/10.1287/mnsc.2021.4129  

   Chen, Xi ; Simchi-Levi, David ; Wang, Yining ( October 2021 , Management Science)

   null (Ed.)

   The prevalence of e-commerce has made customers’ detailed personal information readily accessible to retailers, and this information has been widely used in pricing decisions. When using personalized information, the question of how to protect the privacy of such information becomes a critical issue in practice. In this paper, we consider a dynamic pricing problem over T time periods with an unknown demand function of posted price and personalized information. At each time t, the retailer observes an arriving customer’s personal information and offers a price. The customer then makes the purchase decision, which will be utilized by the retailer to learn the underlying demand function. There is potentially a serious privacy concern during this process: a third-party agent might infer the personalized information and purchase decisions from price changes in the pricing system. Using the fundamental framework of differential privacy from computer science, we develop a privacy-preserving dynamic pricing policy, which tries to maximize the retailer revenue while avoiding information leakage of individual customer’s information and purchasing decisions. To this end, we first introduce a notion of anticipating [Formula: see text]-differential privacy that is tailored to the dynamic pricing problem. Our policy achieves both the privacy guarantee and the performance guarantee in terms of regret. Roughly speaking, for d-dimensional personalized information, our algorithm achieves the expected regret at the order of [Formula: see text] when the customers’ information is adversarially chosen. For stochastic personalized information, the regret bound can be further improved to [Formula: see text]. This paper was accepted by J. George Shanthikumar, big data analytics. 

   more » « less