coopgame 0.3.1

Compute and verify the nucleolus, prenucleolus, kernel, and prekernel of TU cooperative games
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
//! 逐次 LP (Kopelowitz 方式) による仁・プレ仁・最小コアの計算。
//!
//! 第 k 段では、超過がまだ確定していない提携の最大超過 `t` を最小化する:
//!
//! ```text
//! min t  s.t.  v(S) - x(S) <= t   (未確定の S)
//!              x(S) = c_S         (確定済みの S。N を含む)
//!              x_i >= v({i})      (仁の場合のみ)
//! ```
//!
//! 最適値 `t*` を達成する提携のうち、最適解集合全体で超過が `t*` に固定されるものを
//! 「確定」させる。確定判定は、最適解集合の上で `x(S)` を最大化する LP で行う。
//! 確定した提携の特性ベクトルが張る空間が `R^n` 全体になった時点で配分は一意に決まる。
//! 各段で次元が 1 以上増えるため、段数は高々 `n - 1`。
//!
//! LP は絶対誤差で判定するので、値の大きさによらず同じ精度で解けるよう、ゲームの値を 2 のべき乗で割って
//! 最大絶対値を `[1, 2)` にそろえてから解き、結果を元の大きさに戻す (許容誤差も同じ倍率で割る)。
//! 倍率が 2 のべき乗なら、`c` 倍したゲームの結果はちょうど `c` 倍になる。
//!
//! [`Method::ConstraintGeneration`] (既定) では、`2^n` 個の不等式を最初から全て入れず、
//! 解が違反する提携だけを行として追加し、前回の解から解き直す(制約生成)。
//! 一度追加した提携は以降の LP でも初期の行として使う。
//!
//! 同じ仁を別の手法で求めるサブモジュール:
//!
//! | モジュール | 対象 | 手法 |
//! |---|---|---|
//! | (このモジュール) | 全提携の表 ([`ExplicitGame`]) | 逐次 LP + 制約生成 |
//! | [`exact`] | 有理数のゲーム (10 人まで) | 有理数の逐次 LP。許容誤差を使わない |
//! | [`oracle`] | 違反する提携を返せるゲーム | 逐次 LP + オラクルによる制約生成 |
//! | [`convex`] | 凸ゲーム | カーネル = 仁 を使う transfer scheme |
//! | [`sampled`] | 値を返すだけのゲーム | サンプリングした提携だけの逐次 LP (近似) |
//! | [`variants`] | 全提携の表 | per capita 仁・比例仁・modiclus (不満の定義を変えた仁) |
//!
//! ゲームの型からこれらの手法を自動で選ぶには [`crate::auto`] を使う。

pub mod convex;
pub mod exact;
pub mod oracle;
pub mod sampled;
pub mod variants;

use microlp::{Problem, Solution, Variable};

use crate::Domain;
use crate::error::{Error, Result};
use crate::game::allocation::{block_lower_bounds, coalition_sums};
use crate::game::{Coalition, ExplicitGame, default_tolerance};
use crate::linalg::Span;
use crate::lp::{self, Cmp, Counter};
use crate::solution::Guarantee;

/// LP に不等式を入れる方式。
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
#[non_exhaustive]
pub enum Method {
    /// 未確定の提携を全て最初から LP の行に入れる。
    Full,
    /// 解が違反する提携だけを行として追加する。
    #[default]
    ConstraintGeneration,
}

#[derive(Clone, Copy, Debug, PartialEq)]
#[non_exhaustive]
pub struct Options {
    pub domain: Domain,
    /// 超過の比較に使う許容誤差 (ゲームの値と同じ単位)。既定は [`default_tolerance`]。
    ///
    /// 配分集合は `sum v({i}) <= v(N) + tolerance` なら空とみなさない。和が `v(N)` を許容誤差以内で
    /// 超えるときは、超えた分を人数で等分して下限 `v({i})` を下げた 1 点を配分集合とする。
    pub tolerance: f64,
    pub method: Method,
}

impl Options {
    pub fn new(game: &ExplicitGame, domain: Domain) -> Options {
        Options {
            domain,
            tolerance: default_tolerance(game),
            method: Method::default(),
        }
    }

    /// 値を `divisor` で割ったゲームに合わせた設定 (許容誤差も割る)。
    fn divided_by(self, divisor: f64) -> Options {
        Options {
            tolerance: self.tolerance / divisor,
            ..self
        }
    }
}

#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct NucleolusResult {
    pub(crate) allocation: Vec<f64>,
    pub(crate) levels: Vec<f64>,
    pub(crate) lp_solves: usize,
    pub(crate) rows_added: usize,
    pub(crate) guarantee: Guarantee,
}

impl NucleolusResult {
    pub fn allocation(&self) -> &[f64] {
        &self.allocation
    }

    pub fn into_allocation(self) -> Vec<f64> {
        self.allocation
    }

    /// 各段の最適な最大超過 `t*`(非増加列)。
    ///
    /// LP を解かずに配分が決まった場合 (1 人ゲーム、配分集合が 1 点) は空。
    pub fn levels(&self) -> &[f64] {
        &self.levels
    }

    /// 最初から組み立てて解いた LP の数。
    pub fn lp_solves(&self) -> usize {
        self.lp_solves
    }

    /// 制約生成で後から追加した行の数(追加のたびに前回の解から解き直す)。
    pub fn rows_added(&self) -> usize {
        self.rows_added
    }

    /// 逐次 LP では [`Guarantee::Exact`]。
    pub fn guarantee(&self) -> Guarantee {
        self.guarantee
    }

    /// 正規化したゲームで求めた結果を、元の大きさ (`factor` 倍) に戻す。
    pub(crate) fn scaled_by(mut self, factor: f64) -> NucleolusResult {
        for value in self.allocation.iter_mut().chain(self.levels.iter_mut()) {
            *value *= factor;
        }
        self
    }

    /// 手法によらない共通の結果にする (保証はこの結果のものを引き継ぐ)。
    pub(crate) fn into_solution(
        self,
        domain: Domain,
        method: &'static str,
    ) -> crate::solution::Solution {
        crate::solution::Solution {
            domain,
            allocation: self.allocation,
            guarantee: self.guarantee,
            method,
        }
    }
}

#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct LeastCore {
    pub(crate) epsilon: f64,
    pub(crate) allocation: Vec<f64>,
    pub(crate) guarantee: Guarantee,
}

impl LeastCore {
    /// 最小コアの `epsilon`(空でない真部分提携の最大超過の最小値)。負ならコアは内部を持つ。
    ///
    /// 1 人ゲームには真部分提携がないので、最大超過は空集合の最大値として `f64::NEG_INFINITY` とする
    /// (どの `epsilon` でも `epsilon`-コアは `{v(N)}` で、コアは空でない)。
    pub fn epsilon(&self) -> f64 {
        self.epsilon
    }

    /// 最小コアに属する配分の 1 つ。
    pub fn allocation(&self) -> &[f64] {
        &self.allocation
    }

    pub fn into_allocation(self) -> Vec<f64> {
        self.allocation
    }

    pub fn guarantee(&self) -> Guarantee {
        self.guarantee
    }
}

/// 仁(配分集合上で超過ベクトルを辞書式に最小化する点)。
pub fn nucleolus(game: &ExplicitGame) -> Result<NucleolusResult> {
    nucleolus_with(game, Options::new(game, Domain::Imputation))
}

/// プレ仁(原配分集合上で超過ベクトルを辞書式に最小化する点)。
pub fn prenucleolus(game: &ExplicitGame) -> Result<NucleolusResult> {
    nucleolus_with(game, Options::new(game, Domain::Preimputation))
}

pub fn nucleolus_with(game: &ExplicitGame, options: Options) -> Result<NucleolusResult> {
    let (normalized, divisor) = game.normalized();
    let options = options.divided_by(divisor);
    let result = Sequential::new(&normalized, options)?.run()?;
    Ok(result.scaled_by(divisor))
}

/// 提携構造 `blocks` (N の分割) のもとでの仁 (`Domain::Imputation`) またはプレ仁。
///
/// 各ブロック `B` で `x(B) = v(B)` を課し、その中で超過ベクトルを辞書式に最小化する
/// (Aumann & Drèze 1974 の提携構造つきの仁)。ブロックが N だけなら [`nucleolus_with`] と同じ。
/// 分割になっているかは呼び出し側 ([`crate::partition::CoalitionStructure`]) で確かめる。
pub(crate) fn nucleolus_with_structure(
    game: &ExplicitGame,
    blocks: &[Coalition],
    options: Options,
) -> Result<NucleolusResult> {
    let (normalized, divisor) = game.normalized();
    let options = options.divided_by(divisor);
    let lower = block_lower_bounds(&normalized, blocks, options.domain, options.tolerance)?;
    if blocks.iter().all(|block| block.len() == 1) {
        // 全員が単独なら x_i = v({i}) に決まる (逐次 LP は 1 段も解かない)。
        return Ok(NucleolusResult {
            allocation: game.singleton_values(),
            levels: Vec::new(),
            lp_solves: 0,
            rows_added: 0,
            guarantee: Guarantee::Exact,
        });
    }
    let result = Sequential::with_blocks(&normalized, options, blocks, lower).run()?;
    Ok(result.scaled_by(divisor))
}

/// 最小コア: 最大超過を最小化する LP を 1 回解く。
///
/// 1 人ゲームでは配分は `v(N)` だけで、`epsilon` は `f64::NEG_INFINITY` ([`LeastCore::epsilon`])。
pub fn least_core(game: &ExplicitGame, domain: Domain) -> Result<LeastCore> {
    let (normalized, divisor) = game.normalized();
    let options = Options::new(game, domain).divided_by(divisor);
    let mut solver = Sequential::new(&normalized, options)?;
    if solver.n == 1 {
        return Ok(LeastCore {
            epsilon: f64::NEG_INFINITY,
            allocation: vec![game.value(game.grand())],
            guarantee: Guarantee::Exact,
        });
    }
    let (epsilon, allocation) = solver.minimize_max_excess()?;
    Ok(LeastCore {
        epsilon: epsilon * divisor,
        allocation: allocation.iter().map(|v| v * divisor).collect(),
        guarantee: Guarantee::Exact,
    })
}

/// コアが空でないか(最小コアの `epsilon` が 0 以下か)。
pub fn has_nonempty_core(game: &ExplicitGame) -> Result<bool> {
    let least = least_core(game, Domain::Preimputation)?;
    Ok(least.epsilon <= default_tolerance(game))
}

/// 提携 `S` の行の形。
#[derive(Clone, Copy)]
enum RowForm {
    /// `x(S) + t >= v(S)`(最大超過の最小化)。
    WithLevel(Variable),
    /// `x(S) >= v(S) - bound`(最大超過が `bound` 以下の配分に限る)。
    AtMost(f64),
}

struct Sequential<'a> {
    game: &'a ExplicitGame,
    options: Options,
    n: usize,
    /// 各プレイヤーの下限 (`Domain::Imputation` のみ。[`block_lower_bounds`])。
    lower: Option<Vec<f64>>,
    /// 提携構造のブロック (提携構造がなければ全体提携だけ)。
    blocks: Vec<Coalition>,
    /// 超過が確定し、LP の不等式から外した提携(ビット順、長さ `2^n`)。
    determined: Vec<bool>,
    /// 確定した提携と `x(S)` の値。
    fixed: Vec<(Coalition, f64)>,
    span: Span,
    counter: Counter,
    rows_added: usize,
    /// 制約生成で使う行の候補。一度追加した提携を覚えておく。
    pool: Vec<Coalition>,
    in_pool: Vec<bool>,
}

impl<'a> Sequential<'a> {
    fn new(game: &'a ExplicitGame, options: Options) -> Result<Sequential<'a>> {
        let blocks = [game.grand()];
        let lower = block_lower_bounds(game, &blocks, options.domain, options.tolerance)?;
        Ok(Sequential::with_blocks(game, options, &blocks, lower))
    }

    /// 提携構造 `blocks` (N の分割) の各ブロック `B` で `x(B) = v(B)` を課す。
    fn with_blocks(
        game: &'a ExplicitGame,
        options: Options,
        blocks: &[Coalition],
        lower: Option<Vec<f64>>,
    ) -> Sequential<'a> {
        let n = game.players();
        let grand = game.grand();
        let mut determined = vec![false; 1 << n];
        determined[0] = true;
        let mut span = Span::new(n);
        let mut fixed = Vec::with_capacity(blocks.len());
        for &block in blocks {
            determined[block.index()] = true;
            span.insert_coalition(block);
            fixed.push((block, game.value(block)));
        }
        let mut solver = Sequential {
            game,
            options,
            n,
            lower,
            blocks: blocks.to_vec(),
            determined,
            fixed,
            span,
            counter: Counter::default(),
            rows_added: 0,
            pool: Vec::new(),
            in_pool: vec![false; 1 << n],
        };
        // 1 人提携とその補集合があれば、最初の LP は有界になる。
        for i in 0..n {
            let single = Coalition::singleton(i);
            solver.remember(single);
            solver.remember(Coalition(grand.0 & !single.0));
        }
        solver.mark_span_determined();
        solver
    }

    fn run(&mut self) -> Result<NucleolusResult> {
        if self.n == 1 {
            return Ok(NucleolusResult {
                allocation: vec![self.game.value(self.game.grand())],
                levels: Vec::new(),
                lp_solves: 0,
                rows_added: 0,
                guarantee: Guarantee::Exact,
            });
        }
        self.pin_single_point_blocks();
        if self.span.is_full() {
            // 全てのブロックで配分が 1 点に決まった。LP は解かない。
            return Ok(NucleolusResult {
                allocation: self
                    .lower
                    .clone()
                    .expect("1 点に決まるのは配分集合の場合だけ"),
                levels: Vec::new(),
                lp_solves: 0,
                rows_added: 0,
                guarantee: Guarantee::Exact,
            });
        }
        let mut levels = Vec::new();
        let mut allocation = Vec::new();
        while !self.span.is_full() {
            let (level, x) = self.minimize_max_excess()?;
            levels.push(level);
            self.fix_tight_coalitions(level, &x)?;
            self.mark_span_determined();
            allocation = x;
        }
        Ok(NucleolusResult {
            allocation,
            levels,
            lp_solves: self.counter.solves,
            rows_added: self.rows_added,
            guarantee: Guarantee::Exact,
        })
    }

    /// 下限の和が `v(B)` 以上のブロック `B` (許容誤差以内で空の配分集合を含む) では、配分は 1 点
    /// `x_i = lower_i` に決まる。その 1 人提携を確定させる。
    ///
    /// 超過の差が許容誤差より小さくなるので、LP の段で確定させると誤った値で確定しうるため、先に確定させる。
    /// 和の等式と矛盾しないよう、ブロックの最後の 1 人は和の等式に任せる。
    fn pin_single_point_blocks(&mut self) {
        let Some(lower) = self.lower.clone() else {
            return;
        };
        for block in self.blocks.clone() {
            let singles: f64 = block
                .members()
                .map(|i| self.game.value(Coalition::singleton(i)))
                .sum();
            if block.len() < 2 || singles < self.game.value(block) {
                continue;
            }
            for i in block.members().take(block.len() - 1) {
                let single = Coalition::singleton(i);
                self.fixed.push((single, lower[i]));
                self.span.insert_coalition(single);
            }
        }
        self.mark_span_determined();
    }

    fn tolerance(&self) -> f64 {
        self.options.tolerance
    }

    fn remember(&mut self, coalition: Coalition) {
        if !coalition.is_empty() && !self.in_pool[coalition.index()] {
            self.in_pool[coalition.index()] = true;
            self.pool.push(coalition);
        }
    }

    fn is_open(&self, coalition: Coalition) -> bool {
        !self.determined[coalition.index()]
    }

    fn open_coalitions(&self) -> impl Iterator<Item = Coalition> + '_ {
        self.determined
            .iter()
            .enumerate()
            .filter(|(_, determined)| !**determined)
            .map(|(mask, _)| Coalition(mask as u64))
    }

    fn mark_span_determined(&mut self) {
        for mask in 1..self.determined.len() {
            if !self.determined[mask] && self.span.contains_coalition(Coalition(mask as u64)) {
                self.determined[mask] = true;
            }
        }
    }

    fn add_players(&self, problem: &mut Problem, objective: Option<Coalition>) -> Vec<Variable> {
        (0..self.n)
            .map(|i| {
                let lower = self
                    .lower
                    .as_ref()
                    .map_or(f64::NEG_INFINITY, |lower| lower[i]);
                let coefficient = match objective {
                    Some(s) if s.contains(i) => 1.0,
                    _ => 0.0,
                };
                problem.add_var(coefficient, (lower, f64::INFINITY))
            })
            .collect()
    }

    fn add_fixed(&self, problem: &mut Problem, x: &[Variable]) {
        for &(coalition, value) in &self.fixed {
            lp::add(problem, lp::coalition_expr(x, coalition), Cmp::Eq, value);
        }
    }

    fn row(
        &self,
        x: &[Variable],
        form: RowForm,
        coalition: Coalition,
    ) -> (Vec<(Variable, f64)>, f64) {
        let mut terms = lp::coalition_expr(x, coalition);
        let value = self.game.value(coalition);
        match form {
            RowForm::WithLevel(t) => {
                terms.push((t, 1.0));
                (terms, value)
            }
            RowForm::AtMost(bound) => (terms, value - bound),
        }
    }

    /// 行を入れて LP を解く。制約生成では、違反する提携を追加しながら解き直す。
    ///
    /// `build` は変数・目的関数・等式制約だけを入れた LP を作る。
    /// `seed` は最初から入れておく提携(制約生成のときのみ使う)。
    fn solve_rows(
        &mut self,
        build: impl Fn(&Self) -> (Problem, Vec<Variable>, RowForm),
        seed: &[Coalition],
    ) -> Result<(Solution, Vec<Variable>, RowForm)> {
        if self.options.method == Method::ConstraintGeneration
            && let Some(solved) = self.solve_lazily(&build, seed)?
        {
            return Ok(solved);
        }
        // 全ての行を入れて解く(制約生成で有界にならなかった場合もここに来る)。
        let (mut problem, x, form) = build(self);
        for coalition in self.open_coalitions() {
            let (terms, rhs) = self.row(&x, form, coalition);
            lp::add(&mut problem, terms, Cmp::Ge, rhs);
        }
        let solution = self
            .counter
            .solve(&problem)?
            .ok_or_else(|| Error::Numerical("LP が実行不可能".into()))?;
        Ok((solution, x, form))
    }

    /// 制約生成で解く。最初の LP が非有界なら `None` を返す。
    fn solve_lazily(
        &mut self,
        build: &impl Fn(&Self) -> (Problem, Vec<Variable>, RowForm),
        seed: &[Coalition],
    ) -> Result<Option<(Solution, Vec<Variable>, RowForm)>> {
        for &coalition in seed {
            self.remember(coalition);
        }
        let (mut problem, x, form) = build(self);
        let mut in_lp = vec![false; 1 << self.n];
        for &coalition in &self.pool {
            if self.is_open(coalition) {
                let (terms, rhs) = self.row(&x, form, coalition);
                lp::add(&mut problem, terms, Cmp::Ge, rhs);
                in_lp[coalition.index()] = true;
            }
        }
        let mut solution = match self.counter.solve_bounded(&problem)? {
            Some(solution) => solution,
            None => return Ok(None),
        };
        // 違反量がこれを超える提携を追加する。
        let slack = 1e-3 * self.tolerance();
        let batch = 4 * self.n;
        loop {
            let values: Vec<f64> = x.iter().map(|&var| solution[var]).collect();
            let sums = coalition_sums(&values);
            let bound = match form {
                RowForm::WithLevel(t) => solution[t],
                RowForm::AtMost(bound) => bound,
            };
            let mut violated: Vec<(f64, Coalition)> = self
                .open_coalitions()
                .filter(|s| !in_lp[s.index()])
                .filter_map(|s| {
                    let violation = self.game.value(s) - sums[s.index()] - bound;
                    (violation > slack).then_some((violation, s))
                })
                .collect();
            if violated.is_empty() {
                return Ok(Some((solution, x, form)));
            }
            violated.sort_by(|a, b| b.0.total_cmp(&a.0));
            for &(_, coalition) in violated.iter().take(batch) {
                let (terms, rhs) = self.row(&x, form, coalition);
                solution = lp::add_to_solution(solution, terms, Cmp::Ge, rhs)?;
                in_lp[coalition.index()] = true;
                self.remember(coalition);
                self.rows_added += 1;
            }
        }
    }

    /// 未確定の提携の最大超過を最小化し、`(t*, x*)` を返す。
    fn minimize_max_excess(&mut self) -> Result<(f64, Vec<f64>)> {
        let build = |this: &Self| {
            let mut problem = lp::minimize();
            let x = this.add_players(&mut problem, None);
            let t = problem.add_var(1.0, (f64::NEG_INFINITY, f64::INFINITY));
            this.add_fixed(&mut problem, &x);
            (problem, x, RowForm::WithLevel(t))
        };
        let (solution, x, form) = self.solve_rows(build, &[])?;
        let RowForm::WithLevel(t) = form else {
            unreachable!("最大超過の最小化は WithLevel の行を使う")
        };
        let allocation = x.iter().map(|&var| solution[var]).collect();
        Ok((solution[t], allocation))
    }

    /// 最大超過が `level` 以下の配分の中で `x(target)` を最大化する。
    fn maximize_coalition(&mut self, target: Coalition, level: f64) -> Result<(f64, Vec<f64>)> {
        // 最適値の丸め誤差で実行不可能にならないよう、許容誤差の 1% だけ緩める。
        let bound = level + 0.01 * self.tolerance();
        let build = |this: &Self| {
            let mut problem = lp::maximize();
            let x = this.add_players(&mut problem, Some(target));
            this.add_fixed(&mut problem, &x);
            (problem, x, RowForm::AtMost(bound))
        };
        // 補集合の行があれば x(target) は上から抑えられる。
        let complement = Coalition(self.game.grand().0 & !target.0);
        let (solution, x, _) = self.solve_rows(build, &[target, complement])?;
        let allocation: Vec<f64> = x.iter().map(|&var| solution[var]).collect();
        Ok((solution.objective(), allocation))
    }

    fn fix_tight_coalitions(&mut self, level: f64, x: &[f64]) -> Result<()> {
        let sums = coalition_sums(x);
        let tight: Vec<Coalition> = self
            .open_coalitions()
            .filter(|s| {
                let excess = self.game.value(*s) - sums[s.index()];
                (excess - level).abs() <= self.tolerance()
            })
            .collect();
        if tight.is_empty() {
            return Err(Error::Numerical(format!(
                "最大超過 {level} を達成する提携が見つからない"
            )));
        }
        let mut not_fixed = vec![false; tight.len()];
        let mut progressed = false;
        for k in 0..tight.len() {
            if not_fixed[k] || self.span.contains_coalition(tight[k]) {
                continue;
            }
            let target = tight[k];
            let fixed_sum = self.game.value(target) - level;
            let (max_sum, witness) = self.maximize_coalition(target, level)?;
            if max_sum <= fixed_sum + self.tolerance() {
                self.fixed.push((target, fixed_sum));
                self.span.insert_coalition(target);
                progressed = true;
                if self.span.is_full() {
                    break;
                }
            } else {
                // witness では超過が level 未満になる提携も確定していない。
                let witness_sums = coalition_sums(&witness);
                for (later, flag) in tight.iter().zip(not_fixed.iter_mut()).skip(k + 1) {
                    let excess = self.game.value(*later) - witness_sums[later.index()];
                    if excess < level - self.tolerance() {
                        *flag = true;
                    }
                }
            }
        }
        if !progressed {
            return Err(Error::Numerical(format!(
                "最大超過 {level} の段で確定する提携が見つからない(許容誤差 {} を見直す)",
                self.tolerance()
            )));
        }
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::generators;

    fn assert_close(actual: &[f64], expected: &[f64]) {
        assert_eq!(actual.len(), expected.len());
        for (a, e) in actual.iter().zip(expected) {
            assert!((a - e).abs() < 1e-6, "{actual:?} != {expected:?}");
        }
    }

    #[test]
    fn detects_empty_core() {
        assert!(has_nonempty_core(&generators::random_convex(4, 1).unwrap()).unwrap());
        // 3 人多数決: 優加法的だが、コアは空。
        let majority = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
        assert!(!has_nonempty_core(&majority).unwrap());
    }

    #[test]
    fn symmetric_game_splits_equally() {
        let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 60.0, 60.0, 60.0, 72.0]).unwrap();
        assert_close(&nucleolus(&game).unwrap().allocation, &[24.0, 24.0, 24.0]);
        assert_close(
            &prenucleolus(&game).unwrap().allocation,
            &[24.0, 24.0, 24.0],
        );
    }

    #[test]
    fn pair_game() {
        // v(12)=4, v(N)=4、他は 0。仁は (2, 2, 0)。
        let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 4.0, 0.0, 0.0, 4.0]).unwrap();
        let result = nucleolus(&game).unwrap();
        assert_close(&result.allocation, &[2.0, 2.0, 0.0]);
        assert!((result.levels[0] - 0.0).abs() < 1e-9);
    }

    #[test]
    fn bankruptcy_nucleolus_is_talmud_rule() {
        // Aumann-Maschler (1985): 請求 (100, 200, 300) に対するタルムードの配分。
        let claims = [100.0, 200.0, 300.0];
        for (estate, expected) in [
            (100.0, [100.0 / 3.0, 100.0 / 3.0, 100.0 / 3.0]),
            (200.0, [50.0, 75.0, 75.0]),
            (300.0, [50.0, 100.0, 150.0]),
        ] {
            let game = generators::bankruptcy(estate, &claims).unwrap();
            assert_close(&nucleolus(&game).unwrap().allocation, &expected);
        }
    }

    #[test]
    fn prenucleolus_can_leave_imputation_set() {
        // v(3)=5, v(12)=10, v(13)=v(23)=5, v(N)=12。
        // プレ仁は e(12) = x_3 - 2 と e(3) = 5 - x_3 を釣り合わせて x_3 = 3.5 < v(3) となる。
        // 仁は x_3 >= 5 の制約で x_3 = 5 に止まる。
        let game = ExplicitGame::from_lex(&[0.0, 0.0, 5.0, 10.0, 5.0, 5.0, 12.0]).unwrap();
        assert_close(&prenucleolus(&game).unwrap().allocation, &[4.25, 4.25, 3.5]);
        assert_close(&nucleolus(&game).unwrap().allocation, &[3.5, 3.5, 5.0]);
    }

    #[test]
    fn empty_imputation_set_is_error() {
        let game = ExplicitGame::from_lex(&[3.0, 3.0, 3.0, 6.0, 6.0, 6.0, 8.0]).unwrap();
        assert_eq!(nucleolus(&game), Err(Error::EmptyImputationSet));
        assert!(prenucleolus(&game).is_ok());
    }

    #[test]
    fn least_core_of_game_with_empty_core() {
        // 3 人多数決ゲーム: コアは空で、最小コアは epsilon = 1/3、配分は (1/3, 1/3, 1/3)。
        let game = ExplicitGame::from_lex(&[0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0]).unwrap();
        let least = least_core(&game, Domain::Preimputation).unwrap();
        assert!((least.epsilon - 1.0 / 3.0).abs() < 1e-9);
        assert_close(&least.allocation, &[1.0 / 3.0; 3]);
    }
}