Strengthening Full Justified Representation: Efficient Verification and Computation

This paper introduces FJR+, a strict strengthening of the full justified representation (FJR) and EJR+ axioms for approval-based committee elections, which can be both verified and satisfied in polynomial time.

Key contributions:

1. Definition of FJR+: FJR+ generalizes FJR violations by allowing voters and candidates to receive nonnegative weights, with additional variables specifying how much of each approved candidate is assigned to each weighted voter. The conditions are expressed by linear inequalities. FJR+ contains FJR and EJR+ as special cases: If all variables are restricted to 0 or 1, the conditions describe exactly an FJR violation. If only one candidate has positive weight, the conditions describe exactly an EJR+ violation. The paper shows FJR+ is strictly stronger than requiring FJR and EJR+ separately (Proposition 3.8).

2. Polynomial-time verification: For each representation level l, the existence of a violation can be determined by a linear program of polynomial size. Thus, FJR+ can be verified in polynomial time (Theorem 3.4).

3. Residual-Budget Greedy (RBG) algorithm: The paper analyzes RBG, a variant of Ai's descending-budget rule. The main result: The paid candidates form a set P such that every size-k committee containing P satisfies FJR+ (Theorem 3.5). This holds for every execution of RBG, and the rule runs in polynomial time.

4. Priceable completion: Using sequential Phragmén to complete the partial committee from RBG, the paper shows: The resulting committee is priceable and therefore lies in the sub-core (Theorem 4.5). This gives a polynomial-time rule that always satisfies FJR+ and the sub-core, and is also priceable whenever at least k candidates receive an approval.

5. Droop version: Running RBG with candidate price n/(k+1) satisfies Droop-FJR+ under the strict group-size inequality. The paper shows the strict inequality is essential (Proposition 3.7).

6. Participatory budgeting extension: FJR+ and RBG are extended to approval-based participatory budgeting with arbitrary project costs. A project-specific version of RBG computes this property in polynomial time and can be continued to a priceable outcome satisfying a cost-based version of the sub-core (Theorem 6.7).

7. Relations to other axioms: The paper shows FJR+ and the sub-core are incomparable (Proposition 5.1), core stability does not imply FJR+ (Example 5.2), FJR+ is not monotone (Proposition 5.5), and on party-list elections FJR+ is equivalent to lower quota (Proposition 3.9).

The paper concludes that FJR+ strictly strengthens both FJR and EJR+ while retaining polynomial-time verification and polynomial-time construction, and discusses open questions regarding additive utilities, further welfare guarantees, and extensions to temporal voting and proportional rankings.

Improvements to AI Systems:

1. Verification-Integrated Recommendation Systems: AI can now audit any approval-based committee election outcome (e.g., participatory budgeting, panel selection) against the FJR+ axiom in polynomial time. The system can flag violations and provide a certificate (via the linear program) explaining which voter groups and candidate weights cause the failure, enabling transparent, explainable corrections.

2. Guaranteed-Fair Committee Generators: An AI system can implement the RBG algorithm followed by sequential Phragmén completion to produce committees that are provably FJR+-satisfying, priceable, and in the sub-core. This replaces heuristic or approximate fairness with a hard guarantee, useful for automated decision-making in civic tech, resource allocation, or internal AI governance (e.g., selecting diverse training data subsets).

3. Cost-Aware Resource Allocators: For participatory budgeting with arbitrary project costs, the AI can use the project-specific RBG variant to allocate funds while satisfying a cost-based FJR+ and sub-core property. This improves AI-driven budget planning systems, ensuring no group of voters with a justified claim is underrepresented, even with heterogeneous costs.

4. Axiom-Aware Search and Optimization: The polynomial-time verification enables AI to use FJR+ as a hard constraint in search algorithms (e.g., local search, genetic algorithms) for committee selection. The system can iteratively propose committees, verify FJR+, and reject violations, converging to fair outcomes without manual tuning.

5. Strictness and Edge-Case Detection: AI systems can now distinguish between FJR+ and weaker axioms (FJR, EJR+). By checking if a committee satisfies FJR+ but not the others (or vice versa), the AI can identify subtle fairness gaps in existing election data, helping researchers and policymakers understand where current systems fail.

6. Non-Monotonicity-Aware Robustness: Since FJR+ is not monotone (Proposition 5.5), AI systems can be designed to detect when adding a candidate to a committee might break FJR+—useful for dynamic or incremental election scenarios (e.g., real-time voting updates) to avoid unintended fairness losses.

7. Droop-FJR+ for Minority Protection: Using the Droop version (price n/(k+1)), AI can enforce stricter proportional representation for smaller groups. This is valuable for systems needing to protect minority interests, such as AI-mediated consensus in multi-stakeholder settings, where the strict group-size inequality prevents loopholes.

8. Cross-Axiom Comparison Tool: The AI can automatically compare FJR+ against other axioms (core stability, priceability, lower quota) on any given election instance, providing a multi-dimensional fairness profile. This helps system designers choose the right axiom for their specific application and understand trade-offs (e.g., FJR+ vs. sub-core incomparability).