\title{\NP-completeness for Calculating Power Indices \\
    of Weighted Majority Games}
% 
\author{Yasuko Matsui
        \thanks{
  Department of Mathematics,
  Faculty of Science, Tokyo Metropolitan University,
  Minami-Ohsawa, Hachioji, Tokyo 192-03, Japan.
  {\tt yasuko@math.metro-u.ac.jp}}
  \  \and Tomomi Matsui
        \thanks{
  Department of Mathematical Engineering and Information Physics,
  Faculty of Engineering, University of Tokyo,
  Bunkyo-ku, Tokyo 113, Japan.
  {\tt tomomi@misojiro.t.u-tokyo.ac.jp}}
        }
\date{METR 98-01; January 1998}


\begin{abstract}
In this paper, we prove that
  both problems for calculating 
  the Banzhaf power index and 
  the Shapley-Shubik power index 
  for weighted majority games are \NP-complete.
\end{abstract}

\begin{keywords}
weighted majority game, 
 Banzhaf power index, Shapley-Shubik power index, \NP-complete,
 knapsack problem
\end{keywords}