Computer Science – Computational Engineering – Finance – and Science
Scientific paper
2000-11-17
SIAM Journal on Computing, 28(3):955--969, 1999
Computer Science
Computational Engineering, Finance, and Science
Scientific paper
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.
Kao Ming-Yang
Qi Junfeng
Tan Lei
No associations
LandOfFree
Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-93666