著者

YAMAMOTO Yoshitsugu ZHOU You

出版者

University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems & Management

巻号頁・発行日

2013-08

---

This paper is concerned about the aggregation function which plays a centralrole in the majority judgement that was recently proposed by Balinski and Laraki as anew voting mechanism. We raise two issues about their aggregation function, named orderfunction, and show that they are resolved by relaxing the strong monotonicity conditionimposed on the aggregation function, and that the anonymous, weakly monotonic andstrategy-proof aggregation function is completely determined by the set of final grades when the judges split deeply.

著者

IZUNAGA Yoichi YAMAMOTO Yoshitsugu

出版者

University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems & Management

巻号頁・発行日

2013-07

---

The modularity proposed by Newman and Girvan is the most commonly used measure when the nodes of a graph are grouped into communities consisting of tightly connectednodes. We formulate the modularity maximization problem as a set partitioning problem, and propose an algorithm for the problem based on the linear programming relaxation. We solve the dual of the linear programming relaxation by using a cutting plane method. To mediate the slow convergence that cutting plane methods usually suffer, we propose a method for finding and simultaneously adding multiple cutting planes which may complement well each other.

著者

IGARASHI Ayumi YAMAMOTO Yoshitsugu

出版者

University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems & Management

巻号頁・発行日

2012-11

---

In this paper we prove that calculating the average covering tree valuerecently proposed as a single-valued solution of graph games is #P-complete.

著者

Sukegawa Noriyoshi Yamamoto Yoshitsugu

出版者

Springer

雑誌

Japan journal of industrial and applied mathematics (ISSN:09167005)

巻号頁・発行日

vol.29, no.3, pp.547-560, 2012-10

被引用文献数

4

---

Concerning the strategic manipulability of the stable matching produced by the Gale–Shapley algorithm, Kobayashi and Matsui recently considered the existence problem of a preference profile of women, that is, given a preference profile of men, find a preference profile of women that makes the Gale–Shapley algorithm produce the prescribed complete matching of men and women. Reformulating this problem by introducing the set of proposals to be made through the execution of the algorithm, and switching the roles of men and women, we consider the existence problem of a preference profile of men and show that the problem is reduced to a problem of checking if a directed graph is a rooted tree and it is solvable in polynomial time. We also show that the existence problem of preference profiles of both sexes when a set of proposals is given is solvable in polynomial time.