skip to main content


Title: Competitive Bidding Strategies for Online Linear Optimization with Inventory Management Constraints
This paper develops competitive bidding strategies for an online linear optimization problem with inventory management constraints in both cost minimization and profit maximization settings. In the minimization problem, a decision maker should satisfy its time-varying demand by either purchasing units of an asset from the market or producing them from a local inventory with limited capacity. In the maximization problem, a decision maker has a time-varying supply of an asset that may be sold to the market or stored in the inventory to be sold later. In both settings, the market price is unknown in each timeslot and the decision maker can submit a finite number of bids to buy/sell the asset. Once all bids have been submitted, the market price clears and the amount bought/sold is determined based on the clearing price and submitted bids. From this setup, the decision maker must minimize/maximize their cost/profit in the market, while also devising a bidding strategy in the face of an unknown clearing price. We propose DEMBID and SUPBID, two competitive bidding strategies for these online linear optimization problems with inventory management constraints for the minimization and maximization setting respectively. We then analyze the competitive ratios of the proposed algorithms and show that the performance of our algorithms approaches the best possible competitive ratio as the maximum number of bids increases. As a case study, we use energy data traces from Akamai data centers, renewable outputs from NREL, and energy prices from NYISO to show the effectiveness of our bidding strategies in the context of energy storage management for a large energy customer participating in a real-time electricity market.  more » « less
Award ID(s):
2105494 1763617 2136199 1908298 2045641
NSF-PAR ID:
10346192
Author(s) / Creator(s):
; ; ; ;
Date Published:
Journal Name:
ACM SIGMETRICS Performance Evaluation Review
Volume:
49
Issue:
3
ISSN:
0163-5999
Page Range / eLocation ID:
6 to 7
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    Convergence bidding, has been adopted in recent years by most Independent System Operators (ISOs) in the United States as a relatively new market mechanism to enhance market efficiency. Convergence bidding affects many aspects of the operation of the electricity markets and there is currently a gap in the literature on understanding how the market participants strategically select their convergence bids in practice. To address this open Problem, in this paper, we study three years of real-world market data from the California ISO energy market. First, we provide a data - driven overview of all submitted convergence bids (CBs) and analyze the performance of each individual convergence bidder based on the number of their submitted CBs, the number of locations that they placed the CBs, the percentage of submitted supply or demand and CBs, the amount of cleared CBs, and their gained profit or loss. Next, we scrutinize the bidding strategies of the 13 largest market players that account for 75 % of all CBs in. the California ISO market. We identify quantitative features to characterize and distinguish their different convergence bidding strategies. This analysis results in revealing three different classes of CB strategies that are used in practice. We identify the differences between. these strategic bidding classes and compare their advantages and disadvantages. We also explain how some of the most active market participants are using bidding strategies that do not any of the strategic bidding methods that currently exist in the literature. 
    more » « less
  2. This paper discusses a market-based pool strategy for a microgrid (MG) to optimally trade electric power in the distribution electricity market (DEM). The increasing penetration levels of distributed energy resources (DERs) and MGs in distribution system (DS) stress distribution system operator (DSO) and require higher levels of coordinated control strategies. The distribution system operator has limited visibility and control over such distributed resources. To reduce the complexity of the system and improve the efficiency of the electricity market operation, we propose a decentralized pool strategy for an MG to integrate with a distribution system through a market mechanism. A market-based interactions procedure between MGs and DS is developed for MGs as price-makers to find an optimal bidding/offering strategy efficiently. To achieve a market equilibrium among all entities, we initially cast this problem as a bi-level programming problem, in which the upper level is an MG optimal scheduling problem and the lower level presents a DEM clearing mechanism. The proposed bi-level model is converted to a single mix-integer model which is easier to solve. Uncertainties associated with MG's rivals' offers and demands' bids are considered in this problem. The solution results from a modified IEEE 33-Bus distribution system are presented and discussed. Finally, some conclusions are drawn and examined. 
    more » « less
  3. This paper proposes a market mechanism for multi-interval electricity markets with generator and storage participants. Drawing ideas from supply function bidding, we introduce a novel bid structure for storage participation that allows storage units to communicate their cost to the market using energy cycling functions that map prices to cycle depths. The resulting market-clearing process--implemented via convex programming--yields corresponding schedules and payments based on traditional energy prices for power supply and per-cycle prices for storage utilization. We illustrate the benefits of our solution by comparing the competitive equilibrium of the resulting mechanism to that of an alternative solution that uses prosumer-based bids. Our solution shows several advantages over the prosumer-based approach. It does not require a priori price estimation. It also incentivizes participants to reveal their truthful costs, thus leading to an efficient, competitive equilibrium. Numerical experiments using New York Independent System Operator (NYISO) data validate our findings. 
    more » « less
  4. Large fractions of online advertisements are sold via repeated second-price auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer optimize reserve prices by learning from the previous bids while accounting for the long-term incentives and strategic behavior of the bidders? To this end, we consider a seller who repeatedly sells ex ante identical items via a second-price auction. Buyers’ valuations for each item are drawn independently and identically from a distribution F that is unknown to the seller. We find that if the seller attempts to dynamically update a common reserve price based on the bidding history, this creates an incentive for buyers to shade their bids, which can hurt revenue. When there is more than one buyer, incentive compatibility can be restored by using personalized reserve prices, where the personal reserve price for each buyer is set using the historical bids of other buyers. Such a mechanism asymptotically achieves the expected revenue obtained under the static Myerson optimal auction for F. Further, if valuation distributions differ across bidders, the loss relative to the Myerson benchmark is only quadratic in the size of such differences. We extend our results to a contextual setting where the valuations of the buyers depend on observed features of the items. When up-front fees are permitted, we show how the seller can determine such payments based on the bids of others to obtain an approximately incentive-compatible mechanism that extracts nearly all the surplus. 
    more » « less
  5. The classic Vickrey-Clarke-Groves (VCG) mech-anism ensures incentive compatibility, i.e., that truth-telling of all agents is a dominant strategy, for a static one-shot game. However, in a dynamic environment that unfolds over time, the agents’ intertemporal payoffs depend on the expected future controls and payments, and a direct extension of the VCG mechanism is not sufficient to guarantee incentive compati-bility. In fact, it does not appear to be feasible to construct mechanisms that ensure the dominance of dynamic truth-telling for agents comprised of general stochastic dynamic systems. The contribution of this paper is to show that such a dynamic stochastic extension does exist for the special case of Linear-Quadratic-Gaussian (LQG) agents with a careful construction of a sequence of layered payments over time. We propose a layered version of a modified VCG mechanism for payments that decouples the intertemporal effect of current bids on future payoffs, and prove that truth-telling of dynamic states forms a dominant strategy if system parameters are known and agents are rational. An important example of a problem needing such optimal dynamic coordination of stochastic agents arises in power systems where an Independent System Operator (ISO) has to ensure balance of generation and consumption at all time instants, while ensuring social optimality (maximization of the sum of the utilities of all agents). Addressing strategic behavior is critical as the price-taking assumption on market participants may not hold in an electricity market. Agents, can lie or otherwise game the bidding system. The challenge is to determine a bidding scheme between all agents and the ISO that maximizes social welfare, while taking into account the stochastic dynamic models of agents, since renewable energy resources such as solar/wind are stochastic and dynamic in nature, as are consumptions by loads which are influenced by factors such as local temperatures and thermal inertias of facilities. 
    more » « less