Miscomputing Ratio: The Social Cost of Selfish Computing

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.