Metraipolis › archive › dc_bbeb9da4083d

Approximating Optimal Welfare in Complementary Allocation under Decentralized Information — arXiv:2609.14301

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.14301
License (as archived)
CC0-1.0
Archived
2026-10-15T23:48:25.603Z
SHA-256 of the archived text
930882b364717cc21a05ba7eaed9696bbcea659a2f8899245897f0d6ef8fefa0
Stable URL of this page
https://metraipolis.com/documento/dc_bbeb9da4083d

How to cite

Approximating Optimal Welfare in Complementary Allocation under Decentralized Information — arXiv:2609.14301 — arXiv (en), https://arxiv.org/abs/2609.14301 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bbeb9da4083d (Metraipolis archive dc_bbeb9da4083d, sha256 930882b364717cc21a05ba7eaed9696bbcea659a2f8899245897f0d6ef8fefa0)
BibTeX
@misc{dcbbeb9da4083d,
  title = {Approximating Optimal Welfare in Complementary Allocation under Decentralized Information — arXiv:2609.14301},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.14301},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bbeb9da4083d; sha256 930882b364717cc21a05ba7eaed9696bbcea659a2f8899245897f0d6ef8fefa0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14301. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Complementary resources are often allocated by agencies that see different coordinates of an individual's needs. If an intervention requires complementary resources, an agency may know if said person lacks its own resource; yet not know if supplying completes a useful bundle. We study allocation of $m$ divisible complementary goods when each agency observes only its own coordinate of a baseline-access profile. To isolate information from incentives, we measure the welfare cost of this split against a generous decentralized benchmark DEC: the best rule that acts on local information alone, with cooperative agencies and known population distribution and capacities. Even so, local observation alone can make optimally coordinated policies arbitrarily inefficient: a factor linear in $m$ (even with equal capacities), and a factor inverse in OPT (with but three agencies). Threshold referrals recover much of this loss: an agency reports if its value lies below a public threshold, and a clearing rule uses only the joint reports. Aggregating types by their reports captures a rectangle under the optimal half-utility survival curve. Our main tool is a profile-level charging certificate: if optimal utility is at least twice a threshold, OPT pays at least that on every deficient coordinate. This yields welfare at least ${\rm OPT}/[4(1+\ln(2/{\rm OPT}))]$ with one bit per agency; and an equal-revenue family shows this log-loss tight for one threshold. A geometric threshold ladder improves this to a constant fraction of OPT with doubly-logarithmic messages: a staircase recovers ${\rm OPT}/8$ with $\Theta(\log\log(1/{\rm OPT}))$ bits, and this is necessary within the class. The results isolate how a simple reporting language turns large local-info losses into constant-factor recovery. In short: One threshold gets a log-approximation. A staircase, with log-of-log bits, a constant-factor.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-15 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Data Structures and Algorithms (cs.DS); Theoretical Economics (econ.TH).
Pagina del lavoro: https://arxiv.org/abs/2609.14301 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:17:52.830Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).