We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. 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. 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 rule becomes multivalued and none of the standard methods can be applied to compute its outcome. 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 allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).
The polynomial time algorithms in these works are designed for economies that satisfy implicit or explicit convexity assumptions. For example, in the case of Fisher markets, the competitive equilibrium solves the Eisenberg-Gale convex program @cite_67 for a large class of utilities, maximizing the Nash product (i.e., the geometric mean of the utilities weighted by the budgets of the agents). Moreover, the equilibrium is unique, robust @cite_10 (i.e., small errors in the observation of the market parameters do not change the competitive allocation by much), and admits polynomial time approximation algorithms based on gradient descent methods as well as exact algorithms (see, e.g., Chapters 5 and 6 in @cite_12 ). In contrast, in the case of chores, there is a multiplicity of equilibria and no robustness guarantee: the set of equilibria admits no continuous selections @cite_39 .
@cite_67 @cite_10 @cite_12 @cite_39
1980938853 1562593567 2586913291
Abstract : Under the pari-mutuel system of betting on horse races the final track's odds are in some sense a consensus of the 'subjective odds' of the individual bettors weighted by the amounts of their bets. The properties which this consensus must possess and prove that there always exists a unique set of odds having the required properties are formulated. (Author) Continuity of the mapping from initial endowments and utilities to equilibria is an essential property for a desirable model of an economy - without continuity, small errors in the observation of parameters of the economy may lead to entirely different predicted equilibria. We show that for the linear case of Fisher's market model, the (unique) vector of equilibrium prices, p = p(m, U) is a continuous function of the initial amounts of money held by the agents, m, and their utility functions, U. Furthermore, the correspondence X(m, U), giving the set of equilibrium allocations for any specified m and U, is upper hemicontinuous, but not lower hemicontinuous. However, for a fixed U, this correspondence is lower hemicontinuous in m. A mixed manna contains goods (that everyone likes), bads (that everyone dislikes), as well as items that are goods to some agents, but bads or satiated to others. If all items are goods and utility functions are homothetic, concave (and monotone), the Competitive Equilibrium with Equal Incomes maximizes the Nash product of utilities: hence it is welfarist (determined utility-wise by the feasible set of pro les), single-valued and easy to compute. We generalize the Gale-Eisenberg Theorem to a mixed manna. The Competitive division is still welfarist and related to the product of utilities or disutilities. If the zero utility pro le (before any manna) is Pareto dominated, the competitive pro le is unique and still maximizes the product of utilities. If the zero pro le is unfeasible, the competitive pro les are the critical points of the product of disutilities on the eciency frontier, and multiplicity is pervasive. In particular the task of dividing a mixed manna is either good news for everyone, or bad news for everyone. We re ne our results in the practically important case of linear preferences, where the axiomatic comparison between the division of goods and that of bads is especially sharp. When we divide goods and the manna improves, everyone weakly bene ts under the competitive rule; but no reasonable rule to divide bads can be similarly Resource Monotonic. Also, the much larger set of Non Envious and Ecient divisions of bads can be disconnected so that it will admit no continuous selection.