リーグ戦における優勝可能性判定問題

藤重研究室  桂 将太

1.序論

リーグ戦における現時点での勝敗の結果から,あるチームが優勝する可能性を判定する 問題を優勝可能性判定問題と言う.特に,引き分けの試合を考慮しない野球リー グに関する優勝可能性判定は,最大フローネットワークを用いたSchwartz に よる解法が有名である.最近,Wayne は,一度に複数のチームの優勝の可 能性を判定する,パラメトリック最大フローネットワークを用いた判定法を開発す ることによって,この問題の計算量を改善している.
本研究では,これらの判定法を出発点として,新たにサッカーリーグ(勝利: 勝 ち点3,引き分け: 勝ち点1)についての優勝可能性判定を試み,パラメトリッ ク最大フローネットワークを用いた判定法と,各チームの残り試合での勝敗に重 点をおいた一般化フローを用いた判定法を新たに考案した.

2.野球に関する優勝可能性判定問題

リーグ戦にnチームが参加しているものとし,全チームの集合をTとする. チームiは,これまでに,wi試合勝ち,チームjとの間にgij試合を残して いるものとする.残り試合数の合計をgiとする. チームkに関して優勝可能性判定を行う.チームkは残り試合全勝すると仮定 し,その結果W試合勝つとする. 部分集合Rに対して,Rの中で,各チームが既に勝った数の総数を,w(R)で表 し,更にRの中で行われる残り試合の組み合わせの総数を,g(R)で表すと,Rに おける最終平均勝ち数は,a(R) = {w(R)+g(R)}\|R|以上となる.

[定理1]チームkは,a(R) > wk + gkとなるRが存在しない時,
かつその時に限り,優勝の可能性がある.

定理1の条件は,ネットワーク中の最大フローを求めることで効率的 に判定できる.

3.サッカーに関する優勝可能性判定問題

3.1最大平均部分集合を用いた判定法
Rにおける最終平均勝ち点a(R)は以下の不等式を満たす.(ここでのWや w(R)は勝ち点を表す.)
{w(R) + 2g(R)}\|R| <= a(R) <= {w(R) + 3g(R)}\|R|
左辺をb(R)とし,以下の定理を導いた.

[定理2]あるRが存在し,b(R) > wk + 3gk となるとき,チームkは優勝すること が出来ない.

定理2の条件を満たすRは,もし存在するならば,Wayne の解法と同様にパラ メトリック最大フローを用いて,効率的に求めることができる.しかし,定 理2の逆は成立しない.
3.2残り試合の勝敗を考慮した判定法
フローネットワークを構築し(枝(s,{i,j})の容量は3gij),フローを勝ち点と 見立てる.1チームの勝ち点の獲得は1試合当り3,1,0に限られ,各試合にお いて,結果によっては,両チームの勝ち点の和は保存されない.したがって, 流量の保存則は成立しない.そこで,この条件に基づく制約を課し,それに沿 ってフローを流す一般化フロー問題を解き,各チームについての判定を行う.

4.結論

サッカーに関する優勝可能性判定問題について,最初の方法は,b(R) > wk + 3gk の条件を満たすチームしか排除出来ないの で,全ての排除されるチームを見つけることは未解決である(定理2の逆が成立し ないため,全てのRについてb(R) >= wk + 3gk を満たすkが存在しても チームkは排除される可能性がある).第二の方法は,全てのチームについて ,判定を行えるが,場当たり的で,一つのチームに要する計算量が多く非効率的で 改善が望まれる.