Pith. sign in

REVIEW 31 references

Multiwinner Voting with Spatial Preferences under Incomplete Information

T0 review · reviewed 2026-07-02 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An algorithm returns an EJR+ committee in the ARRV spatial model using O(d log d k) Planar queries per voter in expectation, independent of candidate count, for any distribution over rectangular preferences when the electorate is large enough.

arxiv 2607.01036 v1 pith:EWY2KXL4 submitted 2026-07-01 cs.GT

Drew Springham , Edith Elkind , Bart de Keijzer , Maria Polukarov This is my paper · ORCID
classification cs.GT
keywords votercandidatesissueonlypreferencesalgorithmaxis-alignedcandidate
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Voters in big elections cannot rate every candidate. The authors model each voter as approving a rectangle in a d-dimensional space of issues: on each issue the voter has an interval of acceptable positions. Instead of asking for the full rectangle, the algorithm asks only a few 'planar' questions that compare one candidate against the voter's tolerance on one issue. It uses a verify-or-fallback structure that first tries to confirm enough information with few queries and falls back to more queries only when needed. The total queries per voter stay logarithmic in the committee size and linear in the dimension, no matter how many candidates exist. Separate modules handle cases where the distribution of voter rectangles is known, unknown, or smooth. The output committee still meets the EJR+ fairness standard that would normally require complete approval ballots from everyone.
Extended reading notes

Core claim

We give an algorithm returning an EJR+ committee for any distribution over rectangular preferences, using only O(d log d k) Planar queries per voter in expectation given a sufficiently large electorate, independent of the number of candidates m.

Load-bearing premise

The electorate is sufficiently large (abstract, paragraph 3) so that the verify-or-fallback framework with interchangeable modules can achieve the stated query bound for any distribution over ARRV preferences.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Assumptions & free parameters 0 free parameters · 2 assumptions · 1 invented entities

The central claim rests on the ARRV model definition, the EJR+ fairness axiom, and the existence of interchangeable modules that satisfy the verify-or-fallback properties for the three distribution classes. No free parameters or invented physical entities are introduced.

assumptions (2)
  • domain assumption EJR+ is the target proportional fairness notion for multiwinner committees
    Invoked in the abstract as the guarantee the algorithm must return.
  • domain assumption Voter preferences are drawn from the ARRV model of axis-aligned rectangular approvals in d-dimensional space
    Stated as the setting in which the query bound holds.
invented entities (1)
  • ARRV (Axis-aligned Random Rectangle Voter) model
    purpose: To represent incomplete spatial preferences via axis-aligned hyper-rectangles revealed only through Planar queries
    New modeling choice introduced to capture the incomplete-information setting; no independent evidence supplied beyond the model definition itself.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multiwinner Voting with Spatial Preferences under Incomplete Information." pith.science (2026). https://pith.science/paper/EWY2KXL4

@misc{pith2026260701036,
  author       = {Pith},
  title        = {Pith review of: Multiwinner Voting with Spatial Preferences under Incomplete Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EWY2KXL4}},
  note         = {Machine review of arXiv:2607.01036}
}
abstract

In multiwinner elections with many candidates, as in participatory budgeting or large-scale recommendation, voters cannot plausibly evaluate every candidate, yet standard proportional-fairness guarantees such as EJR+ are stated for fully specified approval ballots. We ask whether strong proportional representation can still be guaranteed while eliciting only a little from each voter. We study this in a spatial model, the Axis-aligned Random Rectangle Voter (ARRV) model, in which candidates occupy a $d$-dimensional issue space and each voter approves an axis-aligned hyper-rectangle: a tolerance interval on every issue. Preferences are revealed only through Planar queries, each comparing a voter's tolerance to a candidate on a single issue. We give an algorithm returning an EJR+ committee for any distribution over rectangular preferences, using only $\mathcal{O}(d\log dk)$ Planar queries per voter in expectation given a sufficiently large electorate, independent of the number of candidates $m$, where $d$ is the number of issues and $k$ the committee size. The algorithm rests on a dimension-agnostic verify-or-fallback framework whose query cost is governed by two properties supplied by interchangeable modules. We describe such modules, yielding end-to-end guarantees for known, unknown, and smooth distributions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T.: Justified representation in approval- based committee voting. Soc. Choice Welf.48(2), 461–485 (2017)

    work page 2017

  2. [2]

    Barman, S., Rathi, N.: Fair cake division under monotone likelihood ratios. Math. Oper. Res.47(3), 1875–1903 (2022)

    work page 1903

  3. [3]

    Brill,M.,Peters,J.:Robustandverifiableproportionalityaxiomsformultiwinnervoting.In:Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023. p. 301. ACM (2023)

    work page 2023

  4. [4]

    In: Web and Internet Economics - 21st International Conference, WINE 2025, New Brunswick, NJ, USA, December 8-11, 2025, Proceed- ings

    Casey, M.M., Elkind, E.: Justified representation: From hare to droop. In: Web and Internet Economics - 21st International Conference, WINE 2025, New Brunswick, NJ, USA, December 8-11, 2025, Proceed- ings. pp. 556–573. Lecture Notes in Computer Science, Springer (2025)

    work page 2025

  5. [5]

    Conitzer, V., Sandholm, T.: Vote elicitation: Complexity and strategy-proofness. In: Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada. pp. 392–

    work page 2002

  6. [6]

    AAAI Press / The MIT Press (2002)

    work page 2002

  7. [7]

    In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015

    Dey, P., Bhattacharyya, A.: Sample complexity for winner prediction in elections. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015, Istanbul, Turkey, May 4-8, 2015. pp. 1421–1430. ACM (2015)

    work page 2015

  8. [8]

    In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015

    Elkind, E., Lackner, M.: Structure in dichotomous preferences. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015. pp. 2019–2025. AAAI Press (2015)

    work page 2015

Show all 31 references
  1. [9]

    Cambridge University Press (1984)

    Enelow, J., Hinich, M.: The Spatial Theory of Voting: An Introduction. Cambridge University Press (1984)

    1984

  2. [10]

    In: Proceedings of the 32nd International Joint Con- ference on Artificial Intelligence, IJCAI 2023

    Faliszewski, P., Flis, J., Peters, D., Pierczyński, G., Skowron, P., Stolicki, D., Szufa, S., Talmon, N.: Participatory budgeting: Data, tools and analysis. In: Proceedings of the 32nd International Joint Con- ference on Artificial Intelligence, IJCAI 2023. pp. 2667–2674 (2023)

    2023

  3. [11]

    Godziszewski, M.T., Batko, P., Skowron, P., Faliszewski, P.: An analysis of approval-based committee rules for 2d-euclidean elections. In: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intel...

    2021

  4. [12]

    5448–5455

    pp. 5448–5455. AAAI Press (2021)

    2021

  5. [13]

    In: Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024

    Halpern, D., Hossain, S., Tucker-Foltz, J.: Computing voting rules with elicited incomplete votes. In: Proceedings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024. pp. 941–963. ACM (2024)

    2024

  6. [14]

    Theory and Decision100(1), 257–296 (Feb 2026)

    Halpern, D., Kehne, G., Procaccia, A.D., Tucker-Foltz, J., Wüthrich, M.: Representation with incom- plete votes. Theory and Decision100(1), 257–296 (Feb 2026)

    2026

  7. [15]

    Journal of the American statistical association58(301), 13–30 (1963)

    Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American statistical association58(301), 13–30 (1963)

    1963

  8. [16]

    Imber, A., Israel, J., Brill, M., Kimelfeld, B.: Approval-based committee voting under incomplete infor- mation. Artif. Intell.347, 104381 (2025)

    2025

  9. [17]

    Imber, A., Israel, J., Brill, M., Shachnai, H., Kimelfeld, B.: Spatial voting with incomplete voter informa- tion. In: Thirty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024,...

    2024

  10. [18]

    Springer Briefs in Intelligent Systems, Springer (2023)

    Lackner, M., Skowron, P.: Multi-Winner Voting with Approval Preferences - Artificial Intelligence, Multiagent Systems, and Cognitive Robotics. Springer Briefs in Intelligent Systems, Springer (2023)

    2023

  11. [19]

    CoRRabs/2506.10843(2025)

    Lindeboom, F., Brehm, M., Grossi, D., Murukannaiah, P.K.: A voice for minorities: diversity in approval- based committee elections under incomplete or inaccurate information. CoRRabs/2506.10843(2025)

    2025 arXiv

  12. [20]

    Lu,T.,Boutilier,C.:Multi-winnersocialchoicewithincompletepreferences.In:IJCAI2013,Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013. pp. 263–270. IJCAI/AAAI (2013) Multiwinner Voting with Spatial Preferences und...

    2013

  13. [21]

    In: EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020

    Mandal, D., Shah, N., Woodruff, D.P.: Optimal communication-distortion tradeoff in voting. In: EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020. pp. 795–813. ACM (2020)

    2020

  14. [22]

    Massart, P.: The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. Ann. Probab.18(3), 1269–1283 (1990)

    1990

  15. [23]

    In: ACM Conference onEconomicsandComputation,EC’14,Stanford,CA,USA,June8-12,2014.pp.313–330.ACM(2014)

    Meir, R., Lev, O., Rosenschein, J.S.: A local-dominance theory of voting equilibria. In: ACM Conference onEconomicsandComputation,EC’14,Stanford,CA,USA,June8-12,2014.pp.313–330.ACM(2014)

    2014

  16. [24]

    In: Handbook of Social Choice and Voting, chap

    Miller, N.R.: The spatial model of social choice and voting. In: Handbook of Social Choice and Voting, chap. 10, pp. 163–181. Edward Elgar Publishing (2015)

    2015

  17. [25]

    In: EC ’20: The 21st ACM Con- ference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020

    Peters, D., Skowron, P.: Proportionality and the limits of welfarism. In: EC ’20: The 21st ACM Con- ference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020. pp. 793–794. ACM (2020)

    2020

  18. [26]

    Sánchez-Fernández, L., Elkind, E., Lackner, M., García, N.F., Fisteus, J.A., Basanta-Val, P., Skowron, P.: Proportional justified representation. Artif. Intell.353, 104503 (2026)

    2026

  19. [27]

    Recerca: revista de pensament i anàlisi26(2) (2021)

    Small, C., Bjorkegren, M., Erkkilä, T., Shaw, L., Megill, C.: Polis: Scaling deliberation by mapping high dimensional opinion spaces. Recerca: revista de pensament i anàlisi26(2) (2021)

    2021

  20. [28]

    CoRRabs/2510.11625(2025)

    Springham, D., Elkind, E., de Keijzer, B., Polukarov, M.: Multiwinner voting with interval preferences under incomplete information. CoRRabs/2510.11625(2025)

    2025

  21. [29]

    The Computational Democracy Project: The Klimarat in Austria (8 2022)

    2022

  22. [30]

    In: Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August 6-10, 2018

    Zhao, Z., Li, H., Wang, J., Kephart, J.O., Mattei, N., Su, H., Xia, L.: A cost-effective framework for preference elicitation and aggregation. In: Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI 2018, Monterey, California, USA, August...

    2018

  23. [31]

    Proof.Fix a levelℓ∈[k], callc∈Ctinyifp c,ℓ ≤ℓ/(k+ 1)andlargeifp c,ℓ ≥ℓ/k−δ 1, and write g :=ℓ/(2k(k+ 1))−δ 1/2for the gap separatingq ∗ from each of these two bounds

    to the (PW) notion and the empirical statisticζc used here. Proof.Fix a levelℓ∈[k], callc∈Ctinyifp c,ℓ ≤ℓ/(k+ 1)andlargeifp c,ℓ ≥ℓ/k−δ 1, and write g :=ℓ/(2k(k+ 1))−δ 1/2for the gap separatingq ∗ from each of these two bounds. At this level, NGJCR admits a candidate only via t...

Pith tools

Reviewed July 2, 2026 · model on record in the stance chip above.