###
Bundle Design in Robust Combinatorial Auction Protocol against
False-name Bids

Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara

17th International Joint Conference on Artificial Intelligence
(IJCAI-2001),2001.

This paper presents a method for designing bundles in a combinatorial auction
protocol that is robust against false-name bids.
Internet auctions have become an integral part of
Electronic Commerce and a promising field for applying
AI technologies.
However, the possibility of a new type of cheating called
a false-name bid, i.e., a bid submitted
under a fictitious name, has been pointed out.
A protocol called
Leveled Division Set (LDS) protocol that is robust against false-name
bids has been developed.
However, this protocol requires the auctioneer to
define a leveled division set.
A leveled division set is a series of division sets, where a division
set is a set of divisions and a division is a combination of bundles of goods.
We need to solve a very complicated optimization problem
to construct a leveled division set in order to obtain a good social surplus.
We have developed a heuristic method for overcoming this problem.
In this method,
we first find a good division with a winner determination algorithm,
and then construct a leveled division set by using this division as a seed.
Through a simulation, we show that our method can obtain a social
surplus that is very close to optimal.