Research map / Learning theory and algorithms / Submodular and game algorithms
Double Auction on Diffusion Network
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Dynamic Trade Reduction (DTR), an incentive-compatible, individually rational, weakly budget-balanced double auction on a social network that incentivizes traders to invite neighbours, and adapts it to multi-unit one-sided auctions.
Problem
Designing double auctions on social networks where buyers and sellers are competitors, so they must be incentivized to invite their neighbours while remaining truthful and not running a deficit.
Approach
Dynamic trade reduction iteratively uses a reserve-price variant of McAfee's trade reduction on the currently active traders; traders who cannot trade for sure are allowed to invite their neighbours, and the process repeats until no new traders join. This makes invitation dominant without relying on resale-based payment differences.
Key results
- DTR's social welfare approaches the optimum when connectivity c >= 0.03 in 1000 small-world graphs with |N0|=300, |N|=1000.
- DTR closely approaches optimal social welfare when the number of initial traders |N0| >= 200, while MTR restricted to initial traders stays far lower.
- Theoretically DTR is IC, IR and weakly budget balanced, and weakly dominates MTR on initial traders in transactions, welfare and revenue.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace MTR with DTR, dynamically expanding the trader set | Double auction on a diffusion network · Initial traders only, without diffusion | social welfare | Helped |
| replace MTR with DTR, dynamically expanding the trader set | Double auction on a diffusion network · Initial traders only, without diffusion | number of transactions | Helped |
| replace MTR with DTR, dynamically expanding the trader set | Double auction on a diffusion network · Initial traders only, without diffusion | revenue | Helped |
| use DTR instead of MTR for the network auction | Double auction on a diffusion network · Small-world networks with c ≥ 0.03 | social welfare | Helped |
| increase the number of initial traders while using DTR | Double auction on a diffusion network · Small-world networks with |N0| ≥ 200 | social welfare | Helped |
| apply MTR directly without accounting for the trader network | McAfee’s trade reduction on a network · Double auction on a social network | incentive compatibility | Hurt |
| use DTR with dynamic trade reduction and reserve prices | Double auction on a diffusion network · All report profiles | market-owner revenue | Helped |
Surprising findings
- Directly applying McAfee's trade reduction on the network is not incentive compatible, since uninvited sellers can benefit by inviting competitors.
Limitations
- Truthful invitation gives no positive incentive to invite; the authors note a mild extension is needed and is not elaborated.
- Experiments are on synthetic small-world networks with uniformly random valuations only.
- Multi-item extension is left as an open problem.
Experimental setup
Datasets: synthetic small-world networks with random valuations from {0,...,10000}
Metrics: social welfare ratio to optimal number of transactions revenue
Baselines: McAfee's trade reduction (initial traders only) optimal social welfare LDM-Tree MUDAN
Builds on: McAfee trade reduction VCG mechanism Li et al. 2017 single-item diffusion auction Watts-Strogatz small-world model
Closest papers by meaning
- Mechanism Design in Social Networks (AAAI 2017 · similarity 0.90)
- Multi-Unit Auction in Social Networks with Budgets (AAAI 2022 · similarity 0.89)
- Strategy-Proof and Non-Wasteful Multi-Unit Auction via Social Network (AAAI 2020 · similarity 0.89)
- Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.86)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.83)
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.