Improving Welfare in One-Sided Matchings using Simple Threshold Queries

1 Introduction

One-sided matching scenarios are ubiquitous in multiagent resource-allocation settings and have been well-studied, especially as the housing allocation or housing market problem both in economics [Shapley and Scarf, 1974; Hylland and Zeckhauser, 1979; Roth and Postlewaite, 1977; Abdulkadiro˘glu and S¨onmez, 1998; Abdulkadiro˘glu and S¨onmez, 1999; S¨onmez and ¨Unver, 2010] and in computer science [Abraham et al., 2004; Irving, 2004; Abraham et al., 2006; Filos-Ratsikas et al., 2014; Amanatidis et al., 2021]. Other examples include assigning faculty members to school committees, workers to tasks, etc.

Much of the literature assumes that agents have an acceptable set of objects and that they submit an (ordinal) preference order over this set. Given this, the standard objective is to come up with an assignment of objects to agents (i.e., a matching) that satisfies some desirable property like Pareto optimality [Shapley and Scarf, 1974; Abraham et al., 2004] or rank maximality [Irving, 2004; Irving et al., 2006].

∗Contact Author

Although matchings that satisfy such desirable properties are better than arbitrary ones, one key drawback is that they may not take into account agents' preference intensities. To illustrate this, consider the following simple example where there are three agents {a1, a2, a3} and three objects {o1, o2, o3}. Assume all agents agree that o1 is preferred to o2 which is preferred to o3, but have different preference intensities (i.e., cardinal utilities) for the objects. In particular, a1 and a2 assign utility 0.9 to o1 and 0.1 to o2 while a3 assigns utility 0.51 to a1 and 0.49 to o2. All agents assign zero utility for o3. If only ordinal preferences are considered then any matching is, for example, Pareto optimal. However, any matching that assigns o3 to a3 leads to significant loss in overall social welfare compared to other Pareto optimal matchings and so is, in some sense, less desirable.

The observation that there might be a loss in welfare due to ignoring preference intensities (henceforth, cardinal utilities) is not new, and in particular, has been a much debated issue surrounding various school-choice mechanisms ( [Abdulkadiro˘glu et al., 2011; Abdulkadiro˘glu et al., 2015]). This has also lead to proposals for new school choice mechanisms that ask agents to provide some extra information along with their ordinal preferences [Abdulkadiro˘glu et al., 2015]. Our work here is partially motivated by this line of work, but takes a more computational approach that is similar in style to the work that looks at distortion-which is essentially the cost of using only ordinal information-in various settings [Procaccia and Rosenschein, 2006; Boutilier et al., 2015; Anshelevich and Sekar, 2016; Anshelevich and Zhu, 2017; Goel et al., 2017; Abramowitz and Anshelevich, 2018].

Given a one-sided matching instance (the set of agents, objects, and agents' ordinal preferences), our goal is to find matchings that satisfy some particular property, say, X, while also accounting for agents' cardinal utilities. We accomplish this by designing algorithms that are guaranteed to return matchings that satisfy property X while also achieving a good approximation to the optimal welfare amongst all matchings that satisfy X. One way to achieve this is to ask agents to directly provide their cardinal utilities for objects. Such an approach, however, places a high burden on the agents themselves as they are required to articulate and communicate precise cardinal information. Instead we propose a middleground and use simple binary queries to elicit relevant information from agents. Our goal is to ask each agent a small number of such queries and return a matching that achieves a good approximation as described above.

In particular, we consider the following four wellstudied matching properties: Pareto optimal matchings, rankmaximal matchings, max-cardinality rank-maximal matchings, and fair matchings, and two rich cardinal utility models (unit-sum and unit-range valuations). We first explore adaptive algorithms-algorithms that are able to change their queries depending on how agents answer previous queriesand show how for each of the properties mentioned above and for any ϵ > 0, there is a deterministic algorithm that asks O(c logn) queries per agent, where c = ⌈ log(n2 ·1/ϵ) log (1+ϵ/2) ⌉, and returns a matching that achieves a (1 + ϵ)-approximation to the optimal welfare among all matchings that satisfy the property of interest. We then focus on non-adaptive algorithms which, we argue, have many practical advantages over adaptive algorithms, and explore what is possible to achieve in the special case where the algorithm is allowed at most one query per (agent, object) pair. Table 1 summarizes our results.

RelatedResearch. Motivation for our work is derived from the school choice problem which addresses the loss in welfare due to not taking preference intensities into account [Abdulkadiro˘glu et al., 2011; Abdulkadiro˘glu et al., 2015]. Our concern here is similar, but we take a computational approach, reminiscent to the work on distortion [Procaccia and Rosenschein, 2006; Anshelevich and Zhu, 2017; Abramowitz and Anshelevich, 2018]. However, unlike this body of work which aims to calculate the worst-case loss in welfare due to only having ordinal preferences, we assume that, in addition to ordinal preferences, it is also possible to obtain information about agents' cardinal utilities. This in turn is similar to an approach that has been explored in the voting context [Abramowitz et al., 2019; Amanatidis et al., 2020], and one-sided matching [Amanatidis et al., 2021]. While this latter work also looks at onesided matching, the objective is different with its focus on distortion, as opposed to finding "good" matchings satisfying certain properties. We also observe that the query models used differ (with ours being significantly weaker).

Our work is also related to the study of communication complexity of voting protocols [Mandal et al., 2020], to the work on participatory budgeting which compares different elicitation methods based on the distortion achieved ([Goel et al., 2019; Benade et al., 2020]), and is more broadly in line with the growing body of work that explicitly aims to make mechanisms or algorithms more robust, by either making use of coarse preference information [Chiesa et al., 2012; Chiesa et al., 2014; Menon and Larson, 2019], or by making sure that the algorithms designed produce solutions that work "well" (in the approximation sense) even under slightly modified inputs [Shiryaev et al., 2013; Bredereck et al., 2017; Menon and Larson, 2018; Chen et al., 2019].

2 Model

For k ∈ Z+, let [k] denote the set {1, . . . , k}. We use N, where |N| = n, to denote the set of agents {a1, . . . , an}, and H, where |H| = n, to denote the set of objects {h1, . . . , hn}.

We refer to ai as agent i and hj as object j. Every agent ai has a weak order, Pi, over a subset of objects Ai ⊆ H, where Ai, |Ai| ≥ 1, is the set of objects ai is willing to be matched to, the acceptable set of ai. We use P = (P1, . . . , Pn) to refer to the weak orders of all the agents in N and refer to P as the preference profile of the agents. For an agent ai, and for two objects hj, hk ∈ Ai, we use hj ≻i hk to denote that ai strictly prefers hj over hk, and use hj ⪰i hk to indicate that hj is either strictly preferred or considered to be equivalent to hk. We refer to I = (N,H,P = (P1, . . . , Pn)) as an instance, which encodes all the information about the agents, objects, and the agents' preferences, and use I to denote the set of all possible instances.

Given an instance I = (N,H,P), GI = (N ∪ H, E) is the induced bipartite graph with edges (ai, hj) ∈ E if hj ∈ Ai. We refer to e = (ai, hj) ∈ E as a rank-k edge if |Uij| = k - 1, where Uij = {hℓ ∈ Ai | hℓ ≻i hj}. We also use rank(ai, hj) to denote the k such that (ai, hj) is a rank-k edge and refer to an object hj as ai's rank-k object if rank(ai, hj ) = k.

We additionally assume that each agent ai has a cardinal utility function vi : H → [0, 1], which is consistent with the preference order Pi (meaning, h1 ⪰i h2 ⇔ vi(h1) ≥ vi(h2)); we assume that if h /∈ Ai, then vi(h) = 0. We use v = (v1, . . . , vn) to denote the valuation profile of agents and VI to denote the set of all possible valuation profiles that are consistent with the given preference profile in I. In this work we consider two specific classes of valuation functions;

Unit-sum valuations: For each agent i, vi is such that ∑h∈H vi(h) = 1.

Unit-range valuations: Agents are said to have unit-range valuations if for each agent i, there exists hj, hk ∈ Ai such that hj ≻i hk, and maxh∈Ai vi(h) = 1 and minh∈Ai vi(h) = 0. In words, the most preferred objects have value 1, the least preferred objects have value 0, and every other acceptable object has value between 0 and 1.

Note that information about the cardinal utilities is not part of an instance I. Given I, we are interested in matchings of agents to objects, namely bijections µ: N → H. For c ∈ N ∪H, we refer to µ(c) as c's partner in µ or as c's allocation in µ. Alternatively, a matching is also defined as a collection of edges µ in GI such that each vertex is part of at most one edge in µ. We use MGI to denote the set of all possible matchings in GI.

2.1 Pareto Optimal and Signature-Based Matchings

Although for a given instance there are several possible matchings, we are interested in matchings which also satisfy some additional desirable property. In particular, we consider the following well-studied properties: Pareto optimal matchings [Shapley and Scarf, 1974; Abraham et al., 2004], rankmaximal matchings [Irving, 2004; Irving et al., 2006], maxcardinality rank-maximal matchings [Mehlhorn and Michail, 2005; Abraham et al., 2006], and fair matchings [Mehlhorn and Michail, 2005; Huang et al., 2013]. The latter three are different ways to strengthen Pareto optimality and are together referred to as signature-based matchings.

Definition 1. Given an instance I = (N, H, P), a matching µ ∈MGI is Pareto optimal (PO) w.r.t. I if ∀µ′ ∈MGI

Definition 2. Given an instance I = (N,H,P), and a matching µ ∈ MGI , let si denote the number of agents that are matched to a rank-i edge in µ. Then, µ is

• rank-maximal if µ maximizes the number of agents who are matched to a rank-1 edge and, subject to that, it maximizes the number of agents who are matched to rank-2 edges, and so on. Formally, for each µ′ inMGI define its signature to be the n-tuple sµ′ = (s1, . . . , sn). Then µ is the matching with the lexicographically optimal signature.
• max-cardinality rank-maximal if µ is a maximum cardinality matching and, subject to that, is also rankmaximal. Formally, for each µ′ inMGI define its signature to be the (n+1)-tuple (∑ni=1 si, s1, . . . , sn). Then µ is the matching with the lexicographically optimal signature.
• fair if µ is a maximum cardinality matching and, subject to that, minimizes the number of agents who are matched to a rank-n edge and, subject to that, minimizes the number of agents who are matched to a rank-(n - 1) edge, and so on. Formally, for each µ′ in MGI define its signature to be the (n + 1)-tuple (∑ni=1 si, -sn, -sn-1, . . . , -s1). Then µ is the matching with the lexicographically optimal signature.

Signature-based matchings can be reduced to an instance of the following problem, which we refer to as priority-p matchings, for a given p = (p1, · · · , pn) [Irving, 2004; Irving et al., 2006; Mehlhorn and Michail, 2005; Huang et al., 2013; Michail, 2007].

Definition 3. Given an instance I = (N,H,P = (P1, . . . , Pn)) and a priority vector p = (p1, . . . , pn), where

∀i ∈ [n], pi ∈ Z≥0 and ∃j, k ∈ [n] such that pj ̸= pk, a matching µ ∈ MGI is said to be a priority-p matching if µ is a matching of maximum weight in MGI , where a rank-r edge in GI is assigned the weight pr.

In particular, given an instance I, we can show that, 1

• when pj = n2(n-j+1) for all j ∈ [n], a matching is a priority-p matching if and only if it is rank-maximal matching w.r.t. I.
• when pj = n2n +n2(n-j) for all j ∈ [n], a matching is a priority-p matching if and only if it is a max-cardinality rank-maximal matching w.r.t. I.
• when pj = 4n2n - 2nj-1 for all j ∈ [n], a matching is a priority-p matching if and only if it is a fair matching w.r.t. I.

For ease of exposition, we sometimes use priority-p, where pi = 0 for all i ∈ [n] to refer to Pareto optimal matchings. Note that this is purely for notational convenience since the algorithms we discuss in the context of Pareto optimal matchings are extensions to the ones for priority-p matchings. We also use P to denote the set of priority vectors of interest.

2.2 Worst-CaseWelfare Lost

Given an instance I, we are interested in deterministic algorithms which return a matching that satisfies one of the properties just defined. However, such matchings may not be unique. We argue that a principled way of selecting amongst all such matchings is to consider the cardinal utilities of the agents, returning a matching with small worst-case welfare loss. Formally, for an instance I, consider the set of matchings S ⊆ MGI such that S is the set of all Pareto optimal/rank-maximal/max-cardinality rankmaximal/fair matchings in GI. Next, for a matching µ ∈ S, v ∈ VI, and for an edge e = (ai, hj) ∈ µ, let value(e) =

1 The proof of this can be found in the full version of the paper (arXiv:2011.13977).

Algorithm 1 Welfare Optimal Priority-p Matching

1: Input: I = (N,H,P), priorities p = (p1, . . . , pn), and v = (v1, . . . , vn), where vi : H → [0, 1] 2: Output: welfare-optimal priority-p matching w.r.t. I 3: GI = (N ∪ H, E) ← graph induced by I 4: for e = (ai, hj) ∈ E do 5: r ← rank(ai, hj) 6: we ← pr + vi(hj) 7: end for 8: µ ←max-weight matching in GI with weights {we}e∈E 9: return µ

vi(hj) and SW(µ | v) = ∑e∈µ value(e), the social welfare of µ given the valuations v. 2 Given this, consider a deterministic algorithm A where, for all I ∈ I, A(I) ∈ S and let L(A), which we refer to as the worst-case welfare loss of A, be defined as L(A) := maxI∈I L(A, I), where

The objective is to design algorithms that return a matching with the desired property and minimize L(A). Throughout this paper, we say that, for an α ≥ 1, an algorithm A achieves an α-approximation to the optimal social welfare among Pareto-optimal/rank-maximal/max-cardinality rankmaximal/fair matchings if L(A) ≤ α.

We first observe that any purely ordinal algorithm, that is an algorithm that uses only the ordinal preferences of the agents, performs poorly with respect to worst-case welfare loss. Due to space limitations all proofs are in the full version (arXiv:2011.13977).

Theorem 1. Let X denote one of the properties in the set {Pareto-optimal, rank-maximal, max-cardinality rankmaximal, and fair}. Let A be a deterministic ordinal algorithm that always produces a matching that satisfies property X. If there are n agents with unit-sum valuation functions, then L(A) ∈ Ω(n2 ). If there are n agents with unit-range valuation functions then L(A) ∈ Ω(n). Moreover, these bounds are asymptotically tight.

At the other extreme, an algorithm may have access to all utility information from the agents and, thus, is capable of returning the welfare-optimal matching subject to the underlying desired property. In particular, given an instance I = (N,H,P) and valuation functions of the agents v = (v1, . . . , vn), where vi : H → [0, 1], the welfare-optimal priority-p problem is to find a matching of maximum welfare among the set of priority-p matchings. We observe that this reduces to an instance of the max-weight matching problem on GI .

Theorem 2. Given an instance I = (N,H,P), a vector of priorities p = (p1, . . . , pn), where p ∈ P, and v = (v1, . . . , vn), where vi : H → [0, 1], Algorithm 1 returns a welfare-optimal priority-p matching w.r.t. I.

2 For notational convenience, when v is clear from the context, we just write SW(µ) instead of SW(µ | v).

3 Binary Threshold Queries

In this section we look at the central question of this paper: How can one improve social welfare in one-sided matching problems by asking only a small number of queries? We believe that asking directly for cardinal utility information places a high cognitive burden on agents. Therefore, we aim for a middle-ground between solely ordinal and fully cardinal algorithms. We do this by analysing the power of using very simple queries, namely binary threshold queries.

Definition 4. For an agent ai, object hj, and a real number tk ∈ [0, 1], a binary threshold query, Q(ai, hj, tk), asks agent ai to return 1 (alternatively, asks them to say "Yes") if vi(hj) ≥ tk, and 0 (alternatively, asks them to say "No") otherwise.

Given an instance I and answers to a certain number of binary threshold queries, our goal is to design deterministic algorithms A that minimize the worst-case welfare loss L(A) and, for all I ∈ I, produces a matching in S (i.e., A(I) ∈ S), where S is the set of all Pareto optimal/rank-maximal/maxcardinality rank-maximal/fair matchings in GI. Towards this end, we begin by considering adaptive algorithmsalgorithms that are allowed to change its queries based on the agents' responses-and show how, when considering each of the four properties of interest, one can obtain a (1 + ϵ)- approximation to the optimal welfare. Following this, we look at, what we believe is the more interesting and practical, case of non-adaptive algorithms. In particular, we restrict ourselves to algorithms that can ask at most one query per (agent, object) pair and show upper and lower bounds on the approximation achievable. Unless explicitly specified, all results hold for both unit-sum and unit-range valuations.

3.1 Adaptive Algorithm to Achieve (1 + ϵ)-Approximation

Given an instance I and a property encoded as a priorityvector. Algorithm 2 returns a matching with the desired property. The high-level idea behind the algorithm is straightforward. For a specific choice of parameter c, it associates a partition of objects with every agent, where for k ∈ [c], an object is in Eik if agent ai's value for the object is within some defined interval Bk. Using these partitions, carefully computed weights are assigned to the edges in the induced bipartite graph, GI. A max-weight matching on the resulting weighted graph is then computed. Below we show for c = ⌈ log(n2 ·1/ϵ) log (1+ϵ/2) ⌉, this results in an (1 + ϵ)-approximation algorithm that uses O(c logn) queries per agent. In particular, this means that one can achieve a 2-approximation using O(log2 n) queries per agent.

Theorem 3. Given an ϵ > 0, an instance I = (N,H,P), and a priority vector p = (p1, . . . , pn), Algorithm 2 adaptively asks O(c logn) queries per agent, where c = ⌈ log(n2 ·1/ϵ) log (1+ϵ/2) ⌉, and returns a

1. Pareto optimal matching µ that achieves a (1 + ϵ)- approximation to the optimal welfare among all Pareto optimal matchings when pi = 0 for all i ∈ [n].

Algorithm 2

1: Input: ϵ > 0, I = (N,H,P), and p = (p1, . . . , pn) 2: Output: a PO matching when pi = 0 for all i ∈ [n] and a priority-p matching when p ∈ P 3: GI = (N ∪ H, E) ← graph induced by I 4: c ← ⌈ log(n2 ·1/ϵ) log (1+ϵ/2) ⌉ 5: ti ← ( 2 2+ϵ )i , for i ∈ [c] 6: for ai ∈ N do 7: for k ∈ [c] do 8: Eik ← {(ai, hj) ∈ E | Q(ai, hj, tk) = 1 and, if k ≥ 2, Q(ai, hj , tk-1) = 0} 9: for e = (ai, hj) ∈ Eik do 10: r ← rank(ai, hj ) 11: value′ (e) ← tk 12: we ← pr + value′ (e) 13: end for 14: end for 15: end for 16: µ ←max-weight matching in GI with weights {we}e∈E 17: if pi = 0 for all i ∈ [n] then 18: µ ← run top-trading cycles (TTC) algorithm with µ (from line 16) as the initial endowment 19: end if 20: return µ

1. priority-p matching µ that achieves a (1 + ϵ)- approximation to the optimal welfare among all priorityp matchings when p ∈ P.

We observe that Theorem 3 immediately informs us about distortion. Any algorithm that returns a Pareto-optimal matching and achieves an α-approximation to the optimal welfare amongst all Pareto-optimal matchings must have distortion of α since welfare-optimal matchings are necessarily Pareto-optimal. Thus, we are able to automatically confirm and extend earlier distortion results [Amanatidis et al., 2021], using a weaker query model. Furthermore, we again emphasize our interest in broader classes of matchings.

3.2 Non-Adaptive Algorithms: Asking One Query Per (agent, object) Pair

We now turn our attention to non-adaptive algorithms, in particular looking at algorithms that can only ask one query per (agent, object) pair and cannot change these queries depending on earlier responses. We believe that this is the more interesting and practical setting to consider for this problem, since such an algorithm does not have to wait for the agents to respond and also does not require an agent to answer multiple queries with respect to the same object-doing which would in turn entail that the agent is somewhat sure about their cardinal utilities.

We present two algorithms for when agents have unit-sum valuations, first in the context of priority-p matchings and second for Pareto optimal matchings. The latter is an extension of the former. In Algorithm 3, first the thresholds for the queries are carefully chosen. Then, in the induced bipartite graph, GI, weights for the edges are determined by agents' responses to queries. A max-weight matching in this graph is returned and is guaranteed to be a priority-p matching. If a Pareto-optimal matching is required then a little bit

Algorithm 3

1: Input: an instance I = (N,H,P) and priorities p = (p1, . . . , pn) 2: Output: a priority-p matching when p ∈ P 3: GI = (N ∪ H, E) ← graph induced by I 4: t1 ← 1 n1/3 5: ti ← 1 min{i,n1/3 }·n2/3 , for all i ∈ {2, . . . , n} 6: for e = (ai, hj) ∈ N ×H do 7: r ← rank(ai, hj) 8: if Q(ai, hj , tr) then 9: we ← pr + tr 10: else 11: we ← pr 12: end if 13: end for 14: µ ←max-weight matching in GI, where weights are (we)e∈E 15: return µ

Algorithm 4

• 1: Input: an instance I = (N,H,P = (P1, . . . , Pn))
• 2: Output: a Pareto optimal matching
• 3: µ′MM ←matching returned by Alg 3 on I and p = (0, . . . , 0)
• 4: µMM ← µ′MM \ {e ∈ µMM | we = 0}
• 5: if |µMM| == 0 then
• 6: µ′aux ← matching in GI that maximizes the number of agents who are matched with an edge of rank at most ⌊ 3√n/2⌋
• 7: else
• 8: µ′aux ←matching in GI where as many agents as possible to a rank-1 edge
• 9: end if
• 10: µaux ← µ′aux \ {(a, o) | (a, o) ∈ µ′aux and either a or o is matched in µMM}
• 11: µrest ← arbitrarily match the acceptable (agent, object) pairs that are not matched in µMM ∪ µaux
• 12: µ ← run TTC with µMM ∪ µaux ∪ µrest as initial endowments and return the resulting matching.
• 13: return µ

of additional work is needed to handle the situation where Algorithm 3 returns a matching where not all agents and objects are matched. Algorithm 4 is the extension that handles this case, by carefully handling the initial unmatched agents through the construction of an auxiliary matching.

Theorem 4. Given an instance I = (N, H, P) and a vector of priorities p = (p1, . . . , pn), where p ∈ P, Algorithm 3 asks one non-adaptive query per (agent, object) and returns a priority-p matching that achieves an O(n2/3 )-approximation to the optimal welfare among all priority-p matchings for the case when agents have unit-sum valuations.

Theorem 5. Given an instance I = (N , H, P), Algorithm 4 asks one non-adaptive query per (agent, object) pair and returns a Pareto optimal matching that achieves an O(n2/3 )- approximation to the optimal welfare among all Pareto optimal matchings for the case when agents have unit-sum valuations.

Finally, we also consider the case when agents have unitrange valuations and show that it is possible to obtain an O(√n)-approximation to the optimal social welfare among Pareto optimal and priority-p matchings. The algorithms and analyses for this case share similarities with Algorithms 3 and 4, and can be found in the full version (arXiv:2011. 13977).

Theorem 6. Given an instance I = (N,H,P) and a vector of priorities p = (p1, . . . , pn), where p ∈ P, there exists an algorithm that asks one non-adaptive query per (agent, object) and returns a priority-p matching that achieves an O(√n)-approximation to the optimal welfare among all priority-p matchings for the case when agents have unit-range valuations.

Theorem 7. Given an instance I = (N,H,P), there exists an algorithm that asks one non-adaptive query per (agent, object) and returns a Pareto optimal matching that achieves an O(√n)-approximation to the optimal welfare among all Pareto optimal matchings for the case when agents have unitrange valuations.

Lower Bounds

We finally turn our attention to lower bounds for the case when an algorithm can ask at most one query per (agent, object). We show that, for the unit-sum and unitrange valuation cases, any deterministic algorithm A that asks at most one query per (agent, object) pair and produces a Pareto-optimal/rank-maximal/max-cardinality rankmaximal/fair matching has a worst-case welfare loss of Ω(√n), i.e., L(A) ∈ Ω(√n).

Theorem 8. Let X denote one of the properties in the set {Pareto-optimal, rank-maximal, max-cardinality rankmaximal, and fair}. Let A be a non-adaptive deterministic algorithm that always produces a matching that satisfies property X and asks at most one query per (agent, object) pair. If there are n agents with unit-sum valuation functions or unit-range valuations, then L(A) ∈ Ω(√n).

4 Discussion

We investigated the benefit of eliciting a small amount of information about agents' cardinal utilities in the context of one-sided matching. We designed algorithms that used simple threshold queries and returned a matching satisfying some desirable matching property, while also achieving a good approximation to the optimal welfare among all matchings satisfying that property. Our results show how we can improve welfare by even non-adaptively asking agents for just one bit of extra information per object. Given a one-sided matching instance, there are often multiple matchings of interest and we view the methodology we presented here as providing a principled way of tie-breaking.

While adaptive algorithms provide better approximation guarantees, we believe the benefits of non-adaptive approaches outweigh the negatives. The argument for not insisting agents reveal full and exact cardinal utility information in the first place is that this places too high a cognitive demand on the agents. Our non-adaptive approach, which asks for only one bit of information for each (agent, object) pair, could be implemented using a simple menu - reducing the time and effort an individual agent must interact with the matching process.

There are a number of future research directions that this work can take. For example, we may want multiple agents to be assigned the same object, like when assigning students to courses or schools. Only minimal modifications are needed to address this case. In particular, every time we construct a graph in any of the algorithms, all that needs to be done is to create kj copies for the node that corresponds to object hj. Other open algorithmic problems include addressing the gap between the upper and lower bounds for the nonadaptive algorithms, expanding the set of properties of interest to include, for example, popular matchings [Abraham et al., 2007], or asking similar questions in the context of twosided matching problems. Finally, we are interested in better understanding the implications of deploying such an approach in practice, including evaluating how interface-design might best support queries, as well as better understanding what matching properties are deemed to be most important by users and designers of systems.