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).
Market equilibria of matching markets offer an intuitive and fair solution for matching problems without money with agents who have preferences over the items. Such a matching market can be viewed as a variation of Fisher market, albeit with rather peculiar preferences of agents. These preferences can be described by piece-wise linear concave (PLC) functions, which however, are not separable (due to each agent only asking for one item), are not monotone, and do not satisfy the gross substitute property-- increase in price of an item can result in increased demand for the item. Devanur and Kannan in FOCS 08 showed that market clearing prices can be found in polynomial time in markets with fixed number of items and general PLC preferences. They also consider Fischer markets with fixed number of agents (instead of fixed number of items), and give a polynomial time algorithm for this case if preferences are separable functions of the items, in addition to being PLC functions. Our main result is a polynomial time algorithm for finding market clearing prices in matching markets with fixed number of different agent preferences, despite that the utility corresponding to matching markets is not separable. We also give a simpler algorithm for the case of matching markets with fixed number of different items. In a variety of contexts, individuals must be allocated to positions with limited capacities. Legislators must be assigned to committees, college students to dormitories, and urban homesteaders to dwellings. (A general class of fair division problems would have the positions represent goods.) This paper examines the general problem of achieving efficient allocations when individuals' preferences are unknown and where (as with a growing number of nonmarket allocation schemes) there is no facilitating external medium of exchange such as money. An implicit market procedure is developed that elicits honest preferences, that assigns individuals efficiently, and that is adaptable to a variety of distributional objectives. We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. This model is quite different from the traditional models, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilibria. In particular, our model does not satisfy the condition of non-satiation, which is used critically to show the existence of equilibria in traditional market models and we observe that our set of equilibrium prices could be a connected, non-convex set. We give a proof of the existence of equilibria and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models as well as new models, such as CEEI. We consider markets in the classical Arrow-Debreu model. There are n agents and m goods. Each buyer has a concave utility function (of the bundle of goods he she buys) and an initial bundle. At an ldquoequilibriumrdquo set of prices for goods, if each individual buyer separately ex-changes the initial bundle for an optimal bundle at the set prices, the market clears, i.e., all goods are exactly consumed. Classical theorems guarantee the existence of equilibria, but computing them has been the subject of much recent research. In the related area of Multi-Agent Games,much attention has been paid to the complexity as well as algorithms. While most general problems are hard, polynomial time algorithms have been developed for restricted classes of games, when one assumes the number of strategies is constant.For the Market Equilibrium problem, several important special cases of utility functions have been tackled. Here we begin a program for this problem similar to that for multi-agent games, where general utilities are considered. We begin by showing that if the utilities are separable piece-wise linear concave (PLC) functions, and the number of goods(or alternatively the number of buyers) is constant, then we can compute an exact equilibrium in polynomial time.Our technique for the constant number of goods is to de-compose the space of price vectors into cells using certain hyperplanes, so that in each cell, each buyerpsilas threshold marginal utility is known. Still, one needs to solve a linear optimization problem in each cell. We then show the main result - that for general (non-separable) PLC utilities, an exact equilibrium can be found in polynomial time provided the number of goods is constant. The starting point of the algorithm is a ldquocell-decompositionrdquo of the space of price vectors using polynomial surfaces (instead of hyperplanes).We use results from computational algebraic geometry to bound the number of such cells. For solving the problem inside each cell, we introduce and use a novel LP-duality based method. We note that if the number of buyers and agents both can vary, the problem is PPAD hard even for the very special case of PLC utilities - namely Leontief utilities.