More Like this

1. Optimal algorithms for scheduling under time-of-use tariffs

   https://doi.org/10.1007/s10479-021-04059-3  

   Chen, Lin ; Megow, Nicole ; Rischke, Roman ; Stougie, Leen ; Verschae, José ( September 2021 , Annals of Operations Research)

   null (Ed.)

   Abstract We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some time-dependent cost, the time-of-use tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive single-machine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when time-of-use tariffs must be considered. We contribute optimal polynomial-time algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomial-time algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomial-time approximation scheme (PTAS) based on a dual scheduling approach introduced for scheduling on a machine of varying speed. As the weighted problem is strongly NP-hard, our PTAS is the best possible approximation we can hope for. For preemptive scheduling to minimize the makespan, we show that there is a comparably simple optimal algorithm with polynomial running time. This is true even in a certain generalized model with unrelated machines. 

   more » « less
2. Simple, Credible, and Approximately-Optimal Auctions

   Daskalakis, C ; Fishelson, M ; Lucier, B ; Syrgkanis, V ; Velusamy, S ( January 2020 , 21st ACM Conference on Economics and Computation, EC 2020)

   null (Ed.)

   We identify the first static credible mechanism for multi-item additive auctions that achieves a constant factor of the optimal revenue. This is one instance of a more general framework for designing two-part tariff auctions, adapting the duality framework of Cai et al [CDW16]. Given a (not necessarily incentive compatible) auction format A satisfying certain technical conditions, our framework augments the auction with a personalized entry fee for each bidder, which must be paid before the auction can be accessed. These entry fees depend only on the prior distribution of bidder types, and in particular are independent of realized bids. Our framework can be used with many common auction formats, such as simultaneous first-price, simultaneous second-price, and simultaneous all-pay auctions. If all-pay auctions are used, we prove that the resulting mechanism is credible in the sense that the auctioneer cannot benefit by deviating from the stated mechanism after observing agent bids. If second-price auctions are used, we obtain a truthful O(1)-approximate mechanism with fixed entry fees that are amenable to tuning via online learning techniques. Our results for first price and all-pay are the first revenue guarantees of non-truthful mechanisms in multi-dimensional environments; an open question in the literature [RST17]. 

   more » « less
3. A two-sided model of paid peering

   https://doi.org/10.1016/j.telpol.2022.102352  

   Nikkhah, Ali ; Jordan, Scott ( May 2022 , Telecommunications policy)

   Internet users have suffered collateral damage in tussles over paid peering between large ISPs and large content providers. Paid peering is a relationship where two networks exchange traffic with payment, which provides direct access to each other’s customers without having to pay a third party to carry that traffic for them. The issue will arise again when the United States Federal Communications Commission (FCC) considers a new net neutrality order. We first consider the effect of paid peering on broadband prices. We adopt a two-sided market model in which an ISP maximizes profit by setting broadband prices and a paid peering price. We analytically derive the profit-maximizing prices, and show that they satisfy a generalization of the well-known Lerner rule. Our result shows that paid peering fees reduce the premium plan price, increase the video streaming price and the total price for premium tier customers who subscribe to video streaming services; however, the ISP passes on to its customers only a portion of the revenue from paid peering. ISP profit increases but video streaming profit decreases as an ISP moves from settlement-free peering to paid peering price. We next consider the effect of paid peering on consumer surplus. We find that consumer surplus is a uni-modal function of the paid peering fee. The paid peering fee that maximizes consumer surplus depends on elasticities of demand for broadband and for video streaming. However, consumer surplus is maximized when paid peering fees are significantly lower than those that maximize ISP profit. However, it does not follow that settlement-free peering is always the policy that maximizes consumer surplus. The peering price depends critically on the incremental ISP cost per video streaming subscriber; at different costs, it can be negative, zero, or positive. 

   more » « less
4. Online Revenue Maximization for Server Pricing

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

   Boodaghians, Shant ; Fusco, Federico ; Leonardi, Stefano ; Mansour, Yishay ; Mehta, Ruta ( July 2020 , Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20))

   null (Ed.)

   Efficient and truthful mechanisms to price time on remote servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers online revenue maximization for a unit capacity server, when jobs are non preemptive, in the Bayesian setting: at each time step, one job arrives, with parameters drawn from an underlying distribution.We design an efficiently computable truthful posted price mechanism, which maximizes revenue 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.We also show the pricing mechanism is robust to learning the job distribution from samples, where polynomially many samples suffice to obtain near optimal prices.

    

   more » « less
5. Online Pricing for Multi-User Multi-Item Markets

   Erginbas, Yigit Efe ( December 2023 , Advances in neural information processing systems)

   Online pricing has been the focus of extensive research in recent years, particularly in the context of selling an item to sequentially arriving users. However, what if a provider wants to maximize revenue by selling multiple items to multiple users in each round? This presents a complex problem, as the provider must intelligently offer the items to those users who value them the most without exceeding their highest acceptable prices. In this study, we tackle this challenge by designing online algorithms that can efficiently offer and price items while learning user valuations from accept/reject feedback. We focus on three user valuation models (fixed valuations, random experiences, and random valuations) and provide algorithms with nearly-optimal revenue regret guarantees. In particular, for any market setting with N users, M items, and load L (which roughly corresponds to the maximum number of simultaneous allocations possible), our algorithms achieve regret of order O(NMloglog(LT)) under fixed valuations model, O(√NMLT) under random experiences model and O(√NMLT) under random valuations model in T rounds. 

   more » « less