Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
Authors: Georgios Amanatidis
Georgios Birmpas
Aris Filos-Ratsikas
Alexandros A. Voudouris
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distortion
Matching
Social Choice
Query

Abstract: In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitably leads to poor performance with respect to optimizing a cardinal objective, such as the social welfare, since the values of the agents remain virtually unknown. This loss in performance because of lack of information is measured by distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on a class of combinatorial problems that includes most well-known matching problems and several of their generalizations, such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and k-Constrained Resource Allocation. We design two-query mechanisms that achieve the best-possible worst-case distortion in terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms.

Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
Georgios Amanatidis
Georgios Birmpas Sapienza University of Rome gebirbas@gmail.c com
University of Essex
gorggoo..mamttidd amasserdd@@esser. ac. uk
Aris Ellos-Ratsikan
Alexandros A. Voudouris University of Essex
University of Edinburgh
Aris. Seslloo-Ratsikaseee ac. uk
al exandroos voudouris@essex. ac uk
Abstract
In most social choice settings, the participating agents express their preferences over the different alternatives in the form of linear orderings. While this clearly simplifies preference elicitation, it inevitabyly leads to poor performance with respect optimizing a cardinal objective, such as the social welfare, since the values the agents remain virtually unknown. This loss in performance because of lack of information measured by the notion of distortion. A recent array of works put forward the agenda of designing mechanisms that learn the values of the agents for a small number of alternatives via queries, and use this limited extra information to make better-informed decisions, thus improving distortion. Following this agenda, in this work we focus on class of combinatorial problems that includes most well-known matching problems and several of their generalizations, such as One-Sided Matching, Two-Sided Matching, General Graph Matching, and k- Constrained Resource Allocation. We design Two-query mechanisms that achieve the best-possiin worst-case distortion terms of social welfare, and outperform the best-possible expected distortion achieved by randomized ordinal mechanisms.
Introduction
The notion of distortion in social choice settings defined to capture the loss in aggregate objectives due to the lack of precise information about the preferences of the participants [Procaccial and Rosenschein 2006). More coneretely, the distortion originally defined as measure of the deterioration of the total happiness of the agents when access is given only to the (ordinal) preference rankings of the agents, rather than to the complete numerical (cardinal) information about their preferences. This research agenda has successfully been applied to plethora of different settings, giving rise to a rich and vibrant line of work in major venues at the intersection of computer science and economics, For comprehensive overview, see the survey of Anshelevich et al. [2021].
Out of all of these scenarios, some of the most fundamental matching problems, in which agents are matched to items or other agents, aiming to maximize the social welfare of the matching (the total value of the agents). An example is the classic One-Sided Matching setting [Hylland and Zeckhauseri 1979]. where the goal is to match n items to agents based on the preferences of the agents over the items. For this setting, Frilos-Ratskas al. 2014 showed that the best achievable distortion is
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

@(vn). Importantly, this guarantee is only possible if one is allowed to use randomization and the values of the agents are normalized
Moving on from merely preference rankings, Amanatidis et al. 2021b] recently put forward the agenda of studying the tradeoffs between information and efficiency, when the employed mechanisms are equipped with the capability of learning the values of the agents via queries. The rationale is that asking the agents for more detailed information about only a few options is still cognitively not too burdensome, and could result in notable improvements on the distortion. This was indeed confirmed in that work for general social choice, and in follow-up work for several matching problems (Amanatidis et al., 2021a]. Specifically, the latter work shows that it is possible to obtain distortion ((n+/²) with Ollo m) queries per agent for any constant integer k, and distortion (11) with (log" 2 n) queries per agent. Crucially, the mechanisms achieving these bounds do not use randomization nor demand the values to be normalized.
While these works make a significant first step, they leave some important questions unanswered. The mechanisms they propose require logarithmic number of queries to achieve any significant improvement. Answering that many queries might still be cognitively too demanding for the agents, especially when there is a large number of possible options. The main high-level motivation of this research agenda, from our perspective, is that a small amount of information can be more valuable than randomization. But what does really constitute "small amount"? Ideally, we would like to design mechanisms that make only a few queries per agent, independently of the size of the input parameters. Since with a single query, sub-linear distortion bounds are not possible (Amanatidis) ct al. b) the first fundamental question that we would like to answer is the following:
What is the best achievable distortion when we can only ask two queries per agent?
1.1 Results and Technical Overview
We settle the aforementioned question for several matching problems, including One-Sided Matching, Two-Sided Matching, General Graph Matching, and other more general graph-theoretic problems. For all matching problems considered, we show that there is a deterministic mechanism that makes two queries per agent, runs in polynomial time, and achieves a distortion of O( This upper bound is based on a novel mechanism, which we call MATCH- MATCH-TWOQURRISS in the case of One- Sided Matching (see Mechanism [] The mechanism asks two queries per agent and computes maximum-weit wweghtt matching based of the revealed values due to these queries. starts by querying the agents at the first position of their preference rankings. For the second query, it computes a certain type of assignment A of agents to items (or agents to agents in more general matching problems), to which we refer are assigned to in A. The existence of such an assignment for instances is far from trivial, and one of our main technical contributions is to show its existence and efficient computation for the wide range of problems we consider.
sufficiently representative assignment, and queries the agents about the items they
We also show that no deterministic mechanism for these settings that makes two queries per agent can achieve distortion better than 12( (n) This lower bound follows by a more general construction yielding a lower bound of ((n1/A) on the distortion of any mechanism that makes a constant number A of queries for any of these mechanisms. This mirrors the corresponding lower bounds of Amanntiiss et al. [0211a] for One-Sided Matching.
While our results apply to general matching settings, their most impressive implications are for One- Sided Matching: We show that by using only two cardinal queries per agent, we can match the bound of (v))) for purely ordinal mechanisms, without requiring randomization or any normalization. MATCH-TWOQUERIES clearly also outperforms another mechanism of Amanntiis et al.) [2021a]. which uses two queries and achieves distortion of ( 3/ /log n.) assuming that the values of each agent sum up to 1. In contrast, our mechanism works for unrestricted values, and achieves the best possible distortion of O(yn) based on conceptually much simpler ideas.
Results for general social choice. Given that our approach works for wide variety of matching problems, one might be curious as to whether similar arguments could be used to show bounds for
Note that if any of these assumptions is relaxed, it is impossible to achieve sub- linear distortion using only ordinal information.

---

the general social choice setting, where n agents have preferences over m alternatives, and the goal is to select an alternative with high social welfare: this was after all the original setting that Amanatidis tradeoff research agenda. In
et al. [021b) studied in the introduction of the informatioondistortiiii this setting, the situation quite similar: the upper bounds follow by mechanisms that ask O(log m) queries, and nothing positive is known for smaller numbers of queries.
We show that mechanism with structure similar to that of MATCI- TWOQUERIES can indeed achieve distortion of O( O(ym) using only two queries, subject to being able to compute a sufficiently representative set of alternatives, which is analogous of the sufficiently representative assignment in matching problems. It turns out that this property is very closely connected to the notion of an (approximately) stable committee (Jiang et al., 2020, Cheng et al. [020]] and it follows that exists when m = (m)). thus allowing us to obtain the desired bound of (((m) when this is true. This case quite natural, as it captures instances where a group of people need to decide over a large set of possible options (e.g., shortlisting candidates for job, deciding the best paper for conference, etc.). Interestingly, in contrast to the matching setting for which we show that sufficiently representative assignments can be found via a simple greedy algorithm, computing sufficiently representative sets of alternatives in general social choice requires rather involved techniques [Jiang et al. 2020 Cheng et al. 2020). An obvious open question here is whether the O(v (())) bound can also be achieved by asking only two queries when m = o(n). This seems to be a more challenging task to prove; we discuss it further in Section
We also show that the bound of ((ym) is the best possible, as part of a more general distortion lower bound of 1/mm for mechanisms that make a constant number À of queries per agent; the latter result significantly improves the previously known lower bound of 2m 12(x+++)))))) [Amanatidis)
et al. 2021b
Roadmap. For the sake of presentation, we fully demonstrate how our methodology works for the One-Sided Matching problem in Section [3] Before doing so, we start with some necessary notation and terminology in Section 2 In Section 4 we briefly discuss other graph-theoretic problems for which our methodology can be applied; all missing details are presented in the full version [Amanatidis et al.) 2022]. Our results for general social choice are presented in Section 5 again, the detailed proofs are deferred to the full version. We conclude with some interesting open problems in Section
1.2 Additional Related Work
The literature on the distortion of ordinal mechanisms in social choice is long and extensive, focusing primarily on settings with normalized utilities (e.g.. [Boutilier et al. 2015 Caragiannis et al.] 2017 Filos-Ratsikas et al. (2020). ). or with metric preferences (e.g.. |Anshelevich et al. [0088] Anshelevich and Postl| 2017 7, Gkatzelis et al., 2020)); see the survey Ansheeevichh et al. 2021] for detailed exposition. The distortion of mechanisms for OnedSi Matching and more general graph-theoretic problems has been studied in a series of works for a variety of preference models, but solcly with ordinal information (Anshelevich and Zhu 2018 Abramowitz and Anshelevich 2018 Anshelevich
and Zhu 2017 Anshelevich and Sekar 2016 Fillo---Rssiaann et al. 2014 Caragiannis et al.) 2016).
Besides the papers of Ammamaatis et al. [2021b the effect of limited cardinal information on the
distortion has also been studied in other works [Abramowitz et al.) 2019 Mandal et al.) 2019 2020 Benadè et al. 2021]. Mostly related to us is the paper of Ma et al. [2021] which considered the One-Sided Matching problem with different type of cardinal queries, and showed qualitatively similar results to Amanatidis et al. [2021a] for Pareto optimality (rather than social welfare).
Our upper bound for the general social choice setting makes use of the results of Cheng et al. (2020)
and Jiang et al. (2020) for (approximately) stable committees (see also Aziz et al. [201] 7 ); stable committee very similar to a representative set of alternatives in our terminology.
Cheng al.
(0200 showed that, while exactly stable committees do not always exist (Jiang et al., 2020 finding a random version of such committees, coined stable lotteries, always possible and can be done in polynomial time. Later on, Jiang et al.] (2020) showed that, via an intricate derandomization process, stable lotteries can yield approximately stable committees, where the approximation is a small multiplicative constant; for our purposes, this is sufficient. Interestingly, very recently, Ebadian jet al. (2022) used stable lotteries to construct a purely ordinal randomized social choice mechanism that achieves the best possible distortion under unit-sum normalized values.
3

---

2 Preliminaries on One-Sided Matching, Mechanisms, and Distortion
In One-Sided Matching, there is a set N of n agents and set A of items. Each agent E N has a value Vi,j for each item, j E A: we refer to the matrix v = (Vi.g JiE..JEA as the valuation profile. (one-sided) matching X - - each agent is matched to a different single item. Our goal is to choose a matching X to maximize the social welfare, defined as the total value of the agents for the items they have been matched to according to X: SW(Xlv) = our notation to SW(X) for the social welfare of matching X.
is a bijection from the set of agents to the set of items, i.e.,
Eien (t) Usually v is clear from the context, so we then simplify
As in most of the related literature, we assume that do not have access to the valuation profile of the agents. Instead, we have access to the ordinal preference >; of each agent i, which is derived from the values of the agent for the items, such that >-; b if Us,a 2 Vi,bi we refer to the vector >v= (HilieN as the ordinal profile of the agents.
A mechanism M in our setting operates as follows: It takes as input the ordinal profile > v of the agents. It then makes a number À 2 1 of queries per agent to learn part of the valuation profile. In particular, each agent is asked her value for at most À items. Given the answers to the queries, and also using the ordinal profile, M computes feasible solution (here a matching) M(>v).
In this paper we focus on mechanisms that make two queries per agent, i.e., = 2, and compute a solution of high social welfare. However, pinpointing an (approximately) optimal solution without having full access to the valuation profile of the agents can be quite challenging; the ordinal profile may be consistent with a huge number of different valuation profiles, even after the queries. Nevertheless. we aim to achieve the best asymptotic performance possible, as quantified by the notion of distortion.
Definition 1. The distortion of a mechanism M is the worst-case ratio (over the set V of all valuation profiles in instances with agents and items) between the optimal social welfare and the social welfare of the solution chosen by M:
maxxex SW(X
dist(M
sup VEV
SW(M(>u)\v)
where X is the set of all matchings between N and A.
3 An Optimal Two-Query Mechanism
In this section, we present a mechanism for One-Sided Matching that makes two queries per agent and achieves a distortion of ((vn). Due to the lower bound of ((n on the distortion of any mechanism that can make up to À queries per agent shown by Amanatidis et al. [2021a], our mechanism is asymptotically best possible when À = 2.
Without any normalization assumptions about the valuation functions, it is easy to see that a mecha- nism cannot have any guarantee unless it queries every agent about her favorite item. However, there are no obvious criteria suggesting how to use the second query. Before we present the details of our mechanism, we define a particular type of assignment of agents to items that will be critical for deciding where to make the second queries.
Definition 2. A many-to-one assignment A of agents to items (i.e., each agent is assigned to one item, but multiple agents may be assigned to the same item) is a sufficiently representative assignment (a) For every item j E A, there are at most /n agents assigned to j: (b) For any matching X. there are at most /n agents that prefer the item they matched to in X to the item they are assigned to in A.
A natural question at this point is whether sufficiently representative assignment exists for any instance, and if so, whether it can be efficiently computed. In Section 3.2 we present a simple polynomial-time algorithm for this task.
3.1 The Mechanism
Our mechanism MATCH-TWOQUFRIIS (Mechanism T first queries every agent about her favorite item. Next, it computes a sufficiently representative assignment A (see Section 3.2) and queries each

---

agent about the item she is assigned to in A. Finally, it outputs a matching that maximizes the social welfare based only on the revealed values (all other values are set to 0). Although computational efficiency is not our primary focus here, if we use polynomial-time algorithm for computing maximum weight matching (e.g., the Hungarian method [Kuhn] 1956)), MATCH-TWOQUERIES runs in polynomial time as well.
Mechanism 1 M TWOQUERIES(N A,
1: Query each i N about her favorite item w.r.t. >;
2: Compute a sufficiently representative assignment A
3: Query each agent about the item she is assigned to in A
4: Set all non-revealed values to 0
5: return maximum-weigh perfect matching Y
Of course, if we compare the mechanism's 's behaviour to an actual optimal matching X, we expect to see that we asked agents about the "wrong" items most of the time: for many agents the second query is about better items than what they are matched to in X, and for many agents it is about worse items. MATCH-TWOQQUEE
The desired bound of ( (V))) on the distortion the loss due to each of these two cases.
established by balancing
Theorem 1. MATCH-TWOQUERR
has distortion O(yn).
Proof. Consider any instance with valuation profile Let Y be the matching computed by the MATCH-TWOQUERIN TWOQUERIES mechanism when given as input the ordinal profile >v, and let X be an optimal matching. Let SW (YY be the revealed social welfare of Y, i..., the total value of the agents for the items they are matched to in and for which they were queried about. We will show that SW(X) < (1 + 2/m). SW (Y), ), and then the fact that SW(Y) SW (Y) directly get the desired bound on the distortion.
We can write the optimal social welfare
SW(X) = (X)(X) + SWa(X).
where SW sWR(X) is the revealed social welfare of X that takes into consideration only the values revealed by the queries, whereas SWa(X) is the concealed social welfare of X that takes into consideration only the values not revealed by any queries. Since Y is the matching that maximizes the social welfare based only on the revealed values, we have that
SW (X) S SW)(Y).
To bound the quantity SWc(X), let be the set of agents who are not queried about the items they are matched to in X. We partition S' into the following two subsets consisting of agents for whom the second query of the mechanism is used to ask about items that the agents consider better or worse than the items they are matched to in X. Recall that agent is queried about the item A(i) she is assigned to according to the sufficiently representative assignment A. So, is partitioned into
$2 = {i E S A() 2 v, and s =
=fi E S (2,((1) < v1
Given these sets, we can now write
SWo(X) = SWE + (X),
where
SW2(X)= = Σ (i,(())
iESs
and
SWE(X) Σ (1,((()-
iE8
For every item j. let 87 (i S2 A(i) j} be the set of all agents in S2 that are queried about j by the mechanism using the second query. Thus, s² = U,eA S7. Since A is sufficiently
5

---

representative assignment, | S vn for every item j. Therefore,
(X)
SW
(1) S
Vi
jEA E
JEA iES?
1 Σ |
max Vij S Vn
Σ
max Ui
jEA
iES;
jEA
KESj
S Vn- (Y).
For the last inequality, recall that A assigns every agent to single item, and thus the sets Sf are disjoint. In addition, the values of all the agents for the items they are matched to according to A are revealed by the second query of the mechanism. Since we can match the agent in S that has the maximum value for j to j. and Y maximizes the social welfare based on the revealed values, we obtain that SW (Y) 2 ΣJEA max, Vi.j-
Next consider the quantity SX) By the fact that a sufficiently representative assignment, follows that |8*| < vn: otherwise X would constitute a matching for which there are strictly more than v agents that prefer the item they are matched in X to the item they are assigned by A. Combined with the fact that all agents are queried at the first position of their ordinal preferences, we obtain
SW
Σ (()((()
Σ
JEA
iES
SES
S |S
max max Vi. iES JEA
S vn SW (Y).
(3)
The bound follows directly by
and
3.2 Computing Sufficiently Representative Assignments
To establish the correctness of MATCH- TWOQURRTO,,,,,SS, need to ensure that sufficiently rep- resentative assignment exists for any ordinal profile and that it can be computed efficiently. For this we present simple polynomial time algorithm, which call Vn-SERIAL DICTATORSHIP (Mechanism 2). This algorithm creates /n copies each item and then runs serial dictatorship algorithm, which first fixes an ordering of the agents and then assigns each agent to her most pre- ferred available item according to her ordinal preference. It is easy to see that the running time of VTI-SERIAL DICTATORSIIIP polynomial (in particular, it is O
Mechanism 2 /n-SERIAL DICTATORSHIPW,AA.>>>
1: Let B be multiset containing vn copies of each j E A
2: for every agent i E V do
3: Let o; be most preferred item of agent i in B
4: Remove a; from B
5: end for
6: return A = (ass)seN
Theorem 2. For any instance, the output of Vn-SERIAL DICTATORSHIP is sufficiently representa- tive assignment.
Proof. Let A be the output of the algorithm. During the execution of the algorithm, whenever every copy of an item has been assigned, we say that such an item is exhausted. Assume, towards contradiction, that A is not a sufficiently representative assignment. By construction, every item assigned to at most vn agents, so there must be matching violating the second condition of 2 That is, there is subset of items A' and subset of agents A², such that [A'| = I > /n, and each agent A prefers to be assigned to a distinct item 3, E A' (i.e., B. + 3g for i + j) instead of the item she is assigned to in A.

---

Consider any agent i E N" The fact that this agent was not assigned to B, by the algorithm implies that when the agent was picked. item 3, was exhausted. Since this true for all agents in A at the end of the algorithm all items of 'A' must be exhausted. However, an item is exhausted when all its v copies have been assigned and there are n agents in total, so we can only have as many as n/ /n vn exhausted items. This means that |A|| I vn, contradiction.
L
Further Combinatorial Optimization Problems
The approach of Section 3 can extended to a much broader class of graph-theoret problems. Informally, it works when the objective is to maximize an additive function over subgraphs of a given graph which contain all "small" matchings and have constant maximum degree. To make things more concrete, given constant & N and weighted graph G' on n nodes, say that a family F of subgraphs of G is a matching extending k-family if:
Graphs in F have maximum degree at most
For any matching M of G of size at most [n/3k]] there is a graph in F containing M.
Clearly, the set of matchings of graph is matching extending 1-family, but it not hard to see that different constraints are also captured, e.g., the set of subgraphs that are unions of disjoint paths and even cycles is a matching extending 2-family.
We are ready to introduce the general problem that we tackle here. As this is a special case of the class of problems captured by Martul--a-oo-n--nrea (introduced by Amanatidis al. (202Ia)) we use a similar formulation and name.
Fix a constant l E N and let A be set of agents. Every agent i E N has a (private) valuation function e; : / + Rgo- We are given a graph G = (W, E). an ordinal profile > v= (> s)Ee consistent with extending k-family F. The goal is to find some H E F that maximizes ((.))e (i)
Ordinal-k-
(et)ie,, and concise description of a matching
Besides Ine-Sided Matching, a large number of problems that are relevant to computational social choice are captured by Drdinal-k-Max-on Max-on-Graphs.. Graphs. We give few examples:
General Graph k-Matching: Given a graph G, find k-matching of maximum value, i.c., F contains the subgraphs of G of maximum degree at most & and is matching extending k-family. The problem becomes the General Graph Matching problem when k = 1; by also assuming that G is bipartite. we have the celebrated Two-Sided Matching problem Gale and Shapley 1962. Roth and Sotomayor 1992].
k- d-Constrained Resource Allocation: Given a bipartite graph G = (Ni U22 E), assign at most k nodes of N2 to each node in N₁ so that the total value of the corresponding edges is maximized. That is, F contains all 1-to-k matchings of G and is again matching extending k-family. The problem for k 1 becomes One-Sided Matching, Here N is partitioned into the set N of "actual agents" and the Set No2 of "items", and v. (i) can be strictly positive only for i E Ni.j E N2.
Short Cycle Packing: Given integer E and weighted complete graph G, find collection of node-disjoint cycles of length at most l so that their total weight is maximized. Here, F is a matching extending 3-family (note that k = 2 for any E). It is worth mentioning that Short Cycle Packing is not a generalization of any of the matching problems above. It is also closely related to Clearing Kidney
(-Exchanges [Abrhhmm al. 2007].
It is straightforward to extend the notion of distortion (Definition I for Medinal---Max-on ---Max-onGrraphs -nnGrrpphs by taking the supremum over all instances of a certain size and letting X' be the set of feasible solutions of each instance.
As already discussed, for One-Sided Matching there is a lower bound of 2(n 1/A) on the distortion of deterministic mechanisms that make up to A queries per agent [Amanatidis et al. [021aa. We can get the analogous result for any problem captured by Ordinal-k-Max-oo on-Graphs using reduction that preserves distortion up to a constant factor. Further, by appropriately using the ideas of Section 3 we show that this lower bound is asymptotically tight for the case of two queries. For the statements of the theorems below, we assume that E N is constant and that for every (general bipartite) graph G, matching extending k- k-family F(G) is specified.
7

---

Theorem 3.
No deterministic mechanism using at most X 2 1 queries per agent can achieve distortion better than /2(n'/A) for Ordinal-k: -aalll---a------ M-a-MMax----aeeee on-Graphs.
For the positive result below, we rely on the existence of generalization of sufficiently representative assignments. While the construction is very similar, the counting argument here less intuitive compared to the case of One-Sided Matching.
Theorem 4. There is deterministic mechanism for Ordinal-k-Max-one two queries per agent and has distortion O (()n).
which uses most
Our mechanisms run in polynomial time whenever there is polynomial-time algorithm for the full information version of the corresponding optimization problem. Luckily, all variants of matching problems we presented above can be solved efficiently by Edmond's algorithm [Edmonds, [965] or its extensions [Marsh III 1979].
Corollary 5. There are deterministic polynomial-time mechanisms for General Graph Matching, Two-Sided Matching, General Graph k-Matching, and k- Constrained Resource Allocation which all at most two queries per agent and have distortion (VT)).
Towards Tight Bounds for General Social Choice
Here we consider the general social choice setting where a set N of agents have preferences over set A of m alternatives. As in the One-Sided Matching problem, there is valuation profile v == (et.)) specifying the non-negative value that each agent has for every alternative j- The goal is to choose single alternative r E A to maximize the social welfare, that is, the total value of the agents for æ: SW(xlv) = -iee Vi... Again, when v is clear from context, we will drop from notation. Similarly to One-Sided Matching and the problems discussed in the previous section, unknown, and we are only given access to the ordinal profile >v that is induced by v. Social choice mechanisms must decide single alternative based only > and the values they can learn by making a small number of queries. The notion of distortion (Definition]] I can be extended for this setting well, by taking the supremum over all instances with agents and alternatives, and letting X' be the set A of alternatives.
For this general social choice setting, Amanatidis et al. 2021b showed lower bound of Ω (m²/(2(x+1)) on the distortion of mechanisms that make at most À 2 1 queries per agent. We improve this result by showing lower bound of ((m2/A) for any constant x. The full proof of the following theorem can be found the full version.
Theorem 6. In the social choice setting, the distortion of any deterministic mechanism that makes at most a constant number X 2 1 of queries per agent is 0mml/A)
Proof sketch. Let M be an arbitrary mechanism that makes at most À > queries per agent. Consider the following instance with n agents and m n alternatives. We assume that m satisfies the condition (1-411//A + 2, and also that is superconstant; otherwise the theorem holds trivially. m 2 Σ²_ m
We partition the set of alternatives A into X + 2 sets A₁ Ag, Axt1, Axt2, such that
Arl (m for l [A]:
Axt1l = 2;
|Ax22 = m -/2 E m (A-e11//A - 2.
The ordinal profile has the following properties:
For every E [A + 1), each alternative E A is ranked position by a set Ty of θ (m agents.
For every E [}], every pair of agents that rank the same alternative A at position e, rank the same alternative in A at position E ++ 1.
8

---

For every agent, the alternatives that she does not rank in the first X + positions are ranked arbitrarily from position À + m.
For every agent i, query of M for alternative j reveals a value of mn </> if ranks j at position l E [} + I], and value of 0 if i ranks j at any other position.
Let y be the alternative that M chooses as the winner for this instance. No matter the choice of y. we will define the cardinal profile so that it is consistent to the information revealed by the queries of M, and the values of the agents for alternative y are also consistent the information that would have been revealed, irrespective of whether those values have actually been revealed. That is, any agent has a value of m m- for if she ranks at position E [A+1], and a value of O if she ranks at any other position. Hence, the social welfare of is θ (m({-1)/>) m ee/A = (mm-1/) if y E A, for E [A+ IJ. or of E Ax+2. Consequently, to show the desired bound of (mm-/AA on the distortion of M. it suffices to assume that y E Ag for some E [A + 1J, and prove that the values the agents that have not been revealed and do not correspond to alternative y can always be defined such that there exists an alternative x * y with social welfare ((1). The remaining details showing that such an x always exists can be found in the full version.
Our approach for all the problems discussed in the previous sections can also be applied the much more general social choice setting, subject to being able to compute a particular set of alternatives.
Definition 3. Let e 2 1 be any constant. A subset of alternatives B S A with |B] S c. vm is a sufficientll representative set if, for every alternative E A, at most /m agents prefer j over their favorite alternative in B.
We now present a mechanism that works under the assumption that sufficiently representative sets of alternatives can be (efficiently) computed; we discuss this assumption right after the statement of Theorem
Mechanism 3 SC-TWOQUERIESSA" A,
1: Query each agent about her favorite alternative
2: Compute sufficiently representative set B
3: Query each agent for her favorite alternative in B
4: For every j E A. compute the revealed welfare SW R())
5: return E arg maxzeA (()))
In particular, SC- SC-TROQUERIES (Mechanism B first queries each agent about her overall favorite alternative (the one ranked first). Then, given a sufficiently representative set of alternatives B, it queries each agent for her favorite alternative in B. Given the answers to these two queries per agent, the mechanism outputs an alternative that maximizes the revealed social welfare which is based only on the values learned from the queries.
Theorem 7.
The mechanism SC-EROQUE has distortion O( when restricted to the social choice instances for which sufficiently representative set of alternatives exists.
sufficiently representative set of alternatives trivially exists when m is much larger than n (namely, when 2(n")) )). In contrast, when is much smaller than n. sufficiently representative sets of alternatives do not always exist
2 Jiang et al. (2020) showed the following useful result:
Theorem (Jiang et al. 2020 ). For any & E [n], there exists a set S of alternatives with (S) s 16 n/Ê such that for every E A, there are at most agents that prefer j over their favorite alternative in S.
A set S in the theorem above is called an approximately stable committee Cheng et (2020). Jiang et al. 22000). Clearly, when m 2(n) and & = VT., an approximately stable committee is also
FFor example, for any k y m, consider an instance with n k m! agents, such that for each possible ordering of the m alternatives there are exactly it agents that have as their preference. Then, for any subset B of at most /mn alternatives and any alternative j E .AY \ B, there are at least A > /m agents that prefer j over any alternative in B.

---

a sufficiently representative set with c = 16. Therefore, combining Theorems 7 following.
and 8
we obtain the
Corollary 9. When m 2(n), SC-TROQUERIES has distortion O(ym).
6
Conclusion and Open Problems
In this paper, we showed that for a large class of problems, which includes One-Sided Matching and many other well-studied graph-theoretic problems, it is possible to achieve distortion of ((yn) using a deterministic mechanism that makes at most two queries per agent, and that this is best possible asymptotically. Our whole methodology is based on computing assignments of agents to items or other agents that exhibit a very particular structure. In addition, in the social choice setting, when = [()), sets of alternatives with analogous properties can be computed, and methodology yields two-query mechanism with best possible distortion for this setting as well.
It is an interesting open problem to design a mechanism that makes two queries and achieves the best possible distortion of m(ym) when m = o(n), or show that this is impossible. We suspect that to obtain positive result would need to come up with an adaptive mechanism, which decides where to ask each query based on the answers to all previous ones. Another question, about any of the problems
considered, is whether one can design mechanisms that make at most constant
x 2 queries per agent and their distortion matches the lower bound of [( (or, in the case of social choice, ((m)/A)).
Acknowledgments and Disclosure of Funding
This work was supported by the ERC Advanced Grant 788893 AMDROMA "Algorithmic and Mech- anism Design Research in Online Markets", the MIUR PRIN project ALGADIMAR "Algorithms, Games, and Digital Markets", and the NWO Veni project No. VI. Veni. 192.153.
References
David J. Abraham, Avrim Blum, and Tuomas Sandholm. Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM conference on Electronic commerce (EC). pages 295 304, 2007.
Ben Abramowitz and Elliot Anshelevich. Utilitarians without utilities: Maximizing social welfare for graph problems using only ordinal preferences. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pages 004-900,222 2018.
Ben Abramowitz, Elliot Anshelevich, and Wennan Zhu. Awareness of voter passion greatly improves the distortion of metric social choice. In Proceedings of the The 15th Conference on Web and Internet Economics (WINE), pages 3-16, 2019.
Georgios Amanatidis, Georgios Birmpas, Aris FllssRaasiias,, and Alexandros A. Voudouris. A few queries go long way: Information-distoriio tradeoffs in matching. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5078-5085, 10
Georgios Amanatidis, Georgios Birmpas, Aris
and Alexandros A. Voudouris. Peeking behind the ordinal curtain: Improving distortion via cardinal queries. Artificial Intelligence, 296: 103488, 2021b.
Georgios Amanatidis, Georgios Birmpas, Aris Eilos-Ratsikas. and Alexandros A Voudouris. Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond, arXiv preprint arXiv:2203.01872 2022.
Elliot Anshelevich and John Postl. Randomized social choice functions under metric preferences. Journal of Artificial Intelligence Research, 58:797-827, 2017.
Elliot Anshelevich and Shreyas Sekar. Blind, greedy, and random: Algorithms for matching and clustering using only ordinal information. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pages 390-396, 2016.
10

---

Elliot Anshelevich and Wennan Zhu. Tradeoffs between information and ordinal approximation for bipartite matching. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT), pages 267-279, 2017.
Elliot Anshelevich and Wennan Zhu. Ordinal approximation for social choice, matching, and facility location problems given candidate positions. In Proceedings of the 14th International Conference on Web and Internet Economics ( (WINE). pages 3-20, 2018.
Elliot Anshelevich, Onkar Bhardwaj. Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264:27-51, 2018.
Elliot Anshelevich, Aris Filos- aats-Raasiiaas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in social choice problems: The first 15 years and beyond. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAT), pages 4294-3301 2021.
Haris Aziz, Edith Elkind, Piotr Faliszewski, Martin Lackner, and Piotr Skowron. The condorcet principle for multiwinner elections: from shortlisting to proportionality. Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 84-90, 2017.
Gerdus Benadè, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813-287) 2021.
Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: utilitarian view. Artificial Intelligence, 227:190-21 213, 2015.
Ioannis Caragiannis, Aris Elos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Kristoffer Arnsfelt Hansen, and Zihan Tan. Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship. In International Conference on Web and Internet Economics (WINE), pages 236-250, 2016.
Ioannis Caragiannis, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58:123-152, 2017.
Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang. Group faimesss in committee selection. ACM Transactions Economics and Computation (TEAC), 8(4):1-18, 2020.
Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized distortion and proportional fairness in voting. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022.
Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 130):55-555 1965.
Aris Filos-Ratsikas. Spren Kristoffer Stiil Frederiksen, and Jie Zhang. Social welfare in one-sided matchings: Random priority and beyond. In Proceedings of the 7th Symposium of Algorithmic Game Theory (SAGT), pages 1-12, 2014.
Aris Filos-Ratsikas, Evi Micha, and Alexandros A. Voudouris. The distortion of distributed voting. Artificial Intelligence, 286: 103343, 2020.
David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 6951 1962.
Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah, Resolving the optimal metric distortion conjecture. In Proceedings of the 61 Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1427-1438, 2020.
Aanund Hylland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political economy, 87(2):293-314, 1979.
Zhihao Jiang, Kamesh Munagala, and Kangning Wang. Approximately stable committee selection. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 463-472, 2020.
11

---

Harold W. Kuhn. Variants of the Hungarian method for assignment problems. Naval Research Logistics Quarterly, 3(4):253-258, 1956.
Thomas Ma, Vijay Menon, and Kate Larson. Improving welfare one-sided matchings using simple threshold queries. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. IJCAI 2021, pages 321-327, 2021.
Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, and David P. Woodruff. Efficient and thrifty voting by any means necessary. In Proceedings of the 33rd Conference Neural Information Processing Systems (NeurIPS), pages 7178-7189, 2019.
Debmalya Mandal, Nisarg Shah, and David P Woodruff. Optimal communication- tradeoff in voting. Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 2020.
Alfred Burton Marsh III. Matching algorithms. The Johns Hopkins University, 1979.
Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting, In International Workshop on Cooperative Information Agents (CIA), pages 317-331, 2006.
Alvin E. Roth and Marilda Sotomayor. Two-sided matching. Handbook of Game Theory with Economic Applications, volume I, chapter 16, pages 485 -85-541, Elsevier, 1992.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Due space limitations some proofs have been included in the supplementary material rather than in the main paper.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "p019MdJakZV", "reviewer": "Reviewer_p557", "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.\n", "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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS\n\nS1. 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).\n\nS2. 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\n\nS3. Presentation/Soundness/Related Work: The work is well-written, seems to substantiate all claims (very extensive supplementary material) and cover the relevant related work.\n\nS4. The work discusses a wider range of variants and both possibility results as well as achieved results.\n\nWEAKNESSES\n\nW1. An empirical study could make the paper more relevant to more practically oriented readers.\n\nW2. Although it would seem to be general enough to cover a wider range of applications, some examples for practical applications could be beneficial\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["Discrimination / Bias / Fairness Concerns"]}, "extra_text": {}}, {"review_id": "eT6KoIbpT0Q", "reviewer": "Reviewer_WLMQ", "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).\nBased on the solution to this problem further statements are derived.", "questions": "none", "limitations": "While the paper offers clear progress wrt underlying theory, \nthe paper could have discussed practical applications and applicability at least briefly.\n\n", "rating": 4, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Novel algorithm and theorems about social welfare optimzation given additional queries\n+ Useful extensions beyond the core approach\nWeakness:\n+ 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.\n+ I don't see this as a relevant paper for a machine learning conference", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "e2y7RfIamp6", "reviewer": "Reviewer_NGwA", "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.\n\nThis 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?\n\nThis 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).\n\nIn 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.\n\nThey 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.\n\nFinally, 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)$.\n", "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.\n\n- 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?\n", "limitations": "This is a theory paper, so I think the discussion of limitations and negative social impact is sufficient.  \n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- 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.\n\n- 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.\n\n- 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.\n\nWeaknesses:\n- 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.\n\nOverall, I really liked this paper, and think it should be accepted.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ABdX79-eCXk", "reviewer": "Reviewer_B6to", "summary": "The authors propose a framework that approximates a matching problem using only two queries per agent.\nThe authors show that they can achieve O(sqrt(n)) approximation guarantee, and show that this is the best\nthey can do given the queries.", "questions": "The two queries algorithm is allowed to ask are very different. The first asks the most preferred item,\nwhile the second asks the utility of a certain item. How this compares to the existing work? How this extends\nto lambda > 2 queries.", "limitations": "The available information is so limited, that the algorithm cannot do much here. Essentially, the algorithm\nwill give the preferred option or a random choice. This hints that in practice two queries are too little\nto produce any interesting result. Perhaps developing an algoriithm for higher lambdas would be more fruitful.\n", "rating": 4, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ Theoretically interesting result. Especially the tightness result completes the picture.\n- The amount of information is so limited that the algorithm cannot  do too much.\n- Limited applications", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept