Abstract
Consider a buyer with independent additive valuations for a set of goods, and a seller who is constrained to sell one item at a time in an online fashion. If the seller is constrained to run independent auctions for each item, then he would run Myerson's optimal auction for each item. If the seller is allowed to use the full power of dynamic mechanism design and have the auction for each item depend on the outcome of the previous auctions, he is able to perform much better. The main issues in implementing such strategies in online settings where items arrive over time are that the auction might be too complicated or it makes too strong assumptions on the buyer's rationality or seller's commitment over time. This motivates us to explore a restricted family of dynamic auctions that can be implemented in an online fashion and without too much commitment from the seller ahead of time. In particular, we study a set of auction in which the space of single-shot auctions is augmented with a structure that we call bank account, a real number for each node that summarizes the history so far. This structure allows the seller to store deficits or surpluses of buyer utility from each individual auction and even them out on the long run. This is akin to enforcing individual rationality constraint on average rather than per auction. We also study the effect of enforcing a maximum limit to the values that bank account might grow, which means that we enforce that besides the auction being individually rational on average it is also not far from being individually rational at any given interval. Interestingly, even with these restrictions, we can achieve significantly better revenue and social welfare compared to separate Myerson auctions.
Introduction
In modern digital advertising and online marketplaces, sellers typically rely on static auctions, such as Myerson’s optimal auction, for each individual transaction. While these mechanisms are robust and well-understood, they are fundamentally limited by treating every interaction in isolation. Theoretically, dynamic auctions—where the rules of a current auction are informed by the history of previous interactions—can extract significantly more revenue.
However, the gap between theoretical dynamic design and practical implementation is vast. Full dynamic mechanisms often result in a "gigantic design space" that is computationally intractable and difficult for buyers to navigate, as individual bids can have complex, long-term repercussions. This paper proposes a "middle ground": Bank Account Mechanisms (BAMs). These mechanisms are designed to be simpler than the theoretical ideal while remaining significantly more effective than static auctions.
The Bank Account Mechanism (BAM)
The core innovation of a BAM is the addition of a "bank account" to a standard auction framework. This account is a single real number that serves as a sufficient statistic for the history of the interaction between a buyer and a seller.
As illustrated in the figure above, the bank account tracks the "surplus" or "deficit" of utility a buyer receives over time. If a buyer pays more than their valuation in one round, they "deposit" utility into the account; conversely, if they receive a bargain, they "withdraw." This allows the seller to relax the standard Individual Rationality (IR) constraint. Instead of requiring the buyer to profit from every single item (stage-wise IR), BAMs only require that the buyer profits on average over the long run.
To manage trust and commitment, the authors introduce a bank account limit ($L$). This limit represents the maximum allowable debt or credit. A limit of zero corresponds to a standard static auction, while increasing $L$ allows the seller to capture more of the buyer's total value by smoothing out revenue across transactions.
Experimental Evaluation
The authors evaluated BAMs using synthetic simulations across three standard probability distributions for buyer valuations: Exponential, Lognormal, and Uniform. They specifically examined a practical implementation called the Heuristic Double-Reserve (HDR) auction, which uses two reserve prices (high and low) based on the current state of the buyer's bank account.
As shown in the results above, even with relatively small bank account limits, BAMs consistently outperform separate Myerson auctions. Key findings include:
- Revenue Superiority: BAMs achieve higher revenue than static auctions even when the limit $L$ is less than 50% of the mean valuation.
- Surplus Extraction: As the limit $L$ grows, both the optimal (OPT) and heuristic (HDR) mechanisms converge toward full surplus extraction, where the seller captures nearly 100% of the buyer's valuation.
- Efficiency Gains: The HDR mechanism often achieves higher social welfare (efficiency) than the optimal revenue-maximizing version, particularly in the lognormal distribution case.
Conclusion and Future Work
Bank Account Mechanisms provide a practical path toward implementing dynamic auctions in real-world settings. By using a simple running balance to track utility, sellers can significantly increase revenue without the computational complexity of full dynamic design.
Future research directions include extending the model to multiple competing buyers, addressing potential correlations in valuations over time, and accounting for buyers who may be budget-constrained or myopic rather than perfectly rational. Additionally, the role of seller commitment remains a critical factor; the success of these mechanisms relies on the buyer's trust that the seller will adhere to the long-term rules of the bank account.
Summary updated