  We study fair resource allocation under a connectedness constraint wherein a
set of indivisible items are arranged on a path and only connected subsets of
items may be allocated to the agents. An allocation is deemed fair if it
satisfies equitability up to one good (EQ1), which requires that agents'
utilities are approximately equal. We show that achieving EQ1 in conjunction
with well-studied measures of economic efficiency (such as Pareto optimality,
non-wastefulness, maximum egalitarian or utilitarian welfare) is
computationally hard even for binary additive valuations. On the algorithmic
side, we show that by relaxing the efficiency requirement, a connected EQ1
allocation can be computed in polynomial time for any given ordering of agents,
even for general monotone valuations. Interestingly, the allocation computed by
our algorithm has the highest egalitarian welfare among all allocations
consistent with the given ordering. On the other hand, if efficiency is
required, then tractability can still be achieved for binary additive
valuations with interval structure. On our way, we strengthen some of the
existing results in the literature for other fairness notions such as
envy-freeness up to one good (EF1), and also provide novel results for
negatively-valued items or chores.
