Probabilistic Mechanism Design in Diffusion Auctions
This work addresses the open problem of simultaneously achieving incentive compatibility, non-negative revenue, and approximate efficiency in diffusion auctions, which is relevant for mechanism design over social networks.
The paper proposes the Probabilistic Diffusion Mechanism (PDM) for diffusion auctions, achieving incentive compatibility, non-negative revenue, and approximate efficiency with a constant approximation bound on path graphs, and extends it to general networks and multi-unit settings.
A diffusion auction refers to a selling process conducted over a social network, where each participant submits a bid and may invite other potential buyers to join the auction. Although various mechanisms have been proposed, none of them can simultaneously achieve incentive compatibility, non-negative revenue, and approximate efficiency with a constant approximation bound. In this paper, we propose the Probabilistic Diffusion Mechanism (PDM), a novel mechanism tailored for path graphs, which satisfies all three desired properties. We further extend PDM to general network structures through a map $f$, resulting in the $f$-PDM mechanism, which preserves the key properties of the original design. Beyond these, when $f$ satisfies properties such as breadth-first order, $f$-PDM also ensures Sybil-proofness and provides approximate revenue. Furthermore, to address buyer collusion, we introduce a modified version of the mechanism that balances collusion-proofness with revenue approximation. Finally, we extend the design to multi-unit diffusion auctions -- a more challenging setting -- and propose a simple yet effective mechanism, Multi-Unit PDM (MUPDM), that achieves approximate efficiency while maintaining IC. Moreover, we design Sybil-Proof MUPDM (SP-MUPDM) to resist Sybil attacks in the multi-item scenario.