93 citations · 202 across the 25 of their papers we have counts for
29 papers
Towards Optimal Subsidy Bounds for Envy-freeable Allocations
Yasushi Kawase, Kazuhisa Makino, Hanna Sumita +2
We study the fair division of indivisible items with subsidies among agents, where the absolute marginal valuation of each item is at most one. Under monotone valuations (where…
Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods
Yasushi Kawase, Koichi Nishimura, Hanna Sumita
The fair allocation of mixed goods, consisting of both divisible and indivisible goods, has been a prominent topic of study in economics and computer science. We define an allocati…
Size-stochastic Knapsack Online Contention Resolution Schemes
Toru Yoshinaga, Yasushi Kawase
Online contention resolution schemes (OCRSs) are effective rounding techniques for online stochastic combinatorial optimization problems. These schemes randomly and sequentially ro…
Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
Yasushi Kawase, Atsushi Miyauchi, Hanna Sumita
Network analysis has played a key role in knowledge discovery and data mining. In many real-world applications in recent years, we are interested in mining multilayer networks, whe…
Optimal design of lottery with cumulative prospect theory
Shunta Akiyama, Mitsuaki Obara, Yasushi Kawase
Lotteries are a prevalent form of gambling between a seller and buyers. Designing a lottery requires a model of how buyers make decisions when confronted with uncertain outcomes. C…
Random Assignment of Indivisible Goods under Constraints
Yasushi Kawase, Hanna Sumita, Yu Yokoi
We investigate the problem of random assignment of indivisible goods, in which each agent has an ordinal preference and a constraint. Our goal is to characterize the conditions und…
Fair Division with Two-Sided Preferences
Ayumi Igarashi, Yasushi Kawase, Warut Suksompong +1
We study a fair division setting in which participants are to be fairly distributed among teams, where not only do the teams have preferences over the participants as in the canoni…
Online Max-min Fair Allocation
Yasushi Kawase, Hanna Sumita
We study an online version of the max-min fair allocation problem for indivisible items. In this problem, items arrive one by one, and each item must be allocated irrevocably on ar…
Fair and Truthful Mechanism with Limited Subsidy
Hiromichi Goko, Ayumi Igarashi, Yasushi Kawase +5
The notion of \emph{envy-freeness} is a natural and intuitive fairness requirement in resource allocation. With indivisible goods, such fair allocations are unfortunately not guara…
Fair Ride Allocation on a Line
Yuki Amano, Ayumi Igarashi, Yasushi Kawase +2
The airport game is a classical and well-known model of fair cost-sharing for a single facility among multiple agents. This paper extends it to the so-called assignment setting, th…
Online Knapsack Problems with a Resource Buffer
Xin Han, Yasushi Kawase, Kazuhisa Makino +1
In this paper, we introduce online knapsack problems with a resource buffer. In the problems, we are given a knapsack with capacity , a buffer with capacity , and items…
Approximately Stable Matchings with General Constraints
Yasushi Kawase, Atsushi Iwasaki
This paper focuses on two-sided matching where one side (a hospital or firm) is matched to the other side (a doctor or worker) so as to maximize a cardinal objective under general…
Non-zero-sum Stackelberg Budget Allocation Game for Computational Advertising
Daisuke Hatano, Yuko Kuroki, Yasushi Kawase +3
Computational advertising has been studied to design efficient marketing strategies that maximize the number of acquired customers. In an increased competitive market, however, a m…
Graph Mining Meets Crowdsourcing: Extracting Experts for Answer Aggregation
Yasushi Kawase, Yuko Kuroki, Atsushi Miyauchi
Aggregating responses from crowd workers is a fundamental task in the process of crowdsourcing. In cases where a few experts are overwhelmed by a large number of non-experts, most…
Tight Approximation for Unconstrained XOS Maximization
Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi +1
A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define…
Finding a Path with Two Labels Forbidden in Group-Labeled Graphs
Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi
The parity of the length of paths and cycles is a classical and well-studied topic in graph theory and theoretical computer science. The parity constraints can be extended to label…
Randomized Strategies for Robust Combinatorial Optimization
Yasushi Kawase, Hanna Sumita
In this paper, we study the following robust optimization problem. Given an independence system and candidate objective functions, we choose an independent set, and then an adversa…
Subgame Perfect Equilibria of Sequential Matching Games
Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi
We study a decentralized matching market in which firms sequentially make offers to potential workers. For each offer, the worker can choose "accept" or "reject," but the decision…
Submodular maximization with uncertain knapsack capacity
Yasushi Kawase, Hanna Sumita, Takuro Fukunaga
We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the problem is discussed in the situation that the knaps…
Approximately Stable Matchings with Budget Constraints
Yasushi Kawase, Atsushi Iwasaki
This paper considers two-sided matching with budget constraints where one side (firm or hospital) can make monetary transfers (offer wages) to the other (worker or doctor). In a st…
Optimal Matroid Partitioning Problems
Yasushi Kawase, Kei Kimura, Kazuhisa Makino +1
This paper studies optimal matroid partitioning problems for various objective functions. In the problem, we are given a finite set and weighted matroids $(E, \mathcal{I}_i…
Stochastic Input Models in Online Computing
Yasushi Kawase
In this paper, we study twelve stochastic input models for online problems and reveal the relationships among the competitive ratios for the models. The competitive ratio is define…
Near-Feasible Stable Matchings with Budget Constraints
Yasushi Kawase, Atsushi Iwasaki
We consider the matching with contracts framework of Hatfield and Milgrom when one side (a firm or hospital) can make monetary transfers (offer wages) to the other (a worker or doc…
Antimatroids Induced by Matchings
Yasushi Kawase, Yutaro Yamaguchi
We explore novel connections between antimatroids and matchings in bipartite graphs. In particular, we prove that a combinatorial structure induced by stable matchings or maximum-w…