Characterizing false-name-proof allocation rules in combinatorial auctions

Abstract

A combinatorial auction mechanism consists of an allocation rule that defines the allocation of goods for each agent, and a payment rule that defines the payment of each winner. There have been several studies on characterizing strategy-proof allocation rules. In particular, a condition called weak-monotonicity has been identified as a full characterization of strategy-proof allocation rules. More specifically, for an allocation rule, there exists an appropriate payment rule so that the mechanism becomes strategy-proof if and only if it satisfies weak-monotonicity. In this paper, we identify a condition called sub-additivity which characterizes false-name-proof allocation rules. False-name-proofness generalizes strategy-proofness, by assuming that a bidder can submit multiple bids under fictitious identifiers. As far as the authors are aware, this is the first attempt to characterize false-name-proof allocation rules. We can utilize this characterization for developing a new false-name-proof mechanism, since we can concentrate on designing an allocation rule. As long as the allocation rule satisfies weak-monotonicity and sub-additivity, there always exists an appropriate payment rule. Furthermore, by utilizing the sub-additivity condition, we can easily verify whether a mechanism is false-name-proof. To our surprise, we found that two mechanisms, which were believed to be false-name-proof, do not satisfy sub-additivity; they are not false-name-proof. As demonstrated in these examples, our characterization is quite useful for mechanism verification.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 35 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.