4 papers
On the Equivalence of the Graph-Structural and Optimization-Based Characterizations of Popular Matchings
Yuga Kanaya, Kenjiro Takazawa
Popular matchings provide a model of matching under preferences in which a solution corresponds to a Condorcet winner in voting systems. In a bipartite graph in which the vertices…
M-convexity of the minimum-cost packings of arborescences
Kenjiro Takazawa
The aim of this paper is to reveal the discrete convexity of the minimum-cost packings of arborescences and branchings. We first prove that the minimum-cost packings of disjoint $k…
A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
Kenjiro Takazawa
The study of equilibrium concepts in congestion games and two-sided markets with ties has been a primary topic in game theory, economics, and computer science. Ackermann, Goldberg,…
Popular Maximum-Utility Matchings with Matroid Constraints
Gergely Csáji, Tamás Király, Kenjiro Takazawa +1
We investigate weighted settings of popular matching problems with matroid constraints. The concept of popularity was originally defined for matchings in bipartite graphs, where ve…