skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


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
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. ; (, IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT))
    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. ; ; ; (, Power Systems Computation Conference (PSCC))
    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
  3. ; ; (, IEEE Transactions on Power Systems)
    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
  4. ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Guruswami, Venkatesan (Ed.)
    In decentralized finance ("DeFi"), automated market makers (AMMs) enable traders to programmatically exchange one asset for another. Such trades are enabled by the assets deposited by liquidity providers (LPs). The goal of this paper is to characterize and interpret the optimal (i.e., profit-maximizing) strategy of a monopolist liquidity provider, as a function of that LP’s beliefs about asset prices and trader behavior. We introduce a general framework for reasoning about AMMs based on a Bayesian-like belief inference framework, where LPs maintain an asset price estimate, which is updated by incorporating traders' price estimates. In this model, the market maker (i.e., LP) chooses a demand curve that specifies the quantity of a risky asset to be held at each dollar price. Traders arrive sequentially and submit a price bid that can be interpreted as their estimate of the risky asset price; the AMM responds to this submitted bid with an allocation of the risky asset to the trader, a payment that the trader must pay, and a revised internal estimate for the true asset price. We define an incentive-compatible (IC) AMM as one in which a trader’s optimal strategy is to submit its true estimate of the asset price, and characterize the IC AMMs as those with downward-sloping demand curves and payments defined by a formula familiar from Myerson’s optimal auction theory. We generalize Myerson’s virtual values, and characterize the profit-maximizing IC AMM. The optimal demand curve generally has a jump that can be interpreted as a "bid-ask spread," which we show is caused by a combination of adverse selection risk (dominant when the degree of information asymmetry is large) and monopoly pricing (dominant when asymmetry is small). This work opens up new research directions into the study of automated exchange mechanisms from the lens of optimal auction theory and iterative belief inference, using tools of theoretical computer science in a novel way. 
    more » « less
  5. ; (, Operations Research)
    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
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email