Pith Number

pith:TLJIKKQS

pith:2026:TLJIKKQSDBE2LQHUE663LB4R5J

not attested not anchored not stored refs resolved

Probabilistic Mechanism Design in Diffusion Auctions

Hanpin Wang, Xinlun Zhang, Yongzhi Cao, Yu Huang, Zhechen Li

The Probabilistic Diffusion Mechanism achieves incentive compatibility, non-negative revenue, and constant-approximation efficiency for diffusion auctions on path graphs and extends to general networks.

arxiv:2605.17221 v1 · 2026-05-17 · cs.GT

Open paper page JSON Open Graph Bundle Merged state What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{TLJIKKQSDBE2LQHUE663LB4R5J}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We propose the Probabilistic Diffusion Mechanism (PDM), a novel mechanism tailored for path graphs, which satisfies all three desired properties: incentive compatibility, non-negative revenue, and approximate efficiency with a constant approximation bound.

C2weakest assumption

The base mechanism is defined only for path graphs and extensions rely on a map f that preserves key properties when the network is arbitrary; if no such f exists that simultaneously maintains IC, non-negative revenue, and the constant efficiency bound for general graphs, the general claim fails.

C3one line summary

PDM and f-PDM achieve IC, non-negative revenue, and constant-approximate efficiency in diffusion auctions on paths and general networks, with further variants for Sybil attacks, collusion, and multi-unit cases.

References

46 extracted · 46 resolved · 1 Pith anchors

[1] SIAM Journal on Computing28(6), 2117–2132 (1999) 1999

[2] Proceedings of the National Academy of Sciences97(21), 11149–11152 (2000) 24 X 2000

[3] Journal of Economic Theory100(2), 295– 328 (2001) 2001

[4] Journal of Economic Theory144(2), 565–603 (2009) 2009

[5] In: Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems 2023

Receipt and verification

First computed	2026-05-20T00:03:45.974008Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

9ad2852a121849a5c0f427bdb58791ea57f356ef623551e7c1d18f49aa68ddc3

Aliases

arxiv: 2605.17221 · arxiv_version: 2605.17221v1 · doi: 10.48550/arxiv.2605.17221 · pith_short_12: TLJIKKQSDBE2 · pith_short_16: TLJIKKQSDBE2LQHU · pith_short_8: TLJIKKQS

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/TLJIKKQSDBE2LQHUE663LB4R5J \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 9ad2852a121849a5c0f427bdb58791ea57f356ef623551e7c1d18f49aa68ddc3

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "67d0e4eb3744e860406bc74d317df576c7b3cd06947f788c1ecfecc9df9aae98",
    "cross_cats_sorted": [],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.GT",
    "submitted_at": "2026-05-17T01:54:28Z",
    "title_canon_sha256": "450c06ffb1ab9370cecc77088e9305b2e44f99b44e45ff2d1f9944bd48c96ab3"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.17221",
    "kind": "arxiv",
    "version": 1
  }
}