An official website of the United States government
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
Automatic Power Exchange for Distributed Energy Resource Networks: Flexibility Scheduling and Pricing
This paper proposes an Automatic Power Ex- change (APEX) that enables monetization of underutilized distribution system energy resources. APEX features an open- gate forward market design to incorporate uncertainty from variable resources, and an explicit flexibility market that schedules flexible resources based on information submitted by users through a simple yet expressive order format. We study the non-convex non-preemptive scheduling problem in APEX, proposing polynomial time algorithms with finite and asymptotic performance guarantees. We then analyze the prop- erties of marginal pricing, generalized to fit the APEX context with forward markets and distribution network constraints. We establish that it is revenue adequate but may lead to inadmissible prices for flexible orders. We then suggest a simple pricing mechanism that provably produces admissible prices for users and adequate revenue for APEX if implemented together with the proposed scheduling algorithms.
more »
« less
- Award ID(s):
- 1646612
- PAR ID:
- 10122694
- Date Published:
- Journal Name:
- IEEE Conference on Decision and Control, Miami
- Page Range / eLocation ID:
- 1572 to 1579
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Dynamic Electricity Pricing – Modeling Manufacturer Response and an Application to Cement ProcessingDynamic pricing, also known as real-time pricing, provides electricity users with an economic incentive to adjust electricity use based on changing market conditions. This paper studies the economic implications of real-time pricing mechanisms in a cement manufacturing plant. Production for a representative cement manufacturing plant is modeled using stochastic mathematical programming. The results show that a cement plant can a) reduce electricity costs by shifting electricity load of certain processes to times when electricity prices are lower, and b) profitably reduce electricity use during peak prices through more efficient scheduling of production under real-time pricing compared to fixed pricing. The results suggest that building scheduling flexibility into certain industrial manufacturing processes to reschedule electricity consumption when the electricity prices at their peak may be economical. The results also suggest that shifts in the production schedule of a cement manufacturer that result from real-time pricing may also influence environmental impacts. The modelling framework modeled real-time pricing as a source of risk in this study, which is also applicable to other energy intensive industries. As such, dynamic pricing strategies that include the non-market impacts of electricity generation should be further explored.more » « less
-
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
-
There has been substantial recent concern that pricing algorithms might learn to ``collude.'' Supra-competitive prices can emerge as a Nash equilibrium of repeated pricing games, in which sellers play strategies which threaten to punish their competitors who refuse to support high prices, and these strategies can be automatically learned. In fact, a standard economic intuition is that supra-competitive prices emerge from either the use of threats, or a failure of one party to optimize their payoff. Is this intuition correct? Would preventing threats in algorithmic decision-making prevent supra-competitive prices when sellers are optimizing for their own revenue? No. We show that supra-competitive prices can emerge even when both players are using algorithms which do not encode threats, and which optimize for their own revenue. We study sequential pricing games in which a first mover deploys an algorithm and then a second mover optimizes within the resulting environment. We show that if the first mover deploys any algorithm with a no-regret guarantee, and then the second mover even approximately optimizes within this now static environment, monopoly-like prices arise. The result holds for any no-regret learning algorithm deployed by the first mover and for any pricing policy of the second mover that obtains them profit at least as high as a random pricing would -- and hence the result applies even when the second mover is optimizing only within a space of non-responsive pricing distributions which are incapable of encoding threats. In fact, there exists a set of strategies, neither of which explicitly encode threats that form a Nash equilibrium of the simultaneous pricing game in algorithm space, and lead to near monopoly prices. This suggests that the definition of ``algorithmic collusion'' may need to be expanded, to include strategies without explicitly encoded threats.more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/CDC.2018.8619741
