Miscomputing ratio
Lists
Only you see this
Abstract
Auctions are useful mechanism for allocating items (goods, tasks, resources, etc.) in multiagent systems. The bulk of auction theory assumes that the bidders' valuations for items are given a priori. However, in many applications the bidders need to expend significant computational effort to determine their valuations. We introduce a way of measuring the negative impact of agents choosing computing strategies selfishly. Our miscomputing ratio isolates the effect of selfish computing from that of selfish bidding. We present a Bayes-Nash equilibrium analysis of a Vickrey auction where the bidders' strategies include computational actions. This equilibrium analysis allows us to predict the overhead caused by miscomputing, as measured by the miscomputing ratio. We show that in some situations, the outcome can be arbitrarily far from optimal. However, by carefully designing cost functions for agents, it is possible to provide incentives for bidders to choose computing policies that result in optimal social welfare.
BibTeX
@inproceedings{larson2003miscomputing,
author = {Kate Larson and Tüomas Sandholm},
title = {{Miscomputing ratio}},
booktitle = {Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems - AAMAS '03},
year = {2003},
doi = {10.1145/860616.860619},
}Loading related content...