Proxy bidding has proved useful in a variety of real auction formats and has been proposed for some combinatorial auctions. Restricting interactions with the auction system through proxy agents restricts strategic behavior to statements about the relative values of the different combinations. In addition, in some situations, proxy bidding simplifies the strategic problem by reducing the need to estimate the valuations of the other bidders because the proxy agent will bid just enough to win, and no more. Previous discussions of proxy bidding in combinatorial auctions assume the outcome is determined by simulating the auction with automated bidders. In addition to requiring a computationally costly solution to a WDP each iteration, a simulation's accuracy is a function of the bid increment. Decreasing the bid increment generates more accurate results, but greatly increases the running time. In this paper, we present an algorithm that computes the exact outcome of the proxy auction by examining only the events that cause the proxy agents to change their bidding patterns. This study is motivated by proxy bidding in A1BA , a progressive, anonymous-price, combinatorial auction. The salient features of A1BA are that each bidder wins no more than one bundle, the allocation that produces the maximal revenue (with respect to bids) is selected, and the resulting prices support a nonlinear price equilibrium. In the proxy version, bidders submit a statement to their agent that specifies a value for every bundle. The agent then implements straightforward bidding, that is, the agent bids on the bundle that (myopically) maximizes its surplus at the current prices. If it is already winning the bundle, it keeps its current bid. Otherwise, it bids 5 more than the current ask price for the bundle. Given a set of bids, the auctioneer must now solve the Proxy Auction Problem (PAP), that is, it must compute the prices and allocation that results when all of the agents follow the myopic strategy. Figure 1 shows the progress of the auction for proxy agents with the values shown in Table 1 and the bid increment set to 0.05. The horizontal axis in the graph represents time and is scaled such that 1 unit = the number of agents divided by the bid increment. The simulation represented in Figure 1 took 710 iterations, each of which involves solving an (in this case, easy) WDP problem. The problem in Table 1 entails the key challenges for a PAP solver. Of particular interest is the AB line, which changes slope three times on its way to a long plateau, before increasing again when it collides with the {A,B,-} line. The oscillations that occur near the end of the auction reflect the particular way in which A1BA sets prices. The upper edge of an oscillation corresponds to the price presented when that particular bundle is not part of the winning allocation, and the lower edge corresponds to the price when the bundle is part of the winning allocation. Because bidders do not change their bids when they are winning, the lower edge has no impact on the behavior of the agents. The PAP algorithm we sketch here computes the upper edge; if desired, A1BA prices that support the outcome can be computed at the end of the auction.
展开▼
