Papers - Tamura, Akihisa

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)