pith. sign in

arxiv: 2605.19030 · v1 · pith:CZKLHIQKnew · submitted 2026-05-18 · 💻 cs.GT · cs.MA· econ.TH

Nash Welfare in Additively Separable Hedonic Games

Marta Pagano , Alexander Schlenga This is my paper

Pith reviewed 2026-05-20 07:55 UTC · model grok-4.3

classification 💻 cs.GT cs.MAecon.TH
keywords Nash welfarehedonic gamesadditively separablecoalition formationcontractual Nash stabilityapproximation algorithmscomputational complexity
0
0 comments X

The pith

Partitions with high Nash welfare are contractually Nash stable in symmetric additively separable hedonic games.

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

The paper initiates the study of Nash welfare for coalition partitions in additively separable hedonic games, where each agent's utility is the sum of their valuations for other members. It shows that maximizing or even approximating this welfare measure yields partitions that are stable under contractual deviations in symmetric settings. This stability guarantee is appealing because direct computation of stable partitions can be difficult, while welfare optimization provides a proxy that works even approximately. The authors also map the computational landscape, giving approximation algorithms for specific game classes and proving hardness results when coalition sizes or numbers are not tightly restricted.

Core claim

In additively separable hedonic games, Nash welfare of a coalition partition is the product of the agents' individual utilities derived from additive valuations. The central discovery is that any partition attaining high Nash welfare satisfies contractual Nash stability in symmetric games, and this property holds for every approximation of Nash welfare. Computationally, exact maximization is NP-hard even for symmetric aversion-to-enemies games, but polynomial-time solvable when the coalition size or the number of coalitions is bounded by two, while larger bounds lead to NP-hardness or unbounded inapproximability.

What carries the argument

The Nash welfare objective, which is the product of agents' utilities in a partition, applied to additively separable hedonic games to guarantee contractual Nash stability and to design approximation algorithms.

If this is right

  • Any partition with high Nash welfare is contractually Nash stable in symmetric ASHGs.
  • Approximation algorithms achieve ratios of n-1 for aversion to enemies games and 2n for appreciation of friends games.
  • Maximizing Nash welfare is NP-hard to approximate within a factor better than 1.0000759 in general ASHGs.
  • Polynomial-time algorithms exist when the maximum coalition size or the number of coalitions is at most 2.
  • NP-hardness holds when coalition size or number is bounded by 3 or more.

Where Pith is reading between the lines

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

  • Using Nash welfare as an objective could serve as a practical heuristic for finding stable coalitions in symmetric settings without explicitly enforcing stability constraints.
  • Relaxing symmetry might require alternative welfare measures or additional mechanisms to maintain stability guarantees.
  • The tight bounds on coalition size for tractability suggest that real-world applications with small groups could benefit from exact solutions.

Load-bearing premise

The stability and approximation results assume that preferences are additively separable from individual peer valuations and that the game is symmetric for the contractual Nash stability claim to hold under approximations.

What would settle it

Finding a symmetric additively separable hedonic game instance where a partition with arbitrarily high Nash welfare is not contractually Nash stable would falsify the main stability claim.

Figures

Figures reproduced from arXiv: 2605.19030 by Alexander Schlenga, Marta Pagano.

Figure 1
Figure 1. Figure 1: The mutual-friendship graph of an AEG with two different clique partitions highlighted. In π, no individual deviation is possible. In particular, π ∗ cannot be reached via non-abandoning individual deviations. For our approximation algorithm, we rely on a very useful extension of graph matching which may include triangles as well. Given a graph G and a family of graphs F, a packing of G with F is a partiti… view at source ↗
Figure 2
Figure 2. Figure 2: The partition of optimal Nash welfare (a) is prone to an individual deviation of agent b (b) 8 Conclusion We have initiated the study of Nash welfare in ASHGs. The basis of our com￾putational investigation has been laid by proving NP-hardness of computing a partition of optimal Nash welfare. For the subclasses of AEGs and AFGs, we obtained approximation algorithms with guarantees of n − 1 and 2n, respec￾ti… view at source ↗
read the original abstract

Additively separable hedonic games (ASHGs) are a prominent model of coalition formation where agents' preferences are derived from their individual valuations of peers. While social welfare maximization in ASHGs has traditionally focused mostly on utilitarian welfare, Nash welfare -- a well-established metric in economics which balances fairness with efficiency and offers scale invariance -- has been entirely overlooked. In this paper, we initiate the study of Nash welfare in ASHGs. We point out desirable properties fulfilled by partitions with high Nash welfare. This includes guaranteed contractual Nash stability in symmetric games, even for any approximation of Nash welfare. This is particularly appealing since, as for other welfare notions, Nash welfare turns out to be NP-hard to maximize, even for the ASHG subclass of symmetric aversion to enemies games (AEGs). A main focus of our study is on approximation algorithms for the Nash welfare objective. We present packing-based algorithms with approximation ratios for well-established subclasses of ASHGs: $n-1$ for AEGs and $2n$ for appreciation of friends games. This is complemented by a strict inapproximability result showing it is NP-hard to approximate Nash welfare within a factor of $1.0000759$ in general ASHGs. Further, we investigate the restricted settings with an upper bound on the coalition size or number of coalitions, and draw the boundary between the cases admitting efficient algorithms and those yielding NP-hardness: bounding the allowed size or number of coalitions by $2$ admits polynomial-time solvability, whereas bounds of $3$ or more yield NP-hardness or unbounded inapproximability.

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.

Referee Report

1 major / 2 minor

Summary. The paper initiates the study of Nash welfare maximization in additively separable hedonic games (ASHGs). It shows that partitions with high (even approximate) Nash welfare guarantee contractual Nash stability in symmetric ASHGs. It gives packing-based approximation algorithms with ratios n-1 for aversion-to-enemies games and 2n for appreciation games, a strict inapproximability threshold of 1.0000759 for general ASHGs, and complexity results: polynomial-time solvable when coalition size or number is bounded by 2, NP-hard or unbounded inapproximability for bounds of 3 or larger.

Significance. If the central claims hold, the work usefully extends the hedonic-games literature by shifting focus from utilitarian to Nash welfare, which brings scale invariance and fairness. The stability guarantee that survives approximation is a notable positive feature, and the algorithmic/complexity boundary (poly-time for size/number ≤2, hard thereafter) cleanly delineates tractable cases. The explicit scoping to symmetric and additively separable valuations is appropriately cautious.

major comments (1)
  1. [Abstract / stability section] The contractual-Nash-stability claim for approximate Nash welfare (stated in the abstract and presumably proved in the stability section) is load-bearing for the paper's motivation. The argument appears to rely on symmetry; it would be helpful to see an explicit statement of the approximation factor tolerated and a short proof sketch showing why the contractual-stability property is preserved under any positive approximation ratio.
minor comments (2)
  1. [Inapproximability section] The inapproximability factor 1.0000759 is unusually close to 1; a brief remark on the source of the constant (e.g., which reduction produces it) would aid readability.
  2. [Introduction] Notation for the two subclasses (AEGs and appreciation games) is introduced in the abstract but should be defined on first use in the main text with a short example.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment and constructive feedback. We address the major comment below.

read point-by-point responses

  1. Referee: [Abstract / stability section] The contractual-Nash-stability claim for approximate Nash welfare (stated in the abstract and presumably proved in the stability section) is load-bearing for the paper's motivation. The argument appears to rely on symmetry; it would be helpful to see an explicit statement of the approximation factor tolerated and a short proof sketch showing why the contractual-stability property is preserved under any positive approximation ratio.

    Authors: We agree that clarifying this point will improve the presentation. In the revised manuscript we will add an explicit statement that contractual Nash stability is guaranteed for any positive finite approximation ratio of Nash welfare in symmetric ASHGs. We will also include a short proof sketch in the stability section. revision: yes

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper presents new algorithmic results (packing-based approximations for AEGs and appreciation games) and complexity classifications (poly-time for coalition size/number bounded by 2; NP-hard otherwise) for Nash welfare maximization in ASHGs. These stand on standard computational assumptions and explicit model scoping (additive separability and symmetry for the stability guarantee). No equations, derivations, or self-citations reduce any central claim to fitted inputs or self-definitions by construction; the stability property is shown as a consequence of the welfare objective rather than presupposed.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard definitions of additively separable hedonic games and Nash welfare together with conventional complexity-theoretic assumptions; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard assumptions of computational complexity theory (P ≠ NP) for establishing NP-hardness and inapproximability.
    Invoked to prove that maximizing Nash welfare is NP-hard even in symmetric AEGs and that approximation within 1.0000759 is hard in general ASHGs.

pith-pipeline@v0.9.0 · 5818 in / 1430 out tokens · 43815 ms · 2026-05-20T07:55:09.648787+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

56 extracted references · 56 canonical work pages

  1. [1]

    Theoretical Computer Science863, 69–85 (2021)

    Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., Hollender, A., Voudouris, A.A.: Maximum Nash welfare and other stories about EFX. Theoretical Computer Science863, 69–85 (2021)

    work page 2021

  2. [2]

    Management Science41(9), 1493–1508 (1995)

    Axelrod,R.,Mitchell,W.,Thomas,R.E.,Bennett,D.S.,Bruderer,E.:Coali- tion formation in standard-setting alliances. Management Science41(9), 1493–1508 (1995)

    work page 1995

  3. [3]

    ACM Transactions on Economics and Computation 7(2), 1–29 (2019)

    Aziz,H.,Brandl,F.,Brandt,F.,Harrenstein,P.,Olsen,M.,Peters,D.:Frac- tional hedonic games. ACM Transactions on Economics and Computation 7(2), 1–29 (2019)

    work page 2019

  4. [4]

    Games and Economic Behavior82, 562–581 (2013)

    Aziz, H., Brandt, F., Harrenstein, P.: Pareto optimality in coalition forma- tion. Games and Economic Behavior82, 562–581 (2013)

    work page 2013

  5. [5]

    In: Proceedings of the 22nd International Joint Confer- ence on Artificial Intelligence (IJCAI), pp

    Aziz, H., Brandt, F., Seedig, H.G.: Optimal partitions in additively separa- ble hedonic games. In: Proceedings of the 22nd International Joint Confer- ence on Artificial Intelligence (IJCAI), pp. 43–48 (2011)

    work page 2011

  6. [6]

    Artificial Intelligence195, 316–334 (2013)

    Aziz, H., Brandt, F., Seedig, H.G.: Computing desirable partitions in addi- tively separable hedonic games. Artificial Intelligence195, 316–334 (2013)

    work page 2013

  7. [7]

    In: Proceedings of the 24th In- ternational Joint Conference on Artificial Intelligence (IJCAI), pp

    Aziz, H., Gaspers, S., Gudmundsson, J., Mestre, J., Täubig, H.: Welfare maximization in fractional hedonic games. In: Proceedings of the 24th In- ternational Joint Conference on Artificial Intelligence (IJCAI), pp. 461–467 (2015)

    work page 2015

  8. [8]

    In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D

    Aziz, H., Savani, R.: Hedonic games. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, chap. 15, Cambridge University Press (2016)

    work page 2016

  9. [9]

    Games and Economic Behavior49(1), 1–30 (2004)

    Ballester, C.: NP-completeness in hedonic games. Games and Economic Behavior49(1), 1–30 (2004)

    work page 2004

  10. [10]

    Social Choice and Welfare18, 135–153 (2001) Nash Welfare in Additively Separable Hedonic Games 17

    Banerjee, S., Konishi, H., Sönmez, T.: Core in a simple coalition formation game. Social Choice and Welfare18, 135–153 (2001) Nash Welfare in Additively Separable Hedonic Games 17

    work page 2001

  11. [11]

    Games and Economic Behavior38(2), 201–230 (2002)

    Bogomolnaia, A., Jackson, M.O.: The stability of hedonic coalition struc- tures. Games and Economic Behavior38(2), 201–230 (2002)

    work page 2002

  12. [12]

    Journal of Mathematical Economics99, 102585 (2022)

    Brandl, F., Brandt, F., Greger, M., Peters, D., Stricker, C., Suksompong, W.: Funding public projects: A case for the Nash product rule. Journal of Mathematical Economics99, 102585 (2022)

    work page 2022

  13. [13]

    In: Proceedings ofthe19thInternationalConferenceonAutonomousAgentsandMultiagent Systems (AAMAS), pp

    Bullinger, M.: Pareto-optimality in cardinal hedonic games. In: Proceedings ofthe19thInternationalConferenceonAutonomousAgentsandMultiagent Systems (AAMAS), pp. 213–221 (2020)

    work page 2020

  14. [14]

    In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp

    Bullinger, M., Chatziafratis, V., Shahkar, P.: Welfare approximation in ad- ditively separable hedonic games. In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 418–426 (2025)

    work page 2025

  15. [15]

    In: Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2026)

    Bullinger, M., Dunajski, A., Elkind, E., Gilboa, M.: Single-deviation stabil- ity in additively separable hedonic games with constrained coalition sizes (extended abstract). In: Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (2026)

    work page 2026

  16. [16]

    In: Rothe, J

    Bullinger, M., Elkind, E., Rothe, J.: Cooperative game theory. In: Rothe, J. (ed.) Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, chap. 3, pp. 139– 229, Springer (2024)

    work page 2024

  17. [17]

    ACM Transactions on Algorithms22(1), 4:1–43 (2025)

    Bullinger, M., Romen, R.: Online coalition formation under random arrival or coalition dissolution. ACM Transactions on Algorithms22(1), 4:1–43 (2025)

    work page 2025

  18. [18]

    In: Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp

    Bullinger, M., Romen, R., Schlenga, A.: The power of matching for online fractional hedonic games. In: Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2163–2194 (2026)

    work page 2026

  19. [19]

    ACM Transactions on Economics and Computation7(3), 12:1–12:32 (2019)

    Caragiannis,I.,Kurokawa,D.,Moulin,H.,Procaccia,A.D.,Shah,N.,Wang, J.: The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation7(3), 12:1–12:32 (2019)

    work page 2019

  20. [20]

    International Journal of Game Theory31(3), 353–354 (2002)

    Cechlárová, K., Hajduková, J.: Computational complexity of stable par- titions with B-preferences. International Journal of Game Theory31(3), 353–354 (2002)

    work page 2002

  21. [21]

    In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp

    Cohen, S., Agmon, N.: Egalitarianism in online coalition formation (ex- tended abstract). In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 2475–2477 (2025)

    work page 2025

  22. [22]

    Discrete Applied Mathematics8(1), 25–30 (1984)

    Colbourn, C.J.: The complexity of completing partial latin squares. Discrete Applied Mathematics8(1), 25–30 (1984)

    work page 1984

  23. [23]

    SIAM Journal on Computing47(3), 1211–1236 (2018)

    Cole, R., Gkatzelis, V.: Approximating the Nash social welfare with indi- visible items. SIAM Journal on Computing47(3), 1211–1236 (2018)

    work page 2018

  24. [24]

    Operations Research Letters1(4), 139–143 (1982)

    Cornuéjols, G., Hartvigsen, D., Pulleyblank, W.R.: Packing subgraphs in a graph. Operations Research Letters1(4), 139–143 (1982)

    work page 1982

  25. [25]

    European Journal of Operational Research247(2), 548–559 (2015) 18 M

    Darmann, A., Schauer, J.: Maximizing Nash product social welfare in allo- cating indivisible goods. European Journal of Operational Research247(2), 548–559 (2015) 18 M. Pagano and A. Schlenga

    work page 2015

  26. [26]

    Social Choice and Welfare26(2), 421–433 (2006)

    Dimitrov, D., Borm, P., Hendrickx, R., Sung, S.C.: Simple priorities and core stability in hedonic games. Social Choice and Welfare26(2), 421–433 (2006)

    work page 2006

  27. [27]

    Econometrica48(4), 987–1003 (1980)

    Drèze, J.H., Greenberg, J.: Hedonic coalitions: Optimality and stability. Econometrica48(4), 987–1003 (1980)

    work page 1980

  28. [28]

    Canadian Journal of Mathematics 17, 449–467 (1965)

    Edmonds, J.: Paths, trees and flowers. Canadian Journal of Mathematics 17, 449–467 (1965)

    work page 1965

  29. [29]

    Artificial Intelligence288, 103357 (2020)

    Elkind, E., Fanelli, A., Flammini, M.: Price of pareto optimality in hedonic games. Artificial Intelligence288, 103357 (2020)

    work page 2020

  30. [30]

    In: Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pp

    Fioravantes, F., Gahlawat, H., Melissinos, N.: Exact algorithms and lower bounds for forming coalitions of constrained maximum size. In: Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pp. 13847– 13855 (2025)

    work page 2025

  31. [31]

    Artificial Intelligence302, 103610 (2022)

    Flammini, M., Kodric, B., Varricchio, G.: Strategyproof mechanisms for friends and enemies games. Artificial Intelligence302, 103610 (2022)

    work page 2022

  32. [32]

    Journal of Artificial Intelli- gence Research72, 1215–1250 (2021)

    Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., Zaks, S.: On the online coalition structure generation problem. Journal of Artificial Intelli- gence Research72, 1215–1250 (2021)

    work page 2021

  33. [33]

    Journal of the ACM38(4), 815–853 (1991)

    Gabow, H.N., Tarjan, R.: Faster scaling algorithms for general graph match- ing problems. Journal of the ACM38(4), 815–853 (1991)

    work page 1991

  34. [34]

    Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)

    work page 1979

  35. [35]

    Theoretical Computer Science962, 113932 (2023)

    Garg, J., Murhekar, A.: Computing fair and efficient allocations with few utility values. Theoretical Computer Science962, 113932 (2023)

    work page 2023

  36. [36]

    In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp

    Gokhale, S., Sagar, H., Vaish, R., Yadav, J.: Approximating one-sided and two-sided nash social welfare with capacities. In: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 914–922 (2025)

    work page 2025

  37. [37]

    In: Tucker, A.W., Luce, R.D

    Harsanyi, J.C.: A bargaining model for the cooperative n-person game. In: Tucker, A.W., Luce, R.D. (eds.) Contributions to the Theory of Games, vol. IV, pp. 325–355, Princeton University Press (1959)

    work page 1959

  38. [38]

    Discrete Mathematics49(1), 45–59 (1984)

    Hell, P., Kirkpatrick, D.G.: Packings by cliques and by finite families of graphs. Discrete Mathematics49(1), 45–59 (1984)

    work page 1984

  39. [39]

    9798–9806 (2024)

    Jain, P., Vaish, R.: Maximizing Nash social welfare under two-sided prefer- ences.In:Proceedingsofthe38thAAAIConferenceonArtificialIntelligence (AAAI), pp. 9798–9806 (2024)

    work page 2024

  40. [40]

    Econometrica 47(2), 423–435 (1979)

    Kaneko, M., Nakamura, K.: The nash social welfare function. Econometrica 47(2), 423–435 (1979)

    work page 1979

  41. [41]

    Information Processing Letters122, 17–20 (2017)

    Lee, E.: APX-hardness of maximizing nash social welfare with indivisible items. Information Processing Letters122, 17–20 (2017)

    work page 2017

  42. [42]

    In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp

    Levinger, C., Hazon, N., Simola, S., Azaria, A.: Coalition formation with bounded coalition size. In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1119–1127 (2024)

    work page 2024

  43. [43]

    Econometrica18(2), 155–162 (1950) Nash Welfare in Additively Separable Hedonic Games 19

    Nash, J.F.: The bargaining problem. Econometrica18(2), 155–162 (1950) Nash Welfare in Additively Separable Hedonic Games 19

    work page 1950

  44. [44]

    Princeton University Press, 3rd edn

    von Neumann, J., Morgenstern, O.: Theory of Games and Economic Be- havior. Princeton University Press, 3rd edn. (1953)

    work page 1953

  45. [45]

    In: Proceedings of the 18th Computing: The Australasian Theory Symposium (CATS), Confer- ences in Research and Practice in Information Technology (CRPIT), vol

    Olsen, M.: On defining and computing communities. In: Proceedings of the 18th Computing: The Australasian Theory Symposium (CATS), Confer- ences in Research and Practice in Information Technology (CRPIT), vol. 128, pp. 97–102 (2012)

    work page 2012

  46. [46]

    In: Proceedings of the 25th International Joint Conference on Artificial Intelli- gence (IJCAI), pp

    Peters, D., Elkind, E.: Simple causes of complexity in hedonic games. In: Proceedings of the 25th International Joint Conference on Artificial Intelli- gence (IJCAI), pp. 617–623 (2015)

    work page 2015

  47. [47]

    Oxford University Press (2007)

    Ray, D.: A Game-Theoretic Perspective on Coalition Formation. Oxford University Press (2007)

    work page 2007

  48. [48]

    Economics Letters222, 110956 (2023)

    Suksompong, W.: A characterization of maximum Nash welfare for indivis- ible goods. Economics Letters222, 110956 (2023)

    work page 2023

  49. [49]

    Theory and Decision62(1), 31–45 (2007)

    Sung, S.C., Dimitrov, D.: On myopic stability concepts for hedonic games. Theory and Decision62(1), 31–45 (2007)

    work page 2007

  50. [50]

    European Journal of Operational Research203(3), 635–639 (2010)

    Sung, S.C., Dimitrov, D.: Computational complexity in additive hedonic games. European Journal of Operational Research203(3), 635–639 (2010)

    work page 2010

  51. [51]

    In: Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI) (2026), forthcoming

    Zech, V., Bullinger, M.: Deviation dynamics in cardinal hedonic games. In: Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI) (2026), forthcoming

    work page 2026

  52. [52]

    Theory of Computing3, 103–128 (2007) 20 M

    Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing3, 103–128 (2007) 20 M. Pagano and A. Schlenga Appendix In the appendix, we present the proofs omitted in the main body of the paper. Proofs for Section 3 Here, we provide proofs related to AEGs. Lemma 1.In an AEG, a partitionπis IR if ...

    work page 2007

  53. [53]

    Pagano and A

    Let nowkdenote the number of agentsisuch that 26 M. Pagano and A. Schlenga ui(π)≥ n

    work page

  54. [54]

    We proceed to prove the claimed polynomial running time

    Then, N W(π∗) N W(π) < n r (2n)k · n 4 n−k = n r 8k · n 4 n = n 4 n√ 8k <2n where the last inequality holds sincek < n. We proceed to prove the claimed polynomial running time. To this end, first note that phase 1 of the algorithm clearly takes polynomial time only, including finding a maximal{K2, K3}-packing [38]. For phase 2, we use utilitarian welfare ...

    work page

  55. [55]

    We would therefore just writeN W(s)

    In the corresponding partition of agents into two coalitions of sizessandn−s, every agent in a coalition of sizethas utilityt−1, hence the Nash welfare of a partition is determined bys. We would therefore just writeN W(s). Further, the Nash welfare strictly increases with the functionF(s) := n p N W(s). We have F(s) = (s−1) s ·(n−s−1) n−s. Ifs= 0then the ...

    work page

  56. [56]

    at mostk,

    Then, g′(s) = ln(s−1) + s s−1 −ln(n−s−1)− n−s n−s−1 , and g′′(s) = s−2 (s−1) 2 + n−s−2 (n−s−1) 2 . For2≤s≤ n 2 we haveg′′(s)>0, sog ′ is strictly increasing. Moreoverg′( n 2 ) = 0 by symmetry, and sog′(s)<0for alls < n 2, implying thatg(s), thereforeF(s), and thereforeN W(s)are strictly decreasing in this region. Therefore, among all bipartitions, an opti...

    work page