Computational social choice and approval-based committee elections

Approval-Core Nonemptiness Conjecture

Collaboration beta

Must every approval election contain a committee that no nonempty proposal of size at most k can block with its proportional coalition of strict gainers?

\exists W, | W | = k : ∄ T \subseteq C, 1 \leq | T | \leq k with \sum_{i : u_{i} (T) > u_{i} (W)} w_{i} \geq | T | / k

Known results and sources

A blocker is a nonempty proposal T with 1<=|T|<=k whose strict gainers have normalized total weight at least |T|/k; the conjecture asks whether some size-k committee W has no blocker.

Research problem

Exact mathematical statement

Let $C$ be a finite set of $m$ candidates, fix $1\le k<m$ , and let the positive-weight approval types be $(A_i,w_i)$ with $A_i\subseteq C$ and $\sum_i w_i=1$ . For a set $X\subseteq C$ , type $i$ has utility $u_i(X)=|A_i\cap X|$ .

A nonempty proposal $T\subseteq C$ with $1\le |T|\le k$ blocks a size- $k$ committee $W$ when

\sum_{i:u_i(T)>u_i(W)} w_i \ge \frac{|T|}{k}.

The approval-core nonemptiness conjecture says that every such finite weighted profile has a size- $k$ committee $W$ with no blocking proposal $T$ .

Problem infographic

Problem at a glance

A problem-first diagram of approval types with positive normalized weights, a size-k committee, utilities, a nonempty proposal T satisfying 1<=|T|<=k, and the strict-gainer weight threshold |T|/k, with status open. — With positive weights normalized to one, a nonempty proposal T with 1<=|T|<=k blocks when its strict gainers have total weight at least |T|/k; the existence of an unblocked size-k committee remains open.

Current mathematical picture

Where work on Approval-Core Nonemptiness Conjecture stands

Open conjecture

Selected route highlights from the mathematical source. This is not yet a complete mathematical inventory.

Useful failureUniversal selection of an arbitrary PAV maximizer

The source explicitly records this statement as false and separately records that strict-quota PAV blockers can occur. A symmetry-fixed exact MILP for the three PAV blocking geometries at (12,9,8) remains worthwhile, but can settle only that finite parameter pair.

Route status · Narrowed route

Main reductionMulti-extra face compression

For a rigid base with two extra types, a dominating fractional-core replacement may be sought on a base face of dimension at most two.

Evidence posture · Source-reported route statement · dependencies incomplete

Priority open bridgeConstruct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Approval-Core Nonemptiness Conjecture in numbers

716retained lines of mathematical investigation716 in the current working snapshot

Argument development: 533 · 74%
Explored or eliminated routes: 63 · 9%
Computational analysis: 54 · 8%
Open obligations: 31 · 4%
Definitions and setup: 35 · 5%

6selected mapped statements2routes investigated4open questions4contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Status checkedAug 15, 2026

Source recordedAug 15, 2026

Recommended next task

Construct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).

Suggested move: Enumerate joint diagonal-symmetry orbits, glue support-changing faces through endpoint charts, and preserve exact affine, slope, mask, and size-slack data.

What would count as progress

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

12 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Explored alternatives

Other routes

2 recorded

Narrowed routeUniversal selection of an arbitrary PAV maximizer

Route status · Narrowed route

Narrowed routeCommon-vertex domination for two extra approval objectives

The source says the assertion is false for general polytopes and unproved here, which is why edges and two-faces must be retained. Supported Pareto faces with exact active-cap rank and slope data remain viable replacements for the invalid common-vertex shortcut.

Route status · Narrowed route

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks

Construct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).Suggested move: Enumerate joint diagonal-symmetry orbits, glue support-changing faces through endpoint charts, and preserve exact affine, slope, mask, and size-slack data.

Ready to work on

Exclude all blocker families over the audited decorated-face catalogue, or produce an exact empty-core profile.Suggested move: After the catalogue audit, formulate symmetry-fixed exact MILPs for the three PAV blocking geometries and validate every result with independent exact verifiers.

Ready to work on

First unresolved fronts

The source identifies (12,9,8) and (13,9,6) as the first unresolved small parameter fronts.

Suggested move: Resolve the exact source-reported obligation without treating it as an established negative result.

Ready to work on

Prove a type-independent personalized-load deletion or overload theorem capable of bypassing finite r classifications.Suggested move: Analyze global truncated-load minimizers for balanced deletion witnesses, a marked-state circulation, or a blocker contradiction from an overload certificate.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 15, 2026

Current statusOpen conjecture

Both current primary preprints describe universal approval-core nonemptiness as open. They establish nonemptiness for committee size at most eight, for at most fifteen candidates, and for at most five voters or weighted distinct approval types in their respective scopes.

[1][2]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
PreprintCore nonemptiness is proved for at most five voters and extended to weighted profiles with at most five distinct approval sets.[2]
2025
PreprintCore committees are proved to exist for k<=8 and for m<=15, using linear-program computer search in the latter development.[1]

Mathematical neighborhood

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Corrected the research recordCorrection note

Correction details

Research-record correctionRestrict the blocker definition to nonempty proposals of sizes 1 through k, as the retained source explicitly requires. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Proposal scope clarified

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

4 standing statements2 proposed statements4 open questions2 narrowed routes

Statements by mathematical role6 selected mapped statements

theorem candidate1 of 61
reduction2 of 62
lemma3 of 63

Selected mathematical clusters1 mathematical clusters

Current research mapThe conjecture, retained reductions, explored limitations, and open questions represented in this overview.21 displayed rows · 2 routes included

retained route statementDoes every weighted approval election have an unblocked size-k committee?
retained route statementCurrent reductionintermediate
retained route statementClosing targetintermediate
retained route statementWeighted approval-core statementintermediate
retained route statementReported finite-parameter theoremintermediate
retained route statementMulti-extra face compressionintermediate
Recorded relationshipThe source reports this as a route toward the conjecture; missing or unaudited premises remain and the reduction does not itself prove the target.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
Recorded relationshipThis source-reported claim supports the retained route only within its stated, unaudited scope.supports · reported by source
DerivationThe source reports that completing the closing target would advance the reduction to the main conjecture; this remains an informal route, not a verified derivation.proposed
Useful failureUniversal selection of an arbitrary PAV maximizerreported failure
Useful failureCommon-vertex domination for two extra approval objectivesreported failure
Research targetConstruct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).open
Research targetExclude all blocker families over the audited decorated-face catalogue, or produce an exact empty-core profile.open
Research targetProve a type-independent personalized-load deletion or overload theorem capable of bypassing finite r classifications.open
Research targetFirst unresolved frontsopen
Research targetDecorated-face cataloguesuperseded
Research targetType-independent load routesuperseded
Narrowed routeUniversal selection of an arbitrary PAV maximizerThe source explicitly records this statement as false and separately records that strict-quota PAV blockers can occur. A symmetry-fixed exact MILP for the three PAV blocking geometries at (12,9,8) remains worthwhile, but can settle only that finite parameter pair.
Narrowed routeCommon-vertex domination for two extra approval objectivesThe source says the assertion is false for general polytopes and unproved here, which is why edges and two-faces must be retained. Supported Pareto faces with exact active-cap rank and slope data remain viable replacements for the invalid common-vertex shortcut.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeConstruct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).

2 approaches have already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

Supply a complete argument with every imported premise identified.
Survive an independent attempt to falsify the proposed step.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointConstruct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).

Approval-Core Nonemptiness Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Must every approval election contain a committee that no nonempty proposal of size at most k can block with its proportional coalition of strict gainers?

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references2 cited works · next context review by Nov 15, 2026

The mathematical context was checked on Aug 15, 2026. Status can be refreshed sooner after a material result or claim.

1
The Core of Approval-Based Committee Elections with Few Seatspreprint · Dominik Peters · arXiv · 2025-01-30; revised 2025-05-14 · ARXIV 2501.18304 · accessed Aug 15, 2026
2
Core Existence in Approval-Based Committee Elections with up to Five Voter Typespreprint · Patrick Becker, Matthias Greger, Dominik Peters · arXiv · 2026-05-07 · ARXIV 2605.06194 · accessed Aug 15, 2026

Important qualifications

Primary/current records were limited to the two current arXiv author submissions used here.
No submitted-packet URL was fetched and no source-package attachment was executed or rendered.
External metadata does not independently validate the stronger internal claims in the governing source material.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces

Approval-Core Nonemptiness Conjecture

Exact mathematical statement

Problem at a glance

Where work on Approval-Core Nonemptiness Conjecture stands

Approval-Core Nonemptiness Conjecture in numbers

Construct and independently audit the canonical decorated vertex, edge, and two-face catalogue for the rigid six-row bases at (12,9,8).

How the current approaches connect

Research route map

Other routes

Open questions

The known mathematical landscape

What the literature has established

Related results and reusable starting points

Formal and computational footholds

Formalization opportunities

What changed in the research record

Claims, milestones, and routes in the current map

Conditions that would advance the current route

Contribute

Important qualifications

Compare another research frontier