Bidding Marginal Utility in Simultaneous Auctions

1 Bidding Principles

This paper advocates the following bidding principle for agents participating in simultaneous auctions for comple­ mentary and substitutable goods: "coherent" marginal utility bidding: i.e., bidding marginal utilities on a co­ herent subset of goods. To validate this principle, we compare two combinatorial bidding strategies inspired by ATTAC [Stone et al., 2002] and RoxYBOT [Green­ wald and Boyan, 2001], two agents in the Trading Agent Competition (TAC) (see [Wellman et al., 2002]):

1. one strategy computes the marginal utility of each good independently, much like ATTAC
2. one strategy computes coherent marginal utilities­ it solves the acquisition problem before bidding marginal utilities-much like RoxYBOT

It is established that approach 2 outperforms approach 1 in certain environments. In a longer version of this pa­ per, we experiment with stochastic versions of these algo­ rithms, and establish that approach 2 also outperforms approach 1 in uncertain environments. The insights gained from this study about the design of autonomous bidding agents are applicable beyond the scope of TAC: e.g., eBay is home to numerous SAs for complementary and substitutable goods.

2 Bidding Under Certainty

In constructing bidding policies- mappings from goods to prices-for multi-unit SAs, such as those that charac­ terize TAC, we propose the following natural breakdown of an agent's bidding decisions:

1. how many copies of each good do I want?
2. for the goods I want, how much am I willing to pay?

One straightforward approach to answering these questions, which was employed by ATTAC [Stone et al., 2002], is for the agent to skip question 1, and simply com­ pute how much it is willing to pay for each copy of each good. An alternative approach, employed by RoxYBOT, is to explicitly answer question 1 before question 2; in this way, the agent is certain to bid on a "coherent" set of goods: i.e., a set of goods which together comprise an optimal solution to the acquisition problem.

In this short paper, we compare these two approaches under two assumptions: (i) prices are exogenously de­ termined: i.e., we ignore the impact of agent behav­ iors on prices; and (ii) prices are known with certainty. These assumptions are clearly applicable when prices are posted. In an auction setting, we interpret these assump­ tions as follows: the payment rule is "pay the known price;" the winner determination rule is "win by bidding equal to or more than the price." It is as if an agent is capable of perfectly predicting all other agents' bids, as well as the impact of its own bids on clearing prices.

We begin by investigating ATTAC's approach. One formula for determining willingness to pay is to com­ pute marginal utilities (MUs). This direct MU approach to answering the aforementioned bidding questions ex­ plicitly answers only question 2, but implicitly answers question 1: a willingness to pay 0 suggests that an agent wants 0 additional copies of that good.

As alluded to earlier, computing MUs depends on solv­ ing the acquisition problem. Let us introduce some no­ tation, and formally define acquisition and MU. Let X denote a set of goods; let v(X) denote the (combinato­ rial) valuation of X; let p(x) denote the price of x EX and p(X) = 'L:xEX p(x); finally, let u(X) = v(X) -p(X) denote the utility of X.

Definition 2.1 Given a set of goods X, a combinato­ rial valuation function v : 2x -t ~+, and an exogenous pricing mechanism p : X -t JR+, an optimal solution to the acquisition problem is a subset A · ~ X s. t.

Definition 2.2 Given a set of goods X, the marginal utility of good x is defined as follows: ~-t(xiX) = u(X*)­ u(Y*), where

and

In words, the marginal utility of good x, relative to the set X, is simply the difference between the utility of X, assuming x costs 0, u(Xjp(x) = 0), and the utility of X, assuming x costs oo, u(Xjp(x) = oo).

As is evident from the definition of MU, computing marginal utilities requires two calls to a combinatorial optimization solver. If an agent explicitly answers ques­ tion 1 before question 2, it might determine that it is not necessary to compute marginal utilities for all copies of all goods (although in the worst case it solves one addi­ tional optimization problem). RoxvBoT explicitly an­ swers question 1, before question 2, and usually achieves computational savings over direct MU calculation. But the real motivation behind RoxYBOT's approach is that reasoning about individual goods, rather than coher­ ent sets of goods, when valuations are combinatorial, is suboptimal. In the following example, RoxYBOT's approach is optimal, but the direct MU approach is not.

Example 2.3 Given goods x, y, z, with combinatorial valuations as follows: v(xyz) = v(xy) = v(yz) = 500 and v(x) = v(y) = v(z) = v(xz) = 0. Each good in isolation is of no value, but together with y, either x or z is worth 500. Assume all goods are priced equivalently at 100. The optimal sets of goods in this example are xy and yz, each of which yields utility of 300.

Now let us compute marginal utilities: ~-t(xjxyz) = u(xyzjp(x) = 0)- u(xyzjp(x) = oo) = 400- 300 = 100; ~-t(vixyz) = u(xyzjp(y) = 0)- u(xyzjp(y) = oo) = 4000 = 400; and ~-t(zjxyz) = u(xyzjp(z) = 0) -u(xyzjp(z ) = oo) = 400- 300 = 100. Thus, a MU bidder bids on all three goods, and wins all three goods, obtaining utility v(xyz)- (p(x) + p(y) + p(z)) = 200.

A bidder that first determines the set of goods it wants bids on either x and y, or y and z, but not both. Computing marginal utilities for (say) x and y yields: ~-t(xjxy) = u(xyjp(x) = 0) -u(xyjp(x) = oo) = 400-0 = 400 and ~-t(yixy) = u(xyjp(y) = 0) - u(xyjp(y) = oo) = 400 - 0 = 400. This bidder earns the optimal utility v(xy)- (p(x) + p(y)) = 300. 0

The main observations reported in this paper are the following: (i) for all goods x in an optimal acquisition, the price of x does not exceed the marginal utility of x; (ii) for all goods x not in an optimal acquisition, the marginal utility of x does not exceed the price of x. It follows that bidding marginal utilities on precisely those goods in an optimal acquisition is an optimal bidding policy, if prices are exogenous (e.g., an agent's individual bidding behavior does not impact prices), and prices are known with certainty.

Proposition 2.4 If A · ~ X is an optimal solution to the acquisition problem, then ~-t(xiA*) ~ p(x), Vx E A*, and ~-t(xiA*) ~ p(x), Vx fl. A*.

RoxYBOT's strategy answers questions 1 and 2 in turn, and bids marginal utilities on all the goods it wants. This strategy is optimal, under our assumptions, by the previous observation. In particular, RoxYBOT wins all the goods it wants by bidding marginal utilities. Of course, bidding p(x), or oo, Vx E A*, are also optimal policies in this setting. But bidding the marginal utility of good x is a reasonable heuristic, since it is in fact an optimal bidding policy if the prices of all goods other than x are exogenous and certain.

Acknowledgments

This research was supported by NSF Career Grant #IIS-0133689. The au­ thor also acknowledges Maureen Hurtgen and the funding of CRA 's OMP.