Average-case Analysis of the Assignment Problem with Independent Preferences

1 Introduction

Studies in Mechanism Design focus on designing mechanisms in which truth-telling is a dominant strategy, and so the rational, risk-neutral agents are motivated to play their truth-telling strategies. Subject to this qualitative constraint, a truthful mechanism quantitatively optimizes an objective such as social welfare or revenue. Build upon the classical Mechanism Design framework, Algorithmic Mechanism Design [Nisan and Ronen, 1999] advances research and has evolved to employing two typical analytic tools in Computer Science. One of these tools imposes polynomial-time implementability on designing mechanisms, and the other evaluates mechanism performances through the lens of the worstcase analysis. Typically, the (worst-case) approximation ratio assesses to what extent a mechanism approximately optimizes an objective over all possible inputs and it is dominated by the worst-case inputs [Procaccia and Tennenholtz, 2009]. There is now an extensive literature on topics including matching [Dughmi and Ghosh, 2010; Anshelevich, 2016], scheduling [Koutsoupias, 2014; Christodoulou et al., 2009], facility location [Filos-Ratsikas et al., 2015], kidney exchange [Hajaj et al., 2015], fair division [Chen et al., 2013], social choice [Anshelevich et al., 2018], and auction design [Hartline and Roughgarden, 2009; Mu'alem and Nisan, 2008; Archer et al., 2003]. For a more detailed summary, we refer the reader to [Nisan et al., 2007].

In the assignment problem (a.k.a., one-sided matching or house allocation problem), there is a set of agents and a set of items. The agents participate in a mechanism by reporting their private preferences over the items. The mechanism then assigns items to agents, according to a pre-defined allocation function. The folklore mechanism Random Priority (a.k.a., Random Serial Dictatorship) is mainstream because it satisfies appealing properties including anonymity, truthfulness, and ex-post Pareto efficiency. In addition, there exists no mechanism that is ex-ante Pareto efficient while keeping the first two desired properties [Zhou, 1990]. Random Priority and its variants have notable practical applications. For example, they are used in United States Naval Academy placement [Roth and Sotomayor, 1990], social or governmentsubsidised housing [Abdulkadiroglu and S¨onmez, 1999], graduate housing allocation at a large number of universities [Abdulkadiroglu and S¨onmez, 1998], and high school student assignment in New York [Pathak and Sethuraman, 2011].

For the purpose of maximizing social welfare, i.e., the sum of all agents' utilities, Random Priority can only achieve a Θ(1/√n) fraction of the optimal social welfare in the worst case, where n is the number of agents and items, and it is asymptotically the best amongst all truthful mechanisms [Filos-Ratsikas et al., 2014]. This negative result was considered a cautionary tale discouraging the wide applications of Random Priority. Fortunately, the smoothed analysis and average-case analysis mitigate it by revealing positive results on social welfare approximation. In [Deng et al., 2017], the authors show that when the worst-case inputs are subject to small random noise, Random Priority attains social welfare within a constant factor of the optimal welfare. In addition, when agents' preferences are drawn from a uniform distribution, on average, the optimal social welfare is no more than 1 + e times of the social welfare attainable by Random Priority, where e is the Euler's number. Therefore, on average, the efficiency loss is small. The primal question that remains open is: Does the constant average-case ratio result hold for general probability distributions? In this paper, we partially answer this question by showing the following results.

• When agents' preference values are independent and identically distributed random variables, the averagecase approximation ratio is upper bounded by 1/µ, where µ is the expectation of these random variables.
• When agents' preferences values are independent but not necessarily identically distributed random variables, under mild conditions, the average-case approximation ratio is upper bounded by a constant.

We note that the 1/µ upper bound for the i.i.d. case improves the 3.718 upper bound for the Uniform distribution U[0, 1], as its expectation µ = 12 and 1/µ yields an upper bound of 2. Taken together, these results further pin down the wideapplicability of the Random Priority mechanism, for which the worst-case analysis is insufficient to manifest.

To achieve these results, we employ the Central Limit Theorems and carefully calibrate the values of some parameters in a few building blocks to ascertain the rate that the properly normalized sum of preference values converges to a Normal distribution. By successfully compositing these building blocks together, we bound the average-case ratios.

1.1 RelatedWork

The one-sided matching problem was introduced in [Hylland and Zeckhauser, 1979] and has been studied extensively ever since. Over the years, several different mechanisms have been proposed with various desirable properties related to truthfulness, fairness and economic efficiency with Probabilistic Serial [Abdulkadiro˘glu and S¨onmez, 2013; Bhalgat et al., 2011; Bogomolnaia and Moulin, 2001; Katta and Sethuraman, 2006] and Random Priority [Abdulkadiroglu and S¨onmez, 1998; Svensson, 1999; Christodoulou et al., 2016; Aziz et al., 2013] being the two prominent examples. In the indivisible goods setting, the Top Trading Cycles (TTC) method is well-studied and generalized to investigate various problems. In particular, [Abdulkadiroglu and S¨onmez, 1998] proposed an adaptation of the TTC method and established an equivalence between the adapted mechanism and Random Priority. [Kesten, 2009] proposed several extensions of these popular mechanisms and presented an equivalence result between those mechanisms in terms of economic efficiency. In the presence of incentives, the assignment problem was extensively studied in Computer Science and Economics over the years [Zhou, 1990; Dughmi and Ghosh, 2010; Mennle and Seuken, 2014]. We refer the interested reader to surveys [Abdulkadiro˘glu and S¨onmez, 2013; S¨onmez and ¨Unver, 2011]. [Bhalgat et al., 2011] studied the approximation ratio of matching mechanisms, when the objective is maximization of ordinal social welfare, a notion of efficiency that they define based solely on ordinal information.

Under the average-case analysis framework, [Zhang, 2018] tackled the scheduling unrelated machines problem and showed that the average-case approximation ratio of the mechanism devised in [Koutsoupias, 2014] is upper bounded by a constant, when the machines' costs follow any independent and identical distribution.

A similar notion but fundamentally different to our approach exists in Bayesian analysis [Chawla and Sivan, 2014; Hartline and Lucier, 2010]. We leave a more detailed discussion of the two notions to the next section after formally present the definition of the average-case approximation ratio, to highlight the comparison.

2 Preliminaries

We study the one-sided matching problem that consists of n agents and n indivisible items. The agents are endowed with von Neumann - Morgenstern utilities over the items. Throughout the paper, we denote the utility derived by agent i on obtaining a unit amount of item j by aij. In particular, following the classical literature [Zhou, 1990; Barbera, 2010], agents' preferences aij are represented by unit-range values. That is, with normalization, any agent i's valuation on its most preferred item is 1, i.e., maxj{aij} = 1, and its valuation on the least preferred item is 0, i.e., minj{aij} = 0. However, note that our model would be more general and some calculations would be cleaner if we drop these constraints but only require that 0 ≤ aij ≤ 1, ∀i, j ∈ [n]. A valuation profile (or interchangeably, an instance) of agents' preferences can be represented by a matrix A = [aij]n×n, where the row vector (ai1, . . . , ain) indicates the valuation of agent i's preference.

A matching mechanism collects agents' preference valuations and output an assignment of items to them. Denote a matching assignment by a matrix X = [xij]n×n, where xij indicates the probability of agent i receiving item j. So, a mechanism is a mapping from the input instance A to an output allocation X. Since there is an equal number of agents and items, X will be a doubly stochastic matrix. According to the Birkhoff - von Neumann Theorem, every doubly stochastic matrix can be decomposed into a convex combination of some permutation matrices. Therefore, any probabilistic allocation X can be interpreted as a convex combination of a set of deterministic allocations. We denote the set of all possible instances by A and denote the set of all possible allocation by X . Given a mechanism M and a valuation profile A ∈ A, as well as its allocation X(A) ∈ X, we denote the expected utility of agent i by ui(X(A)) = ∑j aijxij and denote the expected social welfare by SWM(X(A)) = ∑i ui(X(A)). When the context is clear, we drop the allocation notation and simply refer them by ui(A) and SWM(A).

In Mechanism Design, agents are self-interested and may misreport their values if that results in a better matching (from their perspective). We are interested in truthful mechanisms, under which agents cannot improve their utilities by misreporting. Formally, ui(ai, a-i) ≥ ui(a′i , a-i), ∀i, where ai is agent i's true valuations, a-i is other agents' valuations, and a′i is any possible misreported valuation from agent i. The mechanism which is the focus of this paper, Random Priority (RP), is a truthful mechanism. It fixes an ordering of the agents uniformly at random and then allocates them their most preferred item from the set of available items based on this ordering.

The canonical measure of efficiency loss due to the restriction to the class of truthful mechanisms, compared to the optimal social welfare, is the worst-case approximation ratio,

where SWOPT(A) = maxX∈X ∑ni=1 ui(X) is the optimal social welfare which is equal to the value of the maximum weight matching between agents and items. It is shown in [Filos-Ratsikas et al., 2014] that Random Priority achieves the matching approximation ratio bound of Θ(√n). The average-case approximation ratio of a truthful mechanism M is the expectation of the ratio of the optimal social welfare to the social welfare attained by mechanismM. That is,

where the valuation variable aij follows a distribution D. This notion of average-case analysis is a pointwise division that is in the same manner as the worst-case ratio rworst(M) and the smoothed ratio studied in [Deng et al., 2017]. When randomly draw an instance from a distribution, it informs us the expected value of how far is the social welfare attainable by a truthful mechanism M on the instance compared to the optimal social welfare on the same instance.

In Bayesian mechanism design, the dominant approach is the ratio of expectations, defined as E[SWOPT(A)] ≤ r · E[SWM(A)]. When one's interest is the expected social welfare of a mechanism over all possible inputs compared to the expected optimal social welfare, rather than a pointwise comparison over the same instance, the ratio of expectations would be more appropriate. In most cases, it is more tractable, as it calculates two expectations separately.

3 Independent and Identically Distributed Random Values

Subject to the unit-range normalization, there are two preset values (0 and 1, respectively) in each row of a preference matrix A. Let S be the set of indices such that their corresponding entries in A are preset. That is, S = {(i, j) : aij = 0 or aij = 1}. Obviously, |S| = 2n, where | ∗ | denotes the cardinality of a set 1 . In this section, we allow the remaining n2 - 2n values to be independent and identically distributed random variables following a distribution D with expectation µ and variance σ2 , i.e., aij ∼ D[0, 1], ED[aij] = µ,Var[aij] = σ2 , ∀i, j. We will show that the average-case approximation ratio of RP is upper bounded by a constant, for any distribution D[0, 1]. In order to prove our main results, we partition the average-case ratio into two cases according to the social welfare attainable by RP. We carefully choose a scalar such that in one case, the probability that the social welfare attainable by RP is smaller than the scalar is asymptotically small (even if there is a large efficiency loss in this case), and in the other case, the social welfare attainable by RP is asymptotically close to the optimal social welfare. En route to complying with these two conditions simultaneously, we employ the Central Limit Theorem and control the rate that the normalized sum of individual values converges to a normal distribution by carefully calibrating a scalar.

1 It does not matter which 2n of these valuations aij are preset. Our proofs hold for any choice of these 2n entries in A.

One of the tools that we use to control the convergence rate is the Berry-Esseen Theorem [Durrett, 2011].

Theorem 1 (Berry-Esseen) For n ≥ 1, let X1, · · · ,Xn be i.i.d. random variables such that E[X1] = 0 and D[X1] = σ2 . Denote Sn = X1+···+Xn σ√n and Fn(x) = Pr{Sn ≤ x}. Then

where Φ(x) is the cumulative distribution function of the standard Normal distribution, and 0.409 < C < 0.475.

Now we will use the Berry-Esseen Theorem and the Central Limit Theorem to prove a key lemma.

Lemma 1 For a given preference instance A, the probability that the social welfare SWRP (A) attainable by Random Priority is less than λ, is bounded by the following inequality.

where C is the constant in the Berry-Esseen Theorem and λ = 1 + µ(n - 2) - σ√ 2(n-2) n lnn.

Proof: Firstly, for any preference instance A, the social welfare attainable by Random Priority is lower bounded by the following inequality.

Therefore,

Secondly, since aij are i.i.d. random variables and E[aij] = µ,Var[aij] = σ2 , ∀i, j, we know that aij - µ are i.i.d. random variables such that E[aij - µ] = 0,Var[aij - µ] = σ2 , ∀i, j. Let

and Gn(n-2)(x) = Pr{Tn(n-2) ≤ x}.

Following Theorem 1, the random variables Tn(n-2) converge in distribution to the standard Normal distribution N(0, 1). That is, Tn(n-2) d-→N(0, 1). In addition, the rate of convergence is bounded by

where (i, j) /∈ S, and the second inequality holds because 0 < aij < 1 and 0 < µ < 1. Therefore,

Let x = -√2 lnn. Obviously, -x → +∞ when n approaches infinity. Following (2), we get that

Combining (1) and (3), we prove that

We shall see that λ was chosen such that λ ∼ Θ(n), and Pr {SWRP (A) ≤ λ} ∼ O( 1n ). After establishing these building blocks, we are ready to prove the main theorem of this section.

Theorem 2 The average-case approximation ratio of Random Priority, when agents' preferences are independent and identically distributed random variables, is upper bounded by the constant 1/µ, where µ is the expectation of these random variables.

Proof: To calculate the expectation of the ratio of the optimal social welfare to the social welfare attained by RP, we partition the value space of the ratio into two cases according to the threshold parameter λ. In each case, we multiply the ratio by the probability that the case occurs. That is,

Here we plugged in the fact that SWOPT(A) ≤ n, for any instance A.

In addition, as shown in [Filos-Ratsikas et al., 2014], rworst ∼ Θ(√n), there exists a constant c1, such that rworst ≤ c1 · √n, for sufficiently large n. Also, it is obvious that Pr{SWRP (A) > λ} ≤ 1. Now, we plug in these fact and the results established in Lemma 1.

Since 1 1-|t| < 1 + 2|t|, when |t| < 12 . As long as ∣∣∣ 2n - 1 µn + σ√2 ln n µn ∣∣∣ < 1 2 , we conclude that

□

4 Independent but not Necessarily Identical Random Values

In this section, we further generalize the results in Section 3 to the scenario that the n2 - 2n elements in {aij|(i, j) /∈ S} are independent random values but are not restricted to following an identical distribution. So, they may have different expectations E[aij ] = µij and variance Var[aij ] = σ2 ij , ∀i, j. We will show that under mild conditions, the average-case approximation ratio of RP has a constant upper bound. The primary obstruction in this generalization is the difficulty to appropriately control the rate of convergence of the normalized sum of the random values, in order to obtain a constant upper bound. However, we are able to pinpoint a mild condition, such that when the random variables aij comply with the condition, we can establish similar building blocks to the last section. By carefully calibrating the parameter λ, we can assemble them in a compatible way to get a constant upper bound.

Firstly, we identify the following mild conditions:

(i) ∑(i,j)/∈S µij = Ω(n2 ); (ii) ∑(i,j)/∈S σ2 ij = ω(n). Note that there are n2 - 2n elements in the set {aij|(i, j) /∈ S}, so the first condition simply implies that there would not be many of these aij whose expectations are asymptotically small. The second condition merely implies that the variances of the valuations are not too small. In other words, the first condition excludes those instances that many agents' preferences are negligible; the second condition requires their preferences to admit a magnitude of variation.

Secondly, to control the rate of convergence, we will employ the following theorem which is a refined version of the Berry-Esseen Theorem. It holds for non-identically distributed random variables [Esseen, 1945].

Theorem 3 Let Z1, · · · ,Zn be independent random variables such that E[Zi] = 0, D[Zi] = σ2 i , and E[|Zi|]3 < ∞. Denote Xn = Z1+···+Zn √∑i σ2 i and Fn(x) = Pr{Xn ≤ x}. Then there exists a constant C ′ such that

where Φ(x) is the CDF of the standard Normal distribution.

Now, let Zij := aij -µij, where (i, j) /∈ S. Denote their normalized sum of Zij and the CDF ofXn(n-2) by

With this carefully chosen value of λ, we are able to show the following lemma.

Lemma 2 For a given preference matrix A, the probability that the social welfare SWRP (A) attainable by Random Priority is less than λ, is bounded by the following inequality.

where C ′ is the constant in Theorem 3.

Proof: On the one hand, SWRP (A) ≥ 1 + 1n ∑(i,j)̸∈S aij implies that

On the other hand, according to Theorem 3, there exists a constant C ′ , such that

Therefore, ∀x,

Let x = -√2 lnn. Obviously, -x → +∞ when n approaches infinity. Following (5), we obtain that

Combining (4) and (6), we complete the proof. □

Finally, we are ready to prove the main theorem of this section.

Theorem 4 The average-case approximation ratio of Random Priority, when agents' preferences are independent but not necessarily identically distributed random variables, is upper bounded by a constant.

Proof: We partition the value space of the ratio into two cases according to the threshold parameter λ. In each case, we multiply the ratio by the probability that the case occurs. That is,

We assemble the above building blocks and get that

According to the first condition, there ∃µ, ∃N0, such that ∀n > N0, n2 ∑ µij ≤ 1µ . Note that 0 < aij < 1 and 0 < µij < 1, so ∑ µij < n2 , hence 1µ > 1. We also know that ∑ σ2 ij < n2 . Together with the first condition, we have that √2 lnn · √∑ σ2 ij ∑ µij → 0 and n ∑ µij → 0, when n → ∞. Therefore, there ∃N1, such that when n > N1, ∣∣∣∣ √2 ln n√∑ σ2 ij ∑ µij - n ∑ µij ∣∣∣∣ < 1 2 . Hence, when

n > max{N0, N1}, we have that

Because of condition (ii), we know that √n √∑ σ2 ij → 0. In conclusion,

5 Conclusion

This paper extended the average-case analysis in [Deng et al., 2017] from a uniform distribution to any independent distribution and showed a constant upper bound of the approximation ratio. The average-case analysis complements classical worst-case analysis when the worst-case performance is insufficient to characterize the performance of a mechanism. Our results further justify the wide-applicability of the Random Priority mechanism.

There are a few technical points we would like to highlight here. Firstly, the techniques presented in this paper are probably applicable to analyzing other mechanisms and other domains. Secondly, there are various generalizations of the Berry-Esseen Theorem, and each of them may be cast to prove similar results in Section 4. In an earlier version of the present paper, we had also independently proved a version of the convergence rate. The difference in utilizing different versions of these theorems is that they each require a set of conditions to make the rest of the proof work, and the interpretations of those conditions could be different.

There are a number of problems remain open as well. For example, one may be interested in investigating the averagecase ratio of Random Priority in correlated domains. Also, it would be interesting to proving tighter bounds by making more use of the structure of the assignment problem domain.