More Like this

1. Pricing for Routing and Flow-Control in Payment Channel Networks

   https://doi.org/10.1109/TON.2025.3588049  

   Sankagiri, Suryanarayana; Hajek, Bruce (January 2025, IEEE Transactions on Networking)

   A payment channel network is a blockchain-based overlay mechanism that allows parties to transact more efficiently than directly using the blockchain. These networks are composed of payment channels that carry transactions between pairs of users. Due to its design, a payment channel cannot sustain a net flow of money in either direction indefinitely. Therefore, a payment channel network cannot serve transaction requests arbitrarily over a long period of time. We introduce DEBT control, a joint routing and flow-control protocol that guides a payment channel network towards an optimal operating state for any steady-state demand. In this protocol, each channel sets a price for routing transactions through it. Transacting users make flow-control and routing decisions by responding to these prices. A channel updates its price based on the net flow of money through it. We develop the protocol by formulating a network utility maximization problem and solving its dual through gradient descent. We provide convergence guarantees for the protocol and also illustrate its behavior through simulations. 

   more » « less
2. Leveraging ride-hailing services for social good: Fleet optimal routing and system optimal pricing

   https://doi.org/10.1016/j.trc.2023.104284  

   Ke, Zemian; Qian, Sean (October 2023, Transportation Research Part C: Emerging Technologies)
3. Pricing and Routing Mechanisms for Differentiated Services in an Electric Vehicle Public Charging Station Network

   https://doi.org/10.1109/TSG.2019.2938960  

   Moradipari, Ahmadreza; Alizadeh, Mahnoosh (March 2020, IEEE Transactions on Smart Grid)
4. Driver Surge Pricing

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

   Garg, Nikhil; Nazerzadeh, Hamid (January 2021, Management Science)

   Ride-hailing marketplaces like Uber and Lyft use dynamic pricing, often called surge, to balance the supply of available drivers with the demand for rides. We study driver-side payment mechanisms for such marketplaces, presenting the theoretical foundation that has informed the design of Uber’s new additive driver surge mechanism. We present a dynamic stochastic model to capture the impact of surge pricing on driver earnings and their strategies to maximize such earnings. In this setting, some time periods (surge) are more valuable than others (nonsurge), and therefore trips of different time lengths vary in the induced driver opportunity cost. First, we show that multiplicative surge, historically the standard on ride-hailing platforms, is not incentive compatible in a dynamic setting. We then propose a structured, incentive-compatible pricing mechanism. This closed-form mechanism has a simple form and is well approximated by Uber’s new additive surge mechanism. Finally, through both numerical analysis and real data from a ride-hailing marketplace, we show that additive surge is more incentive compatible in practice than is multiplicative surge. This paper was accepted by David Simchi-Levi, revenue management and market analytics. 

   more » « less
5. Pricing ordered items

   https://doi.org/10.1145/3519935.3520065  

   Chawla, Shuchi; Rezvan, Rojin; Teng, Yifeng; Tzamos, Christos (June 2022, Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing)

   We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, item-pricing guarantees an O(logn) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than O(√n). Our work provides a more fine-grained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer than n. We assume the items are partitioned in k categories so that items within a category are totally-ordered and a buyer’s value for a bundle depends only on the best item contained from every category. We show that item-pricing guarantees an O(logk) approximation to the optimal (buy-many) revenue and provide a PTAS for computing the optimal item-pricing when k is constant. We also provide a matching lower bound showing that the problem is (strongly) NP-hard even when k=1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable. 

   more » « less