Necklace Bisection with One Cut Less than Needed A wellknown theorem of Goldberg and West states that two thieves can always split a necklace containing an even number of beads from each of k types fairly by at most k cuts. We prove that if we can use at most k1 cuts and fair splitting is not possible then the thieves still have the following option.  Whatever way they specify two disjoint sets D_1, D_2 of the types of beads with D_1cup D_2neqemptyset, it will always be possible to cut the necklace (with k1 cuts) so that the first thief gets more of those types of beads that are in D_1 and the second gets more of those in D_2, while the rest is divided equally. The proof combines the simple proof given by Alon and West to the original statement with a variant of the BorsukUlam theorem due to Tucker and Bacon.

A Little Charity Guarantees Almost EnvyFreeness Fair division of indivisible goods is a very wellstudied problem. The goal of this problem is to distribute m goods to n agents in a fair manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envyfreeness is the most extensively studied notion of fairness. However, envyfree allocations do not always exist when goods are indivisible. The notion of fairness we consider here is envyfreeness up to any good (EFX) where no agent envies another agent after the removal of any single good from the other agentu0027s bundle. It is not known if such an allocation always exists even when n3. We show there is always a partition of the set of goods into n1 subsets (X_1,ldots,X_n,P) where for i in n, X_i is the bundle allocated to agent i and the set P is unallocated (or donated to charity) such that we havecolon 1) envyfreeness up to any good, 2) no agent values P higher than her own bundle, and 3) fewer than n goods go to charity, i.e., P u003c n (typically m gg n). Our proof is constructive. When agents have additive valuations and lvert P rvert is large (i.e., when P is close to n), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is 47 groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of 12 known for an approximate GMMS allocation.