論文 - 田村　明久

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月

研究論文（国際会議プロシーディングス）, 共著, 査読有り,  ISSN  21595399

　概要を見る

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年

研究論文（国際会議プロシーディングス）, 共著, 査読有り,  ISSN  15488403

　概要を見る

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年

研究論文（国際会議プロシーディングス）, 共著, 査読有り

　概要を見る

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

研究論文（国際会議プロシーディングス）, 共著, 査読有り

• 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年

研究論文（国際会議プロシーディングス）, 共著, 査読有り

• 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年

研究論文（国際会議プロシーディングス）, 共著, 査読有り

• Access to Document (DOI)