Robust Combinatorial Auction Protocol against False-name Bids
Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara
17th National Conference on Artificial Intelligence (AAAI-2000),2000.
This paper presents a new combinatorial auction protocol
(LDS protocol) that is robust against false-name bids.
Internet auctions have become an integral part of
Electronic Commerce (EC) and
a promising field for applying agent and Artificial Intelligence
technologies. Although the
Internet provides an excellent infrastructure for combinatorial
auctions, we must consider the possibility of a
new type of cheating, i.e., an agent tries to profit from
submitting several bids under fictitious names (false-name bids).
If there exists no false-name bid,
the generalized Vickrey auction (GVA) satisfies
individual rationality, Pareto efficiency, and incentive compatibility.
On the other hand, when false-name bids are possible,
it is theoretically impossible for a combinatorial
auction protocol to simultaneously satisfy
these three properties.
The Leveled Division Set (LDS) protocol, which is a modification of the
GVA, utilizes reservation prices
of auctioned goods for making decisions on whether to sell goods in a bundle or
The LDS protocol satisfies
individual rationality and incentive compatibility, although it is not
guaranteed to achieve a Pareto efficient social surplus.
Simulation results show that the LDS protocol can achieve a better social
surplus than that for a protocol that always sells goods in a bundle.