Kazuhisa Makino

Linear programming (LP) problems with gainfree Leontief substitution systems have been intensively studied in economics and operations research, and include the feasibility problem of a class of Horn systems, which arises in, e.g., polyhedral combinatorics and logic. This subclass of LP problems admits a strongly polynomial time algorithm, where devising such an algorithm for general LP problems is one of the major theoretical open questions in mathematical optimization and computer science. Recently, much attention has been paid to devising certifying algorithms in software engineering, since those algorithms enable one to confirm the correctness of outputs of programs with simple computations. Devising a combinatorial certifying algorithm for the feasibility for a fundamental class of Horn systems remains open for almost a decade. In this paper, we provide the first combinatorial (and strongly polynomial time) certifying algorithm for LP problems with gainfree Leontief substitution systems. As a by-product, we resolve the open question on the feasibility for the class of Horn systems.

We consider a matching problem in a hospitals/residents instance G, that is, a many-to-one matching instance, in which every vertex has a strict ranking of its neighbors and hospitals have capacities. A matching M is said to be popular if M does not lose an election against any matching in which vertices cast votes for one matching versus another. There are efficient algorithms to find popular matchings in G, but it is NP-hard to find a min-cost popular matching when edges have costs. When preferences are complete, there is a polynomial-time algorithm for this problem in the one-to-one setting. Interestingly, the set of popular matchings in a many-to-one instance can be richer than the set of popular matchings in the corresponding one-to-one instance obtained by cloning vertices. No polynomial-time algorithm is currently known for the min-cost popular matching problem with complete preferences in the many-to-one setting. We show a polynomial-time algorithm for this problem. Our algorithm includes a subroutine for computing a min-cost popular perfect matching; this subroutine also works for instances with incomplete preferences. History: This manuscript was accepted for the Special Issue on Market Design. Funding: T. Kavitha was supported by the Department of Atomic Energy, Government of India [Grant RTI4001]. K. Makino was partially supported by JSPS KAKENHI [Grant JP20H05967] and the joint project of Kyoto University and Toyota Motor Corporation titled “Advanced Mathematical Science for Mobility Society.”

The airport problem is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This article extends it to a more general setting involving multiple facilities. Specifically, in our model, each agent selects a facility and shares the cost with the other agents using the same facility. This scenario frequently occurs in sharing economies, such as sharing subscription costs for a multi-user license or taxi fares among customers traveling to potentially different destinations along a route. Our model can be viewed as a coalition formation game with size constraints, based on the fair cost-sharing of the airport problem. We refer to our model as a fair ride allocation on a line . We incorporate Nash stability and envy-freeness as criteria for solution concepts in our setting. We show that if a feasible allocation exists, a Nash stable feasible allocation that minimizes the social cost of agents exists and can be computed efficiently. Regarding envy-freeness, we provide several structural properties of envy-free allocations. Based on these properties, we design efficient algorithms for finding an envy-free allocation when either (1) the number of facilities, (2) the number of agent types, or (3) the capacity of facilities, is small. Moreover, we show that a consecutive envy-free allocation can be computed in polynomial time. On the negative front, we show NP-completeness of determining the existence of an allocation under two relaxed envy-free concepts.

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.

In this chapter, we focus on combinatorial optimization problems related to mobility societies. We briefly explain the main existing approaches for solving basic optimization problems and the advanced frameworks that capture realistic problems: online optimization and mechanism design. In relation to these topics, we introduce our results obtained from a joint project between Kyoto University and Toyota Motor Corporation.