We revisit the setting of fair allocation of indivisible items among agents with heterogeneous, non-monotone valuations. We explore the existence and efficient computation of allocations that approximately satisfy either envy-freeness or equity constraints. Approximate envy-freeness ensures that each agent values her bundle at least as much as those given to the others, after some (or any) item removal, while approximate equity guarantees roughly equal valuations among agents, under similar adjustments. As a key technical contribution of this work, by leveraging fixed-point theorems (such as Sperner's Lemma and its variants), we establish the existence of envy-free-up-to-one-good-and-one-chore (EF1_g^c) and equitable-up-to-one-good-and-one-chore (EQ1_g^c) allocations, for non-monotone valuations that are always either non-negative or non-positive. These notions represent slight relaxations of the well-studied envy-free-up-to-one-item (EF1) and equitable-up-to-one-item (EQ1) guarantees, respectively. Our existential results hold even when items are arranged in a path and bundles must form connected sub-paths. The case of non-positive valuations, in particular, has been solved by proving a novel multi-coloring variant of Sperner's Lemma that constitutes a combinatorial result of independent interest. In addition, we also design a polynomial-time dynamic programming algorithm that computes an EQ1_g^c allocation. For monotone non-increasing valuations and path-connected bundles, all the above results can be extended to EF1 and EQ1 guarantees as well. Finally, we provide existential and computational results for certain stronger up-to-any-item equity notions under objective valuations, where items are partitioned into goods and chores.

Early development of digital topology concentrated on tessellations of the plane into square-shaped pixels, each one of which had a 1 or a 0 assigned to it. It became quickly apparent that in order to avoid some “paradoxes” one needs to consider adjacencies in addition to that provided by the edge-adjacency. The customary choice became the use of a pair of adjacencies; one for the 1-pixels and another for the 0-pixels. While this approach can be treated in a mathematically rigorous fashion, it nevertheless remains attractive to consider those digital spaces in which a single adjacency sufficies to usefully define connectivity. This not only makes the resulting mathematics more elegant, but it also brings the subject nearer to classical graph theory and its enormous wealth of results. This is what motivated us to search for an appropriate new concept. Jordan curves have an interior and an exterior which between them contain all the points not on the curve and both of which are connected, but are disconnected from each other. Generalization to surfaces in digital spaces is useful when displaying (only the exterior of a surface is visible from any direction) or analyzing (the interior volume is well defined). Boundaries in digital spaces may or may not be Jordan, but are “guaranteed” to be Jordan in spaces we call strong Jordan graphs. In this paper we define such a notion of a strong Jordan graph. We show that some previously studied classes (such as those of 1-simply connected digital spaces and of bridged graphs) are subclasses of strong Jordan graphs. We also define Jordan graphs, as those digital spaces in which finite boundaries are guaranteed to be Jordan and show that there are Jordan graphs which are not strong Jordan graphs. (Strong) Jordan graphs are characterized by the existence of “cuts” in associated graphs, by the acyclic nature of the adjacency graphs of binary pictures, and also by the connectedness of the immediate interiors (or exteriors) of certain types of surfaces. The surfaces of the last category include the so-called minimally near-Jordan surfaces, which are shown to be of some interest. Finally, we tie some of these notions to standard notions of graph theory, such as the notion of a separating set. Our overall conclusion is that those digital spaces which are Jordan graphs have some very desirable properties which make their use advantageous whenever the underlying situation allows us to use them.

We consider the set union problem (SUP) which consists in designing data for manipulation of a family of disjoint sets which partition a given universe of n elements. In response to a work of Tarjan we prove that the POSTORDER strategy for SUP has a linear length (thus solving a problem of Hart and Sharir). On the other side, we provide a data structure and axioms for an on line strategy-LOCAL POSTORDER-for SUP which fails to be linear but it has a very slow-indeed in the theory of finite sets unprovable-growth. This complements a result of Tarjan who showed an Ackermann type growth for a related problem. Our results may be summarized by saying that (in finite set theory) we may assume that our algorithms are linear (although we know that in fact they fail to be linear). Perhaps this is the first occurrence of unprovability in the complexity analysis of algorithms.