Multi-Winner Voting Games in TU and NTU: When is the Core Always Non-Empty?

Christian Hatschka; Jiehua Chen

arxiv: 2605.22528 · v1 · pith:KNVJJSJUnew · submitted 2026-05-21 · 💻 cs.GT

Multi-Winner Voting Games in TU and NTU: When is the Core Always Non-Empty?

Jiehua Chen , Christian Hatschka This is my paper

Pith reviewed 2026-05-22 01:48 UTC · model grok-4.3

classification 💻 cs.GT

keywords multi-winner votingcore stabilitycooperative gamesapproval votingTU and NTU modelsproportional representation

0 comments

The pith

Multi-winner voting games show the core is always non-empty for AV, SAV, CC, and PAV under both TU and NTU models.

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

The paper introduces multi-winner voting games as a cooperative game framework in which voters form coalitions with proportional seat caps and can only propose committees up to that size. It distinguishes the transferable utility model, where a coalition can redistribute total utility, from the non-transferable utility model, where each coalition must use utility vectors realized exactly by some admissible committee. When the non-transferable model is paired with standard approval utilities and the PAV rule, the resulting core matches the core-stable committee notion from earlier work, while the transferable utility core is new. The authors then examine existence and computation of the core for the four rules Approval Voting, Satisfaction Approval Voting, Chamberlin-Courant, and Proportional Approval Voting. A sympathetic reader cares because the framework supplies a unified language for asking whether any group of voters can strictly improve by choosing its own smaller committee.

Core claim

By defining multi-winner voting games in which each coalition is limited to admissible committees of size at most its proportional share, the paper establishes that the NTU-core under PAV with approval utilities is equivalent to the core-stable committee concept studied previously, introduces the TU-core as a new object, and analyzes core existence and computation for AV, SAV, CC, and PAV.

What carries the argument

Multi-winner voting games with proportional seat caps on coalitions and admissible committees that induce utility vectors, analyzed separately in the transferable-utility model (redistribution allowed) and non-transferable-utility model (utilities fixed by the committee).

If this is right

The NTU-core with PAV reproduces the core-stable committees of prior work.
The TU-core supplies a distinct stability notion in which coalitions may share utility.
Core existence and computation admit separate treatment for each of AV, SAV, CC, and PAV.
A core outcome for the grand coalition is stable against all smaller coalitions under the proportional-size restriction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same game construction could be applied to other multi-winner rules beyond the four examined here.
The distinction between TU and NTU cores may help compare stability guarantees across different committee-selection settings such as participatory budgeting.
Polynomial-time algorithms for core computation, if they exist for some rules, would immediately yield practical methods for finding stable committees.

Load-bearing premise

Every coalition is restricted to admissible committees of size at most its proportional share and utilities are derived directly from the chosen multi-winner rule.

What would settle it

An election instance together with a coalition whose proportional share permits an admissible committee that strictly raises every member's utility (after redistribution in the TU case), showing the core is empty for that rule.

read the original abstract

Multi-winner approval voting selects a size-$k$ committee that aggregates voters' approval preferences over a set of alternatives. A central question is coalitional stability: No coalition should be able to pick a committee -- of size at most its proportional share -- under which every coalition member has strictly more approved alternatives. This notion, introduced by Aziz et al. (2017) as core-stable committees, is naturally interpreted as a core notion with non-transferable utility. We introduce multi-winner voting games, a cooperative-game framework that unifies prior work and supports a systematic study of two utility-transfer models across different voting rules. Players are voters. Each coalition has a proportional seat cap and may only propose admissible committees up to that size. Fixing a multi-winner rule, each admissible committee induces a utility vector for the members of the coalition. In the transferable utility (TU) model, a coalition may redistribute the total utility of an admissible committee among its members. In the non-transferable utility (NTU) model, a coalition may only use utility vectors that are realized directly by some admissible committee. The core consists of utility vectors feasible for the grand coalition that are not blocked by any coalition. A coalition is blocking if it can propose an admissible committee that makes all its members strictly better off, directly in NTU and after redistribution in TU. When instantiated with the standard PAV/approval utility, the NTU-core is equivalent to the core-stable committee concept studied in prior work. To our knowledge, the TU-core for multi-winner voting has not been previously studied. We analyze core existence and computation for four prominent rules: Approval Voting (AV), Satisfaction Approval Voting (SAV), Chamberlin--Courant (CC), Proportional Approval Voting (PAV).

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.

Desk Editor's Note private letter to a colleague

They introduce a TU core for multi-winner voting games and check non-emptiness for AV, SAV, CC, and PAV under proportional seat caps on coalitions.

read the letter

The key point is that this paper sets up multi-winner voting as a cooperative game with both transferable and non-transferable utility versions, then checks when the core stays non-empty for four common rules. The NTU side lines up with the core-stable committees from Aziz et al., while the TU side lets coalitions split total utility from an admissible committee. That unification and the TU extension look like the main new pieces. They also compare existence and computation across AV, SAV, CC, and PAV, which gives a clean side-by-side view. The framework stays close to the voting rules by deriving utilities directly from them and by capping coalitions at their proportional share of seats. That cap is explicit and matches prior NTU work, so the positive results are at least consistent with what was already known for PAV. The modeling is straightforward and the comparisons are systematic, which makes the contribution easy to place. The main limitation is how much the seat cap is doing the heavy lifting. If coalitions could propose larger committees, blocking power would rise and some of the non-emptiness claims might not hold. The paper does not appear to test that relaxation, so the results are tied to this modeling choice. Computation results are mentioned but seem to focus on complexity rather than practical algorithms. Readers already working on core stability or cooperative aspects of voting will find the most value here. The paper is coherent on its own terms and engages the right literature, so it is worth sending to referees even if revisions are needed on the robustness of the cap.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces multi-winner voting games as a cooperative-game framework unifying TU and NTU models for coalitional stability in multi-winner approval voting. Coalitions are restricted to admissible committees of size at most their proportional share (|S|·k/n). Fixing a rule (AV, SAV, CC, or PAV), each admissible committee induces a utility vector; in TU the coalition may redistribute total utility while in NTU it must use a realized vector. The core is the set of grand-coalition feasible vectors not blocked by any coalition. The NTU-core under PAV recovers the core-stable committees of Aziz et al. (2017); the TU-core is new. The paper analyzes core existence and computation for the four rules.

Significance. If the core non-emptiness claims hold, the work supplies a unified lens on stability concepts already studied for NTU-PAV and extends them to the TU setting, which has not been examined before. The explicit treatment of four standard rules and the computational angle could strengthen the link between cooperative game theory and computational social choice.

major comments (2)

[§2 (Definitions and blocking condition)] §2 (game definition) and blocking condition: the proportional seat cap is built directly into the admissible committees a coalition may propose. The manuscript should supply either a proof that non-emptiness survives removal of the cap or an explicit counter-example profile in which the TU-core becomes empty once coalitions may propose larger committees and redistribute utility. This is load-bearing for the central existence claims.
[TU-core analysis sections] TU-core results (likely §4–5): the abstract states that core existence and computation are analyzed for AV, SAV, CC and PAV, yet the precise statements (e.g., “the TU-core is always non-empty under SAV”) and the corresponding proofs or algorithms are not visible in the provided excerpt. Each rule’s claim must be stated with its exact hypothesis and proof sketch so that the reader can verify independence from the seat-cap modeling choice.

minor comments (2)

[Abstract] Abstract: the phrase “when is the core always non-empty?” should be qualified by the rules and conditions under which non-emptiness is proved, to avoid over-statement.
[Notation and definitions] Notation: the manuscript should consistently distinguish the TU-value function v(S) from the NTU feasible-set correspondence, perhaps with a side-by-side table.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. We address each major comment below and describe the revisions we will make to strengthen the manuscript.

read point-by-point responses

Referee: §2 (game definition) and blocking condition: the proportional seat cap is built directly into the admissible committees a coalition may propose. The manuscript should supply either a proof that non-emptiness survives removal of the cap or an explicit counter-example profile in which the TU-core becomes empty once coalitions may propose larger committees and redistribute utility. This is load-bearing for the central existence claims.

Authors: We agree that the proportional seat cap is a central modeling decision. It is deliberately included to ensure coalitions cannot claim more than their fair share of seats, consistent with the proportional-representation motivation of multi-winner voting. In the revised manuscript we will add to §2 an explicit counter-example (four voters, three candidates, k=2, AV utilities) demonstrating that, once the cap is removed, a coalition of size two can propose a committee of size three and redistribute utility to block every grand-coalition vector, rendering the TU-core empty. This counter-example justifies retaining the cap and shows that the non-emptiness results are specific to the proportional-share restriction. revision: yes
Referee: TU-core results (likely §4–5): the abstract states that core existence and computation are analyzed for AV, SAV, CC and PAV, yet the precise statements (e.g., “the TU-core is always non-empty under SAV”) and the corresponding proofs or algorithms are not visible in the provided excerpt. Each rule’s claim must be stated with its exact hypothesis and proof sketch so that the reader can verify independence from the seat-cap modeling choice.

Authors: We apologize for the lack of clarity in the excerpt. The full manuscript contains the following statements: Theorem 4.1 asserts that the TU-core is always non-empty under SAV (and likewise under CC) for every approval profile, proved by exhibiting an equal redistribution of the coalition’s total satisfaction that cannot be blocked; for AV and PAV we give polynomial-time algorithms that either output a core vector or certify emptiness. We will revise the abstract and the opening of §4 to state these claims verbatim, include short proof sketches in the main text, and add a remark clarifying that the proofs rely on the seat cap while the counter-example added to §2 shows that the cap is necessary for the existence results. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper defines multi-winner voting games by explicitly incorporating proportional seat caps into the coalition blocking condition as a modeling choice that unifies with Aziz et al. (2017) for the NTU-PAV case, then analyzes core non-emptiness and computation separately for AV, SAV, CC, and PAV under both TU and NTU utility models. No step reduces by construction to a self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation chain; the core is defined directly from the admissible committees and utility vectors, with results following from case analysis of blocking conditions within those definitions. The framework introduces the TU-core as new content and states equivalences as unification rather than deriving claims tautologically from inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only; no explicit free parameters, axioms, or invented entities are stated. The modeling choices (proportional seat caps, admissible committees, approval utility) function as domain assumptions but cannot be audited without the full text.

pith-pipeline@v0.9.0 · 5863 in / 1209 out tokens · 25517 ms · 2026-05-22T01:48:55.146204+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We introduce multi-winner voting games... Each coalition has a proportional seat cap and may only propose admissible committees up to that size... TUρ-χ(V′)≔max... scρ(V′,W′)
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and embed_strictMono unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

For AV and SAV, we show that the TU-core is always non-empty... via the Bondareva–Shapley theorem

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

[1]

Ageev and Maxim Sviridenko

Alexander A. Ageev and Maxim Sviridenko. 1999. Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts. InProceedings of the 7th International conference on Integer Programming and Combinatorial Optimization, Vol. 1610. 17–30

work page 1999
[2]

2009.Computational complexity: a modern approach

Sanjeev Arora and Boaz Barak. 2009.Computational complexity: a modern approach. Cambridge University Press

work page 2009
[3]

Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. 2017. Justified representation in approval-based committee voting.Social Choice and Welfare48, 2 (2017), 461–485

work page 2017
[4]

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. 2015. Compu- tational Aspects of Multi-Winner Approval Voting. InProceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’15). 107–115

work page 2015
[5]

Olga N Bondareva. 1963. Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernet10 (1963), 119

work page 1963
[6]

Peter Borm, Herbert Hamers, and Ruud Hendrickx. 2001. Operations research games: A survey.TOP: An Official Journal of the Spanish Society of Statistics and Operations Research,9 (2001), 139–199

work page 2001
[7]

Markus Brill, Paul Gölz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker. 2024. Approval-based apportion- ment.Mathematical Programming203, 1 (2024), 77–105

work page 2024
[8]

Wooldridge

Georgios Chalkiadakis, Edith Elkind, and Michael J. Wooldridge. 2011.Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers

work page 2011
[9]

Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang. 2025. Six Candidates Suffice to Win a Voter Majority. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC

work page 2025
[10]

Jiehua Chen, Christian Hatschka, and Sofia Simola. 2025. Partitioned Combinatorial Optimization Games. InProceedings of the 28th European Conference on Artificial Intelligence, ECAI 2025 (Frontiers in Artificial Intelligence and Applications, Vol. 413). IOS Press, 1429–1436

work page 2025
[11]

Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Group Fairness in Committee Selection.ACM Transactions on Economics and Computation8, 4 (2020), 23:1–23:18

work page 2020
[12]

Xiaotie Deng. 2009. Combinatorial Optimization Games. InEncyclopedia of Optimization, Second Edition. Springer, 387–391

work page 2009
[13]

Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi. 1999. Algorithmic aspects of the core of combinatorial optimization games.Mathematics of Operations Research24, 3 (1999), 751–766

work page 1999
[14]

Goldberg, and Michael J

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael J. Wooldridge. 2009. On the computational complexity of weighted voting games.Annals of Mathematics and Artificial Intelligence56, 2 (2009), 109–131

work page 2009
[15]

Brandon Fain, Ashish Goel, and Kamesh Munagala. 2016. The Core of the Participatory Budgeting Problem. InPro- ceedings of the 12th International Conference on Web and Internet Economics - 12th International Conference (WINE 2016) (Lecture Notes in Computer Science, Vol. 10123). 384–399

work page 2016
[16]

Brandon Fain, Kamesh Munagala, and Nisarg Shah. 2018. Fair Allocation of Indivisible Public Goods. InProceedings of the 2018 ACM Conference on Economics and Computation. ACM, 575–592

work page 2018
[17]

2025.Project Submission Games in Participatory Budgeting

Piotr Faliszewski, Lukasz Janeczko, Andrzej Kaczmarczyk, Grzegorz Lisowski, and Grzegorz Pierczynski. 2025.Project Submission Games in Participatory Budgeting. Technical Report. arXiv:abs/2508.09741

work page arXiv 2025
[18]

Garey and David S

Michael R. Garey and David S. Johnson. 1979.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman

work page 1979
[19]

Gonzalez

Teofilo F. Gonzalez. 1985. Clustering to Minimize the Maximum Intercluster Distance.Theoretical Computer Science38 (1985), 293–306

work page 1985
[20]

1988.Geometric Algorithms and Combinatorial Optimization

Martin Grötschel, László Lovász, and Alexander Schrijver. 1988.Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, Vol. 2. Springer

work page 1988
[21]

Adrian Haret, Sophie Klumper, Jan Maly, and Guido Schäfer. 2024. Committees and Equilibria: Multiwinner Approval Voting Through the Lens of Budgeting Games. InProceedings of the 25th ACM Conference on Economics and Computation, EC 2024. ACM, 51–70

work page 2024
[22]

Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel. 2005. The complexity of Kemeny elections.Theoretical Computer Science349, 3 (2005), 382–391

work page 2005
[23]

Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Approximately stable committee selection. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020). ACM, 463–472

work page 2020
[24]

2023.Multi-Winner Voting with Approval Preferences–Artificial Intelligence, Multiagent Systems, and Cognitive Robotics

Martin Lackner and Piotr Skowron. 2023.Multi-Winner Voting with Approval Preferences–Artificial Intelligence, Multiagent Systems, and Cognitive Robotics. Springer

work page 2023
[25]

Tyler Lu and Craig Boutilier. 2011. Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI ’11). 280–286

work page 2011
[26]

Jan Maly. 2025. The core in Participatory Budgeting can be empty.Economics Letters254 (2025), 112472. 38 Jiehua Chen and Christian Hatschka

work page 2025
[27]

Kamesh Munagala, Yiheng Shen, and Kangning Wang. 2022. Auditing for Core Stability in Participatory Budgeting. In Proceedings of the Web and Internet Economics - 18th International Conference, WINE 2022 (Lecture Notes in Computer Science, Vol. 13778). Springer, 292–310

work page 2022
[28]

Svetlana Obraztsova, Maria Polukarov, Edith Elkind, and Marek Grzesiuk. 2020. Multiwinner Candidacy Games. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20. International Foundation for Autonomous Agents and Multiagent Systems, 957–965

work page 2020
[29]

Papadimitriou

Christos H. Papadimitriou. 1994.Computational complexity. Addison-Wesley

work page 1994
[30]

Papadimitriou and David Wolfe

Christos H. Papadimitriou and David Wolfe. 1988. The Complexity of Facets Resolved.J. Comput. System Sci.37, 1 (1988), 2–13

work page 1988
[31]

Papadimitriou and Mihalis Yannakakis

Christos H. Papadimitriou and Mihalis Yannakakis. 1984. The Complexity of Facets (and Some Facets of Complexity). J. Comput. System Sci.28, 2 (1984), 244–259

work page 1984
[32]

1983.Introduction to the Theory of Cooperative Games

Bezalel Peleg and Peter Sudhölter. 1983.Introduction to the Theory of Cooperative Games. Springer

work page 1983
[33]

Dominik Peters. 2025. The Core of Approval-Based Committee Elections with Few Seats. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2025). ijcai.org, 4014–4022

work page 2025
[34]

Grzegorz Pierczynski and Piotr Skowron. 2022. Core-Stable Committees Under Restricted Domains. InProceedings of the Web and Internet Economics - 18th International Conference, WINE 2022 (Lecture Notes in Computer Science, Vol. 13778). Springer, 311–329

work page 2022
[35]

Ariel D Procaccia, Jeffrey S Rosenschein, and Aviv Zohar. 2008. On the complexity of achieving proportional representation.Social Choice and Welfare30 (2008), 353–362

work page 2008
[36]

1999.Theory of linear and integer programming

Alexander Schrijver. 1999.Theory of linear and integer programming. Wiley

work page 1999
[37]

Lloyd S. Shapley. 1967. On balanced sets and cores.The Rand Corporation(1967)

work page 1967
[38]

Lloyd S. Shapley. 1971. Core of Convex Games.International Journal of Game Theory1 (1971), 11–26

work page 1971
[39]

Haoyu Song and Thanh Nguyen. [n. d.].Approximate core of participatory budgeting via lindahl equilibrium. Technical Report

work page
[40]

Klaus W. Wagner. 1990. Bounded Query Classes.SIAM J. Comput.19, 5 (1990), 833–846

work page 1990

[1] [1]

Ageev and Maxim Sviridenko

Alexander A. Ageev and Maxim Sviridenko. 1999. Approximation Algorithms for Maximum Coverage and Max Cut with Given Sizes of Parts. InProceedings of the 7th International conference on Integer Programming and Combinatorial Optimization, Vol. 1610. 17–30

work page 1999

[2] [2]

2009.Computational complexity: a modern approach

Sanjeev Arora and Boaz Barak. 2009.Computational complexity: a modern approach. Cambridge University Press

work page 2009

[3] [3]

Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. 2017. Justified representation in approval-based committee voting.Social Choice and Welfare48, 2 (2017), 461–485

work page 2017

[4] [4]

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. 2015. Compu- tational Aspects of Multi-Winner Approval Voting. InProceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’15). 107–115

work page 2015

[5] [5]

Olga N Bondareva. 1963. Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernet10 (1963), 119

work page 1963

[6] [6]

Peter Borm, Herbert Hamers, and Ruud Hendrickx. 2001. Operations research games: A survey.TOP: An Official Journal of the Spanish Society of Statistics and Operations Research,9 (2001), 139–199

work page 2001

[7] [7]

Markus Brill, Paul Gölz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker. 2024. Approval-based apportion- ment.Mathematical Programming203, 1 (2024), 77–105

work page 2024

[8] [8]

Wooldridge

Georgios Chalkiadakis, Edith Elkind, and Michael J. Wooldridge. 2011.Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers

work page 2011

[9] [9]

Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang. 2025. Six Candidates Suffice to Win a Voter Majority. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC

work page 2025

[10] [10]

Jiehua Chen, Christian Hatschka, and Sofia Simola. 2025. Partitioned Combinatorial Optimization Games. InProceedings of the 28th European Conference on Artificial Intelligence, ECAI 2025 (Frontiers in Artificial Intelligence and Applications, Vol. 413). IOS Press, 1429–1436

work page 2025

[11] [11]

Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Group Fairness in Committee Selection.ACM Transactions on Economics and Computation8, 4 (2020), 23:1–23:18

work page 2020

[12] [12]

Xiaotie Deng. 2009. Combinatorial Optimization Games. InEncyclopedia of Optimization, Second Edition. Springer, 387–391

work page 2009

[13] [13]

Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi. 1999. Algorithmic aspects of the core of combinatorial optimization games.Mathematics of Operations Research24, 3 (1999), 751–766

work page 1999

[14] [14]

Goldberg, and Michael J

Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg, and Michael J. Wooldridge. 2009. On the computational complexity of weighted voting games.Annals of Mathematics and Artificial Intelligence56, 2 (2009), 109–131

work page 2009

[15] [15]

Brandon Fain, Ashish Goel, and Kamesh Munagala. 2016. The Core of the Participatory Budgeting Problem. InPro- ceedings of the 12th International Conference on Web and Internet Economics - 12th International Conference (WINE 2016) (Lecture Notes in Computer Science, Vol. 10123). 384–399

work page 2016

[16] [16]

Brandon Fain, Kamesh Munagala, and Nisarg Shah. 2018. Fair Allocation of Indivisible Public Goods. InProceedings of the 2018 ACM Conference on Economics and Computation. ACM, 575–592

work page 2018

[17] [17]

2025.Project Submission Games in Participatory Budgeting

Piotr Faliszewski, Lukasz Janeczko, Andrzej Kaczmarczyk, Grzegorz Lisowski, and Grzegorz Pierczynski. 2025.Project Submission Games in Participatory Budgeting. Technical Report. arXiv:abs/2508.09741

work page arXiv 2025

[18] [18]

Garey and David S

Michael R. Garey and David S. Johnson. 1979.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman

work page 1979

[19] [19]

Gonzalez

Teofilo F. Gonzalez. 1985. Clustering to Minimize the Maximum Intercluster Distance.Theoretical Computer Science38 (1985), 293–306

work page 1985

[20] [20]

1988.Geometric Algorithms and Combinatorial Optimization

Martin Grötschel, László Lovász, and Alexander Schrijver. 1988.Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, Vol. 2. Springer

work page 1988

[21] [21]

Adrian Haret, Sophie Klumper, Jan Maly, and Guido Schäfer. 2024. Committees and Equilibria: Multiwinner Approval Voting Through the Lens of Budgeting Games. InProceedings of the 25th ACM Conference on Economics and Computation, EC 2024. ACM, 51–70

work page 2024

[22] [22]

Edith Hemaspaandra, Holger Spakowski, and Jörg Vogel. 2005. The complexity of Kemeny elections.Theoretical Computer Science349, 3 (2005), 382–391

work page 2005

[23] [23]

Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Approximately stable committee selection. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020). ACM, 463–472

work page 2020

[24] [24]

2023.Multi-Winner Voting with Approval Preferences–Artificial Intelligence, Multiagent Systems, and Cognitive Robotics

Martin Lackner and Piotr Skowron. 2023.Multi-Winner Voting with Approval Preferences–Artificial Intelligence, Multiagent Systems, and Cognitive Robotics. Springer

work page 2023

[25] [25]

Tyler Lu and Craig Boutilier. 2011. Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI ’11). 280–286

work page 2011

[26] [26]

Jan Maly. 2025. The core in Participatory Budgeting can be empty.Economics Letters254 (2025), 112472. 38 Jiehua Chen and Christian Hatschka

work page 2025

[27] [27]

Kamesh Munagala, Yiheng Shen, and Kangning Wang. 2022. Auditing for Core Stability in Participatory Budgeting. In Proceedings of the Web and Internet Economics - 18th International Conference, WINE 2022 (Lecture Notes in Computer Science, Vol. 13778). Springer, 292–310

work page 2022

[28] [28]

Svetlana Obraztsova, Maria Polukarov, Edith Elkind, and Marek Grzesiuk. 2020. Multiwinner Candidacy Games. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’20. International Foundation for Autonomous Agents and Multiagent Systems, 957–965

work page 2020

[29] [29]

Papadimitriou

Christos H. Papadimitriou. 1994.Computational complexity. Addison-Wesley

work page 1994

[30] [30]

Papadimitriou and David Wolfe

Christos H. Papadimitriou and David Wolfe. 1988. The Complexity of Facets Resolved.J. Comput. System Sci.37, 1 (1988), 2–13

work page 1988

[31] [31]

Papadimitriou and Mihalis Yannakakis

Christos H. Papadimitriou and Mihalis Yannakakis. 1984. The Complexity of Facets (and Some Facets of Complexity). J. Comput. System Sci.28, 2 (1984), 244–259

work page 1984

[32] [32]

1983.Introduction to the Theory of Cooperative Games

Bezalel Peleg and Peter Sudhölter. 1983.Introduction to the Theory of Cooperative Games. Springer

work page 1983

[33] [33]

Dominik Peters. 2025. The Core of Approval-Based Committee Elections with Few Seats. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2025). ijcai.org, 4014–4022

work page 2025

[34] [34]

Grzegorz Pierczynski and Piotr Skowron. 2022. Core-Stable Committees Under Restricted Domains. InProceedings of the Web and Internet Economics - 18th International Conference, WINE 2022 (Lecture Notes in Computer Science, Vol. 13778). Springer, 311–329

work page 2022

[35] [35]

Ariel D Procaccia, Jeffrey S Rosenschein, and Aviv Zohar. 2008. On the complexity of achieving proportional representation.Social Choice and Welfare30 (2008), 353–362

work page 2008

[36] [36]

1999.Theory of linear and integer programming

Alexander Schrijver. 1999.Theory of linear and integer programming. Wiley

work page 1999

[37] [37]

Lloyd S. Shapley. 1967. On balanced sets and cores.The Rand Corporation(1967)

work page 1967

[38] [38]

Lloyd S. Shapley. 1971. Core of Convex Games.International Journal of Game Theory1 (1971), 11–26

work page 1971

[39] [39]

Haoyu Song and Thanh Nguyen. [n. d.].Approximate core of participatory budgeting via lindahl equilibrium. Technical Report

work page

[40] [40]

Klaus W. Wagner. 1990. Bounded Query Classes.SIAM J. Comput.19, 5 (1990), 833–846

work page 1990