google-deepmind / google-deepmind/open_spiel

lp_solver: solve() returns None on solver errors, so is_dominated() can return a wrong answer

Open
#1,617 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
5.5k
Forks
1.2k
Avg merge
2d 8h
Merged PRs (30d)
4

Description

Since the cvxopt to cvxpy migration in #1479, `LinearProgram.solve()` in `open_spiel/python/algorithms/lp_solver.py` returns `None` in two unrelated situations and callers can't tell which one happened:

```python
try:
problem.solve(**kwargs_)
value = x.value
except cp.SolverError as e:
print(f"Something went wrong, as of {e}")
value = None
return value
```

1. The LP is infeasible or unbounded. `x.value` is `None`, and `problem.status` is never checked, so `None` comes back with no message.
2. The solver itself fails (not installed, numerical trouble). The `SolverError` is printed and swallowed, and `None` comes back.

The first case is a legitimate result. The second is an error. They look identical to the caller.

The consequence that worries me most is in `is_dominated()`. It reads `None` as "the LP is infeasible, so no dominating mixture exists, so the action is not dominated". That's the right interpretation for case 1. But in case 2 it also returns `False`, for actions that really are dominated, and nothing is raised. Easy to reproduce: patch `cvxpy.Problem.solve` to raise `SolverError`, then call

```python
is_dominated(0, [[1, 1], [2.1, 0], [0, 2]], 0, DominanceType.DOMINANCE_STRICT)
```

Action 0 is strictly dominated by the 50/50 mix of actions 1 and 2, but the call returns `False`.

The other callers (`solve_zero_sum_matrix_game`, `sequence_form_lp`, `value_iteration`, `double_oracle`, `maximal_lotteries`, `jpsro`) all index the result directly, so they crash with `TypeError: 'NoneType' object is not subscriptable` a few frames away from the real cause, with the actual solver message only on stdout.

I have a small fix ready with tests: let `SolverError` propagate, return `None` only when `problem.status` says infeasible or unbounded and say so in the docstring since `is_dominated` depends on it, and have `solve_zero_sum_matrix_game` raise a clear error naming the status instead of failing on the slice. I'll open the PR shortly and link it here.

Contributor guide

Open the contributing guide

Research direction

Start in open_spiel/python/algorithms/lp_solver.py and inspect LinearProgram.solve(), is_dominated(), and solve_zero_sum_matrix_game(). Reproduce the SolverError case described in the issue, then run the added LP solver tests; done means solver failures propagate, infeasible or unbounded statuses remain distinguishable, and callers report a clear status error.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.