google-deepmind / google-deepmind/open_spiel
lp_solver: solve() returns None on solver errors, so is_dominated() can return a wrong answer
- 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
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