Day 102-Q5 | Auction Algorithm（オークションアルゴリズム）

問題

$N$人の作業員と$N$個の仕事がある。作業員$i$が仕事$j$を担当したときの価値は$v_{i,j}$で与えられる。各作業員がちょうど1つの仕事を、各仕事がちょうど1人の作業員に割り当てられるようにするとき、価値の総和の最大値を求めよ。

ハンガリアン法（$O(N^3)$）が定番だが、ここでは経済学的発想のAuction Algorithm（Bertsekasのオークションアルゴリズム）を扱う。各仕事に「価格」を設定し、各作業員が「価値−価格」最大の仕事に対して2番目との差額+$\varepsilon$だけ価格を吊り上げて入札する。整数問題では$\varepsilon$を段階的に縮小する$\varepsilon$-scalingにより厳密最適解に収束する。

入力形式

N
v_{1,1} v_{1,2} ... v_{1,N}
:
v_{N,1} v_{N,2} ... v_{N,N}

制約

$1 \le N \le 8$

$1 \le v_{i,j} \le 10^4$

すべて整数

入出力例

入力例1

出力例1

作業員1→仕事1(3)、作業員2→仕事2(4)、作業員3→仕事3(3)で合計10が最大。

入力例2

2
5 1
1 5

出力例2

対角割当（1→1, 2→2）で5+5=10。交差割当は1+1=2で明らかに劣る。

概念図

ヒント（段階的開示）

ヒント1: 方向性

「全員が同時に最も欲しい仕事に応札し、価格をせり上げていく」という市場メカニズムをそのままシミュレーションする、という発想がスタート地点。ハンガリアン法のような「増加路を明示的に探す」手法とは全く異なるアプローチで、局所的な入札のやり取りだけで大域最適に収束する点が面白い。

ヒント2: アプローチ

未割当の作業員$i$がいる限り、(1)$i$にとって「価値−現在の価格」が最大になる仕事$j^*$と2番目の値$w$を求める。(2)$j^*$の価格を「現在の価格+（最良の差−2番目の差）+$\varepsilon$」まで引き上げる。(3)$j^*$に以前割り当てられていた作業員がいればその人を未割当に戻し、$i$を$j^*$に割り当てる。整数値に厳密に収束させるには、価値を$(N+1)$倍にスケーリングしてから$\varepsilon$を段階的に縮小する「$\varepsilon$-scaling」を行う。

ヒント3: 誘導（コード骨格）

scale = N + 1
v = [[value[i][j] * scale for j in range(N)] for i in range(N)]
price = [0] * N
eps = max(max(row) for row in v)

while eps >= 1:
    owner = [-1] * N
    assigned_to = [-1] * N
    unassigned = list(range(N))
    while unassigned:
        i = unassigned.pop()
        best_val = second_val = -float('inf')
        best_j = -1
        for j in range(N):
            val = v[i][j] - price[j]
            if val > best_val:
                best_val, second_val, best_j = val, best_val, j
            elif val > second_val:
                second_val = val
        bid = price[best_j] + (best_val - second_val) + eps
        price[best_j] = bid
        if owner[best_j] != -1:
            unassigned.append(owner[best_j])
        owner[best_j] = i
        assigned_to[i] = best_j
    eps //= 4

total = sum(value[i][assigned_to[i]] for i in range(N))

各$\varepsilon$の段階で割当をリセットして再度オークションを行う「$\varepsilon$-scaling」の実装が要点。

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    value = []
    for _ in range(N):
        row = [int(data[idx + j]) for j in range(N)]
        idx += N
        value.append(row)

    scale = N + 1
    v = [[value[i][j] * scale for j in range(N)] for i in range(N)]

    price = [0] * N
    assigned_to = [-1] * N

    eps = max(max(row) for row in v) if N > 0 else 1
    if eps == 0:
        eps = 1

    while eps >= 1:
        owner = [-1] * N
        assigned_to = [-1] * N
        unassigned = list(range(N))

        while unassigned:
            i = unassigned.pop()
            best_val = -float('inf')
            second_val = -float('inf')
            best_j = -1
            for j in range(N):
                val = v[i][j] - price[j]
                if val > best_val:
                    second_val = best_val
                    best_val = val
                    best_j = j
                elif val > second_val:
                    second_val = val
            if second_val == -float('inf'):
                second_val = best_val

            bid = price[best_j] + (best_val - second_val) + eps
            price[best_j] = bid

            prev_owner = owner[best_j]
            if prev_owner != -1:
                assigned_to[prev_owner] = -1
                unassigned.append(prev_owner)
            owner[best_j] = i
            assigned_to[i] = best_j

        eps //= 4

    total = sum(value[i][assigned_to[i]] for i in range(N))
    print(total)


solve()

計算量: $O(N^2 \log(N \cdot V_{\max}))$ 程度（$\varepsilon$-scalingの段階数×各段階での入札処理）。

Step-by-Step 解説

1整数スケーリング
価値を$(N+1)$倍にしておくことで、$\varepsilon<1$に到達したときの割当が厳密最適であることが保証される（$\varepsilon$-complementary slacknessの理論）。

2最良・2番目良い仕事を探す
「価値−価格」が最大の仕事とその次に良い値の差が、入札の上乗せ額の核心部分になる。

3価格の吊り上げと割当の入れ替え
入札額だけ価格を上げ、既存の担当者がいれば未割当に戻して再入札させる。

4$\varepsilon$-scalingで段階的に精度を上げる
$\varepsilon$を4分の1ずつ縮小しながらオークションをやり直し、$\varepsilon<1$になった時点の割当が厳密最適。

よくあるミス

ミス	原因	正しい書き方
スケーリングをせず$\varepsilon$-scalingを行う	$\varepsilon$が整数のまま1未満になれず理論的保証が成立しない	価値をあらかじめ$(N+1)$倍しておく
「2番目に良い値」の初期化を忘れる	仕事が1つしかない場合など2番目の候補が存在しない	`second_val`未更新時は`best_val`と同値にするフォールバックを入れる
$\varepsilon$を一気に0にする	途中で最適でない割当のまま終了し局所最適に収束する	徐々に（例えば4分の1ずつ）縮小するscalingを行う
出力を「割当そのもの」にしてしまう	タイがある場合、実装依存でジャッジと一致しない可能性がある	本問では「価値の総和」のみを出力すればよい

次のステップ

発展: 非正方（作業員数≠仕事数）の場合への拡張（ダミー仕事/作業員を追加して正方化する）
発展: 分散システムでの並列実装（各買い手が独立に入札するAuction Algorithmは並列化しやすく、実際にネットワークルーティングや経済学のモデルにも応用される）
次回予告: （Master Levelローテーション継続、次回の出題テーマは実行時に選定）

自己評価

完全理解おおむね理解要復習

Day 102-Q5 — Auction Algorithm（オークションアルゴリズム）

問題