Competitive analysis of incentive compatible on-line auctions.

*(English)*Zbl 1098.91044Summary: This paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, on-line auctions.

We first characterize exactly on-line auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller’s revenue and in terms of the total social efficiency obtained.

We first characterize exactly on-line auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller’s revenue and in terms of the total social efficiency obtained.

##### MSC:

91B26 | Auctions, bargaining, bidding and selling, and other market models |

68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |

68Q25 | Analysis of algorithms and problem complexity |

68W40 | Analysis of algorithms |

PDF
BibTeX
XML
Cite

\textit{R. Lavi} and \textit{N. Nisan}, Theor. Comput. Sci. 310, No. 1--3, 159--180 (2004; Zbl 1098.91044)

Full Text:
DOI

##### References:

[1] | Z. Bar-Yossef, K. Hildrum, F. Wu, Incentive-compatible online auctions for digital goods, in: Proceedings of the 13th Symposium on Discrete Algorithms (SODA’02), 2002. · Zbl 1092.91522 |

[2] | A. Blum, V. Kumar, A. Rudra, F. Wu, Online learning in online auctions, in: Proceedings of the 14th Symposium on Discrete Algorithms (SODA’03), 2003. · Zbl 1094.68620 |

[3] | A. Blum, T. Sandholm, M. Zinkevich, Online algorithms for market clearing, in: Proceedings of the 13th Symposium on Discrete Algorithms (SODA’02), 2002. · Zbl 1092.91523 |

[4] | Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), The MIT Press Cambridge, MA · Zbl 1158.68538 |

[5] | ebay, Web page: http://www.ebay.com. |

[6] | El-Yaniv, R., Competitive solutions for on-line financial problems, () |

[7] | El-Yaniv, R.; Borodin, A., On-line computation and competitive analysis, (1998), Cambridge University Press Cambridge · Zbl 0931.68015 |

[8] | R. El-Yaniv, A. Fiat, R. Karp, G. Turpin, Competitive analysis of financial games, in: Proceedings of the 33rd Symposium on Foundations of Computer Science (FOCS’92), 1992, pp. 327-333. · Zbl 0977.68504 |

[9] | E. Ephrati, J.S. Rosenschein, The clarke tax as a consensus mechanism among automated agents, in: Proceedings of the National Conference on Artificial Intelligence, 1991. |

[10] | Ferguson, D.F.; Nikolaou, C.; Sairamesh, J.; Yemini, Y., Economic models for allocating resources in computer systems, () |

[11] | A. Fiat, A. Goldberg, J. Hartline, A. Karlin, Competitive generalized auctions, in: Proceedings of the 34th ACM Symposium on Theory of Computing (STOC’02), 2002. |

[12] | Fiat, A.; Woeginger, G., Online algorithms: the state of art, Lecture notes in computer science, Vol. 1442, (1998), Springer Berlin · Zbl 1177.68009 |

[13] | A. Goldberg, J. Hartline, A. Wright, Competitive auctions and digital goods, in: Proceedings of the 12th Symposium on Discrete Algorithms (SODA’01), 2001. · Zbl 0988.91024 |

[14] | Jiang, H.; Jordan, S., Connection establishment in high speed networks, IEEE J. selected areas commun., 13, 7, (1995) |

[15] | Klemperer, P., Auction theorya guide to the literature, J. econom. surveys, 13, 3, 227-286, (1999) |

[16] | Korilis, Y.A.; Lazar, A.A., On the existence of equilibria in non-cooperative optimal flow control, J. ACM, 42, 3, (1995) · Zbl 0885.68015 |

[17] | Kraus, S., An overview of incentive contracting, Artificial intelligence, 83, 2, (1996) |

[18] | A.A. Lazar, N. Semret, The progressive second price auction mechanism for network resource sharing, in: Proceedings of the 8th International Symposium on Dynamic Games, 1998. |

[19] | Mackie-Mason, J.K.; Varian, H.R., Pricing the Internet, () |

[20] | Mas-Collel, A.; Whinston, W.; Green, J., Microeconomic theory, (1995), Oxford University Press Oxford · Zbl 1256.91002 |

[21] | Maskin, E.S.; Riley, J.G., Optimal multi-unit auctions, () |

[22] | Miller, M.S.; Drexler, K.E., Markets and computation: agoric open systems, () |

[23] | Moai, Web page: http://www.moai.com. |

[24] | N. Nisan, Algorithms for selfish agents, in: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS’99), 1999. |

[25] | N. Nisan, A. Ronen, Algorithmic mechanism design (extended abstract), in: Proceedings of the 31st ACM Symposium on Theory of Computing (STOC’99), 1999, pp. 129-140. · Zbl 1346.68246 |

[26] | Rosenschein, J.S.; Zlotkin, G., Rules of encounter: designing conventions for automated negotiation among computers, (1994), MIT Press Cambridge, MA |

[27] | Sandholm, T., Distributed rational decision making, (), 201-258 |

[28] | T. Sandholm, F. Ygge, On the gains and losses of speculation in equilibrium markets, in: Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97), 1999. |

[29] | S. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, in: Proceedings of the ACM SIGCOMM, 1994. |

[30] | Vickrey, W., Counterspeculations, auctions, and competitive sealed tenders, J. finance, 16, 8-37, (1961) |

[31] | Waldspurger, C.A.; Hogg, T.; Huberman, B.A.; Kephart, J.O.; Stornetta, W.S., Spawna distributed computational ecology, IEEE trans. software eng., 18, 2, 103-117, (1992) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.