### 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 language | English (US) |
---|---|

Title of host publication | Computing and Combinatorics - 3rd Annual International Conference COCOON 1997, Proceedings |

Editors | Tao Jiang, D.T. Lee |

Publisher | Springer Verlag |

Pages | 192-201 |

Number of pages | 10 |

ISBN (Print) | 354063357X, 9783540633570 |

DOIs | |

State | Published - Jan 1 1997 |

Event | 3rd Annual International Computing and Combinatorics Conference, COCOON 1997 - Shanghai, China Duration: Aug 20 1997 → Aug 22 1997 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1276 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 3rd Annual International Computing and Combinatorics Conference, COCOON 1997 |
---|---|

Country | China |

City | Shanghai |

Period | 8/20/97 → 8/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

*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