# Efficiency in Truthful Auctions via a Social Network

arXiv: https://arxiv.org/abs/1904.12422 · HTML: https://mlsanity.com/paper/1904.12422/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2019.

## Built on by (most cited first, 3 of 3)

- [Emerging Methods of Auction Design in Social Networks](https://mlsanity.com/paper/2108.00381/) (2021)
- [Test-Time Compute Games](https://mlsanity.com/paper/2601.21839/) (2026)
- [Strategyproofness and Monotone Allocation of Auction in Social Networks](https://mlsanity.com/paper/2507.14472/) (2025)

## Abstract (arXiv)

In this paper, we study efficiency in truthful auctions via a social network, where a seller can only spread the information of an auction to the buyers through the buyers' network. In single-item auctions, we show that no mechanism is strategy-proof, individually rational, efficient, and weakly budget balanced. In addition, we propose α-APG mechanisms, a class of mechanisms which operate a trade-off between efficiency and weakly budget balancedness. In multi-item auctions, there already exists a strategy-proof mechanism when all buyers need only one item. However, we indicate a counter-example to strategy-proofness in this mechanism, and to the best of our knowledge, the question of finding a strategy-proof mechanism remains open. We assume that all buyers have decreasing marginal utility and propose a generalized APG mechanism that is strategy-proof and individually rational but not efficient. Importantly, we show that this mechanism achieves the largest efficiency measure among all strategy-proof mechanisms.