Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of maintaining a good revenue in a shrinking market for combinatorial auctions of n bidders and m items. The shrinking market is modeled as follows: every bidder n participates in the market independently with probability p (the valuations of the bidders participating in the market are hidden). The modeling of the problem is the first contribution of the paper. The second contribution is to show that in general settings, not handling the shrinking market specifically may not just incur a revenue that is p times the optimal revenue but significantly less. This result motivates even further the need to understand how much the revenue changes in a shrinking market. The third contribution is a possibility result, showing a lower bound on the revenue that can be extracted from a shrinking market. The result’s proof is based on a new construction, the winner diagram which may be of independent interest. The last contribution is a learning-from-samples-type algorithm for nearly achieving this revenue. 

strengths_and_weaknesses: Strengths.
1) The problem studied in the paper seems fundamental and to the best of my knowledge, it has not been addressed in the literature. I was also thinking that although the paper is written in a way to emphasize the inherent MD component, the problem looks like a core ML theoretical problem phrased as follows: Let S be a sample on which an algorithm is trained and obtains a model M with loss L. If instead of S, the same algorithm is used on a subset of S (say S’ \subseteq S) then how far away are the two models M’ and M in terms of their losses? This is not precisely the question addressed in this work, but I was wondering whether there is a more ML-theoretic language to phrase the problem.
2) The paper is very well written. I also liked the story of the paper because I found it rather “complete”; for the problem at hand not only do the paper presents how much revenue can be preserved but also how to efficiently learn an auction achieving this revenue (i.e., an auction robust to market shrinkage or general market uncertainty). 
3) The winner diagram technique (which is at the center of the construction for the possibility result) is quite neat. To be honest I was wondering whether there are certain classes of auctions where one can build and traverse these graphs fast enough so that we don’t have to learn from samples, but this is certainly not required for me to think positively about this paper.

Weaknesses. 
Knowing p (or the distribution D) is restrictive. Do the current results hold even if you know p approximately? This would mean that there is a distribution D’ that is known with small distance from D. Such a result would strengthen the punchline of the paper even more. 

Evaluation.
In my opinion, the weakness that I pointed out above was not as important as the strengths of the paper. Moreover, they mostly constitute interesting directions for future work. For that, I’m leaning positive for the paper.

Additional Comments. 
* I understand that the assumption on the existence of independence in choosing the subset is done for technical reasons and I think it is okay given that this is one of the first studies of market shrinkage. But in reality shouldn’t we expect that there is some correlation between people who decide to leave the market? That is at least the case in all the examples mentioned in the introduction where there was an outside “force” pushing people out of the market.
* In lines 56-61: I would suggest adding a short description of what delineability is.
* In the first paragraph of Section 3, when describing v_j(b), would you mind explaining why this is correlated with i? And what is i in this case fixed to? 
* After Def 5 I would suggest adding a short paragraph about what d, h, and \theta are for certain well-known examples, like the second price auction.

questions: See my question inside the first strength above about a more learning-theoretic phrasing of the problem. My other questions are mostly related to different assumptions in the model, so I listed them under “Additional Comments”. 

limitations: properly addressed by the authors
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies revenue guarantees for multi-item auctions under shrinking markets, where the participation of bidders in auctions are independent and random. The paper first presents a motivating example for VCG auctions that demonstrate only an exponentially small fraction of revenue can be guaranteed under shrinking markets when bidders’ values also depend on what others receive. The paper then develops a probabilistic argument to show for a sufficiently large class of mechanisms, there must exist a mechanism that is robust to market shrinkage, and preserves a certain level of revenue. Finally, the paper presents a sample based approach to find a mechanism that yields revenue at least the presented guarantee on revenue with high probability. 

strengths_and_weaknesses: Strengths:
The paper is well-written, and to the best of my knowledge, the probabilistic existence result for mechanisms that achieve certain revenue guarantees (along with the construction and analyses of the “winner diagram”) under shrinking markets is novel, and provides quite substantial contribution to the understanding of auction revenue in this particular market scenario. I find the motivating example in Section 3 that states in certain scenarios VCG can only retain an exponentially small fraction of revenue quite enlightening, and I appreciate the exemplifying numerics for revenue loss presented after Theorem 3.1. Despite being a theoretical paper, I feel the paper presents nice insights into challenges for auction design and revenue maximization in practice.  

Weaknesses:
I do not see major weaknesses in the paper. Perhaps one question/concern I have for the overall methodology of mechanism $\mathcal{A}$ and the sample based approach to find a particular mechanism with good revenue guarantees, is that both rely on the knowledge of $p$  which is the probability that a bidder participates in an auction. If there is misspecification in this parameter (especially over estimations), it seems that certain mechanism equivalence classes may be ruled out which in the worst case may be those who correspond to the highest revenues. If this is true, is there any intuition regarding how sensitive are the revenue guarantees to misspecification of $p$? I may be missing something here, and would be great if the authors can clarify.

questions: See above in strengths and weaknesses.
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper models shrinking markets with uncertain size in multi-item setting, and proposes a sample-based learning algorithm with provable guarantees on how much revenue can be preserved in the face of uncertain market. The major novelty is the construction of a winner diagram, which captures all possible executions of an auction on an uncertain set of bidders, and a general possibility result by analyzing the winner diagram shows the proposed bound on the revenue guarantee.
strengths_and_weaknesses: Strength:
* The paper is well-written, all the ideas are clearly discussed and properly organized.
* The paper states that the proposed model of shrinking markets is the first formal model in multi-item setting, which seems technically non-trivial.

Weaknesses: NA


questions: This paper is not in my area, and I have very limited related knowledge to give technical comments.
1. One question on bidder participation distribution: In Appendix C.5, the paper states that the proof techniques easily generalize to handle any distribution $D$ over subsets of bidders, does it imply that bidder participation probabilities can be mutually dependent? What is the impact on the revenue guarantee if the bidder participation distributions are not independent? 
2. Do we have existing revenue guarantee on markets with known size? If yes, given the proposed model of market with uncertain size, how much loss do we encounter on revenue guarantee? Does the proposed algorithm have orderly optimal performance on revenue guarantee?
limitations: I did not notice any.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the mechanism design problem when all the players' valuation functions are known, and each player participates with certain probability. It provides a randomized mechanism with revenue lower bound guarantee and also a sample-based mechanism which can be implemented efficiently. 
strengths_and_weaknesses: Strengths:
1. I like the idea that each player participates with uncertainty. 
2. This paper provides a first lower bound result for the "market shrinkage" problem, and provides a sample-based algorithm. 

Weaknesses:
1. The assumption that the valuations for all players are known is kind of restricted.
2. This paper seems more related to market uncertainty, but less to market shrinkage. What is the formal economic definition of market shrinkage? 
questions: Theorem 4.3 states there must exists a (deterministic) mechanism. Where does it prove its existence?

limitations: Not applicable.
review_title: null

Meta-review: metareview: The reviews are all positive. The reviewers agree that the paper studies a fundamental problem with nice insights and interesting techniques, and the paper is well-written. 
confidence: Certain
Decision: Accept