pith. sign in

arxiv: 2607.01036 · v1 · pith:EWY2KXL4new · submitted 2026-07-01 · 💻 cs.GT

Multiwinner Voting with Spatial Preferences under Incomplete Information

Drew Springham , Edith Elkind , Bart de Keijzer , Maria Polukarov This is my paper

Pith reviewed 2026-07-02 04:02 UTC · model grok-4.3

classification 💻 cs.GT
keywords votercandidatesissueonlypreferencesalgorithmaxis-alignedcandidate
0
0 comments X

The pith

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.

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

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.

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.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 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.

axioms (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 no independent evidence
    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.

pith-pipeline@v0.9.1-grok · 5755 in / 1442 out tokens · 31743 ms · 2026-07-02T04:02:43.248924+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 2 canonical work pages · 1 internal anchor

  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)

    2017

  2. [2]

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

    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)

    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)

    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–

    2002

  6. [6]

    AAAI Press / The MIT Press (2002)

    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)

    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)

    2015

  9. [9]

    Cambridge University Press (1984)

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

    1984

  10. [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

  11. [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 Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial...

    2021

  12. [12]

    5448–5455

    pp. 5448–5455. AAAI Press (2021)

    2021

  13. [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

  14. [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

  15. [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

  16. [16]

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

    2025

  17. [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, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2...

    2024

  18. [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

  19. [19]

    Diverse Committees with Incomplete or Inaccurate Approval Ballots

    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)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  20. [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 under Incomplete Information 15

    2013

  21. [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

  22. [22]

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

    1990

  23. [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

  24. [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

  25. [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

  26. [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

  27. [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

  28. [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)

    work page arXiv 2025

  29. [29]

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

    2022

  30. [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 6-10, 2018. pp. 446–456. AUAI Press (2018) 16 D. Springham et al. A Table of No...

    2018

  31. [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 the testζc/h1 ≥q ∗, so it can violate (PW) with marginδ1 only by admitting some t...