We study the fair division of indivisible items with subsidies among n agents, where the absolute marginal valuation of each item is at most one. Under monotone nondecreasing valuations (where each item is a good), Brustle et al. [9] demonstrated that a maximum subsidy of 2 ( n − 1 ) and a total subsidy of 2 ( n − 1 ) 2 are sufficient to guarantee the existence of an envy-freeable allocation. In this paper, we improve upon these bounds, even in a wider model. Namely, we show that, given an EF1 allocation, we can compute in polynomial time an envy-free allocation with a subsidy of at most n − 1 per agent and a total subsidy of at most n ( n − 1 ) / 2 . Moreover, when the valuations are monotone nondecreasing, we provide a polynomial-time algorithm that computes an envy-free allocation with a subsidy of at most n − 1.5 per agent and a total subsidy of at most ( n 2 − n − 1 ) / 2 .

The Shapley–Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets, M -convex sets, and L -convex sets, which are major classes of discrete convex sets in discrete convex analysis.

We study the fair division of indivisible items with subsidies among n agents, where the absolute marginal valuation of each item is at most one. Under monotone valuations (where each item is a good), it is known that a maximum subsidy of 2(n-1) and a total subsidy of 2(n-1)² are sufficient to guarantee the existence of an envy-freeable allocation. In this paper, we improve upon these bounds, even in a wider model. Namely, we show that, given an EF1 allocation, we can compute in polynomial time an envy-free allocation with a subsidy of at most n-1 per agent and a total subsidy of at most n(n-1)/2. Moreover, we present further improved bounds for monotone valuations.

We consider an allocation problem of multiple types of objects to agents, where each type of object has multiple copies (e.g., multiple seats in a school), each agent is endowed with an object, and some distributional constraints are imposed on the allocation (e.g., minimum/maximum quotas). We develop two mechanisms that are strategyproof, feasible (they always satisfy distributional constraints), and individually rational, assuming the distributional constraints are represented by an M-convex set. One mechanism, based on Top Trading Cycles, is Pareto efficient; the other, which belongs to the mechanism class specified by Kojima et al. [1], satisfies a relaxed fairness requirement. The class of distributional constraints we consider contains many situations raised from realistic matching problems, including individual minimum/maximum quotas, regional maximum quotas, type-specific quotas, and distance constraints. Finally, we experimentally evaluate the performance of these mechanisms by a computer simulation.

In discrete convex analysis, the scaling and proximity properties for the class of L^natural-convex functions were established more than a decade ago and have been used to design efficient minimization algorithms. For the larger class of integrally convex functions of n variables, we show here that the scaling property only holds when n leq 2, while a proximity theorem can be established for any n, but only with an exponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discretely convex function in one dimension to the case of integrally convex functions in two dimensions. Furthermore, we identified a new class of discrete convex functions, called directed integrally convex functions, which is strictly between the classes of L^natural -convex and integrally convex functions but enjoys the same scaling and proximity properties that hold for L^natural -convex functions.

In this paper, we consider two-sided, many-to-one matching problems where agents in one side of the market (schools) impose some distributional constraints (e.g., a maximum quota for a set of schools), and develop a strategyproof mechanism that can handle a very general class of distributional constraints. We assume distributional constraints are imposed on a vector, where each element is the number of contracts accepted for each school. The only requirement we impose on distributional constraints is that the family of vectors that satisfy distributional constraints must be hereditary, which means if a vector satisfies the constraints, any vector that is smaller than it also satisfies them. When distributional constraints are imposed, a stable matching may not exist. We develop a strategyproof mechanism called Adaptive Deferred Acceptance mechanism (ADA), which is nonwasteful and "more fair" than a simple nonwasteful mechanism called the Serial Dictatorship mechanism (SD) and "less wasteful" than another simple fair mechanism called the Artificial Cap Deferred Acceptance mechanism (ACDA). We show that we can apply this mechanism even if the distributional constraints do not satisfy the hereditary condition by applying a simple trick, assuming we can find a vector that satisfy the distributional constraints efficiently. Furthermore, we demonstrate the applicability of our model in actual application domains.

Let G be an undirected graph with V vertices and E edges. Many algorithms have been developed for enumerating all spanning trees in G. Most of the early algorithms use a technique called "backtracking." Recently, several algorithms using a different technique have been proposed by Kapoor and Ramesh (1992), Matsui (1993), and Shioura and Tamura (1993). They find a new spanning tree by exchanging one edge of a current one. This technique has the merit of enabling us to compress the whole output of all spanning trees by outputting only relative changes of edges. Kapoor and Ramesh first proposed an O(N + V + E)-time algorithm by adopting such a "compact" output, where N is the number of spanning trees. Another algorithm with the same time complexity was constructed by Shioura and Tamura. These are optimal in the sense of time complexity but not in terms of space complexity because they take O(VE) space. We refine Shioura and Tamura's algorithm and decrease the space complexity from O(VE) to O(V + E) while preserving the time complexity. Therefore, our algorithm is optimal in the sense of both time and space complexities.