Optimal bidding algorithms against cheating in multiple-object auctions

Ming Yang Kao, Junfeng Qi, Lei Tan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper studies some basic problems in a multiple-object auction model using methodologies from theoretical computer science. We are especially concerned with situations where an adversary bidder knows the bidding algorithms of all the other bidders. In the two-bidder case, we derive an optimal randomized bidding algorithm, by which the disadvantaged bidder can procure at least half of the auction objects despite the adversary's a priori knowledge of his algorithm. In the general k-bidder case, if the number of objects is a multiple of k, an optimal randomized bidding algorithm is found. If the k − 1 disadvantaged bidders employ that same algorithm, each of them can obtain at least 1/k of the objects regardless of the bidding algorithm the adversary uses. These two algorithms are based on closed-form solutions to certain multivariate probability distributions. In situations where a closed-form solution cannot be obtained, we study a restricted class of bidding algorithms as an approximation to desired optimal algorithms.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings
EditorsTao Jiang, D.T. Lee
PublisherSpringer Verlag
Pages192-201
Number of pages10
ISBN (Print)354063357X, 9783540633570
DOIs
StatePublished - Jan 1 1997
Event3rd Annual International Computing and Combinatorics Conference, COCOON 1997 - Shanghai, China
Duration: Aug 20 1997Aug 22 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1276
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Annual International Computing and Combinatorics Conference, COCOON 1997
CountryChina
CityShanghai
Period8/20/978/22/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal bidding algorithms against cheating in multiple-object auctions'. Together they form a unique fingerprint.

  • Cite this

    Kao, M. Y., Qi, J., & Tan, L. (1997). Optimal bidding algorithms against cheating in multiple-object auctions. In T. Jiang, & D. T. Lee (Eds.), Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings (pp. 192-201). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1276). Springer Verlag. https://doi.org/10.1007/bfb0045086