Papers - Tamura, Akihisa

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

Murota, K. and Tamura, A.

Japan Journa of Industirial and Applied Mathematics 42 ( 5 ) 2037 - 2056 2025.06

Research paper (scientific journal), Joint Work, Accepted,  ISSN  09167005

　View Summary

This paper gives two different proofs to a structural theorem of decreasing minimization (lexicographic optimization) on integrally convex sets. The theorem states that the set of decreasingly minimal elements of an integrally convex set can be represented as the intersection of a unit discrete cube and a face of the convex hull of the given integrally convex set. The first proof resorts to the Fenchel-type duality theorem in discrete convex analysis and the second is more elementary using Farkas’ lemma.

• Access to Document (DOI)

Shapley–Folkman-type theorem for integrally convex sets

Murota, K. and Tamura, A.

Discrete Applied Mathematics 360   42 - 50 2025

Research paper (scientific journal), Joint Work, Accepted,  ISSN  0166218X

　View Summary

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)

Towards optimal subsidy bounds for envy-freeable allocations

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

Artificial Intelligence  2025

Research paper (scientific journal), Joint Work, Accepted

Note on Minkowski Summation and Unimodularity in Discrete Convex Analysis

Murota, K. and Tamura, A.

Journal of the Operations Research Society of Japan (The Operations Research Society of Japan)  67 ( 4 ) 126 - 134 2024.10

Research paper (scientific journal), Joint Work, Accepted,  ISSN  04534514

　View Summary

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. and Tamura, A.

Japan Journa of Industirial and Applied Mathematics 41 ( 2 ) 987 - 1011 2024.05

Research paper (scientific journal), Joint Work, Accepted,  ISSN  09167005

　View Summary

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

Research paper (scientific journal), Joint Work, Accepted,  ISSN  08998256

　View Summary

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

Research paper (scientific journal), Joint Work, Accepted,  ISSN  00043702

　View Summary

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 (Springer Science and Business Media {LLC})  39 ( 2 ) 599 - 630 2022

Research paper (scientific journal), Joint Work, Corresponding author, Accepted,  ISSN  09167005

　View Summary

Discrete Fenchel duality is one of the central issues in discrete convex analysis. The Fenchel-type min–max theorem for a pair of integer-valued M^♮-convex functions generalizes the min–max formulas for polymatroid intersection and valuated matroid intersection. In this paper we establish a Fenchel-type min–max formula for a pair of integer-valued integrally convex and separable convex functions. Integrally convex functions constitute a fundamental function class in discrete convex analysis, including both M^♮-convex functions and L^♮-convex functions, whereas separable convex functions are characterized as those functions which are both M^♮-convex and L^♮-convex. The theorem is proved by revealing a kind of box integrality of subgradients of an integer-valued integrally convex function. The proof is based on the Fourier–Motzkin elimination.

• Access to Document (DOI)

Directed discrete midpoint convexity

Tamura, A. and Tsurumi, K.

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

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Discrete midpoint convexity

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

Mathematics of Operations Research 45   99 - 128 2020

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Integrality of subgradients and biconjugates of integrally convex functions

Murota, K. and Tamura, A.

Optimization Letters 14   195 - 208 2020

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted,  ISSN  00255610

　View Summary

© 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

Research paper (scientific journal), Joint Work, Accepted,  ISSN  00220531

　View Summary

© 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)

The Students/Departments Allocation Problem with Group Constraints - An Application of Discrete Convex Analysis (in Japanese)

Akahori, T., Sekiguchi, Y. and Tamura, A.

Transactions of the Operations Research Society of Japan 60   50 - 73 2017.08

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Construction of Hamilton path tournament designs

Ikebe, Y.T. and Tamura, A.

Graphs and Combinatorics 27   703 - 711 2011

Research paper (scientific journal), Joint Work, Accepted

• 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

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

On the existence of sports schedules with multiple venues

Ikebe, Y.T. and Tamura, A.

Discrete Applied Mathematics 156   1694 - 1710 2008

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

A two-sided discrete-concave market with possibly bounded side payments: An approach by discrete convex analysis

Fujishige, S. and Tamura, A.

Mathematics of Operations Research 32 ( 1 ) 136 - 155 2007

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

A general two-sided matching market with discrete concave utility functions

Fujishige, S. and Tamura, A.

Discrete Applied Mathematics 154   950 - 970 2006

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

A semidefinite programming relaxation for the generalized stable set problem

Fujie, T. and Tamura, A.

IEICE Transactions on Fundamentals E88-A ( 5 ) 1122 - 1128 2005.05

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Coordinatewise domain scaling algorithm for M-convex function minimization

Tamura, A.

Mathematical Programming 102 ( 2 ) 339 - 354 2005.03

Research paper (scientific journal), Single Work, Lead author, Corresponding author, Accepted

• Access to Document (DOI)

Discrete fixed point theorem reconsidered

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

Journal of Mathematical Economics 41 ( 8 ) 1030 - 1036 2005

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Proximity theorems of discrete convex functions

Murota, K. and Tamura, A.

Mathematical Programming 99 ( 3 ) 539 - 562 2004

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

A new characterization of M#-convex set functions by substitutability

Farooq, R. and Tamura, A.

Journal of the Operations Research Society of Japan 47 ( 1 ) 18 - 24 2003

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

On convolution of L-convex functions

Tamura, A.

Optimization Methods and Software 18 ( 2 ) 231 - 245 2003

Research paper (scientific journal), Single Work, Accepted

• Access to Document (DOI)

Polyhedral proof of a characterization of perfect bidirected graphs

Ikebe, Y. T. and Tamura, A.

IEICE Transactions on Fundamentals E86-A ( 5 ) 1000 - 1007 2003

Research paper (scientific journal), Joint Work, Accepted

New characterizations of M-convex functions and their applications to economic equilibrium models

Murota, K. and Tamura, A.

Discrete Applied Mathematics 131 ( 2 ) 495 - 512 2003

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Application of M-convex submodular flow problem to mathematical economics

Murota, K. and Tamura, A.

Japan Journal of Industrial and Applied Mathematics 20 ( 3 ) 257 - 277 2003

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

On Gr\"otschel-Lov'asz-Schrijver's relaxation of stable set polytopes

Fujie, T. and Tamura, A.

Journal of the Operations Research Society of Japan 45 ( 3 ) 285 - 292 2002

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

A revision of Minty's algorithm for finding a maximum weight stable set of a claw-free graph

Nakamura, D. and Tamura, A.

Journal of the Operations Research Society of Japan 44 ( 2 ) 194 - 204 2001

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

On circuit valuation of matroids

Murota, K. and Tamura, A.

Advances in Applied Mathematics 26 ( 3 ) 192 - 225 2001

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Perfect (0,+/-1)-matrices and perfect bidirected graphs

Tamura, A.

Theoretical Computer Science 235 ( 2 ) 339 - 356 2000

Research paper (scientific journal), Single Work, Accepted

• Access to Document (DOI)

A linear time algorithm for the generalized stable set problem on triangulated bidirected graphs

Nakamura, D. and Tamura, A.

Journal of the Operations Research Society of Japan 43 ( 1 ) 162 - 175 2000

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

EP theorems and linear complementarity problems

Fukuda, K., Namiki, M. and Tamura, A.

Discrete Applied Mathematics 84 ( 1-3 ) 107 - 119 1998

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

An optimal algorithm for scanning all spanning trees of undirected graphs

Shioura, A., Tamura, A. and Uno, T.

SIAM Journal on Computing 26 ( 3 ) 678 - 692 1997

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

The generalized stable set problem for perfect bidirected graphs

Tamura, A.

Journal of the Operations Research Society of Japan 40 ( 3 ) 401 - 414 1997

Research paper (scientific journal), Single Work, Accepted

• Access to Document (DOI)

Efficiently scanning all spanning trees of an undirected graph,

Shioura, A. and Tamura, A.

Journal of the Operations Research Society of Japan 38 ( 3 ) 331 - 344 1995.09

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Ideal polytopes and face structures of some combinatorial optimization problems

Ikebe, Y.T. and Tamura, A.

Mathematical Programming 71 ( 1 ) 1 - 15 1995

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

An efficient algorithm for finding the minimum norm point in the convex hull of a finite point set in the plane

Makimoto, N., Nakagawa, I. and Tamura, A.

Operations Research Letters 16 ( 1 ) 33 - 40 1994

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

The rooted tree embedding problem into points in the plane

Ikebe, Y., Perles, M.A., Tamura, A. and Tokunaga, S.

Discrete and Computational Geometry 11 ( 1 ) 51 - 63 1994

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Algorithms for finding a kth best valued assignment

Matsui, T., Tamura, A. and Ikebe, Y.

Discrete Applied Mathematics 50 ( 3 ) 283 - 296 1994

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Adjacency of the best and second best valued solutions in combinatorial optimization problems

Ikebe, Y., Matsui, T. and Tamura, A.

Discrete Applied Mathematics 47 ( 3 ) 227 - 232 1993

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Transformation from arbitrary matchings to stable matchings

Tamura, A.

Journal of Combinatorial Theory, Series A 62 ( 2 ) 310 - 323 1993

Research paper (scientific journal), Single Work, Accepted

• Access to Document (DOI)

A recursive algorithm for a class of convex min-max problems

Sekitani, K., Tamura, A. and Yamamoto, Y.

Asia-Pacific Journal of Operational Research 10 ( 1 ) 93 - 108 1993

Research paper (scientific journal), Joint Work, Accepted

A theorem on the average number of subfaces in arrangements and oriented matroids

Fukuda, K., Tamura, A. and Tokuyama, T.

Geometriae Dedicata 47 ( 2 ) 129 - 142 1993

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Degree constrained embedding into points in the plane

Tamura, A. and Tamura, Y

Information Processing Letters 44 ( 4 ) 211 - 214 1992

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Bounding the number of k-faces in arrangements of hyperplanes

Fukuda, K., Saito, S., Tamura, A. and Tokuyama, T.

Discrete Applied Mathematics 31 ( 2 ) 151 - 165 1991

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Combinatorial face enumeration in arrangements and oriented matroids

Fukuda, K., Saito, S. and Tamura, A.

Discrete Applied Mathematics 31 ( 2 ) 141 - 149 1991

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Dualities in signed vector systems

Fukuda, K. and Tamura, A.

Portugaliae Mathematica 47 ( 2 ) 151 - 165 1990

Research paper (scientific journal), Joint Work, Accepted

Characterizations of *-families

Fukuda, K. and Tamura, A.

Journal of Combinatorial Theory, Series B 47 ( 1 ) 107 - 110 1989

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

A dual interior primal simplex method for linear programming

Tamura, A., Takehara, H., Fukuda, K., Fujishige, S. and Kojima, M.

Journal of the Operations Research Society of Japan 31 ( 3 ) 413 - 429 1988

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Local deformation and orientation transformation in oriented matroids

Fukuda, K. and Tamura, A.

ARS Combinatoria 25 ( A ) 243 - 258 1988

Research paper (scientific journal), Joint Work, Accepted

Recent progress on integrally convex functions

Murota, K. and Tamura, A.

Japan Journa of Industirial and Applied Mathematics (Japan Journal of Industrial and Applied Mathematics)  40 ( 3 ) 1445 - 1499 2023

Research paper (scientific journal), Joint Work, Accepted,  ISSN  09167005

　View Summary

Integrally convex functions constitute a fundamental function class in discrete convex analysis, including M-convex functions, L-convex functions, and many others. This paper aims at a rather comprehensive survey of recent results on integrally convex functions with some new technical results. Topics covered in this paper include characterizations of integral convex sets and functions, operations on integral convex sets and functions, optimality criteria for minimization with a proximity-scaling algorithm, integral biconjugacy, and the discrete Fenchel duality. While the theory of M-convex and L-convex functions has been built upon fundamental results on matroids and submodular functions, developing the theory of integrally convex functions requires more general and basic tools such as the Fourier–Motzkin elimination.

• Access to Document (DOI)

Gross Substitutes Condition and Discrete Concavity for Multi-Unit Valuations: A Survey

Shioura, A. and Tamura, A.

Journal of the Operations Research Society of Japan 58 ( 1 ) 61 - 103 2015.03

Research paper (scientific journal), Joint Work, Accepted

• Access to Document (DOI)

Applications of discrete convex analysis to mathematical economics

Tamura, A.

Publications of RIMS, Kyoto University 40 ( 3 ) 1015 - 1037 2004

Research paper (scientific journal), Single Work, Accepted

• Access to Document (DOI)

The linear complementarity problem on oriented matroids

Tamura, A.

IEICE Transactions on Information and Systems E83-D ( 3 ) 353 - 361 2000

Research paper (scientific journal), Single Work, Accepted

Towards Optimal Subsidy Bounds for Envy-Freeable Allocations

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

Proceedings of the AAAI Conference on Artificial Intelligence (Proceedings of the AAAI Conference on Artificial Intelligence)  38 ( 9 ) 9824 - 9831 2024.03

Research paper (international conference proceedings), Joint Work, Accepted,  ISSN  21595399

　View Summary

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)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, we present further improved bounds for monotone valuations.

• Access to Document (DOI)

Fair and Truthful Mechanism with Limited Subsidy

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

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS)  1   534 - 542 2022

Research paper (international conference proceedings), Joint Work, Accepted,  ISSN  15488403

　View Summary

The notion of envy-freeness is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guaranteed to exist. Classical works have avoided this issue by introducing an additional divisible resource, i.e., money, to subsidize envious agents. In this paper, we aim to design a truthful allocation mechanism of indivisible goods to achieve both 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. For superadditive valuations, we show that there is a truthful mechanism that achieves envy-freeness and utilitarian optimality, with each agent receiving a subsidy of at most m; furthermore, we show that the amount m is necessary even when agents have additive valuations.

Efficient allocation mechanism with endowments and distributional constraints

Suzuki T., Tamura, A. and Yokoo M.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS)  1   50 - 67 2018

Research paper (international conference proceedings), Joint Work, Accepted

　View Summary

© 2018 International Foundation for Autonomous Agents and Multiagent Systems. We consider an allocation problem of multiple types objects to agents, where each type of an object has multiple copies (e.g., mult iple seats of 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 a mechanism that is based on the Top Trading Cycles mechanism, which Is strategy-proof, feasible (always satisfies distributional constraints). Pareto efficient, and individually rational, assuming the distributional constraints are represented as an M-convex set. The class of distributional cons traints we consider contains many situations raised from realistic matching problems, including individual minimum/maximum quot as, regional maximum quotas, type-specific quotas, and distance constraints. To the best of our knowledge, we are the first to develop a mechanism with these desirable properties.

A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model

Eguchi, A., Fujishige, S. and Tamura, A.

Algorithms and Computation, Lecture Notes in Computer Science 2906, Springer    495 - 504 2003

Research paper (international conference proceedings), Joint Work, Accepted

• Access to Document (DOI)

The generalized stable set problem for claw-free bidirected graphs

Nakamura, D. and Tamura, A.

Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 1412, Springer    69 - 83 1998

Research paper (international conference proceedings), Joint Work, Accepted

• Access to Document (DOI)

On the greedy algorithm for stochastic optimization problems

Kijima, M. and Tamura, A.

Stochastic Modeling in Innovative Manufacturing, Lecture Notes in Economics and Mathematical Systems 445, Springer    19 - 29 1996

Research paper (international conference proceedings), Joint Work, Accepted

• Access to Document (DOI)