Kate Larson and Tuomas Sandholm
Auctions are useful mechanism for allocating items (goods, tasks, resources, etc.) in multiagent sys-tems. The bulk of auction theory assumes that the bidders’ valuations for items are given a priori. In many applications, however, the bidders need to expend significant effort to determine their valua-tions. In this paper we analyze computational bid-der agents that can refine their valuations (own and others') using computation. We introduce a way of measuring the negative impact of agents choosing computing strategies selfishly. Our miscomputin 8 ratio isolates the effect of selfish computing from that of selfish bidding. We show that under both limited computing and costly computing, the out-come can be arbitrarily far worse than in the case where computations are coordinated. However, un-der reasonable assumptions on how limited com-puting changes valuations, bounds can be obtained. Finally, we show that by carefully designing com-puting cost functions, it is possible to provide ap-propriate incentives for bidders to choose comput-ing policies that result in the optimal social welfare.