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: The manuscript tackles the problem of maximising social welfare amongst agents for assignments of items to agents when agents only disclose their preference ordering of items (base on a hidden score of each item). The manuscript focuses strongly on the distortion of a matching mechanism, i.e., the worst-case ratio between achieved and optimal social welfare amongst all possible valuation profiles. One major result is that asking agents first for their favourite alternative, then computing a representative subset and asking for their favourite alternative amongst the subset yields a $O(\sqrt{n})$ distortion ($n$ is both the number of items and agents). Previously, such a result required randomization and normalization of agent values, whereas the novel result is deterministic and obiviates the need for normalization and thereby extends the applicability of the result. This comes only at the cost of having to elicit preference twice from agents, which seems acceptable in most settings. The challenging part of developing the approach lies in the computation of the representative subset to allow for the resulting analysis.

strengths_and_weaknesses: STRENGTHS

S1. Motivation/Relevance: Interesting, very general problem of how to match agents with items based only on ordinal preference indications (which is generally easier to elicit).

S2. Novelty/Significance: The basic idea of eliciting preferences twice, first on all items and then a representative subset seems novel and a simple, elegant solution

S3. Presentation/Soundness/Related Work: The work is well-written, seems to substantiate all claims (very extensive supplementary material) and cover the relevant related work.

S4. The work discusses a wider range of variants and both possibility results as well as achieved results.

WEAKNESSES

W1. An empirical study could make the paper more relevant to more practically oriented readers.

W2. Although it would seem to be general enough to cover a wider range of applications, some examples for practical applications could be beneficial

questions: Q1. What are some examples of practical applications mentioned in Section C of the supplementary material?
limitations: Specifically, as Section C in the supplementary highlights performance in practice, it would be useful to add a small (simple) empirical study with simulated agents with some prior randomised approach as a baseline and mention a few concrete examples of potential applications.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose a framework that approximates a matching problem using only two queries per agent.
The authors show that they can achieve O(sqrt(n)) approximation guarantee, and show that this is the best
they can do given the queries.
strengths_and_weaknesses: + Theoretically interesting result. Especially the tightness result completes the picture.
- The amount of information is so limited that the algorithm cannot  do too much.
- Limited applications
questions: The two queries algorithm is allowed to ask are very different. The first asks the most preferred item,
while the second asks the utility of a certain item. How this compares to the existing work? How this extends
to lambda > 2 queries.
limitations: The available information is so limited, that the algorithm cannot do much here. Essentially, the algorithm
will give the preferred option or a random choice. This hints that in practice two queries are too little
to produce any interesting result. Perhaps developing an algoriithm for higher lambdas would be more fruitful.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper deals with optimizing social welfare given preference orderings of agents. The paper improves social welfare by asking each agent two additional questions and it shows that social welfare can be optimized compared to knowing all agents' exact valuations up to a divisor of SQRT(n).
Based on the solution to this problem further statements are derived.
strengths_and_weaknesses: Strengths:
+ Novel algorithm and theorems about social welfare optimzation given additional queries
+ Useful extensions beyond the core approach
Weakness:
+ The main comparisons are constituted by logarithmically many queries. For most practical purposes, logarithm is like a constant. A practically relevant comparison should therefore show the advantage also empirically by experiments.
+ I don't see this as a relevant paper for a machine learning conference
questions: none
limitations: While the paper offers clear progress wrt underlying theory, 
the paper could have discussed practical applications and applicability at least briefly.
review_title: null

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 social welfare maximization when given only ordinal information for each agent, but where we are allowed to make *two* cardinal queries per agent.  They focus on "one-sided matching", but their results also extend more generally.  In slightly more detail, suppose that every agent has a value for every item, and our goal is to find the matching maximizing the social welfare.  However, we are not given the value ("cardinal") information, but are instead only given the *ordering* for every agent.  We can then design mechanisms that use only this ordinal information, and use as our measure of quality the worst case over all valuations of the optimal social welfare (matching) vs the welfare achieved by the mechanism.  This is called the "distortion".  This has been studied extensively over the past decade, and much is known.

This paper continues a new line of work where we augment our mechanisms with the ability to make a small number of valuation ("cardinal") queries.  A previous paper showed that with $O(\log n)$ queries per agent we can get $O(^{1/k})$ distortion for any constant k that we want, and it was also shown that with k queries the best distortion we can hope for is $\Omega(n^{1/k})$.  So there was an obvious open question: can we get sublinear distortion with less than $\log n$ queries?  In the extreme: what distortion is achievable with only *two* queries?

This paper resolves the two-query case, showing that $O(n^{1/2})$ distortion is achievable.  They do this with a deterministic algorithm and with no assumptions on the valuations.  Previous sublinear distortion bounds (e.g., without any queries) required either randomness, assumptions on the valuations, or both.  Their algorithm first queries the valuation of every agent's highest-rank item.  They then use the ordinal information to compute a "sufficiently representative assignment" A -- this is basically a many-one assignment where every item is matched to at most $n^{1/2}$ agents, and also there are at most $n^{1/2}$ agents that prefer what they are matched with in OPT to what they are matched to in the assignment.  The authors show that a simple algorithm can be used to generate such an assignment using only the ordinal information.  Then for the second query, they query the valuation for every agent of the item they're matched to in A.  Finally, they compute an optimal solution that uses only the valuations from these two queries (all non-queried valuations are set to 0).

In the analysis, they show that the dual $n^{1/2}$ guarantees of the sufficiently representative assignment can be used to balance the cost both of the agents that query a "too high" item (an item that they prefer to what they get in OPT) and of the agents that query a "too low" item.

They then study more general settings than just one-sided matching.  First, they study a wider variety of graph problems which they call "matching extended k-families", and which include pretty natural problems such as two-sided matching and general graph k-matchings.  Technically, this type of problem does not include the one-sided matching case, since they assume in their graphs that every vertex is an agent.  So the cannot just re-use the exact same ideas and results.  However, they show that an $\Omega(n^{1/k})$ lower bound still holds, and that a similar algorithm with a more complicated argument also gives $O(n^{1/2})$ distortion with only two queries per agent.

Finally, they study the most general social choice setting, where there are $n$ agents, $m$ alternatives, every agent has a valuation for every alternative, and we want to choose the alternative that maximizes social welfare.  Here they show an $\Omega(m^{1/k})$ lower bound on deterministic mechanisms that make at most $k$ queries, and give an algorithm which is essentially a generalization of their previous algorithms which gives distortion $O(\sqrt{m})$ as long as $m = \Omega(n)$.

strengths_and_weaknesses: Strengths:
- This is a pretty natural set of questions.  Distortion of having only ordinal information has been well-studied and seems to be pretty well-motivated.  But since we have strong lower bounds in that setting, it's natural to try to go "beyond worst-case" by allowing extra information.  A small number of value queries seems to me to be a pretty natural way to do this (of course it's not the only possible way of going beyond worst-case, but I think it's an interesting one).  And this is not the first paper which studies this setting.

- The main upper bound seems quite strong to me.  The problem is particularly natural (one-sided matching), it matches a known lower bound, the algorithm is quite simple but requires some non-obvious analysis, and they show that two queries are already enough to give nontrivial distortion guarantees.  It feels to me like the "right" result, for a natural and interesting problem.

- The generalizations are also quite interesting.  The problems are very natural (particularly two-sided matching and general social choice), and the results are pretty strong (particularly for two-sided matching and the other graph-based generalizations, where no extra assumptions are needed).  And the algorithms are basically the same as the one-sided matching case, but with slight tweaks and more complicated analyses.  So they're generalizations in a sense that I like a lot -- they reinforce the main ideas of the paper, rather than giving an entirely new set of ideas, but do add significant technical difficulty and complexity.

Weaknesses:
- The main result is quite strong (as I discussed above), but is actually a little weaker than I was hoping for.  This is because the result only holds for two-queries.  In many algorithmic settings, there is a tradeoff between some parameter and some notion of "quality", and when there's not such a tradeoff there is some kind of "phase transition".  Based on the known lower bound, I was hoping that this paper have an $O(n^{1/k})$-distortion upper bound for $k$ queries (giving a tradeoff), or alternatively showed that it was not possible to get below $n^{1/2}$ queries without using superconstant queries (showing a phase transition).  But this paper didn't give any results on constant queries beyond 2, which I found a little disappointing.  However, it's worth pointing out that two is a particularly interesting case, since (as the authors point out) it is the smallest number of queries for which sublinear bounds are possible.  I just wish the authors had either given more general results, or discussed why their approach doesn't / can't give such results.

Overall, I really liked this paper, and think it should be accepted.
questions: - You list handling a constant number $>2$ queries as an open problem.  It would be nice to discuss this a bit more, and in particular discuss why your approach can't already achieve this.

- You also mention that for the general social choice problem, you suspect that adaptivity is necessary.  It would be nice to expand on this.  Why do you suspect that adaptivity is necessary?  Could adaptivity be used even in the grpah case to get better results with 3 or more queries?

limitations: This is a theory paper, so I think the discussion of limitations and negative social impact is sufficient.
review_title: null

Meta-review: metareview: This work studies a narrow, but important problem of how much cardinal information is needed to achieve near optimal matchings. The authors show that with just two queries (one is required for any non-trivial results) they can achieve non-trivial results in a very general setting. Moreover, they show that their results are tight. 
confidence: Certain
Decision: Accept