- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2(+1)
- Soundness
- 3(+2)
Read review
Paper summary
The article considers an online matching problem with an offline side and independent vertex arrivals on the other side. Motivated by the work of Ahmadian et al. (2026), the authors address the question of designing universally bounded menus (only depending on ) for the online vertices producing a ()-approximation of the expected maximum size matching without any assumptions on the matching mass distributions across edges. The main contribution of the article is the proof of the existence of menu's sizes depending only on for any product-arrival instance. This theoretical result is then enforced with numerical experiments.
Critical strengths
- The article considers a novel problem based on a recent publication in NeurIPS26
- The considered problem is timely, with potential applications regarding the size of the information that an arriving vertex might have to declare in order to still guarantee a close-to-optimal allocation.
- Theorem 3.1 gives a bound on the size of the menus only depending on the accuracy level .
- The article presents empirical validation of the theoretical results.
Critical weaknesses
- The article is very difficult to read since it does not properly introduce many of the terms it uses during the different discussions. The current state of the document gives the impression of being a highly AI written paper without a proper human post-checking in order to make the text clearer. Due to this, it is nearly impossible to asses the contributions of the article.
- The addressed problem in the article is not properly motivated. The article starts saying "Resource allocation often separates local candidate selection from global coordination". First of all, it is not clear what this phrase tries to say. Second, no references are given of matching problems where such separation holds.
- The whole paper is based on Ahmadian et al. (2026), an article fairly new. However, the citation is never properly discussed, giving the impression that the article contains a small incremental contribution to the literature. In particular, it is never explained why the assumption of Ahmadian et al. (2026) requires a study beyond it. Due to this, the article's contribution does not seem to be at the level of acceptance for ICLR.
Questions for authors
I have no questions.
3 comments
I thank the authors for the revised article as well as their detailed answers. Additionally, I excuse for taking so long in answering, but I have taken a bit of time as I wanted to read the new version of the paper entirely, the other reviews, and the other answers of the authors. I'm greatly satisfied with the new version of the article's introduction. The problem is much better explained, the connections and differences with Ahmadian et al. 2026 are well discussed, and several examples are included allowing the reader to get convinced about the importance of the considered problem. As mentioned by the authors, the wording of "two-stage process" is indeed a much better choice. Even though Section 2 does not present changes, the technical part of the article is much reader-friendly once we have gotten a better idea of the paper's framework during Section 1. I'm convinced that both the theoretical contribution of the paper as well as the techniques used to establish it are both strong and sound. In particular, I have changed both my presentation and soundness scores.
That said, I agree with reviewer KmHQ that Section 3 is still difficult to follow and that only people already used to using all these techniques can get the most out of it. In particular, I think the article would benefit for a more detailed definition/discussion on the terms "endpoints", "endpoints weights", "overloaded endpoints weights", "free-status indicators", "query", "endpoint loads", "localized dependencies", among others.
In order to properly understand Section 3, the reader is required to jump go and back to the referred appendices all the time. This is of course not a major weakness in an article, however, for the conference format where an article must be able to fully convince the reader of all its claims in its main body, relegating such fundamental discussions to the supplementary material does represent an important issue. The same issue also holds in Section 4, where without reading the corresponding appendix, it is impossible to understand both the experiment and its results. For example, NC, NCH, MH4, and MHk are not explained in the paper main body. The article should either present a more developed empirical section or simply to fully relegate it to the appendix as, anyway, in its current form the article does not get any major improvement from Section 4.
I have decided to improve my score, however, I remain on the opinion that the article is not well-suited for the conference format and therefore I recommend for weak rejection.
Thank you for carefully reading the revision and reconsidering your assessment. We appreciate your recognition of the strength and soundness of the contribution and techniques.
We revised accordingly and now clarified “free” and “endpoint load” where they first appear in the proof-ideas discussion. Other terminology is also explained when introduced.
Regarding the experiments, we agree that the setup and results are best presented together. Due to space limitations, expanding section 4 would result in trimming the proof overview. We would be happy to follow your suggestion and move Section 4 and its figure entirely to Appendix I, retaining only a brief pointer in the introduction. The experiments illustrate behavior at moderate menu sizes and the effect of sampling choices and the theoretical guarantees are established independently of them.
We hope these clarifications and the proposed consolidation of the experiments address your remaining presentation concerns. The complete proof is indeed involved and even if we move section 4 content to the appendix we do not see a way to fit all the details in the main 10 pages. Thank you again for your time and constructive feedback.
Follow-up on our rebuttal and revised manuscript
Thank you again for reviewing our paper. As the discussion period approaches its close, we would appreciate your feedback on our response and the revised manuscript uploaded on November 11. We expanded the motivation and application references, added an explicit comparison with Ahmadian et al., and clarified definitions and the proof overview.
Could you please indicate which concerns remain after these changes? In particular, could you identify the specific claim, assumption, or proof step underlying your soundness assessment? We requested this clarification in our November 8 response and would appreciate the opportunity to address it before the discussion closes.
Please also let us know whether our response and revision address your concerns about the motivation and contribution beyond prior work.