- Rating
- 2
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
First, I would like to clarify that I am not familiar with the multiplayer Nim problem. Although I tried my best to understand the paper, I might have misunderstood some aspects.
The paper studies the problem of determining the outcome of a multiplayer Nim where each player has reverse cyclic preferences over the winner. More specifically, the paper considers the setting where one heap can be arbitrarily large and the total size of the other heaps is not overly larger than twice the number of players. It denotes the excess amount as . The proposed algorithm compiles the problem into multiple fixed-dimensional integer linear programming and proves that the number of variables in each ILP is bounded by 2$q$+1. The running time of the proposed algorithm has an exponent that depends on , and runs in polynomial time when is a constant.
Critical strengths
1. The paper proposes a new algorithm and establishes its time complexity bound.
The proposed algorithm is supported by formal proof and analysis. The authors also provide complexity bounds under the stated assumptions, which strengthen the theoretical contribution of the paper.
Critical weaknesses
1. The problem seems to be outside the scope of ICLR.
The paper proposes an algorithm for solving multiplayer Nim under certain constraints. However, this is a theoretical and combinatorial problem, and it does not appear to have a direct connection to machine learning, learning theory, or optimization. The references also seem to have limited connection to the ICLR research community. Therefore, I believe the authors should more clearly explain the relevance of this work to ICLR and discuss real-world applications of the problem.
2. The significance of the results under the considered constraints seems unclear.
This may be due to my lack of expertise in this area, but I believe the authors should further clarify the origin of this problem and why addressing this problem is important. Regardless of whether the paper is outside the scope of ICLR, I also find it difficult to assess the significance of this work within the combinatorics and game theory community. It is unclear whether the constraints of one additional heap and a total size bound are motivated by the significance of the problem itself or by mathematical tractability.
3. It is unclear how reasonable it is to treat as a constant.
The polynomial time bound holds only when is regarded as a constant, and the degree of the polynomial grows rapidly as increases. Furthermore, the fixed-dimensional ILP solver also requires an exponential time over . Thus, the running time analysis heavily depends on treating as a constant, and I believe the authors should discuss how reasonable this restriction is.
Questions for authors
Questions
Q1. Could the authors further clarify the relevance of this work to ICLR and discuss its potential real-world applications?
Q2. Could the authors further discuss how reasonable the constraints in the problem settings are?
Suggestions
The paper would benefit from adding an introduction to multiplayer Nim including a demonstrating example, a formal problem definition, and discussion on the significance of the problem for the readers who are less familiar with this research area.