リーグ戦における優勝可能性判定問題
藤重研究室　　桂　将太

1.序論

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

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が存在しない時，
かつその時に限り，優勝の可能性がある．

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

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

4.結論

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