Metraipolis › archive › dc_e3ff59283d36

Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains — arXiv:2610.06871

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.06871
License (as archived)
CC0-1.0
Archived
2026-10-07T11:27:46.360Z
SHA-256 of the archived text
eeb3cb665c0f3935b68e37dc2383e0dbdf87a477d763bdff4d0fd2738f36b2ff
Stable URL of this page
https://metraipolis.com/documento/dc_e3ff59283d36

How to cite

Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains — arXiv:2610.06871 — arXiv (en), https://arxiv.org/abs/2610.06871 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e3ff59283d36 (Metraipolis archive dc_e3ff59283d36, sha256 eeb3cb665c0f3935b68e37dc2383e0dbdf87a477d763bdff4d0fd2738f36b2ff)
BibTeX
@misc{dce3ff59283d36,
  title = {Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains — arXiv:2610.06871},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.06871},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e3ff59283d36; sha256 eeb3cb665c0f3935b68e37dc2383e0dbdf87a477d763bdff4d0fd2738f36b2ff},
  year = {2026}
}

Archived text

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

For approval-based committee elections, the sizewise least-core value $\Gamma(P)$ minimizes the maximum excess support of a deviation over size-$k$ committees. Deviations are nonempty and contain at most $k$ candidates, with support measured relative to their Hare quota. A negative value certifies core nonemptiness, while $-\Gamma(P)$ is the largest worst-case quota shortfall secured by any committee. We quantify this margin on candidate-disjoint approval chains, a domain whose qualitative core nonemptiness is already known. We first factor each committee's deviation score over disjoint components. For chains, a closed local table yields the exact value and an attaining committee in polynomial time for rational weights. For nonnegative normalized real weights, let $q_{\mathrm{act}}\ge1$ count the connected components of the positive-support incidence graph. Then \[ \Gamma(P)\le-\frac{1}{k\min\{q_{\mathrm{act}},k+1\}}. \] Explicit extremal profiles show that this dependence on the active-component count is sharp. The margin is $1$-Lipschitz in total variation on the full ballot space. Each negative margin therefore certifies a neighborhood with nonempty core, even when perturbations leave the chain domain.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.06871 — 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-07T11:16:54.469Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).