Pith. sign in

REVIEW 5 minor 49 references

The Price of Connectivity in Fair Division

T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The price of connectivity, the worst-case ratio between the best connected fairness guarantee and the unconstrained one, is 1/k for graphs with a cut vertex that splits into k pieces, at least 3/4 for biconnected graphs with two agents, and 1/(m−n+1) for paths and stars.

desk verdict Genuinely new measure with clean exact results; worth a careful read and a serious referee. read the letter →

arxiv 1908.05433 v3 pith:EHQ2M47E submitted 2019-08-15 cs.GT cs.DMmath.CO

Xiaohui Bei , Ayumi Igarashi , Xinhang Lu , Warut Suksompong This is my paper · ORCID
classification cs.GTcs.DMmath.CO
keywords agentsgraphsenvy-freenessfairnessmaximinshareallocationcase
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

Imagine dividing a row of offices between two research groups, with the rule that each group gets a connected block. Fair division without this rule already has a standard guarantee called the maximin share, the most value an agent can secure when goods are split into n parts and she gets the worst one. This paper asks how much of that guarantee is lost when the parts have to be connected subgraphs of a given graph, and calls the worst-case loss the price of connectivity.

For two agents, the answer depends on how robustly the graph itself is connected. If deleting some vertex shatters the graph into up to k pieces, the price is exactly 1/k, so the guarantee can be as low as half of the unconstrained share for trees. If the graph is biconnected, meaning no single vertex disconnects it, you can always guarantee at least 3/4 of the share, and this is tight even for some 3-connected and 5-connected graphs. For any number of agents, every connected graph yields at least 1/(m−n+1) of the maximin share, and this is exact for stars and for paths. The path result is derived through a new relaxation of proportionality called the indivisible proportional share.

On the envy side, the paper determines the smallest k such that an envy-free-up-to-k-goods allocation always exists for two agents on any given graph, and characterizes the trees and complete bipartite graphs that guarantee EF1 for three agents. All guarantees come with polynomial-time algorithms except for one existence theorem.

Extended reading notes

Core claim

Corollary 3.2: Let n be any positive integer, G any graph, and α := PoC(G,n). If n = 2, or if G is a tree, then there always exists a connected allocation that gives each agent at least α times their MMS, and the factor α is tight. In addition, for two agents, every biconnected graph has PoC ≥ 3/4 (Theorem 3.7), every connectivity-1 graph with maximum k components after vertex deletion has PoC = 1/k (Theorem 3.3), and every pair of agents on any connected graph has a connected EFk allocation for the smallest k determined by the block-decomposition condition of Theorem 4.3.

Load-bearing premise

The maximin-share and PoC results assume additive utilities, as stated at the start of Section 3. All PoC upper-bound constructions and lower-bound arguments, including Lemma 3.5 and the averaging in Theorem 3.16, use additivity in an essential way; if agents have non-additive valuations, the PoC notion and the 1/(m−n+1) guarantee have no stated content. Additionally, the connected MMS guarantee for arbitrary graphs in Theorem 3.17 inherits the prior G-MMS existence theorem for trees (Bouveret et al., Thm 5.4), so a failure of that prior theorem would break the universal guarantee.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. This paper studies the fair allocation of indivisible goods that form a connected undirected graph, with the requirement that each agent receive a connected bundle. It introduces the price of connectivity (PoC) as the worst-case ratio between the graph-restricted maximin share and the unconstrained maximin share. For two agents, the paper proves PoC = 1/k for graphs of connectivity 1 (where k is the maximum number of components after deleting a vertex), PoC ≥ 3/4 for biconnected graphs, and exact PoC values for several families, including complete graphs with a matching removed; it also proposes a conjecture, verified for a nontrivial class, that would settle the two-agent case. For general n, it establishes a universal lower bound 1/(m−n+1) and tight bounds for paths and stars, introducing the indivisible proportional share (IPS) property in the process. On the envy-freeness side, the paper characterizes, for every graph and two agents, the smallest k for which an EFk allocation is always guaranteed, via a block-decomposition condition; it also characterizes the trees and complete bipartite graphs that guarantee EF1 for three agents. Most guarantees come with polynomial-time algorithms.

Significance. The paper gives a clean, parameter-free quantitative framework for the fairness loss caused by connectivity constraints, with tight results for several major graph classes and a complete two-agent EFk characterization. The PoC notion meaningfully connects graph connectivity to MMS approximation, and the lower-bound constructions are explicit utility functions rather than existential arguments. The paper also introduces IPS, a new proportionality relaxation stronger than several existing notions, and shows it is always achievable on paths; this is likely to be of independent interest. The proofs are detailed and largely constructive, with polynomial-time algorithms for most theorems, including the 3/4-MMS approximation for biconnected graphs in Appendix A. The main open conjecture (Conjecture 3.13) is well-motivated and is verified for complete graphs with a matching removed, lending further credibility to the proposed framework.

minor comments (5)
  1. [Section 3.2, Proposition 3.21] The proof uses the assertion that any superset of an IPS bundle is also IPS, but this is stated without proof. The claim is true for the IPS constants used (since c ≤ 1), but it requires a short argument; moreover, in Case 2 the application of the non-IPS condition uses sets Y and Z that may include goods already allocated to earlier agents, so the proof should explicitly invoke monotonicity of u and restrict the set B to the goods available at the relevant time. Please add these details.
  2. [Section 3.1, Lemma 3.5] The dichotomy 'each part either has value at most αx, or at least y+(1−α)x' is correct but terse; a one-line explanation (at least one part must have value at most αx, hence the other part has value at least the total minus αx) would prevent reader confusion.
  3. [Section 3.2, Theorem 3.22] The upper-bound proofs for paths rely on 'one can check' statements asserting that some part has value at most 1 in any connected n-partition. Please add a short pigeonhole argument: since high-value goods are separated by value-1 goods, a connected part avoiding all high-value goods can contain at most one unit-valued good.
  4. [Section 4.1, Theorem 4.3] The proof of Theorem 4.3 is intricate, and the switch operations in Cases 1 and 2 are described with the help of Figures 4 and 5. A sentence explicitly pointing the reader to the relevant figure when the first switch operation is introduced would improve readability.
  5. [Throughout] There are several typographical issues, such as 'an d' in the abstract, 'und irected' in the first sentence, and inconsistent spacing in some references; these should be cleaned up in the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the PoC and EFk results are established by independent constructions and external theorems, not by restating their own inputs.

full rationale

The paper's central derivation chain is self-contained against external benchmarks. The PoC bounds in Section 3 are proved by direct constructions and averaging arguments rather than by restating the definition of PoC; for example, Theorem 3.16 proves PoC(G,n) >= 1/(m-n+1) by expanding an arbitrary MMS partition to a connected partition, and Theorems 3.19 and 3.22 prove matching upper bounds with explicit utility functions. Corollary 3.2 invokes two prior existence results (Lonc-Truszczynski Cor. 2 and Bouveret et al. Thm. 5.4) to convert G-MMS guarantees into MMS guarantees, but those results are independent published theorems with stated assumptions, not restatements of anything derived in this paper. The EFk characterization in Theorem 4.3 uses Bilo et al.'s bipolar-ordering/EF1 equivalence as a lemma, but the proof of Theorem 4.3 supplies its own merge, switch, and binary-utility arguments for both directions; the cited equivalence is not the conclusion of the theorem. The remaining graph-theoretic tools (Whitney's open ear decomposition, block decomposition) are standard external facts. No fitted parameter is renamed as a prediction, and no load-bearing claim reduces by definition to its own input. The self-citations to Bouveret et al. and Bilo et al., which share co-authors with this paper, are therefore not circular.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper introduces new mathematical definitions such as PoC, G-MMS, IPS, and dependents and guardians in block trees, but no new ontological or physical entities, no new forces, and no new conserved quantities. All new constructs are defined within the model and require no independent empirical handle, so the invented-entities ledger is empty. The free-parameters ledger is empty because the utility functions in upper-bound constructions are adversarial instance inputs, not fitted constants; the derived bounds depend only on graph invariants and the number of agents and goods.

assumptions (8)
  • domain assumption Additive utility functions are assumed for all maximin share and PoC results (Section 3).
    Stated at the start of Section 3. All PoC bounds and MMS guarantees in Section 3 rely on additivity, including Lemma 3.5, Theorem 3.16, and the path and star constructions.
  • domain assumption Arbitrary monotonic utilities are assumed for the envy-freeness results (Section 4).
    Stated in Section 2 and used throughout Section 4; the EFk and EF1 characterizations are claimed for all monotonic utilities.
  • domain assumption Goods correspond bijectively to vertices of a connected undirected graph, and allocations must assign connected subgraphs (Section 2).
    This is the underlying model inherited from Bouveret et al. and Bilo et al.
  • standard math Whitney's open ear decomposition theorem for biconnected graphs, with arbitrary first ear (Proposition 3.6).
    Used in the proof of Theorem 3.7 to construct a bipolar ordering starting and ending at prescribed heavy goods.
  • standard math The block decomposition of a connected graph is a tree (Bondy and Murty, Proposition 4.1).
    Used in Theorem 4.3 to define paths in the block tree and to count dependents.
  • standard math Bilo et al. characterization: a graph guarantees EF1 for two agents iff it admits a bipolar ordering (Proposition 4.2).
    Used as the base equivalence for the EFk generalization and in the proof of Theorem 4.3.
  • standard math There always exists a connected allocation giving every agent her G-MMS when n=2 (Lonc and Truszczynski, Cor. 2) or when the graph is a tree (Bouveret et al., Thm 5.4).
    Used in Corollary 3.2 and Theorem 3.17 to convert PoC bounds into MMS guarantees.
  • standard math Existence of a 5-connected graph that is not 2-linked (Meszaros 2015) and 2-linkedness of 6-connected graphs (Jung 1970).
    Used for Corollary 3.10 and the surrounding discussion of linkedness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Price of Connectivity in Fair Division." pith.science (2026). https://pith.science/paper/EHQ2M47E

@misc{pith2026190805433,
  author       = {Pith},
  title        = {Pith review of: The Price of Connectivity in Fair Division},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EHQ2M47E}},
  note         = {Machine review of arXiv:1908.05433}
}
abstract

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least $3/4$ of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most $1/2$. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems.

Figures

Figures reproduced from arXiv: 1908.05433 by the authors.

Figure 1
Figure 1. An instance showing that the PoC of a wheel graph is at mos [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Graph L5 and utilities showing that its PoC is at most 3/4. Proof. We proceed by induction on k. For the base case k = 1 we must have s = 2, x1 = 2, r = 0, and the result holds trivially. Suppose now that the result holds for k −1; we will prove it for k. Assume without loss of generality that x1 = max{x1, x2, . . . , xk}. First, assume that x1 ≤ 2. Define yi := x1 + x2 + · · · + xi for each i. The sequence 0, y1, y… view at source ↗
Figure 3
Figure 3. An example of a block decomposition B(G) in the proof of Theorem 4.3. Blue vertices correspond to blocks in G and red vertices correspond to cut vertices in G. Here, C(P) = {v1, v3, v6, v7}. In this example, v1 is the guardian of all vertices in block v2 except itself, v3 is the guardian of all vertices in blocks v4 and v5 except itself, while v6 and v7 are not guardians of any vertices. Theorem 4.3. For any connect… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: An example of a switch operation on the tree [PITH_FULL_IMAGE:figures/full_fig_p024_4.png]
Figure 5
Figure 5. Figure 5: An example of a switch operation on the tree [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]
Figure 6
Figure 6. Figure 6: Example of an instance in the proof of Theorem 4.7. [PITH_FULL_IMAGE:figures/full_fig_p028_6.png]
Figure 7
Figure 7. Figure 7: Example of an instance in the proof of Theorem 4.9. [PITH_FULL_IMAGE:figures/full_fig_p030_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 45 canonical work pages

  1. [1]

    Rediet Abebe, Jon Kleinberg, and David C. Parkes. Fair division via social comparison. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS) , pages 281--289, 2017

    work page 2017

  2. [2]

    Knowledge, fairness, and social constraints

    Haris Aziz, Sylvain Bouveret, Ioannis Caragiannis, Ira Giagkousi, and J\' e r\^ o me Lang. Knowledge, fairness, and social constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI) , pages 4638--4645, 2018

    work page 2018

  3. [3]

    Fair allocation of indivisible goods and chores

    Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair allocation of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , pages 53--59, 2019

    work page 2019

  4. [4]

    Approximation algorithms for maximin fair division

    Siddharth Barman and Sanath Kumar Krishna Murthy . Approximation algorithms for maximin fair division. In Proceedings of the 18th ACM Conference on Economics and Computation (EC) , pages 647--664, 2017

    work page 2017

  5. [5]

    Networked fairness in cake cutting

    Xiaohui Bei, Youming Qiao, and Shengyu Zhang. Networked fairness in cake cutting. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI) , pages 3632--3638, 2017

    work page 2017

  6. [6]

    Local envy-freeness in house allocation problems

    Aur \' e lie Beynier, Yann Chevaleyre, Laurent Gourv \` e s, Julien Lesca, Nicolas Maudet, and Ana \" e lle Wilczynski. Local envy-freeness in house allocation problems. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS) , pages 292--300, 2018

    work page 2018

  7. [7]

    Vittorio Bil\` o , Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. Almost envy-free allocations with connected bundles. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS) , pages 14:1--14:21, 2019. Extended version: CoRR, abs/1808.09406

    work page Pith review arXiv 2019

  8. [8]

    Fair division under cardinality constraints

    Arpita Biswas and Siddharth Barman. Fair division under cardinality constraints. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , pages 91--97, 2018

    work page 2018

Show all 49 references
  1. [9]

    John Adrian Bondy and U. S. R. Murty. Graph Theory . Springer, 1st edition, 2008

    2008

  2. [10]

    Fair division of a graph

    Sylvain Bouveret, Katar\' i na Cechl\' a rov\' a , Edith Elkind, Ayumi Igarashi, and Dominik Peters. Fair division of a graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI) , pages 135--141, 2017

    2017

  3. [11]

    Chore division on a graph

    Sylvain Bouveret, Katar\' i na Cechl\' a rov\' a , and Julien Lesca. Chore division on a graph. Autonomous Agents and Multi-Agent Systems , 33(5):540--563, 2019

    2019

  4. [12]

    Brams and Peter C

    Steven J. Brams and Peter C. Fishburn. Fair division of indivisible items between two people with identical preferences: Envy-freeness, P areto-optimality, and equity. Social Choice and Welfare , 17(2):247--267, 2000

    2000

  5. [13]

    Brams and Alan D

    Steven J. Brams and Alan D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution . Cambridge University Press, 1996

    1996

  6. [14]

    Brams and Alan D

    Steven J. Brams and Alan D. Taylor. A procedure for divorce settlements. Mediation Quarterly , 13(3):191--205, 1996

    1996

  7. [15]

    Brams, D

    Steven J. Brams, D. Marc Kilgour, and Christian Klamler. The undercut procedure: an algorithm for the envy-free division of indivisible items. Social Choice and Welfare , 39(2--3):615--631, 2012

    2012

  8. [16]

    Brams, D

    Steven J. Brams, D. Marc Kilgour, and Christian Klamler. Two-person fair division of indivisible items: an efficient, envy-free algorithm. Notices of the AMS , 61(2):130--141, 2014

    2014

  9. [17]

    Envy-free allocations respecting social networks

    Robert Bredereck, Andrzej Kaczmarczyk, and Rolf Niedermeier. Envy-free allocations respecting social networks. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS) , pages 283--291, 2018

    2018

  10. [18]

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes

    Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy , 119(6):1061--1103, 2011

    2011

  11. [19]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Herv\' e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum N ash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC) , pages 305--322, 2016

    2016

  12. [20]

    Fair public decision making

    Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC) , pages 629--646, 2017

    2017

  13. [21]

    Impartial division of a dollar

    Geoffroy de Clippel , Herv\' e Moulin, and Nicolaus Tideman. Impartial division of a dollar. Journal of Economic Theory , 139:176--191, 2008

    2008

  14. [22]

    Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D

    John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, and Tuomas Sandholm. The computational rise and fall of fairness. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI) , pages 1405--1411, 2014

    2014

  15. [23]

    Computing an st -numbering

    Shimon Even and Robert Endre Tarjan. Computing an st -numbering. Theoretical Computer Science , 2(3):339--344, 1976

    1976

  16. [24]

    Fair allocation of indivisible goods: Improvements and generalizations

    Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC) , pages 539--556, 2018

    2018

  17. [25]

    On maximin share allocations in matroids

    Laurent Gourv\` e s and J\' e r\^ o me Monnot. On maximin share allocations in matroids. Theoretical Computer Science , 754:50--64, 2019

    2019

  18. [26]

    Algorithm 447: Efficient algorithms for graph manipulation

    John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM , 16(6):372--378, 1973

    1973

  19. [27]

    Pareto-optimal allocation of indivisible goods with connectivity constraints

    Ayumi Igarashi and Dominik Peters. Pareto-optimal allocation of indivisible goods with connectivity constraints. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) , pages 2045--2052, 2019

    2019

  20. [28]

    Heinz A. Jung. Eine V erallgemeinerung des n -fachen Z usammenhangs f \" u r G raphen. Mathematische Annalen , 187(2):95--103, 1970

    1970

  21. [29]

    Marc Kilgour and Rudolf Vetschera

    D. Marc Kilgour and Rudolf Vetschera. Two-player fair division of indivisible items: C omparison of algorithms. European Journal of Operational Research , 271(2):620--631, 2018

    2018

  22. [30]

    Procaccia, and Junxing Wang

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM , 64(2):8, 2018

    2018

  23. [31]

    Voudouris

    Maria Kyropoulou, Warut Suksompong, and Alexandros A. Voudouris. Almost envy-freeness in group resource allocation. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI) , pages 400--406, 2019

    2019

  24. [32]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC) , pages 125--131, 2004

    2004

  25. [33]

    Maximin share allocations on cycles

    Zbigniew Lonc and Miroslaw Truszczynski. Maximin share allocations on cycles. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI) , pages 410--416, 2018

    2018

  26. [34]

    When do envy-free allocations exist? In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) , pages 2109--2116, 2019

    Pasin Manurangsi and Warut Suksompong. When do envy-free allocations exist? In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) , pages 2109--2116, 2019

    2019

  27. [35]

    Approximation algorithms and hardness results for fair division

    Evangelos Markakis. Approximation algorithms and hardness results for fair division. In Ulle Endriss, editor, Trends in Computational Social Choice , chapter 12, pages 231--247. AI Access, 2017

    2017

  28. [36]

    Linkedness and Path-Pairability in the Cartesian Product of Graphs

    G\' a bor M\' e sz\' a ros. Linkedness and Path-Pairability in the Cartesian Product of Graphs . PhD thesis, Central European University, 2015

    2015

  29. [37]

    Fair Division and Collective Welfare

    Herv\' e Moulin. Fair Division and Collective Welfare . MIT Press, 2003

    2003

  30. [38]

    Fair division in the internet age

    Herv\' e Moulin. Fair division in the internet age. Annual Review of Economics , 11:407--441, 2019

    2019

  31. [39]

    Procaccia, and Warut Suksompong

    Hoon Oh, Ariel D. Procaccia, and Warut Suksompong. Fairly allocating many goods with few queries. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) , pages 2141--2148, 2019

    2019

  32. [40]

    Almost envy-freeness with general valuations

    Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2584--2603, 2018

    2018

  33. [41]

    Communication complexity of discrete fair division

    Benjamin Plaut and Tim Roughgarden. Communication complexity of discrete fair division. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2014--2033, 2019

    2014

  34. [42]

    Jens M. Schmidt. A simple test on 2-vertex- and 2-edge-connectivity. Information Processing Letters , 113(7):241--244, 2013

    2013

  35. [43]

    Democratic fair allocation of indivisible goods

    Erel Segal-Halevi and Warut Suksompong. Democratic fair allocation of indivisible goods. Artificial Intelligence , 277:103167, 2019

    2019

  36. [44]

    Fairly allocating contiguous blocks of indivisible items

    Warut Suksompong. Fairly allocating contiguous blocks of indivisible items. Discrete Applied Mathematics , 260:227--236, 2019

    2019

  37. [45]

    Introduction to the theory of fair allocation

    William Thomson. Introduction to the theory of fair allocation. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J\' e r\^ o me Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice , chapter 11, pages 261--283. Cambridge University Press, 2016

    2016

  38. [46]

    Congruent graphs and the connectivity of graphs

    Hassler Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics , 54(1):150--168, 1932

    1932

  39. [47]

    Non-separable and planar graphs

    Hassler Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society , 34(2):339--362, 1932

    1932

  40. [48]

    Woeginger

    Gerhard J. Woeginger. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters , 20(4):149--154, 1997

    1997

  41. [49]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence '...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.