Optimally Solving Dec-POMDPs as Continuous-State MDPs

1 Introduction

Matching problems are ubiquitous and find application in a variety of domains. One of the most widely studied economic matching problems is the stable marriage problem [Gale and Shapley, 1962], in which members of two disjoint groups (colloquially men and women) express preferences for being matched (married) to members of the opposite group. A stable matching ensures that specified partnerships offer no incentive for an unmatched pair to defect from the matching. The stable marriage problem is emblematic of a rich set of bipartite matching problems in which elements of each set have some affinity for, or preference over, elements of the other. It has direct application to a variety of problems (e.g., labor market matching, school admissions) [Niederle et al., 2008]; and the classic Gale-Shapley (GS) algorithm [Gale and Shapley, 1962], and its variants, can be used to compute stable matchings very effectively.

While algorithms for many forms of stable matching are computationally efficient, the informational burden they place on participants can be severe: they usually require that participants rank all potential partners/matches. Of course, algorithms like GS can be used in an interactive fashion to avoid this, as we outline below, but are not designed specifically to minimize this informational burden. For large-scale matching problems involving hundreds or thousands of options on each side (e.g., hospital-resident matching, or paperreviewer matching), not only is the cognitive burden on participants high, much of this ranking information will generally be irrelevant to the goal of producing a stable matching. For example, in resident matching, one expects some degree of correlation across hospitals in the assessment of the most desirable candidates, and residents to have correlated views on the desirability of hospitals. Thus, more desirable candidates will tend to be matched to more desirable hospitals, and "first-tier" participants (hospitals and residents) are wasting time and mental energy if they offer precise rankings of lower-tier alternatives, while second-tier participants should not bother providing precise rankings of first-tier alternatives.

In this paper, we develop a framework for incremental preference elicitation in stable matching problems, as well as procedures for robust matching in the presence of incomplete preference information. Our goal is two-fold: first, we want to find stable matchings while requiring that participants specify only relevant information about their preferences; second, because full stability may require considerable preference information, we want to exploit some form of approximate stability to further reduce the information burden in practice. To address the latter goal, we use maximum regret to bound the potential for defection in a matching with partial preferences, and devise algorithms for computing matchings with minimal maximum (minimax) regret. To address the former, we develop elicitation schemes that use the matchings computed via minimax regret to find suitable queries. Our empirical results suggest that our regret-based methods and elicitation heuristics find approximate and exact stable matchings with much less than complete preference information across a variety of preference distributions, and significantly outperform the (interactive) GS algorithm.

2 Background

We first describe the stable matching problem addressed in this paper, briefly discuss prior work on matching with partial preferences and elicitation, then outline the probabilistic preference models used in our experiments.

Stable Matching. In this paper we focus on the classic stable marriage/matching problem (SMP) [Gale and Shapley, 1962], which we formulate using the common "marriage scenario." An SMP consists of set of men M and women W, each of size n, and a set of preference orderings associated with each participant: each man m ∈ M has a strict total preference order ≻m over W, with w ≻m w′ indicating that m prefers w to w′ as a potential partner; each w ∈ W has a similar ordering over M. We use ≻ to denote the set of preference rankings or preference profile of the SMP. For any q ∈ M ∪W, we use Rq to refer q's (range of) potential partners, i.e., Rq = W if q ∈ M, and Rq = M if q ∈ W. A matching is a function μ : M ∪ W → M ∪ W, such that μ(q) ∈ Rq , and q = μ(μ(q)). In other words, μ matches men and women in a 1:1 correspondence. Given a matching μ, we say (m,w) is a blocking pair if w ≻m μ(m) and m ≻w μ(w). A blocking pair destabilizes μ since m and w prefer each other to their partners in μ, and thus have incentive to defect (or "run away" with each other). A matching is stable if it admits no blocking pairs.

The Gale-Shapley (GS) algorithm [Gale and Shapley, 1962] for finding stable matchings proceeds in rounds (we describe the female-proposing variant). Initially, nobody is engaged. At each round, any unengaged woman proposes to the favorite man in her preference order to whom she has not yet proposed. Each man receiving (one or more) proposals accepts the proposal of the proposer (including his current engaged partner, if any) who is highest in his preference ranking-they become engaged-and rejects all other proposals. Once a round is reached where each woman is engaged, the current set of engagements is returned as the matching μ. This mechanism has a number of remarkable properties: it will converge to a stable matching in polynomial time; it is strategy-proof for women (but not men, vice versa if men propose); and among (the lattice of) all stable matchings it gives every woman her most preferred "achievable" partner [Gale and Shapley, 1962; Niederle et al., 2008].

This approach has been extended in a variety of ways and has been applied in many practical settings. Many-to-one extensions are common (e.g., hospital-resident or studentschool match [Roth, 1984; Abdulkadiroglu et al., 2005]), and more flexible forms of preferences can be accommodated. For instance, "incomplete" preference lists can be used to express acceptability thresholds: a total order over a subset of partners is specified, with unranked partners deemed unacceptable [Roth et al., 1993]. Indifference (ties) in rankings can also be accounted for [Irving, 1994], and give rise to new forms of stability. For instance, weak stability requires that both partners in a blocking pair strictly prefer each other, whereas strong stability allows one of the partners to be indifferent between his/her current and blocking partners. These two extensions can be combined to form the Stable Matching Problem with Incomplete Lists and Ties (SMP-ILT): determining if there is a weakly stable matching in SMP-ILT where all men (or women) are matched is NP-complete [Iwama et al., 1999]; however, SMP-ILT can be addressed heuristically [Gelain et al., 2010; Gent and Prosser, 2002].

Related Work. The problems of incremental preference elicitation and computing stable matchings with partial preference information have received relatively little attention. GS is typically implemented by having participants submit their complete preferences, with the "proposal/acceptance" simulated within the algorithm. However, it can be viewed as an interactive elicitation algorithm as well, with proposers and acceptors providing only the information needed to run GS. We are unaware attempts to use early termination of GS to find approximately stable matches. Pini et al. [2011] develop several notions of approximate stability, but this is not used to address partial information (and relies on real-valued utilities rather than ordinal preferences). Closest in spirit to our work is that of Rastegari et al. [2013], who investigate the problem of minimizing the number of interviews needed to find a stable matching in a labor market. They analyze the problem from several perspectives. They show that finding a minimal certificate (i.e., set of partial preferences that supports an employer-optimal matching) is NP-hard. They also provide an MDP-formulation assuming a prior over preferences (which enumerates all, information states or, in our terminology below, "partial preference profiles"), but is otherwise polynomial in this (exponentially-sized) set. Our work differs in its focus on computing matches that are approximately stable given partial preferences, computationally effective heuristics for elicitation, and anytime evaluation (we also evaluate our schemes experimentally).

Bir´o and Norman [2012] present a method for stable matching that can be viewed as an elicitation scheme. Individuals interact randomly, and form a new pair if it offers benefit (relative to their current partners). They show that this is likely to result in an egalitarian solution. However, interpreted as an elicitation scheme, it seems to both scale poorly computationally and require far more elicitation rounds than our approach. Other work has considered equilibrium matching with unobservable preferences [Liu et al., 2012]. It is known that the communication complexity of stable matching is Ω(n2 log n) [Chou and Lu, 2010], hence no elicitation scheme can reduce elicitation burden the worst case.

Our work is closely related to previous work on regret-based robust optimization and preference elicitation [Boutilier et al., 2006; Braziunas and Boutilier, 2007; Lu and Boutilier, 2011b]. Specifically, we adapt the methods of Lu and Boutilier [2011b] for regret-based winner determination and elicitation in voting using ordinal preference rankings to our robust stable matching problem.

Probabilistic PreferenceModels. To capture correlations in preferences, we consider several standard probabilistic models of preferences below. The Mallows φ-model [Mallows, 1957; Marden, 1995] is parameterized by a modal or reference ranking σ and a dispersion parameter φ ∈ (0, 1], with the probability of a ranking r given by P (r | σ, φ) ∝ φd(r,σ) , where d is Kendall's τ distance metric. When φ = 1 we obtain the uniform distribution over rankings (i.e., impartial culture), and as φ → 0 the distribution concentrates all mass on σ. The Mallows model (and mixtures thereof) have plausible psychometric motivations and are commonly used in machine learning [Murphy and Martin, 2003; Meila and Chen, 2010; Lebanon and Mao, 2008; Lu and Boutilier, 2011a].

The riffle independence model [Huang and Guestrin, 2009]

partitions a set of items into two sets: a ranking of each set is generated stochastically (and independently); then a stochastic process is used to interleave or "riffle" the two resulting rankings to produce a combined ranking. The model can also be defined hierarchically, with the same process used to generate the subrankings.

3 Matching with Partial Preferences

In any preference-based matching process, it may be appropriate to elicit only partial information about user preferences, especially when certain preference information is unlikely to be relevant in the computation of the matching or when the costs of elicitation outweigh the benefits derived. However, the partial information elicited may not be sufficient to produce a fully stable matching. In this section, we define a specific form of approximate stability given partial preferences using minimax regret. Apart from providing worst-case stability guarantees, we will see that it is a very effective driver of preference elicitation in Sec. 4.

3.1 Minimax Regret

For any q ∈ M ∪W, we assume that q's ordinal preferences are captured by a total order or ranking ≻q over Rq . (Our methods can be readily adapted to handle ties and unacceptable alternatives in a person's preferences, but we focus on total orders for ease of exposition.) However, we suppose that we have access only to partial information about these preferences. This information takes the form of a partial ranking Pq for q, which is a partially order over Rq , or equivalently (the transitive closure of) a consistent collection of pairwise comparisons of the form r ≻q r′ . Most constraints on preferences, including responses to most natural queries can be represented in this way. A partial preference profile P is a set of a partial rankings {Pq : q ∈ M ∪W}. A completion of Pq is any total order ≻q that extends Pq. Let C (Pq) denote the set of completions of Pq and define the completions C (P) of a partial profile P in the obvious way.

Several special forms of partial preferences are of interest, including top-k preferences, in which a user expresses a total order over her k most preferred partners and provides no information over the remaining partners (other than the implicit fact that they are less preferred). Partitioned preferences [Lebanon and Mao, 2008] allow a user q to partition potential partners Rq into an ordered set of subsets R1, . . . ,Rs s.t. (a) for all i < j ≤ s, if x ∈ Ri and y ∈ Rj then x ≻q y; and (b) for each i ≤ s, items in Ri are unordered. Top-k preferences are a special case of partitioned preferences and both can be represented as a set of pairwise comparisons.

Example 1. To illustrate consider an example with n = 4 men and women in which all men and women have identical preferences. Let ≻w be the same for each w ∈ W, with m0 ≻w m1 ≻w m2 ≻w m3; and similarly let w0 ≻m w1 ≻m w2 ≻m w3 for each m ∈ M. One possible partial preference ranking for mi consists of two equal-sized partitions: Pmi = (w0,w1) ≻ (w2,w3). Indeed, this takes the form of partitioned preferences. This partial preference has four possible completions (e.g., w1 ≻ w0 ≻ w3 ≻ w2) including the true underlying full ranking. The partial profile P consisting of this same "two-by-two" partitioning for each m ∈ M, w ∈ W will be discussed below.

Our interest is in partial-preference stable matching problems (PP-SMPs), SMPs in which the user preferences are replaced by partial rankings. Given the uncertainty inherent in a partial preference profile P, one cannot guarantee the existence of a stable matching: while a matching μ may be stable under some completions of P, it may not be under other completions. Thus, intuitively, a solution for a PP-SMP instance should be as stable as possible. We measure the stability of μ by considering the maximal possible incentive that some blocking pair might have for "defecting" over all possible realizations of their preferences. While there are several plausible ways in which to measure the incentive for a blocking pair to deviate, we adopt one reasonably natural one here. Specifically, we define the incentive for q to switch from partner r to partner r′ to be the improvement in rank position in ≻q attained by the switch. For any total order ≻q over Rq , let sq(r, ≻q) = n - rank(r,≻q) be the Borda score of r in q's ranking. For any q ∈ M ∪W, preference ordering ≻q, partial ranking Pq and r, r′ ∈ Rq, define:

Regret(q, r′ , r,≻q) is the degree to which r′ is preferred to r by q given known preference ≻q. When only partial preferences Pq are known, pairwise max regret PMR(q, r′ , r, Pq) is the greatest degree to which r′ might be preferred to r over all possible preference realizations.

Example 2. Using the partial profile described in Example 1, we have PMR(m0, w1, w2, Pm0 ) = 3: m0's Borda score for w1 could up to 3 greater than his score for w2 in some completion of his partial ranking (indeed, this is so in the completion described in Example 1).

Using rank improvement to measure the incentive for an individual to deviate from one partner to another gives us the ability to measure the degree of instability of a blocking pair. 1

Definition 3. Given a SMP and matching μ, the (degree of) instability of pair (m, w) (resp. μ) is:

With complete preferences, (m,w) is a blocking pair iff Inst (m, w, μ, ≻m, ≻w) > 0 and μ is stable iff Inst(μ,≻) ≤ 0. In this sense, our definition generalizes that of stability on the full information sense.

Notice that we assume the incentive of a pair to deviate is that of the least willing partner. This is sensible under the usual assumption of non-transferable utility. But other definitions are possible, including the summing the PMR values of both members of the pair. Similarly, we equate the instability of a matching with that of the maximally unstable pair. The main reason to adopt this definition is that defection of a single pair is often sufficient to cause a cascade of deviations and unravel the matching. Furthermore, these definitions reduce to the usual notion of stability in SMPs given full preferences (which is not generally the case for other definitions, e.g., summing the pairwise max-regret of each individual). However, other definitions of instability require no substantive changes to our underlying conceptual framework or definitions (though the details and analysis of our algorithmic approach below may be sensitive to such changes).

1 Pini et al. [2011] develop several notions of degree of stability using real-valued preferences, and our full (but not our partial) information definition is a special case of their notion of α-stability.

With full information, we are assured a stable matching exists with Inst(μ, ≻) ≤ 0. With only a partial profile P, the stability of any matching μ may not be known for sure. To provide guarantees on the quality of a matching, we define the maximum regret of μ by considering its worst-case instability over all possible preference completions.

Definition 4. Given a PP-SMP with partial profile P, the max regret of matching μ and the minimax regret of P are:

MR(μ,P) reflects the worst-case degree of instability over possible preference realizations. A minimax optimal matching μ∗P has the best such stability guarantee, namely MMR(P): for any other matching μ there is some completion of preferences for which μ is at least as unstable as the maximum possible instability of μ∗P. As such, μ∗P represents a robust matching in the face of preference uncertainty.

Our goal in solving a PP-SMP is as follows: given a partial preference profile P, find the minimax regret optimal match μ∗P. Notice that if MMR(P) ≤ 0, then matching μ∗P is in fact stable in the traditional sense, despite the fact that we have a partial profile, a fact we will exploit below to terminate the elicitation process. If the partial profile is complete, then any stable matching has max regret no greater than 0.

Example 5. In Example 1 we see that MMR(P) = 1. Several minimax-regret optimal matchings exist: any matching that pairs each of {m0,m1} with one of {w0,w1}, and each of {m2,m3} with one of {w2,w3}, suffices. The stable matching for the true underlying preferences, μ0(mi) = wi, ∀i, is one such matching (though it is not "known" to be stable given only the partial profile P).

3.2 Computing Approximately Stable Matchings

The decision variant of computing a minimax-optimal matching with partitioned preferences-and by extension, with arbitrary partial preferences-is NP-complete:

Theorem 6. Given partitioned partial profile P, deciding if some matching μ∗P has MR(μ∗P, P) < k is NP-complete.

Proof Sketch. PP-SMP is easily seen to be in NP: checking if a match has max regret k takes at most 2n3 pairwise maxregret calculations, which can be computed in polynomial time using techniques for finding ranking completions to determine minimax regret in Borda voting with partial votes [Lu and Boutilier, 2011b].

We use a reduction from SMP-ILT (see Sec. 2) to show PPSMP is NP-hard. Assume an arbitrary SMP-ILT instance of size n, where k is the size of the largest "tie" (group of equally

Algorithm 1 IP for Minimax-optimal Matching

Objective: minimize δ Subject to: δ ≥ PMR(m, w, m′ , w′ )(μm′ ,w +μm,w′ - 1), ∀m,m′ , w, w′ ∑w∈W μwm = 1, ∀m ∈ M ∑m∈M μwm = 1, ∀w ∈ W μwm ∈ {0, 1}, ∀w ∈ W, ∀m ∈ M

preferred partners) in some preference order. We create a corresponding instance of PP-SMP with 2n + j + 1 individuals on each side of the market, with j ≤ n2 . Men and women are broken into three groups, each with distinct partitioned preferences. We describe the men (women are analogous). Group O: the original n men in SMP-ILT; Group I: n + 1 additional men Im, used to guarantee that no one is matched to an unacceptable partner; Group T: j additional men Tm, used to ensure weak stability.

Men in Om have a partition for each of their tied groups (including singletons) in SMP-ILT, and a partition for all unacceptable partners; these are ordered as in SMP-ILT. All partitions are padded to have size k using women in Tw (arbitrarily). Finally, a partition with all women in Iw is inserted between the least-preferred acceptable and unacceptable partitions (any unused Tws are placed in this partition as well).

Each man in Im has the set Ow as his favorite partition. Then he has a unique woman from Iw as his next preferred, with the remaining women in Iw women ordered arbitrarily after this. Women in Tw are ordered arbitrarily below Iw.

Each man in Tm has a unique woman from Tw woman as his favorite, with the remaining women in Tw women ordered arbitrarily below this woman. An arbitrary ordering of Iw follows this, and finally all of Ow comprises a single partition at the bottom of his preference.

It is straightforward to verify that this construction of a partial preference profile P leads to a PP-SMP problem where a matching μ∗P has MR(μ∗P, P) < k iff the original SMP-ILT instance admits a weakly stable matching (we omit details for space reasons). Since finding a weakly stable matching for SMP-ILT in NP-hard, the hardness of PP-SMP follows.

Despite its computational complexity we consider several methods for both exact and heuristic solution of PP-SMP. We first observe that PP-SMP can be formulated as a polynomially sized integer program (IP). Given a matching μ and potential defecting pair (m,w), we can compute the relevant completions of their partial preferences (w.r.t. their partners μ(m), μ(w)) that maximize their instability Inst(m, w, μ) in polynomial time. Given a partial profile P, define:

The O(n3 ) preference completions needed to compute these O(n4 ) constants can each be determined in polynomial time. With these constants in hand, we formulate the minimaxoptimal matching as the IP in Algorithm 1, using 0-1 matching variables μm,w.

The IP performs reasonably well for small values of n, but becomes impractical beyond n = 30 (see Sec. 4). Because PP-SMP is NP-complete, the LP-relaxation tends to produce highly fractional matchings, in contrast to IPs for SMP [Roth et al., 1993]. Our IP works with arbitrary partial profiles; when partial preferences have structure (e.g., partitioned, topk) we believe more compact IP formulations are possible.

Since our goal is to use minimax regret to support incremental elicitation, we need not compute minimax regret exactly to effectively reach stable matchings, as we will see below. Instead consider a set of related alternative strategies that provide us with an upper bound on minimax regret and can be computed very quickly. Given a partial profile P, let ≻ ∈ C (P) be some completion. Notice that we can readily use GS to compute a stable matching μ for this complete profile ≻ and compute its max regret MR(μ, P) in O(n2 ) time. The max regret of the matching so produced provides us with an upper bound on MMR(P), and specifically, if MR(μ,P) is no greater than zero, μ is in fact a stable matching for any completion of P.

The value of this upper bound depends on the completion used to generate the matching μ. We consider several distinct ways of generating a completion, leading to different variants of the partial preference Gale-Shapley (PPGS) algorithm for approximating minimax regret. PPGS-R (random) chooses a completion of each user q's partial preference uniformly at random from the set C (Pq). PPGS-k is the same as PPGS-R except that the process is repeated k times and the matching with minimal max regret is returned. If some probabilistic preference model is given, PPGS-ML uses this model to determine the maximum likelihood completion of each user's preferences and runs GS on the resulting profile. Finally, PPGS-F is much like PPGS-ML except that an arbitrary fixed reference ranking is used to find a maximally consistent completion.

As with exact MMR, special structure in partial preferences can be exploited to approximate MMR. For example, MMR can be bounded quickly with partitioned preferences:

Observation 7. Given partitioned preferences with largest partition of size p, there is a matching with max regret at most p - 1. This matching can be found in polynomial time.

By treating each partition as if they represented "ties" in a full information setting, we can compute a weakly stable matching in polynomial time [Roth et al., 1993] and bound its max regret by p - 1. Tighter post-hoc bounds on max regret can be easily computed given the resulting matching μ. We discuss the computational effectiveness of these schemes in the next section.

4 Preference Elicitation

We now turn to interactive elicitation of preferences as a means of reducing cognitive burden. We present a general method that uses minimax regret to drive the elicitation process and empirically compare it to GS in terms of number of queries and rounds required to reach a stable (or approximately stable) matching.

4.1 Elicitation Schemes

We expect preferences in naturally occurring problems to exhibit correlations. Elicitation schemes that exploit this fact can substantially ease the cognitive burden on users, the

Algorithm 2 Regret-based Halving: Elicitation

Require: Partitioned preference profile P, threshold τ

loop 1: Compute (approximate) μ = μ∗ (P), compute MR(μ, P). 2: if MMR(P) ≤ τ , done. 3: for each q ∈ RI (μ) s.t. q not queried this round 4: if r and μ(q) are in the same block B of 5: Pq for some r ∈ BP(q) 6: Ask q to split B. 7: else 8: for each r ∈ BP(q) s.t. r not queried this round 9: if q and μ(r) are in the same block B of Pr 10: Ask r to split B. 11: if ∄Pj ∈ P s.t. Pj was updated this round 12: for each Pj ∈ P 13: Ask j to split j's largest partition Bjm s.t. |Bjm| > 1.

amount of preference information revealed, and communication costs. Consider again the extreme case where all user preferences are identical (e.g., as illustrated in Example 1): stability requires that the kth-ranked man be matched with the kth-ranked woman. If GS is used for elicitation, low-ranked women (proposers) and men (acceptors) will specify their entire preference ranking, even though only the bottom of their ranking is actually needed. While half of all potential partners are ranked (on average) using GS, a user q using "binary search" can identify the kth-ranked element of Rq without reasoning about her precise ranking. Well-designed queries could further lessen the burden on users, as some queries are intrinsically easier than others.

This example, while suggestive, is unrealistic. Apart from assuming extreme correlation, it presumes the ability to identify the kth-ranked person on each side of the market. In general, knowing which parts of a user's ranking need to be refined requires some prediction of the matching that will result. However, this motivates a new elicitation method, the regret-based halving (RBH) strategy, outlined in Alg. 2. RBH works by maintaining a partial profile P in the form of partitioned preferences for each user q: i.e., a rank-ordered set of blocks Bq 1 , . . . ,Bqk , where partners within a block have not yet been compared to each other. At each round of elicitation, RBH asks one or more users q to split a single block Bq j into an upper block U and lower block L of (roughly) equal size such that r ≻q r′ for all r ∈ U, r′ ∈ L. For instance, Fig. 1 shows the evolution of partitioned preferences discovered using RBH for one of the women in Example 1.

To identify appropriate queries at each round, RBH computes (or approximates) the minimax-optimal matching μ relative to P. Users whose preference imprecision is "contributing" to max regret MR(μ) are queried so as to reduce imprecision in the relevant partition. More specifically, let the regret-inducing individuals RI (μ) be those q ∈ M ∪ W for which there is an r ∈ Rq , s.t. PMR(q, r, μ(q), Pq) = MR(μ) and PMR(r, q, μ(r), Pr) ≥ MR(μ): intuitively, q is a user whose potential preference for new partner r (who potentially reciprocates at least as strongly) determines the max regret of the matching. We call any such r a blocking partner for q, and denote the set of such as BP(q) (see Fig. 1 for an illustration). RBH will ask queries only of such individuals, or their potential partners, in a direct attempt to reduce MR(μ); see line 4 of Alg. 2. This can be viewed as a form of current solution elicitation [Boutilier et al., 2006; Braziunas and Boutilier, 2007; Lu and Boutilier, 2011b], where queries are driven by the regret-optimal solution.

The selection of individuals for querying occurs in lines 4-10. Intuitively, querying the regret-inducing individuals q and their blocking partners has the greatest potential to lower the max regret of the current matching. Lines 4-6 ask q to split the block containing both its current partner μ(q) and blocking r ∈ BP(q) when they are in the same block. This will either confirm μ(q) or r as preferred by q, or will reduce their PMR by a half. If q's blocking partner r is not in the same block as μ(q), we instead query r, asking him to split the block containing q and μ(r) if they are in the same block for similar reasons (lines 8-10): note that r's PMR for q is at least as great as that of q for r. In both cases, queries are targeted toward individuals where a single block contains the "relevant" uncertainty required to identify the optimal "attainable" partner, in some loose sense simulating binary search. If neither of these conditions holds for any q ∈ RI (μ), we resort to asking each individual to split their largest block to ensure that elicitation does not stall.

CognitiveCosts. Asking a person to "split a block" based on preferences is a very different form of query than those asked by GS. Furthermore, not all splitting queries are equally difficult, since the sizes of the blocks that are split varies (and may contain potential partners that are either very close of very distant from each other in terms of preference). To meaningfully compare RBH with GS, we measure the number and cognitive difficulty of the pairwise comparisons required to answer their queries. We show that, in practice, RBH outperforms GS with respect to the total cognitive complexity of queries, as well as the number of queries itself.

One natural measure for comparing how difficult queries are would be to simply consider the number of pairwise comparisons required. Using a Quickselect-style algorithm [Hoare, 1961], a block of size z can be split using O(z) comparisons (assuming reasonable pivot choices). For GS, proposers can select the next best partner to propose to using O(z) comparisons when selecting from z unproposed candidates; and acceptors similarly must make comparisons linear in the number of received proposals. Of course, not all pairwise comparisons are equally difficult. Intuitively, comparing two partners widely separated in one's ranking is easier than comparing two that are close, a fact reflected in many psychometric and behavioral economics models of choice [Louviere et al., 2000; Camerer et al., 2003]. To reflect this, we measure the difficulty of a comparison using the Luce-Shepard choice model [Luce, 1959; Shepard, 1959], in which the probability of choosing a lower ranked item over a higher ranked item decreases exponentially with their separation or difference in utility. Equating degree of difficulty with choice error, given an underlying ranking ≻q for person q, temperature γ ≥ 0, and threshold τ, the cost of comparing r with r′ is:

(Note: γ = 0 makes all comparisons equally difficult.) We assess the cognitive complexity of both RBH and GS below.

4.2 Empirical Results

We now describe experiments that test the effectiveness of our elicitation schemes. We draw preference profiles from specific preference distributions, and measure the average number of queries and rounds needed to reach a stable matching (i.e., max regret zero), the cognitive complexity of those queries, and their anytime performance w.r.t. approximate stability. We also assess their computational performance.

Number of queries. We first consider small instances with n = 20 (i.e., 20 men, 20 women) to allow use of the IP (Alg. 1) to compute true minimax regret. Table 1 shows the average number of queries (over 30 trials) per proposer/acceptor and number of rounds required by different schemes using a Mallows models to generate preferences with φ = 1 (impartial culture) and φ = 0.2 (strongly correlated preferences). GS marginally outperforms all RBH schemes when preferences are completely uncorrelated, but except for IP, the differences are not statistically significant for proposers, and the advantage for acceptors is quite small. With strongly correlated preferences, the RBH schemes (apart from IP) reach a stable matching with far fewer queries per proposer, and differ from GS by less than one query per acceptor. In all cases, the RBH schemes (excluding IP) ask fewer than log n queries per person; thus they even outperform binary search for a known target partner (of course, the target is not known a priori). The IP scheme works surprisingly poor. This is, in large part, due to the fact that the matchings computed by the IP often do not match individuals to partners in the partitions that they ultimately end up being matched in.

For these small instances, the IP requires roughly 0.5 sec. to compute the MMR matching (and hence generate queries in a given round), but becomes impractical beyond n = 30. We do not consider IP further on the larger instances below. The other RBH schemes require 0.01-0.06 sec. on average to generate a matching, compute its max regret, and generate queries. GS is much faster, but does not compute max regret; thus it offers no anytime guarantees (as we discuss below).

Table 2 shows similar results for n = 250, and Fig. 2 shows the performance of PPGS-F and GS as φ varies. On these much larger matching problems, PPGS-F and PPGS-ML offer superior performance (both averaging fewer than log(n) queries per person). With correlated preferences (φ = 0.2) all RBH schemes dramatically outperform GS. Notice that GS is also unbalanced or "unfair," asking proposers 10 times as many queries as acceptors. PPGS-ML has slightly (but statistically significant) better query performance than PPGSF. It offers much better performance in terms of rounds-an important measure of latency in interactive elicitation-and uses only 31.8 rounds (cf. 272.8 for GS). With completely random preferences, GS has a query advantage over the other schemes, but it is slight (about 1.5 queries for proposers, under 2 for acceptors), and also has much higher variance. GS still requires more rounds than PPGS-ML in this case.

Anytime performance. Computationally, GS takes negligible time per round to compute queries, while PPGS-ML and PPGS-F take approximately 27s. per round when n = 250. Of course, the RBH schemes must compute max regret, specifically PMR for alternative partners for each person. However, since the PMR values for person q are independent of those for q′ , these computations can be fully parallelized. Computing preference completions for each q is the most time-consuming aspect of RBH, so full parallelization can reduce real-time latency by a factor of roughly 2n. More importantly, computing the max regret of the current matching allows one to determine approximately stable matchings at any time and terminate the querying process when max regret reaches an acceptable level. We compare this anytime Queries per Person performance of PPGS-ML and GS in Fig. 3. 2

Figure 3: Max regret vs. number of queries (per person): n = 250, φ = 0.2, 20 trials, with error bars (low std. dev.).

PPGS-ML displays very desirable behavior, on average roughly halving max regret with each (per person) query, inducing rapid convergence to a stable matching. Critically, it admits early termination of elicitation with high quality matchings. By contrast, GS reduces max regret at an extremely low rate, providing almost no ability to quickly find matchings with low max regret. The ability to determine approximately stable matchings so quickly is a key reason to use our regret-based approaches to elicitation.

Cognitive costs. Simply measuring the number of queries does not consider how difficult each query is, which may be misleading. We thus analyze the cognitive complexity of each query (see Eq. 7). We set γ = 0.5 and τ = 5 (and normalize costs by eγn for clarity); results are qualitatively similar for other cost parameters. In the (n = 250, φ = 0.2)-instances above, the cognitive cost of full sorting is 310.34 (per person), assuming Quicksort with perfect pivots. Proposers average a cognitive cost of 1,830.89 using GS, so we instead assume that proposers fully (and perfectly efficiently) sort their lists ahead of time when using GS, giving a cost of 310.34. (This is itself unrealistic, since using GS as elicitation is unlikely to result in proposers sorting their entire list, so true cognitive cost will exceed 310 but fall short of 1830.) Acceptors' average cost for GS is only 13.08, since they make fewer decisions and their comparisons are often widely separated. PPGS-ML's results are much more egalitarian, with proposers and acceptors having cognitive costs of 53.80 and 53.77, respectively. Its average cost of 53.79 is much lower than that of GS-even with perfect sorting by proposers-which averages 161.71 per person. Even with φ = 1, while GS asks slightly fewer queries per person, its average cognitive cost is 60.8 (men 121.10, women 0.43) remains greater than the 57.8 for PPGS-ML (54.99 proposers, 57.68 acceptors). This is a compelling reason to use regret-based elicitation.

Riffle models. We now consider a more complicated riffle model of preferences. This model makes the realistic assumption that certain (either latent or observable) features correlate user preferences. We assume that every man is one of two

2 Note that GS does not compute intermediate matchings at each round, so we use the PPGS-ML scheme to find a matching using the information elicited by the GS queries. Other RBH schemes are excluded, but perform similarly to PPGS-ML.

"types" corresponding to some (for ease of exposition) observable characteristic. For each type, we assume a distinct Mallows model over the men of each type. A woman's preference for men is generated by first drawing a ranking from each of these models, then interleaving them using a riffle process, with a parameter p reflecting the woman's bias toward each type: the full ranking is generated by iteratively placing the top "remaining" item from the Type 1 ranking into the next spot in her full ranking with probability p, and the top item from the Type 2 ranking with probability 1 - p, until all men have been inserted into the ordering. The bias p towards one type of the other is drawn from an equal-weight mixture of two Gaussians (truncated over [0, 1]) with variance σ = 0.1 and means of 0.25 and 0.75 (so women are unlikely to be "indifferent" between the two types of men). Men's preferences are generated in the same way.

We compare PPGS-F to GS in terms of number of queries to reach a stable matching in this model, using three different dispersion parameters for the underlying Mallows models. (We don't use PPGS-ML since maximum likelihood estimation is less straightforward in this mixture process.) Results in Table 3 show that PPGS-F vastly outperforms GS, when φ = 0, 0.1, 0.2; and it remains competitive with GS when φ = 1. It always requires fewer rounds as well.

MovieLens Models. We next consider matching problems in which preferences are generated from the MovieLens collaborative filtering data set. 3 The MovieLens data set consists of 100,000 ordinal ratings (1-5 scale) of 1682 movies by 943 users. We convert this into preference rankings of users for each other by generating an affinity score between pairs of users based on the similarity of their movie ratings.

Let M (a) denoted the set of movies rated by user a, and ra her rating vector. Given two users a and b, we define their affinity score to be s(a, b) = ∑m∈M(a)∩M(b) 5 - |ra(m) - rb(m)|, where 5 reflects the maximum rating. This scores creates very correlated preferences: individuals who rate a larger number of movies will tend to be viewed as more desirable across the population. We also create somewhat less correlated affinities by normalizing scores by the number of movies rated in common: sN (a, b) = s(a, b)/|M (a)∩M (b)|. With these affinities, we create random matching problems by drawing 250 "men" and 250 "women" uniformly at random, and generating preference rankings for the appropriate side of the market using these real-valued affinities to order potential partners (breaking ties arbitrarily). As expected, the Unnormalized Movie Matching (U-MM) problems using score s exhibit more correlation than their unnormalized counterparts (N-MM) generated using sN . 4

3 See http://www.grouplens.org/node/73, the 100K data set.

Table 4 shows the performance of GS and PPGS-F for both U-MM and N-MM, averaged over 20 random matching instances. PPGS-F outperforms GS with respect to number of queries in both settings, but requires more rounds in N-MM. Not surprisingly the performance gap is greater in when preferences are more correlated. PPGS-F similarly outperforms GS with respect to cognitive cost (setting γ = 0.5, τ = 5 as above). In U-MM, average cognitive cost per person for GS is 788.52 for proposers, and 3.56 for acceptors. Using PPGS-F, average costs are 55.31 and 55.40 for proposers and acceptors, respectively. Again, note that the cost of fully sorting all alternatives is 310.34 per person. PPGS-F also outperform GS on N-MM problems: GS has an average cognitive cost of 250.04 and 1.35 for proposers and acceptors, respectively, while PPGS-F has costs of 58.84 and 58.59, respectively.

5 Conclusions and FutureWork

We have proposed the use of minimax regret as a robustness criterion for stable matching with incomplete information, and developed several heuristic elicitation schemes designed to quickly reduce regret. These schemes compare favorably to the use of Gale-Shapley for interactive elicitation, especially when preferences exhibit some correlation: they reach stable matching with fewer queries, fewer rounds of elicitation, and with lower cognitive cost. Critically for domains where approximate stability is desirable (e.g., when elicitation/interviewing costs or switching/defection costs are high), our elicitation schemes demonstrate vastly superior anytime performance to GS, allowing approximately stable matchings to be found with very little preference information.

Many interesting research directions remain, including: improved procedures for exact MMR computation; new algorithms tuned to specific forms of partial preferences; analysis of additional probabilistic preference models and the use of priors to further improve elicitation performance; the assessment of our methods for different measures of approximate stability; and the extension to other stable matching problems.

Acknowledgments. Drummond was supported by OGS and a Microsoft Research Graduate Women's Scholarship. We acknowledge the support of NSERC, and thank Tyler Lu for generously sharing his code and the reviewers for their helpful suggestions.

4 Using Kendall's τ-statistic, the average correlation statistics for U-MM are 0.4539 (proposers) and 0.4653 (acceptors); while for NMM, they are 0.1462 (proposer) and 0.1184 (acceptors).