A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints

Hiromitsu Hattori, Makoto Yokoo, Yuko Sakurai, Toramatsu Shintani

TL;DR

This paper introduces a novel dynamic programming approach to optimize bidding strategies in sequential auctions. By reformulating the agent's utility as quasi-linear, they significantly reduce the state space and computation time compared to existing additive utility models, achieving an m-fold speedup. They also propose a method to handle budget constraints, yielding a semi-optimal strategy that closely matches the optimal one.

What Problem Does This Paper Address?

Online auctions are booming, and users often participate in multiple auctions, sometimes for items with complementary or substitutable values. While combinatorial auctions handle complex preferences, they are computationally intensive. Sequential auctions, where items are sold one after another, are more common and easier to model. Existing dynamic programming methods for sequential auctions assume an "additive utility" model. This model requires explicitly tracking the agent's remaining money in every state, leading to a state space that grows linearly with the initial budget ($m$). This makes finding optimal strategies computationally prohibitive for large budgets. The paper addresses this by developing a more efficient model that can handle sequential auctions with quasi-linear utility and budget constraints.

Methods

The core innovation lies in the quasi-linear utility model. Instead of explicitly tracking the remaining money in each state, the authors treat the payment for an item as a state-transition cost. This allows them to represent the agent's utility as $U(R_s) - Z_{R_s}$, where $U(R_s)$ is the valuation for the set of items $R_s$ and $Z_{R_s}$ is the total payment. This formulation dramatically reduces the number of states from $O(m \times 2^n)$ to $O(2^n)$, where $n$ is the number of items.

For budget constraints, which are not naturally handled by the quasi-linear model, they propose a two-stage approach:

  1. Obtain an optimal strategy without budget constraints using the quasi-linear dynamic programming method.
  2. Modify this strategy to satisfy budget constraints. This involves calculating an upper bound for each bid based on the original optimal bid and the remaining budget. A second dynamic programming pass is then used to find the best bid within this new upper bound. This yields a "semi-optimal" strategy.

Datasets

Not discussed in the paper. The authors use simulated scenarios for evaluation.

Key Insights and Ideas

  • Quasi-linear utility is a game-changer for sequential auctions: By abstracting away the explicit representation of money, the state space shrinks dramatically, making computations feasible for larger budgets. This is a significant improvement over additive utility models.
  • Payment as a transition cost simplifies state representation: This elegant reformulation is the key to the efficiency gains.
  • Budget constraints require a pragmatic approach: Directly optimizing with budget constraints is hard with the quasi-linear model. The proposed two-stage heuristic (prorating bids) provides a good approximation and is much faster than a full additive model with budget tracking.
  • Speedup is directly related to the budget: The $m$-fold speedup in computation time is a direct consequence of reducing the state space by a factor of $m$.

Key Results

  • The quasi-linear model achieves an $m$-fold speedup in computation time compared to the additive utility model, where $m$ is the initial endowment of money. This is demonstrated through experimental evaluations.
  • The proposed method for handling budget constraints results in a semi-optimal strategy that closely matches the optimal strategy obtained by the additive method (which inherently handles budget constraints).
  • The computation time for the budget-constrained method is approximately $m/2$-fold faster than the additive method.

Limitations and Future Work

  • Heuristic for budget constraints: The method for incorporating budget constraints is heuristic. While it performs well in experiments, it doesn't guarantee optimality. The authors acknowledge that a more sophisticated method for setting bid upper bounds might be needed if winning probabilities change drastically with small bid variations.
  • Learning optimal strategies: The current approach assumes the agent knows the distribution of other agents' bids. Future work includes developing methods for learning optimal bidding strategies from experience, potentially using reinforcement learning techniques, without prior knowledge of these distributions.
  • Generalization of budget constraint handling: Further evaluation across various problem settings is needed to fully understand the efficiency of the budget constraint handling method.

Summary updated

Abstract

In this paper, we develop a new method for finding an optimal biddingstrategy in sequential auctions, using a dynamic programming technique. Theexisting method assumes that the utility of a user is represented in anadditive form. Thus, the remaining endowment of money must be explicitlyrepresented in each state, and the calculation of the optimal biddingstrategy becomes time-consuming when the initial endowment of money mbecomes large.In this paper, we develop a new problem formalization that avoids explicitlyrepresenting the remaining endowment, by assuming the utility of a user canbe represented in a quasi-linear form, and representing the payment as astate-transition cost. Experimental evaluations show that we can obtainmore than an m-fold speed-up in the computation time. Furthermore, we havedeveloped a method for obtaining a semi-optimal bidding strategy underbudget constraints, and have experimentally confirmed the efficacy of thismethod.
BibTeX
@inproceedings{hattori2001dynamic,
  author = {Hiromitsu Hattori and Makoto Yokoo and Yuko Sakurai and Toramatsu Shintani},
  title = {{A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2001},
}
Figure