Successful Manipulation in Stable Marriage Model with Complete Preference Lists
スポンサーリンク
概要
- 論文の詳細を見る
This paper deals with a strategic issue in the stable marriage model with complete preference lists (i.e., a preference list of an agent is a permutation of all the members of the opposite sex). Given complete preference lists of n men over n women, and a marriage µ, we consider the problem for finding preference lists of n women over n men such that the men-proposing deferred acceptance algorithm (Gale-Shapley algorithm) adopted to the lists produces µ. We show a simple necessary and sufficient condition for the existence of a set of preference lists of women over men. Our condition directly gives an O(n2) time algorithm for finding a set of preference lists, if it exists.
- （社）電子情報通信学会の論文
- 2009-02-01
著者
-
Matsui Tomomi
University of Tokyo
-
Matsui Tomomi
Faculty Of Science And Engineering Chuo University
-
KOBAYASHI Hirotatsu
Faculty of Science and Engineering, Chuo University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
-
Matsui Tomomi
Univ. Of Tokyo
-
Matsui Tomomi
The Authors Are With The Department Of Mathematical Informatics Graduate School Of Information Scien
-
Kobayashi Hirotatsu
Faculty Of Science And Engineering Chuo University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
関連論文
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- Successful Manipulation in Stable Marriage Model with Complete Preference Lists
- 2-C-14 Cheating Strategies for Gale-Shapley Algorithm with Complete Preference Lists
- A note on Asymmetric Power Index for Voting Games
- A note on mixed level supersaturated designs
- Approximate Counting Scheme for m×n Contingency Tables(Foundations of Computer Science)
- Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling(Discrete Mathematics and Its Applications)
- Home-Away Table Feasibility Problem
- Notes on Equitable Round-Robin Tournaments(Special Section on Discrete Mathematics and Its Applications)
- Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
- A Linear Relaxation for Hub Network Design Problems(Special Section on Discrete Mathematics and Its Applications)
- Linear Relaxation for Hub Network Design Problems
- DS-1-8 Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network
- 0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Note on Equitable Round-Robin Tournaments
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)