  We study the problem of allocating divisible bads (chores) among multiple
agents with additive utilities when monetary transfers are not allowed. The
competitive rule is known for its remarkable fairness and efficiency properties
in the case of goods. This rule was extended to chores in prior work by
Bogomolnaia, Moulin, Sandomirskiy, and Yanovskaya (2017). The rule produces
Pareto optimal and envy-free allocations for both goods and chores. In the case
of goods, the outcome of the competitive rule can be easily computed.
Competitive allocations solve the Eisenberg-Gale convex program; hence the
outcome is unique and can be approximately found by standard gradient methods.
An exact algorithm that runs in polynomial time in the number of agents and
goods was given by Orlin (2010).
  In the case of chores, the competitive rule does not solve any convex
optimization problem; instead, competitive allocations correspond to local
minima, local maxima, and saddle points of the Nash social welfare on the
Pareto frontier of the set of feasible utilities. The Pareto frontier may
contain many such points; consequently, the competitive rule's outcome is no
longer unique.
  In this paper, we show that all the outcomes of the competitive rule for
chores can be computed in strongly polynomial time if either the number of
agents or the number of chores is fixed. The approach is based on a combination
of three ideas: all consumption graphs of Pareto optimal allocations can be
listed in polynomial time; for a given consumption graph, a candidate for a
competitive utility profile can be constructed via an explicit formula; each
candidate can be checked for competitiveness, and the allocation can be
reconstructed using a maximum flow computation.
  Our algorithm gives an approximately-fair allocation of indivisible chores by
the rounding technique of Barman and Krishnamurthy (2018).
