論文 - 田村　明久

Two proofs of a structural theorem of decreasing minimization on integrally convex sets

Murota K., Tamura A.

Japan Journal of Industrial and Applied Mathematics 2025年06月

研究論文（学術雑誌）, 共著, 査読有り

Shapley–Folkman-type theorem for integrally convex sets

Murota K., Tamura A.

Discrete Applied Mathematics 360   42 - 50 2025年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  0166218X

　概要を見る

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.

• Access to Document (DOI)

Note on Minkowski Summation and Unimodularity in Discrete Convex Analysis

Murota K., Tamura A.

Journal of the Operations Research Society of Japan （The Operations Research Society of Japan）  67 （ 4 ） 126 - 134 2024年10月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  04534514

　概要を見る

This short note gives an elementary alternative proof for a theorem of Danilov and Koshevoy on Minkowski summation and unimodularity in discrete convex analysis. It is intended to disseminate this fundamental theorem and make its proof accessible to researchers in optimization and operations research.

• Access to Document (DOI)

Decomposition of an integrally convex set into a Minkowski sum of bounded and conic integrally convex sets

Murota K., Tamura A.

Japan Journal of Industrial and Applied Mathematics 41 （ 2 ） 987 - 1011 2024年05月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  09167005

　概要を見る

Every polyhedron can be decomposed into a Minkowski sum (or vector sum) of a bounded polyhedron and a polyhedral cone. This paper establishes similar statements for some classes of discrete sets in discrete convex analysis, such as integrally convex sets, L ♮ -convex sets, and M ♮ -convex sets.

• Access to Document (DOI)

A fair and truthful mechanism with limited subsidy

Goko H., Igarashi A., Kawase Y., Makino K., Sumita H., Tamura A., Yokoi Y., Yokoo M.

Games and Economic Behavior 144   49 - 70 2024年03月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  08998256

　概要を見る

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve fairness and efficiency criteria with a limited amount of subsidy. Following the work of Halpern and Shah, our central question is as follows: to what extent do we need to rely on the power of money to accomplish these objectives? We show that, when agents have matroidal valuations, there is a truthful allocation mechanism that achieves envy-freeness and utilitarian optimality by subsidizing each agent with at most 1, the maximum marginal contribution of each item for each agent. The design of the mechanism rests crucially on the underlying matroidal M-convexity of the Lorenz dominating allocations.

• Access to Document (DOI)

Strategyproof Allocation Mechanisms with Endowments and M-convex Distributional Constraints

Suzuki, T., Tamura, A., Yahiro, K., Yokoo, M., Zhang, Y.

Artificial Intelligence （Artificial Intelligence）  315 2023年02月

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  00043702

　概要を見る

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.

• Access to Document (DOI)

Discrete Fenchel duality for a pair of integrally convex and separable convex functions

Murota, K. and Tamura, A.

Japan Journa of Industirial and Applied Mathematics 39 （ 2 ） 599 - 630 2022年

研究論文（学術雑誌）, 共著, 責任著者, 査読有り

• Access to Document (DOI)

Directed discrete midpoint convexity

Tamura, A. and Tsurumi, K.

Japan Journal of Industrial and Applied Mathematics 38   1 - 37 2021年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Discrete midpoint convexity

Moriguchi, S., Murota, M., Tamura, A. and Tardella, F.

Mathematics of Operations Research 45   99 - 128 2020年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Integrality of subgradients and biconjugates of integrally convex functions

Murota, K. and Tamura, A.

Optimization Letters 14   195 - 208 2020年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Scaling, proximity, and optimization of integrally convex functions

Moriguchi, S., Murota, M., Tamura, A. and Tardella, F.

Mathematical Programming （Mathematical Programming）  175 （ 1 ） 119 - 154 2019年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  00255610

　概要を見る

© 2018, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. In discrete convex analysis, the scaling and proximity properties for the class of L ♮ -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≤ 2 , while a proximity theorem can be established for any n, but only with a superexponential bound. This is, however, sufficient to extend the classical logarithmic complexity result for minimizing a discrete convex function of one variable to the case of integrally convex functions of any fixed number of variables.

• Access to Document (DOI)

Designing matching mechanisms under constraints: An approach from discrete convex analysis

Kojima F., Tamura, A. and Yokoo, M.

Journal of Economic Theory 176   803 - 833 2018年

研究論文（学術雑誌）, 共著, 査読有り,  ISSN  00220531

　概要を見る

© 2018 Elsevier Inc. We consider two-sided matching problems where agents on one side of the market (hospitals) are required to satisfy certain distributional constraints. We show that when the preferences and constraints of the hospitals can be represented by an M♮-concave function, (i) the generalized Deferred Acceptance (DA) mechanism is strategyproof for doctors, (ii) it produces the doctor-optimal stable matching, and (iii) its time complexity is proportional to the square of the number of possible contracts. Furthermore, we provide sufficient conditions under which the generalized DA mechanism satisfies these desirable properties. These conditions are applicable to various existing works and enable new applications as well, thereby providing a recipe for developing desirable mechanisms in practice.

• Access to Document (DOI)

学生にグループ分けのある学科配属問題 --- 離散凸解析の適用例

赤堀峻, 関口陽介, 田村 明久

Transactions of the Operations Research Society of Japan 60   50 - 73 2017年08月

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Designing matching mechanisms under general distributional constraints

Goto, M., Kojima, F., Kurata, R., Tamura, A. and Yokoo, M.

American Economic Journal: Microeconomics 9 （ 2 ） 226 - 262 2017年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Stability in supply chain networks: An approach by discrete convex analysis

Ikebe, Y.T. and Tamura, A.

Journal of the Operations Research Society of Japan 58 （ 3 ） 271 - 290 2015年07月

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions

Ikebe, Y. T, Sekiguchi, Y., Shioura, A. and Tamura, A.

Japan Journal of Industrial and Applied Mathematics 32 （ 2 ） 373 - 410 2015年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Matching with partially ordered contracts

Farooq, R., Fleiner, T. and Tamura, A.

Japan Journal of Industrial and Applied Mathematics 29   401 - 417 2012年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Sperner's lemma and zero point theorems on a discrete simplex and a discrete simplotope

Iimura, T., Murota, K. and Tamura, A.

Discrete Applied Mathematics 160   588 - 592 2012年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

Construction of Hamilton path tournament designs

Ikebe, Y.T. and Tamura, A.

Graphs and Combinatorics 27   703 - 711 2011年

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)

On labor allocation model with possibly bounded salaries

Farooq, R., Ikebe, Y.T. and Tamura, A.

Journal of the Operations Research Society of Japan 51 （ 2 ） 136 - 154 2008年06月

研究論文（学術雑誌）, 共著, 査読有り

• Access to Document (DOI)