Miscomputing ratio: The social cost of selfish computing

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 miscomputin8 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