next up previous
Next: Example Up: General Approach Previous: Approximation via Sampling


The Full Approach

Leveraging from the preceding analysis, we define our sampling-based approach to profit prediction in general simultaneous, multi-unit auctions for interacting goods. In this scenario, let there be $n$ simultaneous, multi-unit auctions for interacting goods $a_0,\ldots,a_{n-1}$. The auctions might close at different times and these times are not, in general, known in advance to the bidders. When an auction closes, let us assume that the $m$ units available are distributed irrevocably to the $m$ highest bidders, who each need to pay the price bid by the $m$th highest bidder. This scenario corresponds to an $m$th price ascending auction.5 Note that the same bidder may place multiple bids in an auction, and thereby potentially win multiple units. We assume that after the auction closes, the bidders will no longer have any opportunity to acquire additional copies of the goods sold in that auction (i.e., there is no aftermarket).

Our approach is based upon five assumptions. For $G =
(g_0,\ldots,g_{n-1}) \in \Nats^n$, let $v(G) \in \Reals$ represent the value derived by the agent if it owns $g_i$ units of the commodity being sold in auction $a_i$. Note that $v$ is independent of the costs of the commodities. Note further that this representation allows for interacting goods of all kinds, including complementarity and substitutability.6 The assumptions of our approach are as follows:

  1. Closing prices are somewhat, but only somewhat, predictable. That is, given a set of input features $X$, for each auction $a_i$, there exists a sampling rule that outputs a closing price $y_i$ according to a probability distribution of predicted closing prices for $a_i$.

  2. Given a vector of holdings $H=(h_0,\ldots,h_{n-1})$ where $h_i \in \Nats$ represents the quantity of the commodity being sold in auction $a_i$ that are already owned by the agent, and given a vector of fixed closing prices $Y = (y_0,\ldots,y_{n-1})$, there exists a tractable procedure $\mbox{opt}(H,Y)$ to determine the optimal set of purchases $(g_0,\ldots,g_{n-1})$ where $g_i \in \Nats$ represents the number of goods to be purchased in auction $i$ such that

    \begin{displaymath}v(\mbox{opt}(H,Y)+H) - \mbox{opt}(H,Y) \cdot Y \geq v(G+H) - G \cdot
Y\end{displaymath}

    for all $G \in \Nats^n$. This procedure corresponds to the optimization problem $\mbox{opt}(H,i,Y)$ in Equation 3.

  3. An individual agent's bids do not have an appreciable effect on the economy (large population assumption).

  4. The agent is free to change existing bids in auctions that have not yet closed.

  5. Future decisions are made in the presence of complete price information. This assumption corresponds to the operator reordering approximation from the previous section.
While these assumptions are not all true in general, they can be reasonable enough approximations to be the basis for an effective strategy.

By Assumption 3, the price predictor can generate predicted prices prior to considering one's bids. Thus, we can sample from these distributions to produce complete sets of closing prices of all goods.

For each good under consideration, we assume that it is the next one to close. If a different auction closes first, we can then revise our bids later (Assumption 4). Thus, we would like to bid exactly the good's expected marginal utility to us. That is, we bid the difference between the expected utilities attainable with and without the good. To compute these expectations, we simply average the utilities of having and not having the good under different price samples as in Equation 8. This strategy rests on Assumption 5 in that we assume that bidding the good's current expected marginal utility cannot adversely affect our future actions, for instance by impacting our future space of possible bids. Note that as time proceeds, the price distributions change in response to the observed price trajectories, thus causing the agent to continually revise its bids.

Table 1 shows pseudo-code for the entire algorithm. A fully detailed description of an instantiation of this approach is given in Section 5.


Table 1: The decision-theoretic algorithm for bidding in simultaneous, multi-unit, interacting auctions.
\begin{table}{\sloppy\small
\hrule
\vspace{\hrulegap}
\begin{itemize}
\item Let ...
...ction $a_i$.
\end{itemize}\end{itemize}\vspace{\hrulegap}
\hrule
}\end{table}



next up previous
Next: Example Up: General Approach Previous: Approximation via Sampling
Peter Stone 2003-09-24