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).
Eisenberg and Gale (1959) gave a convex program for computing market equilibrium for Fisher's model for linear utility functions, and Eisenberg (1961) generalized this to concave homogeneous functions of degree one. We further generalize to:1. Homothetic, quasi-concave utilities. This also helps extend Eisenberg's result to concave homogeneous functions of arbitrary degree.2. We introduce the notion of a trading cone which enables us to compute market equilibrium in the presence of economies of scale in production provided differential pricing is allowed. Applications to network pricing are provided. Utility functions satisfying gross substitutability have been studied extensively in the economics literature [1,11,12] and recently, the importance of this property has been recognized in the design of combinatorial polynomial time market equilibrium algorithms [8]. This naturally raises the following question: is it possible to design a combinatorial polynomial time algorithm for this general class of utility functions? We partially answer this question by giving an algorithm for separable, differentiable, concave utility functions satisfying gross substitutes. Our algorithm uses the auction based approach of [10].  We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme, unless every problem in PPAD is solvable in polynomial time.  We consider exchange economies where the traders' preferences are expressed in terms of the extensively used constant elasticity of substitution (CES) utility functions. We show that for any such economy it is possible to say in polynomial time whether an equilibrium exists. We then describe a convex formulation of the equilibrium conditions, which leads to polynomial time algorithms for a wide range of the parameter defining the CES utility functions. This range includes instances that do not satisfy weak gross substitutability. As a byproduct of our work, we prove the uniqueness of equilibrium in an interesting setting where such a result was not known. The range for which we do not obtain polynomial-time algorithms coincides with the range for which the economies admit multiple disconnected equilibria.  We provide the first polynomial time exact algorithm for computing an Arrow-Debreu market equilibrium for the case of linear utilities. Our algorithm is based on solving a convex program using the ellipsoid algorithm and simultaneous diophantine approximation. As a side result, we prove that the set of assignments at equilibrium is convex and the equilibrium prices themselves are log-convex. Our convex program is explicit and intuitive, which allows maximizing a concave function over the set of equilibria. On the practical side, Ye developed an interior point algorithm [Lecture Notes in Comput. Sci. 3521, Springer, New York, 2005, pp. 3-5] to find an equilibrium based on our convex program. We also derive separate combinatorial characterizations of equilibrium for Arrow-Debreu and Fisher cases. Our convex program can be extended for many nonlinear utilities and production models. Our paper also makes a powerful theorem (Theorem 6.4.1 in [M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd ed., Springer-Verlag, Berlin, Heidelberg, 1993]) even more powerful (in Theorems 12 and 13) in the area of geometric algorithms and combinatorial optimization. The main idea in this generalization is to allow ellipsoids to contain not the whole convex region but a part of it. This theorem is of independent interest. We consider a nonlinear extension of the generalized network flow model, with the flow leaving an arc being an increasing concave function of the flow entering it, as proposed by Truemper and Shigeno. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an @math -approximate solution in @math arithmetic operations and value oracle queries, where @math and @math are upper bounds on simple parameters. This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg, Plot kin and Tardos, not using any cycle cancellations. We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [4]. Our first result shows membership in PPAD for the problem of computing approximate equilibria for an Arrow-Debreu exchange market for piecewise-linear concave (PLC) utility functions. As a corollary we also obtain membership in PPAD for Leontief utility functions. This settles an open question of Vazirani and Yannakakis (2011). Next we show FIXP-hardness of computing equilibria in Arrow-Debreu exchange markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets, thereby settling these open questions of Vazirani and Yannakakis (2011). As corollaries, we obtain FIXP-hardness for PLC utilities and for Arrow-Debreu markets under linear utility functions and polyhedral production sets. In all cases, as required under FIXP, the set of instances mapped onto will admit equilibria, i.e., will be "yes" instances. If all instances are under consideration, then in all cases we prove that the problem of deciding if a given instance admits an equilibrium is ETR-complete, where ETR is the class Existential Theory of Reals. As a consequence of the results stated above, and the fact that membership in FIXP has been established for PLC utilities, the entire computational difficulty of Arrow-Debreu markets under PLC utility functions lies in the Leontief utility subcase. This is perhaps the most unexpected aspect of our result, since Leontief utilities are meant for the case that goods are perfect complements, whereas PLC utilities are very general, capturing not only the cases when goods are complements and substitutes, but also arbitrary combinations of these and much more. Finally, we give a polynomial time algorithm for finding an equilibrium in Arrow-Debreu exchange markets under Leontief utility functions provided the number of agents is a constant. This settles part of an open problem of Devanur and Kannan (2008). A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective ∑ij∈E Cij(fij) over feasible flows f, where on every arc ij of the network, Cij is a convex function. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The key characteristic of this class is that an optimal solution can be computed exactly provided its support. This includes separable convex quadratic objectives and also certain market equilibria problems: Fisher's market with linear and with spending constraint utilities. We thereby give the first strongly polynomial algorithms for separable quadratic minimum-cost flows and for Fisher's market with spending constraint utilities, settling open questions posed e.g. in [15] and in [35], respectively. The running time is O(m4 log m) for quadratic costs, O(n4+n2(m+n log n) log n) for Fisher's markets with linear utilities and O(mn3 +m2(m+n log n) log m) for spending constraint utilities. Although the study of market equilibria has occupied center stage within mathematical economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's (1995) primal-dual algorithm for bipartite matching. We give the rst strongly polynomial time algorithm for computing an equilibrium for the linear utilities case of Fisher’s market model. We consider a problem with a set B of buyers and a set G of divisible goods. Each buyer i starts with an initial integral allocation ei of money. The integral utility for buyer i of good j is Uij. We rst develop a weakly polynomial time algorithm that runs in O(n 4 logUmax +n 3 emax) time, where n =jBj +jGj. We further modify the algorithm so that it runs in O(n 4 logn) time. These algorithms improve upon the previous best running time of O(n 8 logUmax +n 7 logemax), due to [5] In this paper we study efficient algorithms for computing equilibrium price in the Fisher model for a class of nonlinear concave utility functions, the logarithmic utility functions. We derive a duality relation between buyers and sellers under such utility functions, and use it to design a polynomial time algorithm for calculating equilibrium price, for the special case when either the number of sellers or the number of buyers is bounded by a constant.