Open Access

Asymptotic Welfare Performance of Boston Assignment Algorithms

Geoffrey Pritchard
Geoffrey Pritchard
[email protected]
https://orcid.org/0000-0002-5660-4503
Statistics, University of Auckland, Auckland 1010, New Zealand;
Search for more papers by this author
,
Mark C. Wilson
Corresponding Author
Mark C. Wilson
[email protected]
https://orcid.org/0000-0002-3343-7458
Mathematics and Statistics, University of Massachusetts Amherst, Amherst, Massachusetts 01003
Search for more papers by this author

Geoffrey Pritchard

[email protected]

https://orcid.org/0000-0002-5660-4503

Statistics, University of Auckland, Auckland 1010, New Zealand;

Search for more papers by this author

Mark C. Wilson

Corresponding Author

Mark C. Wilson

[email protected]

https://orcid.org/0000-0002-3343-7458

Mathematics and Statistics, University of Massachusetts Amherst, Amherst, Massachusetts 01003

Search for more papers by this author

Published Online:24 Jan 2023https://doi.org/10.1287/stsy.2022.0104

Abstract

We make a detailed analysis in a special case of the Boston algorithm, which is widely used around the world to assign students to schools. We compute the limiting distribution in large random markets of both the utilitarian welfare and the order bias, a recently introduced average-case fairness measure. Our results show that the differences in utilitarian welfare between the Boston algorithms and the serial dictatorship (SD) algorithm are small and positive, whereas the differences in terms of order bias are large and positive. The naive implementation of the Boston algorithm beats its adaptive implementation on both utilitarian welfare and order bias, and both apparently beat SD on both criteria. In order to establish our results, we derive several basic results on the time evolution of the assignments made by the algorithms, which we expect to be useful for other applications. For example, we compute limiting distributions as a function of $θ \in [0, 1]$ of the exit time and preference rank obtained for an arbitrary agent whose initial relative position in the tiebreak order is θ.

1. Introduction

The school choice problem, involving matching students to places in schools, is of great theoretical and practical interest. The Boston mechanism is widely used in practice for school choice, despite criticism that it gives strategic incentives for agents (students and parents) to misrepresent their preferences. Its main rival is the (student-proposing) deferred acceptance (DA) mechanism, which is strategyproof; there is no incentive for students to misrepresent their preferences. However, it has been long known that DA pays a price in overall welfare for this. This important trade-off has been heavily studied.

Analysis of such mechanisms is not easy in full generality, and various simplifying assumptions are often made. As do many authors, we consider here the very special case in which each school has a single seat, schools have strict priorities given by a common tiebreak order over the students, and students have complete strict preferences over schools. This leads us to the house allocation (Hylland and Zeckhauser 1979) or one-sided matching problem, another classic problem in the area of allocation of indivisible goods. Note that this is different from the closely related housing market problem of Shapley and Scarf (1974) because in our case, agents do not start with an item and trade it but are simply matched to an item.

In the housing allocation framework, perhaps the most commonly seen mechanism in theory and practice is serial dictatorship (SD), which is strategyproof. The Boston algorithms are believed to generally outperform SD in overall welfare, but analytic results are currently lacking. The present paper derives precise asymptotic results to help fill this gap.

1.1. The Algorithms

In this paper, we consider three prominent algorithms: serial dictatorship and the naive and adaptive variants of the Boston mechanism. Each can be described (and may be implemented in practice) via a centralized procedure that takes an entire preference profile and outputs a matching of agents to items, but each is more easily and commonly interpreted as a dynamic process. This interpretation does not change the results because we care only about which agent ultimately obtains which item, not the process that delivers such an allocation. Each algorithm assumes an exogenous total order on agents, allowing them to take turns choosing or bidding for items.

SD is perhaps the most famous algorithm for housing allocation; each agent, in turn, chooses and is matched to the item he most prefers among those still available.

Naive Boston (NB) proceeds in rounds. In each round, some of the agents and items will be permanently matched, and the rest will be relegated to the following round. At round r ( $r = 1, 2 \dots$ ), each remaining unmatched agent, in turn, bids for his rth choice among all the items and will be matched to that item if it is still available.

Adaptive Boston (AB) is similar but differs in the bidding. At each round of this algorithm, each remaining agent, in turn, bids for his most-preferred item among those still available at the start of the round. The adaptive Boston mechanism takes fewer rounds to finish than the naive version because agents do not waste time bidding for items that have already been assigned to someone else in a previous round. Naive and adaptive Boston are identical in the first round but different thereafter; in round r, each remaining agent bids for his sth preference, where $s \geq r$ and s depends on the agent (and the history of the process so far).

1.2. Performance Measures

Comparisons between mechanisms require a performance measure (sometimes called a figure of merit) to assess the value of the matchings achieved. If such a measure is to be derived from the agents’ satisfaction with the items they are assigned, then in the absence of other information, it can only be based on their ordinal preference ranks for those items. One commonly used way to quantify this is to devise a positional scoring rule giving the utility $σ (s)$ derived by any agent from receiving his sth choice of item. In this paper, we consider two performance measures and two scoring rules. The normalized Borda score (also known as linear utility) for the sth preference among n items is $σ (s) = \frac{n - s}{n - 1}$ . For many purposes, any decreasing linear function of s would be equivalent. The other scoring rule is k-approval, which has $σ (s) = 1$ for $s \leq k$ and $σ (s) = 0$ for s > k.

Utilitarian welfare judges the value of a matching to be the total utility derived by all agents from the items they are assigned. Order bias (Freeman et al. 2021), a more recently introduced measure, is the maximum difference in expected utility obtained by any two agents. This is an average-case measure; the use of expected utilities implies averaging over a probability distribution on profiles and their resulting outcomes, a point we discuss. Usually but not always, the two agents whose expected utilities are maximally different will be the first and last agents in the exogenous choosing order.

1.3. Random Markets

A baseline probability model for preferences is that each agent has a preference order chosen at random, independently of other agents, with all possible permutations of the items being equally likely. This is often called the random market model or (sometimes in the social choice literature) impartial culture. Although far from realistic, this model has the advantage of mathematical tractability; it is often possible to obtain explicit distributional results for the outcomes of social-choice mechanisms in the random-market case.

1.4. Assumptions on Agent Behavior

We make the further assumption that agents are sincere; they do not misrepresent their preferences in an attempt to obtain a better outcome for themselves. Both Boston mechanisms are susceptible to this kind of manipulation, which can lead to worse outcomes for less adept players.

As a justification for this assumption, we offer two arguments. First, the random market model provides a partial defense against manipulation. If each agent knows only the (uniform) distribution of preferences of the other agents (which seems realistic in many applications), then there is no incentive to deviate from sincerity; in other words, the sincere profile is a Bayesian Nash equilibrium for the game induced by the mechanism. Second, understanding the social choice rule underlying a given mechanism is a first important step when comparing mechanisms, and the approach is often used in the literature.

In any case, from now on we shall ignore any issues of strategic behavior by agents.

1.5. Description of Our Results

This paper reports results on the asymptotic performance for the housing allocation problem of the Boston mechanisms in large random markets, where the number n of agents (and of items) tends to $\infty$ .

A key general observation regarding this setting is that agents’ preferences are rather diverse, so much so that with high probability, it is possible to match most of the agents to one of their first few preferences—and both Boston algorithms will successfully do so. More precisely, a given agent’s preference rank R for the item he is assigned has a probability distribution that converges to a limit as $n \to \infty$ . This means, in particular, that the value of R an agent is likely to obtain does not increase with n but has much the same distribution for any sufficiently large n. For the Boston mechanisms (but not for serial dictatorship), this is even true of the very last agent in the choosing order. This paper’s main results describe explicitly the limiting distributions for the preference rank obtained by an agent in a given position $θ \in [0, 1]$ in the choosing order, as a function of θ. We then obtain consequent results for the order bias and utilitarian welfare. To our knowledge, these are the first detailed analytic results on the rank distribution of allocations given by the Boston algorithms.

Our results suggest that serial dictatorship is (slightly) inferior to the Boston algorithms in utilitarian welfare and (very much) inferior in order bias.

1.6. Literature Review

We give a brief summary of some key references, with no claim to be complete. The housing allocation problem was formally introduced by Hylland and Zeckhauser (1979), the school choice problem was introduced by Abdulkadiroğlu and Sönmez (2003), and the Boston mechanism was introduced by Abdulkadiroğlu et al. (2005). The adaptive Boston mechanism was formalized by Mennle and Seuken (2021).

A persistent theme of the research literature is the inevitable trade-off between strategy proofness and agent welfare, and there is still much to be learned about these issues. SD is strategyproof, whereas neither Boston mechanism is; AB gives less incentive to strategize than NB (Mennle and Seuken 2021). A comparison of Boston and other school choice mechanisms shows that welfare is generally higher under Boston (Calsamiglia et al. 2020). The Boston mechanism has been studied axiomatically (Kojima and Ünver 2014, Dur et al. 2018). Several arguments in favor of the Boston mechanism have been made, mainly on the basis of improved efficiency/welfare (Miralles 2009, Abdulkadiroğlu et al. 2011), and several against (Ergin and Sönmez 2006, Pathak and Sönmez 2008), mainly on the basis of unfairness to agents who strategize poorly.

Several authors have studied the behavior of prominent algorithms for house allocation in the large random market model (Knuth 1996, Nikzad 2022, Ortega and Klein 2022) (we say more about their results in Section 8.2). More general analysis of entire classes of algorithms was performed by Che and Tercieux (2018), showing that under rather general conditions on the utility functions of agents and even allowing for some correlation in preferences, all Pareto efficient mechanisms (a class that includes Boston and SD) asymptotically achieve the maximum possible utilitarian welfare. Pycia (2019) showed that, for a more general class of problems that includes house allocation, most common measures of performance are asymptotically the same for all Pareto efficient and strategyproof mechanisms.

1.7. Outline of the Remainder of the Paper

Each section deals first with average-case results for an arbitrary initial segment of agents in the choosing order and then, with the fate of an individual agent at an arbitrary position.

The core technical results for naive Boston are Theorem 7 (number of agents remaining at a given round) and Theorem 9 (exit time of a given agent). For adaptive Boston, we have Theorem 10 (number of agents remaining at a given round), Theorem 12 (bids and exits at a given round), and Theorem 13 (fate of a given agent). The results involve recursively defined quantities $ω_{r}, z_{r}, y_{r}, u_{r s}$ .

The results for serial dictatorship are straightforwardly derived, but the Boston algorithms require nontrivial analysis. Of those, naive Boston is much easier because the exit time of an agent equals the preference rank of the item obtained by the agent. However, in adaptive Boston, this is no longer true, which necessitates substantial extra technical work.

We apply the basic results to compute utilitarian welfare in Section 3.1, the key result being Theorem 2 and its corollaries, and order bias in Section 3.2, the main results being Theorems 4–6. Sections 4–6 present and prove the technical results needed to establish the results. We give all remaining proofs of the main results in Section 7. In Section 8, we discuss the limitations and implications of our results and point out opportunities for future work.

2. Preliminaries

In this section, we list more formally the basic assumptions that delineate our study in this paper.

2.1. The Model

We assume throughout that n is a positive integer. An instance of the housing allocation problem of size n is defined by a set A_n of n agents and a set I_n of n items. Each agent has a complete strict preference ordering (linear order) of items, and together, these form a preference profile. We assume sincere behavior by all agents throughout—their submitted preference orders are identical to their sincere orders.

In addition, there is an exogenous linear order ρ on A_n. All of the algorithms we consider will rely on this order when agents are required to take turns choosing or bidding. We shall consider the fortunes of agents as functions of their position in the order ρ.

Definition 1.

Define the relative position of an agent a in the order ρ to be the fraction of all the agents whose position in ρ is no worse than that of a (this includes a itself). Thus, the first agent in ρ has relative position $1 / n$ , and the last has relative position 1. For $0 \leq θ \leq 1$ , let $A_{n} (θ)$ denote the set of agents whose relative position is at most θ, and let $a_{n} (θ)$ be the last agent in $A_{n} (θ)$ .

Remark 1.

For completeness, when $θ < 1 / n$ we let $a_{n} (θ)$ be the first agent in ρ. This exceptional definition will cause no trouble, as for $θ > 0$ it applies to only finitely many n and so, does not affect asymptotic results, whereas for θ = 0, it allows us to say something about the first agent in ρ.

We shall assume throughout that we deal with a random market. This means that each agent’s preference order is sampled independently from the uniform distribution on all $n!$ such orders of I_n. The order ρ on agents is not random but fixed. Our results deal exclusively with large random markets: that is, asymptotically as $n \to \infty$ .

2.2. Evolution of Assignments by the Algorithms

Each matching algorithm could be described and implemented as a two-step process. First, the agents generate their preference orders; then, a centralized procedure processes the preference profile and outputs a matching of agents to items. However, it is often more convenient to imagine the agents developing their preference orders as the algorithm proceeds rather than in advance. This interpretation does not change the result, only the process that delivers the final matching. The evolution of the assignments for the Boston algorithms can then be described by the following stochastic processes.

In the first round, the naive and adaptive Boston processes proceed identically; each agent randomly chooses one of the n items, independently of other agents and with uniform probabilities $\frac{1}{n}$ , as his most preferred item for which to bid. Each item that is so chosen is assigned to the first (in the sense of the agent order ρ) agent who bids for it; items not chosen by any agent are relegated, along with the unsuccessful agents, to the next round.

In the rth round ( $r \geq 2$ ), the naive algorithm causes each remaining agent to randomly choose his rth most-preferred item, independently of other agents and of his own previous choices, uniformly from the $n - r + 1$ items for which he has not previously bid. (Note that included among these are all the items still available in the current round.) Each item so chosen is assigned to the first agent who chose it; other items and unsuccessful agents are relegated to the next round.

In the rth round of the adaptive Boston algorithm, each agent repeatedly chooses his next most-preferred item by random sampling, without replacement, from the set of items he has not previously chosen until the item chosen is among those still available at this round. This item becomes his bid for the round. Bids are then resolved as in the naive mechanism. Each chosen item is assigned to the first agent who chose it; other items and unsuccessful agents are relegated to the next round.

Example 1.

Consider a situation with n = 4, agents $1, \dots 4$ and objects $a, b, c, d$ , and an exogenous order $1, 2, 3, 4$ on the agents. Suppose that agents 1, 3, 4 have a as their first choice, and agent 2 ranks b first. Under SD, agent 1 takes object a, and agent 2 takes b. We then proceed to agent 3, who must take his second choice—unless that is b, in which case he must be content with his third choice. Finally, agent 4 takes the last remaining object.

If the same four agents instead use NB, then in the first round, agent 1 takes a and agent 2 takes b. In the second round, agents 3 and 4 each bid for their second choice. Suppose these bids are b for agent 3 and c for agent 4; then, agent 4 takes c and agent 3 is relegated to the third round, in which he is the only participant. It is now inevitable that agent 3 will be matched to d, the only remaining item, but if we suppose that his third choice is c, he must first make a useless bid for that item before receiving d in the fourth round.

Should the same agents instead use AB, the first round is the same as for NB, but in the second round, agents 3 and 4 both bid for c, which is given to agent 3. The process terminates after the third round, in which agent 4 bids for and receives d.

Thus, if the partial profile looks like $1 : a, 2 : b, 3 : abc, 4 : a c$ , then under SD, we obtain the assignment $1 : a, 2 : b, 3 : c, 4 : d$ ; under NB, $1 : a, 2 : b, 3 : d, 4 : c$ ; and under AB, $1 : a, 2 : b, 3 : c, 4 : d$ . For each algorithm, every 1 of the 72 profiles consistent with this partial profile outputs the same assignment.

2.3. Performance Measures

To compare the performance of the algorithms, we impute utility to agents. This requires a means of converting ordinal preferences to numerical utility values.

Definition 2.

A positional scoring rule is given by a sequence ${(σ_{n} (s))}_{s = 1}^{n}$ of real numbers with $0 \leq σ_{n} (s) \leq σ_{n} (s - 1) \leq 1$ for $2 \leq s \leq n$ .

Each positional scoring rule defines an induced rank utility function, common to all agents; an agent matched to his sth preference derives utility $σ_{n} (s)$ therefrom. Commonly used scoring rules include k-approval defined by $(1, 1, \dots, 1, 0, 0, \dots, 0)$ , where the number of ones is fixed at k independent of n; when k = 1, this is the usual plurality rule. Note that k-approval is coherent; for all n, the utility of a fixed rank object depends only on the rank and not on n. Another well-known rule is Borda defined by $σ_{n} (s) = \frac{n - s}{n - 1}$ ; Borda is not coherent. Borda utility is often used in the literature, sometimes under the name linear utilities.

The (utilitarian) welfare performance measure is defined as follows. Suppose that an assignment mechanism for n agents matches $S_{n} (s, θ)$ of the agents with relative position at most θ to their sth preferences, for each $s = 1, 2, \dots$ . According to the utility function induced by the scoring rule ${(σ_{n} (s))}_{s = 1}^{n}$ , the welfare (total utility) of the agents with relative position at most θ is thus

W_{n} (θ) = \sum_{s = 1}^{n} σ_{n} (s) S_{n} (s, θ) .

(1)

Remark 2.

Note that the k-approval welfare is just the fraction of agents who obtain one of their top k choices. Also, the average rank of the item received by a random agent, another well used measure, equals $1 + n (1 - u)$ , where u is the expected Borda utility. Thus, $u \to 1$ as $n \to \infty$ if and only if the expected rank is o(n).

We also consider the order bias, an average-case performance measure recently introduced in Freeman et al. (2021). The relevant definitions are recalled here for an arbitrary discrete assignment algorithm $A$ that fixes an order on agents (such as the order ρ assumed in the present paper).

Definition 3.

The expected rank distribution under $A$ is the mapping $D_{A}$ on ${1, \dots, n} \times {1, \dots, n}$ whose value at (r, j) is the probability, under the random-market assumption, that $A$ assigns the rth agent his jth most-preferred item.

We usually represent this mapping as a matrix where the rows represent agents and the columns represent items.

Definition 4.

Let u be a common rank utility function for all agents; u(j) is the utility derived by an agent who obtains his jth preference. Define the order bias of $A$ by

β_{n} (A; u) = \frac{\max_{1 \leq p, q \leq n} | U (p) - U (q) |}{u (1) - u (n)},

where

U (p) = \sum_{j = 1}^{n} D_{A} (p, j) u (j)

, the expected utility of the item obtained by the pth agent.

It is often desirable that β_n be as small as possible, out of fairness to each position in the order in the absence of any knowledge of the profile. In any case, knowledge of the order bias is important. For example, we may wish to apply “affirmative action,” as is done for example in many sports draft procedures.

In all three mechanisms in this paper (naive and adaptive Boston and serial dictatorship), the two agents whose expected utilities are maximally different are the first and last agents in ρ. The first agent in ρ always obtains his first-choice item, and so has the best possible expected utility. The last agent in ρ has the smallest expected utility; this is a consequence of the following result.

Theorem 1

(Earlier Positions Do Better on Average). Let a be an agent in an instance of the house allocation problem with random-market preferences. Let the random variable S be the preference rank of the item obtained by a. The naive and adaptive Boston mechanisms and serial dictatorship all have the property that for all $s \geq 1, P (S > s)$ is monotone increasing in the relative position of a (i.e., greater for later agents in ρ).

Proof.

See Section 7. □

Remark 3.

Thus, the probability distribution of the preference rank of the item received by an agent stochastically dominates that for any later agent. For each common rank utility function u, the expected utility of agent a is $u (1) + \sum_{s = 1}^{n - 1} (u (s + 1) - u (s)) P (S > s)$ , so Theorem 1 implies that the expected utility is monotone decreasing in the relative position of a. In particular, the first agent has the highest and the last agent the lowest expected utility.

3. Main Results on Agent Satisfaction

In this section, we state the main results of this paper. Proofs are deferred to Section 7.

3.1. Welfare

In this section, we state results on the utilitarian welfare achieved by the three mechanisms.

For each $s = 1, 2, \dots$ , we denote by $S_{n} (s, θ)$ the number of agents with relative position at most θ who are matched to their sth preferences.

Theorem 2

(Asymptotic Welfare of the Mechanisms). Assume an assignment mechanism with

\frac{1}{n} S_{n} (s, θ) \overset{p}{\to} \int_{0}^{θ} q_{s} (ϕ) d ϕ a s n \to \infty, for each s = 1, 2, \dots,

where

\sum_{s = 1}^{\infty} q_{s} (θ) = 1

. Suppose the scoring rule

{(σ_{n} (s))}_{s = 1}^{n}

satisfies

σ_{n} (s) \to λ_{s} a s n \to \infty, for each s = 1, 2, \dots

Then, the welfare given by (1) satisfies

\frac{1}{n} W_{n} (θ) \overset{p}{\to} \sum_{s = 1}^{\infty} λ_{s} \int_{0}^{θ} q_{s} (ϕ) d ϕ .

Corollary 1.

The average k-approval welfare over all agents satisfies

\frac{1}{n} W_{n} (1) \overset{p}{\to} {\begin{array}{l} 1 - ω_{k + 1} & for naive Boston \\ (1 - e^{- 1}) \sum_{{(r, s) : r \leq s \leq k}} e^{1 - r} u_{r s} & for adaptive Boston \\ \frac{k}{k + 1} & for serial dictatorship . \end{array}

The sequence ω_k is defined by $ω_{1} = 1$ and the recursion $ω_{k + 1} = ω_{k} e^{- ω_{k}}$ for $k \geq 1$ . The bivariate sequence u_rs is defined by the recursion $u_{11} = 1, u_{1, s} = 0$ for s > 1, u_rs = 0 for s < r, and

u_{r s} = e^{1 - r} u_{r - 1, s - 1} + (1 - e^{1 - r}) u_{r, s - 1} .

The limiting values of k-approval welfare are given in some special cases in Table 1. Figure 1 shows the limiting values for the three-approval scoring rule. It shows that naive Boston outperforms the adaptive version, with much of the difference attributable to the last 20% of agents. Also, serial dictatorship is more favorable for agents in the middle of the order but much worse for those toward the end.

Table 1. Limiting Values as $n \to \infty$ of k-Approval Welfare

Table 1. Limiting Values as $n \to \infty$ of k-Approval Welfare

Algorithm	k = 1	k = 2	k = 3
Naive Boston	$1 - e^{- 1} \approx 0.632$	$1 - e^{- 1} e^{- e^{- 1}} \approx 0.745$	$1 - e^{- 1} e^{- e^{- 1}} e^{- e^{- e^{- 1}}} \approx 0.803$
Adaptive Boston	$1 - e^{- 1} \approx 0.632$	$(1 - e^{- 1}) (1 + e^{- 2}) \approx 0.718$	$(1 - e^{- 1}) (1 + 2 e^{- 2} - e^{- 3} + e^{- 5}) \approx 0.776$
Serial dictatorship	$1 / 2 = 0.500$	$2 / 3 \approx 0.667$	$3 / 4 = 0.750$

**Figure 1. Limiting Values as $n \to \infty$ of Cumulative Three-Approval Welfare as a Function of θ**

Corollary 2.

Let σ be a positional scoring rule such that for all but finitely many s, $σ_{n} (s) = 0$ for all n. Then, the asymptotic utilitarian welfare with respect to σ is strictly greater under naive Boston than under serial dictatorship.

This last result is intuitively reasonable because naive Boston maximizes the number of agents receiving their first choice, then subject to that the number receiving their second choice, etc. Note that this is not a proof because it may be that NB makes choices that may prevent it beating SD in some lower ranks. Adaptive Boston apparently scores better than serial dictatorship for each k and worse than naive Boston, although we do not yet have a formal proof. Figure 2 illustrates this for $1 \leq k \leq 10$ . Already for k = 3, the algorithms give similar welfare results, and they each asymptotically approach one as $k \to \infty$ .

Figure 2. Limiting Values as $n \to \infty$ of k-Approval Welfare for $1 \leq k \leq 10$
*Note*. (Top line) Naive Boston. (Middle line) Adaptive Boston. (Bottom line) Serial dictatorship.

In contrast to the results for k-approval, the Borda welfare does not distinguish asymptotically between the three algorithms.

Corollary 3.

For an assignment mechanism as in Theorem 2, the Borda welfare satisfies

\frac{1}{n} W_{n} (θ) \overset{p}{\to} θ .

Corollary 4.

For each of naive Boston, adaptive Boston, and serial dictatorship, the average normalized Borda welfare over all agents is asymptotically equal to one, and hence, the average rank obtained by an agent is o(n).

Remark 4.

Note that the Borda utility of a fixed preference rank s has the limit $λ_{s} = 1$ , meaning that, in the asymptotic limit as $n \to \infty$ , agents value the sth preference (of n) just as highly as the first preference. Consequently, mechanisms such as serial dictatorship or the Boston algorithms, which in a random market, are able to give most agents one of their first few preferences, achieve the same asymptotic Borda welfare as if every agent was matched to his first preference. This behavior is really a consequence of the normalization of the Borda utilities $σ_{n} (s) = \frac{n - s}{n - 1}$ to the interval $[0, 1]$ ; the first few preferences all have utility close to one.

A striking feature of our welfare results is that although the Boston algorithms have a utilitarian welfare advantage over serial dictatorship, the advantage is rather small. Asymptotically, both achieve maximum possible welfare under the Borda scoring rule. Under k-approval for fixed k, there is an advantage to Boston that of course decreases with k. These results are consistent with those of Che and Tercieux (2018), which state that under rather weak conditions, Pareto efficient mechanisms all asymptotically attain the maximum possible utilitarian welfare (normalized to one in our results). This is because the k-approval utility function does not satisfy the hypotheses of the results in Che and Tercieux (2018), and although neither does Borda, that case is similar to the special case with $U (x, y) = y$ ; the utilities are chosen independently and uniformly distributed on $[0, 1]$ , so that the utility of the kth preference will be approximately $1 - \frac{k}{n}$ if n is large.

3.2. Order Bias

In this section, we state results on the order bias achieved by the three mechanisms. Proofs are mostly deferred to Section 7.

Theorem 3.

For each fixed k, the k-approval order bias of naive Boston is asymptotically $\prod_{j = 2}^{k + 1} (1 - ω_{j})$ , where $(ω_{j})$ is as given in Definition 5.

Theorem 4.

For each fixed k, the k-approval order bias of adaptive Boston is asymptotically

1 - e^{- 1} \sum_{{(r, s) : r \leq s \leq k}} {(1 - e^{- 1})}^{r - 1} u_{r s} .

$(u_{r s})$ is as given in (17).

Theorem 5.

The Borda order bias of each Boston mechanism is asymptotically zero.

The order bias of serial dictatorship is easy to analyze; we include the results here for comparison with the Boston mechanisms.

Theorem 6.

Fix $k \geq 1$ and $n \geq 1$ .

The k-approval order bias for serial dictatorship equals $1 - \frac{k}{n}$ .
The Borda order bias for serial dictatorship equals $1 / 2$ .

Corollary 5.

For each fixed k, the k-approval order bias of SD is asymptotically equal to 1, and the Borda order bias is asymptotically equal to 1/2.

Figure 3 compares the asymptotic k-approval order bias for $1 \leq k \leq 10$ . Table 2 gives some numerical values.

Figure 3. Limiting Values as $n \to \infty$ of k-Approval Order Bias for $1 \leq k \leq 10$
*Note*. (Top line) Serial dictatorship. (Middle line) Adaptive Boston. (Bottom line) Naive Boston.

Table 2. Limiting Quantities for k-Approval Order Bias

Table 2. Limiting Quantities for k-Approval Order Bias

Algorithm	k = 1	k = 2	k = 3
NB	$1 - e^{- 1} \approx 0.632$	$(1 - e^{- 1}) (1 - e^{- 1} e^{- e^{- 1}}) \approx 0.471$	$(1 - e^{- 1}) (1 - e^{- 1} e^{- e^{- 1}}) (1 - e^{- 1} e^{- e^{- 1}} e^{- e^{- e^{- 1}}}) \approx 0.378$
AB	$1 - e^{- 1} \approx 0.632$	$(1 - e^{- 1}) (1 - e^{- 2}) \approx 0.547$	$(1 - e^{- 1}) (1 - e^{- 2}) - {(1 - e^{- 1})}^{2} (e^{- 2} + e^{- 4}) \approx 0.485$
SD	1	1	1

There is a large difference between mechanisms in their order bias. For k-approval, serial dictatorship is asymptotically as biased as it could be, whereas the Boston algorithms have much lower bias. The Boston algorithms are asymptotically unbiased with respect to our normalized Borda utilities, whereas SD has bias 1/2 for every n. In other words, when n is large then under SD, the last agent receives a random rank item, whereas under the Boston algorithms, this agent is quite likely to get one of his top few choices.

4. Technical Results and Proofs for Naive Boston

Theorem 2 involves a random quantity, which in the asymptotic limit as $n \to \infty$ , approximates a constant (nonrandom) fraction of n. There are several more results of this kind in this section and the next one. A useful first move in approaching such results is to replace the random quantity with its expectation.

Lemma 1.

Let $(X_{n})$ be a sequence of nonnegative random variables with $Var (X_{n}) \leq E [X_{n}]$ and $\frac{1}{n} E [X_{n}] \to c$ as $n \to \infty$ , for some constant c. Then, $\frac{1}{n} X_{n} \overset{p}{\to} c$ as $n \to \infty$ (convergence in probability).

Remark 5.

The bounding of the variance of a random variable by its mean implies a distribution with relatively little variation about the mean when the mean is large. Lemma 1 makes use of this behavior to provide us with a stepping stone to establish results like Theorem 2 by performing an average-case analysis only. The same idea works if the averages are conditional expectations, as in the following lemma.

Lemma 2.

Let $(X_{n})$ be a sequence of nonnegative random variables and $(F_{n})$ a sequence of σ-fields, with $Var (X_{n} | F_{n}) \leq E [X_{n} | F_{n}]$ and $\frac{1}{n} E [X_{n} | F_{n}] \overset{p}{\to} c$ as $n \to \infty$ . Then, $\frac{1}{n} X_{n} \overset{p}{\to} c$ as $n \to \infty$ .

Proof of Lemmas 1 and 2.

Lemma 1 is just the special case of Lemma 2, in which all the σ-fields $F_{n}$ are trivial. For a proof of Lemma 2, it suffices to show that $\frac{1}{n} (X_{n} - E [X_{n} | F_{n}]) \overset{p}{\to} 0$ . For any $ϵ > 0$ , we have by Chebyshev’s inequality (Durrett 2019)

P (| X_{n} - E [X_{n} | F_{n}] | > ϵ n | F_{n}) \leq {(ϵ n)}^{- 2} Var (X_{n} | F_{n}) \leq {(ϵ n)}^{- 2} E [X_{n} | F_{n}] .

Because $n^{- 2} E [X_{n} | F_{n}] \overset{p}{\to} 0$ , it follows that $P (| X_{n} - E [X_{n} | F_{n}] | > ϵ n | F_{n}) \overset{p}{\to} 0$ . As these conditional probabilities are a bounded (and thus, uniformly integrable) sequence, the convergence is also in $L_{1}$ (theorem 4.6.3 in Durrett 2019), and so,

P (\frac{1}{n} | X_{n} - E [X_{n} | F_{n}] | > ϵ) = E [P (| X_{n} - E [X_{n} | F_{n}] | > ϵ n | F_{n})] \to 0,

giving the required convergence in probability. □

In the present analysis, the random variables will mostly be numbers of agents who are successful (or not) at a given round of one of the Boston mechanisms. The next lemma provides the necessary variance bounds in such cases.

Lemma 3.

Suppose we have m items ( $m \geq 2$ ), of which $ℓ$ are blue. A sequence of agents (Agent 1, Agent 2, $\dots$ ) each randomly (independently and uniformly) chooses an item. Let $A \subseteq N$ be a subset of the agents, and let C_A be the number of blue items first chosen by a member of A. Equivalently, C_A is the number of members of A who choose a blue item that no previous agent has chosen: that is, the cardinality of the set

{a \in A : Q_{a} i s blue and Q_{b} \neq Q_{a} \forall b < a},

where Q_a denotes the item chosen by a. Then,

Var (C_{A}) \leq E [C_{A}] = \frac{ℓ}{m} \sum_{a \in A} {(1 - \frac{1}{m})}^{a - 1} .

Remark 6.

Lemma 3 describes a situation congruent to the way bids are resolved in a round of the naive Boston mechanism. The “blue” items correspond to those still available at the start of the round, and C_A is the number of members of A who successfully obtain an item during the round. In the actual naive Boston algorithm, the set of unavailable items that an agent may still bid for will typically be different for different agents, but the number of them ( $m - ℓ$ ) is the same for all agents, which is all that matters for our purposes.

Lemma 3 is also applicable to the adaptive Boston mechanism. In this case, $ℓ = m$ ; agents bid only for items still available at the start of the round.

Proof of Lemma 3.

Let F_i denote the agent who is first to choose item I and X_ia the indicator of the event ${F_{i} = a}$ . That is, X_ia = 1 if and only if F_i = a. We have $P (F_{i} = a) = \frac{1}{m} {(1 - \frac{1}{m})}^{a - 1}$ ; agent a must choose i, whereas all previous agents choose items other than i. Let B be the set of blue items. Then, $C_{A} = \sum_{i \in B} \sum_{a \in A} X_{i a}$ , so

E [C_{A}] = \sum_{i \in B} \sum_{a \in A} P (F_{i} = a) = \sum_{i \in B} \sum_{a \in A} \frac{1}{m} {(1 - \frac{1}{m})}^{a - 1} = \frac{ℓ}{m} \sum_{a \in A} {(1 - \frac{1}{m})}^{a - 1},

as claimed. Also,

E [C_{A}^{2}] = \sum_{i \in B} \sum_{j \in B} \sum_{a \in A} \sum_{b \in A} E [X_{i a} X_{j b}] .

(2)

For $a \neq b$ , these summands are identical for all $i \neq j$ (and zero for i = j); for a = b, they are identical for all i = j (and zero for $i \neq j$ ). Thus, (2) reduces to

E [C_{A}^{2}] = ℓ (ℓ - 1) \sum_{a, b \in A; a \neq b} E [X_{1, a} X_{2, b}] + ℓ \sum_{a \in A} E [X_{1, a}] .

(3)

The second term of (3) is $E [C_{A}]$ again. For a < b and $i \neq j$ , we have

E [X_{i a} X_{j b}] = P (F_{i} = a and F_{j} = b) = {(1 - \frac{2}{m})}^{a - 1} \frac{1}{m} {(1 - \frac{1}{m})}^{b - a - 1} \frac{1}{m} .

(Agents prior to a must choose neither i nor j, a must choose i, agents between a and b must choose items other than j, and b must choose j.) Because $1 - \frac{2}{m} < {(1 - \frac{1}{m})}^{2}$ , this gives

E [X_{i a} X_{j b}] \leq \frac{1}{m^{2}} {(1 - \frac{1}{m})}^{a + b - 3} .

(4)

As this last expression is symmetric in a and b, (4) also holds for a > b. Hence,

E [C_{A}^{2}] \leq E [C_{A}] + \frac{ℓ (ℓ - 1)}{m^{2}} \sum_{a, b \in A; a \neq b} {(1 - \frac{1}{m})}^{a + b - 3} .

We have $\frac{ℓ (ℓ - 1)}{m^{2}} = \frac{ℓ^{2}}{m^{2}} (1 - \frac{1}{ℓ}) \leq \frac{ℓ^{2}}{m^{2}} (1 - \frac{1}{m})$ because $ℓ \leq m$ . This gives

E [C_{A}^{2}] \leq E [C_{A}] + \frac{ℓ^{2}}{m^{2}} \sum_{a, b \in A; a \neq b} {(1 - \frac{1}{m})}^{a + b - 2},

enabling us to bound the variance as required;

Var (C_{A}) = E [C_{A}^{2}] - E {[C_{A}]}^{2}

, and so,

\begin{array}{l} Var (C_{A}) - E [C_{A}] \leq \frac{ℓ^{2}}{m^{2}} \sum_{a, b \in A; a \neq b} {(1 - \frac{1}{m})}^{a + b - 2} - {(\frac{ℓ}{m} \sum_{a \in A} {(1 - \frac{1}{m})}^{a - 1})}^{2} \\ = \frac{ℓ^{2}}{m^{2}} (\sum_{a, b \in A; a \neq b} {(1 - \frac{1}{m})}^{a + b - 2} - \sum_{a, b \in A} {(1 - \frac{1}{m})}^{a + b - 2}) \\ \leq 0 . □ \end{array}

The limiting constants for the naive Boston algorithm will often involve terms of the following sequence.

Definition 5.

The sequence ${(ω_{r})}_{r = 1}^{\infty}$ is defined by $ω_{1} = 1$ and the recursion $ω_{r + 1} = ω_{r} e^{- ω_{r}}$ for $r \geq 1$ .

Thus, for example, $ω_{1} = 1, ω_{2} = e^{- 1}, ω_{3} = e^{- 1} e^{- e^{- 1}}$ . The value of ω_r approximates $r^{- 1}$ , a relationship made more precise in the following result.

Lemma 4.

For all $r \geq 3$ ,

\frac{1}{r + \log r} < ω_{r} < \frac{1}{r} .

Proof.

For $3 \leq r \leq 8$ , the inequalities can be verified by direct calculation. Beyond this, we rely on induction; assume the result for a given $r \geq 8$ , and consider $ω_{r + 1}$ . Observe that the function $x \mapsto x e^{- x}$ is monotone increasing on $[0, 1]$ ; this gives us

ω_{r + 1} = ω_{r} e^{- ω_{r}} < \frac{e^{- 1 / r}}{r} = \frac{1}{r + 1} \exp (\log (1 + \frac{1}{r}) - \frac{1}{r}) \leq \frac{1}{r + 1}

via the well-known inequality

\log (1 + x) \leq x

. Also,

\begin{array}{l} ω_{r + 1} = ω_{r} e^{- ω_{r}} > \frac{e^{- 1 / (r + \log r)}}{r + \log r} \\ \geq \frac{1}{r + 1 + \log (r + 1)} (1 + \frac{1 + \log (r + 1) - \log r}{r + \log r}) (1 - \frac{1}{r + \log r}) \end{array}

via the well-known inequality

e^{- x} \geq 1 - x

. Thus,

\begin{array}{l} ω_{r + 1} > \frac{1}{r + 1 + \log (r + 1)} (1 + \frac{(r - 1 + \log r) (\log (r + 1) - \log r) - 1}{{(r + \log r)}^{2}}) \\ > \frac{1}{r + 1 + \log (r + 1)} (1 + \frac{- 2 + \log r}{(r + 1) {(r + \log r)}^{2}}) \end{array}

because

\log (r + 1) - \log r = \int_{r}^{r + 1} t^{- 1} d t > \frac{1}{r + 1} .

For $r \geq 8$ , we have $\log r > 2$ , and so, the result follows. □

4.1. Groups of Agents

In this subsection, we present results concerning the fortunes of those agents whose relative positions fall in an interval.

Theorem 7

(Number of Agents Remaining). Consider the naive Boston algorithm. Fix $r \geq 1$ and a relative position $θ \in [0, 1]$ . Then, the number $N_{n} (r, θ)$ of members of $A_{n} (θ)$ present at round r satisfies

\frac{1}{n} N_{n} (r, θ) \overset{p}{\to} z_{r} (θ) .

where

z_{1} (θ) = θ

and

z_{r + 1} (θ) = z_{r} (θ) - (1 - e^{- z_{r} (θ)}) ω_{r} for r \geq 1 .

(5)

In particular, the total number of agents (and of items) present at round r satisfies

\frac{1}{n} N_{n} (r, 1) \overset{p}{\to} ω_{r} .

Proof.

Induct on r. For r = 1, the result is immediate because $N_{n} (1, θ) = ⌊ n θ ⌋$ . Now, fix $r \geq 1$ , and assume the result for round r. Let $F_{r}$ be the σ-field generated by events prior to round r. Conditional on $F_{r}$ , we have the situation of Lemma 3; there are $N_{n} (r)$ available items and $N_{n} (r, θ)$ agents of $A_{n} (θ)$ who will be the first to attempt to claim them, with the agents’ bids chosen independently and uniformly from a larger pool of $n - r + 1$ items. Letting S_n denote the number of these agents whose bids are successful, Lemma 3 gives

Var (S_{n} | F_{r}) \leq E [S_{n} | F_{r}] = \frac{N_{n} (r)}{n - r + 1} \sum_{a = 1}^{N_{n} (r, θ)} {(1 - \frac{1}{n - r + 1})}^{a - 1} .

Summing the geometric series,

E [S_{n} | F_{r}] = N_{n} (r) (1 - {(1 - \frac{1}{n - r + 1})}^{N_{n} (r, θ)}) .

It then follows by the inductive hypothesis that

\frac{1}{n} E [S_{n} | F_{r}] \overset{p}{\to} ω_{r} (1 - e^{- z_{r} (θ)}) as n \to \infty .

By Lemma 2,

\frac{1}{n} S_{n} \overset{p}{\to} ω_{r} (1 - e^{- z_{r} (θ)}) .

We have $N_{n} (r + 1, θ) = N_{n} (r, θ) - S_{n}$ and so, obtain

\frac{1}{n} N_{n} (r + 1, θ) \overset{p}{\to} z_{r} (θ) - ω_{r} (1 - e^{- z_{r} (θ)}) = z_{r + 1} (θ) .

The result follows. □

Some of the functions $z_{r} (θ)$ are illustrated in Figure 4. Note that agents with an earlier position in ρ are more likely to exit in the early rounds. A consequence is that the position of an unsuccessful agent relative to other unsuccessful agents tends to improve each time he fails to claim an item.

**Figure 4. The Limiting Fraction of the Agents Who Have Relative Position θ or Better and Survive to Participate in the rth Round**

Corollary 6

(Limiting Distribution of Exit Time/Preference Rank Obtained). The number $S_{n} (s, θ)$ of members of $A_{n} (θ)$ matched to their sth preference satisfies

\frac{1}{n} S_{n} (s, θ) \overset{p}{\to} \int_{0}^{θ} q_{s} (ϕ) d ϕ .

where

q_{s} (θ) = z_{s}^{'} (θ) - z_{s + 1}^{'} (θ) = z_{s}^{'} (θ) ω_{s} e^{- z_{s} (θ)} .

In particular, the fraction of agents who exit at round s satisfies

\frac{1}{n} S_{n} (s, 1) \overset{p}{\to} ω_{s} - ω_{s + 1} .

Proof.

An agent is matched to his sth preference if, and only if, he is present at round s but not at round s + 1. The result follows by Theorem 7. □

The limiting functions $q_{s} (θ)$ are illustrated in Figure 5 (note that the vertical scale is logarithmic).

Figure 5. The Limiting Probability That an Agent Exits the Naive Boston Mechanism at the rth Round (and So, Obtains His rth Preference) as a Function of the Agent’s Initial Relative Position θ
*Note*. Logarithmic scale on the vertical axis.

A better understanding of the functions $z_{r} (θ)$ is given by the following result.

Theorem 8.

The functions $z_{r} (θ)$ satisfy $z_{r} (θ) = \int_{0}^{θ} z_{r}^{'} (ϕ) d ϕ$ , where

z_{r}^{'} (θ) = \prod_{k = 1}^{r - 1} f_{k} (θ) for r \geq 2, and z_{1}^{'} (θ) = 1

(6)

f_{r} (θ) = 1 - ω_{r} \exp (- z_{r} (θ)) .

(7)

In particular,

z_{r}^{'} (1) = \prod_{k = 2}^{r} (1 - ω_{k})

(8)

f_{r} (1) = ω_{r + 1} .

(9)

Proof.

Differentiate (5) with respect to θ. Alternatively, integrate (6) by parts. □

The quantity $f_{r} (θ)$ can be interpreted (in a sense to be made precise later) as the conditional probability that an agent with relative position θ, if present at round r, is unmatched at that round. The quantity $z_{r}^{'} (θ)$ can then be interpreted as the probability that an agent with relative position θ is still unmatched at the beginning of round r. Other quantities for the first few rounds are shown in Table 3.

Table 3. Limiting Quantities as $n \to \infty$ for the Early Rounds of the Naive Boston Algorithm

Table 3. Limiting Quantities as $n \to \infty$ for the Early Rounds of the Naive Boston Algorithm

Meaning at round r	Quantity	r = 1	r = 2	r = 3
Fraction of all agents
Present	ω_r	1	$e^{- 1} \approx 0.3679$	$\exp (- 1 - e^{- 1}) \approx 0.2546$
In $A_{n} (θ)$ and present	$z_{r} (θ)$	θ	$θ + e^{- θ} - 1$	$θ + e^{- θ} - 1 - e^{- 1} + \exp (- θ - e^{- θ})$
For an agent with relative position θ
P(present)	$z'_{r} (θ)$	1	$1 - e^{- θ}$	$(1 - e^{- θ}) (1 - \exp (- θ - e^{- θ}))$
P(unmatched—present)	$f_{r} (θ)$	$1 - e^{- θ}$	$1 - \exp (- θ - e^{- θ})$	$1 - \exp (- θ - e^{- θ} - \exp (- θ - e^{- θ}))$

4.2. Individual Agents

Theorem 7 and Corollary 6 are concerned with the outcomes achieved by the agent population collectively and will yield the results in Section 3.1 on utilitarian welfare.

Suppose, however, that our interest lies with individual agents. It is tempting to informally “differentiate” the result of Theorem 7 with respect to θ and thereby, draw conclusions about the fate of a single agent. The following result puts those conclusions on a sound footing.

Theorem 9

(Exit Time of Individual Agent). Consider the naive Boston algorithm. Fix $r \geq 1$ and a relative position $θ \in [0, 1]$ . Let $R_{n} (θ)$ denote the round number at which the agent $a_{n} (θ)$ (the last agent with relative position at most θ) is matched. Equivalently, $R_{n} (θ)$ is the preference rank of the item obtained by this agent. Then,

P (R_{n} (θ) \geq r) \to z_{r}^{'} (θ) a s n \to \infty .

Proof.

The result is trivial for r = 1. Assume the result for a given value of r, and let $F_{r}$ be the σ-field generated by events prior to round r. Conditional on $F_{r}$ , we can apply Lemma 3 to the single agent $a_{n} (θ)$ to obtain

P (R_{n} (θ) \geq r + 1) = E [P (R_{n} (θ) \geq r + 1 | F_{r})] = E [1_{R_{n} (θ) \geq r} Y_{n}],

(10)

where

Y_{n} = 1 - {(1 - \frac{1}{n - r + 1})}^{N_{n} (r, θ) - 1} (\frac{N_{n} (r)}{n - r + 1}) .

Observe that $Y_{n} \overset{p}{\to} 1 - ω_{r} e^{- z_{r} (θ)} = f_{r} (θ)$ from Theorem 7. Equation (10) gives

P (R_{n} (θ) \geq r + 1) - z_{r + 1}^{'} (θ) = E [1_{R_{n} (θ) \geq r} (Y_{n} - f_{r} (θ))] + E [1_{R_{n} (θ) \geq r} - z_{r}^{'} (θ)] f_{r} (θ) .

The second term converges to zero as $n \to \infty$ by the inductive hypothesis. For the first term, note that the convergence $Y_{n} - f_{r} (θ) \overset{p}{\to} 0$ is also convergence in $L_{1}$ by theorem 4.6.3 in Durrett (2019) and so, $1_{R_{n} (θ) \geq r} (Y_{n} - f_{r} (θ)) \to 0$ in $L_{1}$ also. □

Remark 7.

The result of Theorem 9 could equivalently be stated as

P (R_{n} (θ) = r) \to q_{r} (θ),

where

q_{r} (θ)

is as in Corollary 6. Note that

\sum_{r = 1}^{\infty} q_{r} (θ) = 1

, consistent with the role of

q_{r} (θ)

as an asymptotic probability.

Remark 8.

Theorem 9 tells us that an agent with fixed relative position θ has a good chance of obtaining one of his first few preferences, even if n is large. This is even true of the very last agent (θ = 1). For example, the first agent is guaranteed his first choice, and an agent at relative position 1/2 has probability over 78%, whereas the last agent has corresponding probability just under 37%.

5. Technical Results and Proofs for Adaptive Boston

We again begin with results about initial segments of the queue of agents and follow up with results about individual agents. More work is required than in the naive case because the rank of the object obtained is not the same as the round in which it is obtained.

5.1. Groups of Agents

A simple stochastic model of bidding for the adaptive Boston mechanism can be similar to the naive case. At the beginning of the rth round, each remaining agent randomly chooses an item as his next preference for which to bid; the bid is successful and the agent is matched to that item if no other agent with an earlier position in the order ρ bids for the same item. However, whereas a naïve Boston participant chooses from the set of $n - r + 1$ items for which he has not already bid, the adaptive Boston participant chooses from a smaller set: the $N_{n} (r)$ items actually still available at the beginning of the round. This model allows a result analogous to Theorem 7.

Theorem 10

(Number of Agents Remaining). Consider the adaptive Boston algorithm. Fix $r \geq 1$ and a relative position $θ \in [0, 1]$ . Then, the number $N_{n} (r, θ)$ of members of $A_{n} (θ)$ present at round r satisfies

\frac{1}{n} N_{n} (r, θ) \overset{p}{\to} y_{r} (θ) .

where

y_{1} (θ) = θ

and

y_{r + 1} (θ) = y_{r} (θ) - e^{1 - r} (1 - \exp (- e^{r - 1} y_{r} (θ))) for r \geq 1 .

(11)

In particular, the total number $N_{n} (r)$ of agents (and of items) present at round r satisfies

\frac{1}{n} N_{n} (r) \overset{p}{\to} y_{r} (1) = e^{1 - r} .

Proof.

Induct on r. For r = 1, we have $N_{n} (1, θ) = ⌊ n θ ⌋$ ; the result follows immediately. Now, suppose the result for a given value of r, and consider r + 1. Let T_n be the number of agents of $A_{n} (θ)$ matched at round r. Conditioning on the σ-field $F_{r}$ generated by events prior to round r, we have the situation of Lemma 3 (with $ℓ = m$ ); there are $N_{n} (r)$ available items and $N_{n} (r, θ)$ agents of $A_{n} (θ)$ who will be the first to attempt to claim them, with each such agent bidding for one of the available items, chosen uniformly at random independently of other agents. Lemma 3 gives us $Var (T_{n} | F_{r}) \leq E [T_{n} | F_{r}]$ and

E [T_{n} | F_{r}] = \sum_{a = 1}^{N_{n} (r, θ)} {(1 - \frac{1}{N_{n} (r)})}^{a - 1} = N_{n} (r) (1 - {(1 - \frac{1}{N_{n} (r)})}^{N_{n} (r, θ)}) .

By the inductive hypothesis,

\frac{N_{n} (r)}{n} \overset{p}{\to} e^{1 - r} and {(1 - \frac{1}{N_{n} (r)})}^{N_{n} (r, θ)} \overset{p}{\to} \exp (- e^{r - 1} y_{r} (θ)) .

This gives us

\frac{1}{n} E [T_{n} | F_{r}] \overset{p}{\to} e^{1 - r} (1 - \exp (- e^{r - 1} y_{r} (θ))) = y_{r} (θ) - y_{r + 1} (θ) .

By Lemma 2, then

\frac{1}{n} T_{n} \overset{p}{\to} y_{r} (θ) - y_{r + 1} (θ) .

Because $T_{n} = N_{n} (r, θ) - N_{n} (r + 1, θ)$ , it follows that $\frac{1}{n} N_{n} (r + 1, θ) \overset{p}{\to} y_{r + 1} (θ)$ and hence, the result. □

Remark 9.

Some of the functions $y_{r} (θ)$ are illustrated in Figure 4. It is apparent that the adaptive Boston mechanism proceeds more quickly than naive Boston; $e^{1 - r}$ decays much more quickly than ω_r as $r \to \infty$ . Also, the tendency of advantageously ranked agents to be matched in relatively early rounds is even greater for the adaptive version of the algorithm. In an adaptive Boston assignment of a large number of items to agents with random-market preferences, under 2% of the agents will be unmatched after four rounds (versus 16% for naive Boston), and most of these (about 2/3) will be among the last 10% of agents in the original agent order.

A better understanding of the functions $y_{r} (θ)$ is given by the following result, which is analogous to Theorem 8.

Theorem 11.

The functions $y_{r} (θ)$ satisfy $y_{r} (θ) = \int_{0}^{θ} y_{r}^{'} (ϕ) d ϕ$ , where

y_{r}^{'} (θ) = \prod_{k = 1}^{r - 1} g_{k} (θ) for r \geq 2, and y_{1}^{'} (θ) = 1

(12)

g_{r} (θ) = 1 - \exp (- e^{r - 1} y_{r} (θ)) .

(13)

In particular,

y_{r}^{'} (1) = {(1 - e^{- 1})}^{r - 1}

(14)

g_{r} (1) = 1 - e^{- 1} .

(15)

Proof.

Differentiate (11) with respect to θ. Alternatively, integrate (12) by parts. □

Remark 10.

The quantity $g_{r} (θ)$ is analogous to $f_{r} (θ)$ in the naive case and can be interpreted (in a sense to be made precise later) as the conditional probability that an agent with relative position θ, if present at round r, is unmatched at that round. The quantity $y_{r}^{'} (θ)$ , analogous to $z_{r}^{'} (θ)$ in the naive case, can then be interpreted as the probability that an agent with relative position θ is still unmatched at the beginning of round r. Other quantities for the first two rounds are shown in Table 4.

Table 4. Limiting Quantities for the Early Rounds of the Adaptive Boston Algorithm

Table 4. Limiting Quantities for the Early Rounds of the Adaptive Boston Algorithm

Meaning at round r	Quantity	r = 1	r = 2
Fraction of all agents
Present	$e^{1 - r}$	1	$e^{- 1} \approx 0.3679$
In $A_{n} (θ)$ and present	$y_{r} (θ)$	θ	$θ + e^{- θ} - 1$
For an agent with relative position θ
P(present)	$y_{r}^{'} (θ)$	1	$1 - e^{- θ}$
P(unmatched—present)	$g_{r} (θ)$	$1 - e^{- θ}$	$1 - \exp (- e (θ + e^{- θ} - 1))$
P(bids for sth preference—present)	u_rs	$1_{s = 1}$	$e^{- 1} {(1 - e^{- 1})}^{s - 2} 1_{s \geq 2}$

5.1.1. The Rank of the Item Received.

Theorem 10 is less satisfying than Theorem 7. The naive Boston mechanism has a key simplifying feature; the rank of an item within its assigned agent’s preference order is equal to the round number in which it was matched. This means that Theorem 7 already enables some conclusions about agents’ satisfaction with the outcome of the process (see Corollary 6). However, in the adaptive case, we know only that an item matched at round r > 1 will be no better (and could be worse) than its assigned agent’s rth preference.

To do better, we need a more detailed stochastic bidding model. An agent a still present at the beginning of the rth round will have thus far determined an initial subsequence of his preference order comprising some number $F_{a, r - 1}$ of most-preferred items and failed to obtain any of them. He thus has a pool of $n - F_{a, r - 1}$ previously unconsidered items from which to choose, of which the $N_{n} (r)$ items actually still available are a subset. In accordance with the random market model, let us imagine that he now generates further preferences by repeated random sampling without replacement from the previously unconsidered items, until one of the available items is sampled; this item becomes his bid in the current round. Denote by G_ar the number of items sampled to construct this bid; thus, $F_{a r} = \sum_{j = 1}^{r} G_{a j}$ and $G_{a, 1} = 1$ . If the bid is successful, the agent will be matched to his F_arth preference.

Note that although the simple bidding model used in Theorem 10 provides enough information to determine the matching of items to agents (along with the round numbers at which the items are matched), it does not completely determine the agents’ preference orders. In particular, it does not determine the agents’ preference ranks for the items they are assigned. The random variables G_ar provide additional information sufficient to determine this interesting feature of the outcome.

It is convenient to think of the G_ar and F_ar as being determined by an auxiliary process that runs after the simple bidding model has been run and the matching of agents to items determined. This auxiliary process can be described in the following way. Fix integers $n_{1} > n_{2} > \dots > n_{r} > 0$ .

Place n₁ balls, numbered from one to n₁, in an urn.
For $i = 1, \dots, r$ ,
- deem the n_i lowest-numbered balls remaining in the urn “good,” and
- draw balls at random from the urn, without replacement, until a good ball is drawn.

Let $H (n_{1}, \dots, n_{r})$ be the probability distribution of the total number of balls drawn and $q (s; n_{1}, \dots, n_{r}) = P (X = s)$ , where $X \sim H (n_{1}, \dots, n_{r})$ .

Denote by $M$ the σ-field generated by the simple bidding model, including the items on which each agent bids and the resulting matching. Conditional on $M$ , the random variable F_ar for an agent a still present at round r has the $H (n, N_{n} (2), \dots, N_{n} (r))$ distribution. That is,

P (F_{a r} = s | M) = q (s; n, N_{n} (2), \dots, N_{n} (r)) .

(16)

Also, the ${F_{a r} : a present at round r}$ are conditionally independent given $M$ .

Lemma 5.

$q (1; n_{1}) = 1$ , $q (s; n_{1}) = 0$ for s > 1, and $q (s; n_{1}, \dots, n_{r}) = 0$ for s < r or $s > n_{1} - n_{r} + 1$ . The $H (n_{1}, \dots, n_{r})$ distribution’s other probabilities are given by the recurrence

q (s; n_{1}, \dots, n_{r}) = \sum_{t = r - 1}^{s - 1} q (t; n_{1}, \dots, n_{r - 1}) (\frac{n_{r}}{n_{1} - s + 1}) \prod_{0 \leq i < s - t - 1} (1 - \frac{n_{r}}{n_{1} - t - i}) .

Proof.

Let N be the number of balls drawn in the first r – 1 iterations of the process and M the number drawn in the final iteration. Then, $P (N + M = s) = \sum_{t = r - 1}^{s - 1} P (N = t) P (M = s - t | N = t)$ , and we have

P (M = s - t | N = t) = (\frac{n_{r}}{n_{1} - s + 1}) \prod_{0 \leq i < s - t - 1} (1 - \frac{n_{r}}{n_{1} - t - i}) .

(The final iteration must first sample $s - t - 1$ consecutive nongood balls; the probabilities of achieving this are $1 - \frac{n_{r}}{n_{1} - t}$ for the first, $1 - \frac{n_{r}}{n_{1} - t - 1}$ for the second, $\dots 1 - \frac{n_{r}}{n_{1} - s + 2}$ for the last. At last, a good ball must be drawn; the probability of this is $\frac{n_{r}}{n_{1} - s + 1}$ .) The result follows. □

Our interest in the $H (n_{1}, \dots, n_{r})$ distribution mostly concerns its asymptotic limits as the numbers of balls become large, and the “without replacement” stipulation becomes unimportant. To this end, fix $p_{1}, \dots, p_{r} \in (0, 1]$ , and let $u (s; p_{1}, \dots, p_{r}) = P (r + \sum_{i = 1}^{r} G_{i} = s)$ , where $G_{1}, \dots, G_{r}$ are independent random variables with geometric distributions: $P (G_{i} = x) = p_{i} {(1 - p_{i})}^{x}$ for $x = 0, 1, \dots$ .

Lemma 6.

$u (s; p) = p {(1 - p)}^{s - 1}$ , $u (s; p_{1}, \dots, p_{r}) = 0$ for s < r, and

u (s; p_{1}, \dots, p_{r}) = \sum_{t = r - 1}^{s - 1} u (t; p_{1}, \dots, p_{r}) p_{r} {(1 - p_{r})}^{s - t - 1} .

Proof.

P (r + \sum_{i = 1}^{r} G_{i} = s) = \sum_{t = r - 1}^{s - 1} P (r - 1 + \sum_{i = 1}^{r - 1} G_{i} = t) P (1 + G_{r} = s - t) . □

Lemma 7.

q (s; n_{1}, \dots, n_{r}) \to u (s; p_{1}, \dots, p_{r}) a s n_{1}, \dots, n_{r} \to \infty with \frac{n_{i}}{n_{1}} \to p_{i} .

Proof.

Take limits in Lemma 5; compare Lemma 6. □

Corollary 7.

Consider the adaptive Boston mechanism, and fix s. We have

q (s; n, N_{n} (2), \dots, N_{n} (r)) \overset{p}{\to} u (s; 1, e^{- 1}, \dots, e^{1 - r}) a s n \to \infty .

Proof.

Use the convergence of $\frac{1}{n} N_{n} (i)$ given by Theorem 10. □

Corollary 7 and (16) give us an asymptotic limit for the distribution, conditional on $M$ , of F_ar, the preference rank of the bid made at round r by an agent still present at that round. To condense notation, we will denote the limit $u (s; 1, e^{- 1}, \dots, e^{1 - r})$ by u_rs. That is,

P (F_{a r} = s | M) \overset{p}{\to} u_{r s} .

Note that the limit u_rs does not depend on the position of the agent a in the choosing order. It is fairly clear why this should be so; all remaining agents must enter their bids at the beginning of the round, before any other agent has bid, and so, the bidding process, at least, treats them symmetrically. The advantage arising from a favorable position lies in a higher probability of obtaining the item bid for, not in constructing the bid itself.

We make use of the following simplified recurrence.

Lemma 8.

$u (s; p) = p {(1 - p)}^{s - 1}$ and $u (s; p_{1}, \dots, p_{r}) = 0$ for s < r; other values are given by the recurrence

u (s; p_{1}, \dots, p_{r}) = p_{r} u (s - 1; p_{1}, \dots, p_{r - 1}) + (1 - p_{r}) u (s - 1; p_{1}, \dots, p_{r}) .

In particular, $u_{11} = 1, u_{1, s} = 0$ for s > 1, u_rs = 0 for s < r, and

u_{r s} = e^{1 - r} u_{r - 1, s - 1} + (1 - e^{1 - r}) u_{r, s - 1} .

(17)

Proof.

The recurrence in (17) has a unique solution, as does the one in Lemma 6. It is easy to check that either solution also satisfies the other recurrence. □

Remark 11.

It follows directly from (17) that the bivariate generating function $F (x, y) = \sum_{r, s} u_{r s} x^{r} y^{s}$ satisfies the defining equation $F (x, y) (1 - y) = x y + F (x / e, y) (x - e)$ . It follows directly (from substituting y = 1) that $\sum_{s = r}^{\infty} u_{r s} = 1$ , consistent with its role as a probability distribution. We have not found a nicer explicit formula for u_rs.

We can now state a more detailed version of Theorem 10.

Theorem 12

(The Bidding Process at a Given Round). Consider the adaptive Boston algorithm. Fix $s \geq r \geq 1$ and a relative position $θ \in [0, 1]$ . Let $y_{r} (θ)$ be as in Theorem 10 and u_rs be as in Lemma 8.

The number $N_{n} (r, s, θ)$ of members of $A_{n} (θ)$ making a bid for their sth preference at round r satisfies
$\frac{1}{n} N_{n} (r, s, θ) \overset{p}{\to} u_{r s} y_{r} (θ) .$
The number $U_{n} (r, s, θ)$ of members of $A_{n} (θ)$ making an unsuccessful bid for their sth preference at round r satisfies
$\frac{1}{n} U_{n} (r, s, θ) \overset{p}{\to} u_{r s} y_{r + 1} (θ) .$
The number $S_{n} (r, s, θ)$ of members of $A_{n} (θ)$ making a successful bid for their sth preference at round r satisfies
$\frac{1}{n} S_{n} (r, s, θ) \overset{p}{\to} u_{r s} (y_{r} (θ) - y_{r + 1} (θ)) .$

Proof.

Conditional on the σ-field $M$ , each agent a participating in round r enters a bid for his F_arth preference; the F_ar for this group of agents is conditionally independent given $M$ . Thus, the conditional distribution of $N (r, s, θ)$ given $M$ is the binomial distribution with $N_{n} (r, θ)$ trials and success probability $P (F_{a r} = s | M)$ given by (16). The variance of a binomial distribution never exceeds its mean (Feller 1970), so Lemma 2 applies. We will thus obtain part (i) of the theorem if we can merely show that $\frac{1}{n} E [N_{n} (r, s, θ) | M] \overset{p}{\to} u_{r s} y_{r} (θ)$ ; that is,

\frac{1}{n} N_{n} (r, θ) q (s; n, N_{n} (2), \dots, N_{n} (r)) \overset{p}{\to} u_{r s} y_{r} (θ) .

(18)

Theorem 10 gives $\frac{1}{n} N_{n} (r, θ) \overset{p}{\to} y_{r} (θ)$ , and Corollary 7 gives $q (s; n, N_{n} (2), \dots, N_{n} (r)) \overset{p}{\to} u_{r s}$ . Part (i) follows.

The proof of part (ii) is very similar; the conditional distribution of $U (r, s, θ)$ given $M$ is the binomial distribution with $N_{n} (r + 1, θ)$ trials and success probability $P (F_{a r} = s | M)$ given by (16). Part (iii) follows from parts (i) and (ii). □

We now have the analog for adaptive Boston of Corollary 6.

Corollary 8

(Limiting Distribution of Preference Rank Obtained). The number $S_{n} (s, θ)$ of members of $A_{n} (θ)$ matched to their sth preference satisfies

\frac{1}{n} S_{n} (s, θ) \overset{p}{\to} \int_{0}^{θ} q_{s} (ϕ) d ϕ .

where

q_{s} (θ) = \sum_{r = 1}^{s} u_{r s} (y_{r}^{'} (θ) - y_{r + 1}^{'} (θ)) = \sum_{r = 1}^{s} u_{r s} y_{r}^{'} (θ) \exp (- e^{r - 1} y_{r} (θ)) .

In particular,

\frac{1}{n} S_{n} (s, 1) \overset{p}{\to} (1 - e^{- 1}) \sum_{r = 1}^{s} e^{1 - r} u_{r s} .

Proof.

This is an immediate consequence of part (iii) of Theorem 12, with Theorem 11 providing the integral form of the limit. □

The functions $q_{s} (θ)$ are illustrated in Figure 6. Figure 7 shows for the last agent (θ = 1) the distribution of the rank of the item bid for and the item obtained at the second round.

Figure 6. The Limiting Probability $q_{s} (θ)$ That an Agent Obtains His sth Preference via the Adaptive Boston Mechanism as a Function of the Agent’s Initial Relative Position θ
*Note*. Logarithmic scale on the vertical axis.

**Figure 7. Distribution of Rank of the Item for Which the Last Agent Bids (Upper Dots) and Successfully Bids (Lower Dots) in Round 2, Adaptive Boston**

Remark 12.

It is clear from the definition (and Remark 11) that $\sum_{s = 1}^{\infty} q_{s} (θ) = 1$ . This is consistent with the implied role of $q_{s} (θ)$ as a probability distribution: the limiting probability that an agent in position θ obtains his sth preference. See also Theorem 13, part (iv).

5.2. Individual Agents

If we wish to follow the fate of a single agent in the adaptive Boston mechanism, we need limits analogous to that of Theorem 9. These are provided by the following result.

Theorem 13

(Exit Time and Rank Obtained for Individual Agent). Consider the adaptive Boston algorithm. Fix $s \geq r \geq 1$ and a relative position $θ \in [0, 1]$ . Let $V_{n} (r, θ)$ denote the preference rank of the item for which the agent $a_{n} (θ)$ (the last agent with relative position at most θ) bids at round r. (For completeness, set $V_{n} (r, θ) = 0$ whenever $a_{n} (θ)$ is not present at round r.) Let $R_{n} (θ)$ denote the round number at which $a_{n} (θ)$ is matched.

(Agent present at round r.)
$P (R_{n} (θ) \geq r) \to y_{r}^{'} (θ) a s n \to \infty .$
(Agent bids for sth preference at round r.)
$P (V_{n} (r, θ) = s) \to y_{r}^{'} (θ) u_{r s} a s n \to \infty .$
(Agent matched to sth preference at round r.)
$P (R_{n} (θ) = r and V_{n} (r, θ) = s) \to y_{r}^{'} (θ) u_{r s} (1 - g_{r} (θ)) a s n \to \infty .$
(Agent matched to sth preference.)
$P (V_{n} (R_{n} (θ), θ) = s) \to q_{s} (θ) a s n \to \infty .$

The limiting quantities $y_{r}^{'} (θ), g_{r} (θ)$ , u_rs, and $q_{s} (θ)$ are as defined in Theorem 11, Lemma 8, and Corollary 8.

Proof.

Part (i) is proved in a similar way to Theorem 9. The result is trivial for r = 1. Assume the result for a given value of r, and let $F_{r}$ be the σ-field generated by events prior to round r. Then,

P (R_{n} (θ) \geq r + 1) = E [P (R_{n} (θ) \geq r + 1 | F_{r})] = E [1_{R_{n} (θ) \geq r} Y_{n}],

(19)

where (by applying Lemma 3 (with

ℓ = m

) to the single agent

a_{n} (θ)

)

Y_{n} = 1 - {(1 - \frac{1}{N_{n} (r)})}^{N_{n} (r, θ) - 1} .

Observe that $Y_{n} \overset{p}{\to} 1 - \exp (- e^{r - 1} y_{r} (θ)) = g_{r} (θ)$ by Theorem 10. Equation (19) gives

P (R_{n} (θ) \geq r + 1) - y_{r + 1}^{'} (θ) = E [1_{R_{n} (θ) \geq r} (Y_{n} - g_{r} (θ))] + E [1_{R_{n} (θ) \geq r} - y_{r}^{'} (θ)] g_{r} (θ) .

The second term converges to zero as $n \to \infty$ by the inductive hypothesis. For the first term, note that the convergence $Y_{n} - g_{r} (θ) \overset{p}{\to} 0$ is also convergence in $L_{1}$ by theorem 4.6.3 in Durrett (2019) and so, $1_{R_{n} (θ) \geq r} (Y_{n} - g_{r} (θ)) \to 0$ in $L_{1}$ also. Part (i) follows.

For part (ii), we have

P (V_{n} (r, θ) = s) = E [1_{R_{n} (θ) \geq r} P (F_{a_{n} (θ), r} = s | M)] = E [1_{R_{n} (θ) \geq r} q (s; n, N_{n} (2), \dots, N_{n} (r))] .

Hence,

P (V_{n} (r, θ) = s) - u_{r s} y_{r}^{'} (θ) = E [1_{R_{n} (θ) \geq r} (q (s; n, N_{n} (2), \dots, N_{n} (r)) - u_{r s})] + u_{r s} (P (R_{n} (θ) \geq r) - y_{r}^{'} (θ)) .

(20)

Both terms converge in probability to zero. For the second term, the convergence is given by part (i). For the first term, it is a consequence of Corollary 7: $q (s; n, N_{n} (2), \dots, N_{n} (r)) \overset{p}{\to} u_{r s}$ , which is also convergence in $L_{1}$ by theorem 4.6.3 in Durrett (2019). Part (ii) follows.

The proof of part (iii) is very similar to that of part (ii); just replace $1_{R_{n} (θ) \geq r}$ by $1_{R_{n} (θ) = r}$ and $y_{r}^{'} (θ)$ by $y_{r}^{'} (θ) - y_{r + 1}^{'} (θ)$ .

Part (iv) is obtained from part (iii) by summation over r. □

6. Technical Results and Proofs for Serial Dictatorship

Unlike the Boston algorithms, SD is strategyproof, but it is known to behave worse in welfare and fairness. However, we are not aware of detailed quantitative comparisons in the literature. The analysis for SD is very much simpler than for the Boston algorithms. In particular, the exit time is not interesting.

6.1. Groups of Agents

Analysis in this case is much simpler than for the Boston algorithms. Results analogous to those in Sections 4 and 5 are obtainable from the following explicit formula.

Theorem 14.

The probability that the kth agent obtains his sth preference is $(\begin{matrix} n - s \\ k - s \end{matrix}) / (\begin{matrix} n \\ k - 1 \end{matrix})$ for $s = 1, \dots, k$ and zero for other values of s.

Proof.

By the time agent k gets an item, a random subset T of k – 1 of the n items is already taken. This agent’s sth preference will be the best one left if and only if T includes his first s – 1 preferences but not the sth preference. Of the $(\begin{matrix} n \\ k - 1 \end{matrix})$ equally probable subsets T, the number satisfying this condition is $(\begin{matrix} n - s \\ k - s \end{matrix})$ ; the remaining k – s items in T must be chosen from n – s possibilities. □

In particular, the nth and last agent is equally likely to get each possible item.

Corollary 9

(Preference Rank Obtained). Consider the serial dictatorship algorithm. Fix $s \geq 1$ and a relative position $θ \in [0, 1]$ . The number $S_{n} (s, θ)$ of members of $A_{n} (θ)$ matched to their sth preference satisfies

\frac{1}{n} S_{n} (s, θ) \overset{p}{\to} \int_{0}^{θ} q_{s} (ϕ) d ϕ,

where

q_{s} (θ) = θ^{s - 1} (1 - θ)

Proof.

Let $p_{k n} = (\begin{matrix} n - s \\ k - s \end{matrix}) / (\begin{matrix} n \\ k - 1 \end{matrix})$ . Let X_kn be the indicator of the event that the kth agent (of n) is matched to his sth preference; thus, $E [X_{k n}] = p_{k n}$ and $Var (X_{k n}) = p_{k n} (1 - p_{k n})$ . The impartial culture model requires agents to choose their preferences independently; thus, the random variables ${(X_{k n})}_{k = 1}^{n}$ are independent. We have

S_{n} (s, θ) = \sum_{k = s}^{⌊ n θ ⌋} X_{k n},

and so,

E [S_{n} (s, θ)] = \sum_{k = s}^{⌊ n θ ⌋} p_{k n}

and

Var (S_{n} (s, θ)) = \sum_{k = s}^{⌊ n θ ⌋} p_{k n} (1 - p_{k n})

. Hence,

Var (S_{n} (s, θ)) \leq E [S_{n} (s, θ)]

, and Lemma 1 applies. It now remains only to show that

\frac{1}{n} E [S_{n} (s, θ)] \to \int_{0}^{θ} q_{s} (ϕ) d ϕ

Note that

p_{k n} = \frac{(n - k + 1) \cdot (k - 1) (k - 2) \dots (k - s + 1)}{n (n - 1) \dots (n - s + 1)} = (1 - \frac{k - 1}{n}) \prod_{j = 1}^{s - 1} (\frac{k - j}{n - j}) .

Hence,

\frac{1}{n} E [S_{n} (s, θ)] = \frac{1}{n} \sum_{k = s}^{⌊ n θ ⌋} (1 - \frac{k - 1}{n}) \prod_{j = 1}^{s - 1} (\frac{k - j}{n - j}) = \int_{0}^{θ} f_{n} (ϕ) d ϕ,

where

f_{n} (ϕ) = {\begin{array}{l} (1 - \frac{k - 1}{n}) \prod_{j = 1}^{s - 1} (\frac{k - j}{n - j}) & for \frac{k - 1}{n} \leq ϕ < \frac{k}{n}, k = s, \dots, ⌊ n θ ⌋ \\ 0 & otherwise . \end{array}

As $n \to \infty, f_{n} (ϕ) \to (1 - ϕ) ϕ^{s - 1}$ pointwise; because we also have $0 \leq f_{n} (ϕ) \leq 1$ , the dominated convergence theorem (Durrett 2019) ensures that $\int_{0}^{θ} f_{n} (ϕ) d ϕ \to \int_{0}^{θ} (1 - ϕ) ϕ^{s - 1} d ϕ$ . □

6.2. Individual Agents

For individual agents, we have the following analogous result.

Theorem 15

(Preference Rank Obtained). Consider the serial dictatorship algorithm. Fix $s \geq 1$ and a relative position $θ \in [0, 1]$ . The probability that agent $a_{n} (θ)$ (the last with relative position at most θ) is matched to his sth preference converges to $q_{s} (θ) = θ^{s - 1} (1 - θ)$ as $n \to \infty$ .

Proof.

From Theorem 14, this probability is

(1 - \frac{⌊ n θ ⌋ - 1}{n}) \prod_{j = 1}^{s - 1} (\frac{⌊ n θ ⌋ - j}{n - j}) .

The result follows immediately. □

Figure 8 compares the limiting values of $S_{n} (3, θ)$ for our three algorithms. There is an interesting relationship between the curves. For small θ, AB is most likely to get its third choice, followed by NB and then SD. For most of the range, SD is the most likely, and NB overtakes AB only around $θ = 0.65$ . Near θ = 1, SD drops dramatically, consistent with what we already know about how badly the last 10%–20% of agents are treated under SD.

**Figure 8. Limiting Values as $n \to \infty$ of the Probability of Getting One’s Third Choice as a Function of θ**

7. Remaining Proofs of Theorems

In this section, we provide proofs of results not provided earlier in the paper.

Proof of Theorem 1.

Let a₁ and a₂ be consecutive agents, with a₂ immediately after a₁ in ρ. Let S₁ and S₂ be the preference ranks of the items obtained by a₁ and a₂. It will suffice to show that $P (S_{1} > s) \leq P (S_{2} > s)$ . To this end, consider an alternative instance of the problem in which a₁ and a₂ exchange preference orders before the allocation mechanism is applied. We will refer to this instance and the original one as the “exchanged” and “nonexchanged” processes, respectively. Denote by $S_{1}^{'}$ and $S_{2}^{'}$ the preference ranks of the items obtained by a₁ and a₂ in the exchanged process. Because the exchanged process is also a random market, S₁ and $S_{1}^{'}$ have the same probability distribution and similarly, S₂ and $S_{2}^{'}$ .

We now show that all three of our allocation mechanisms have the property that $S_{1} \leq S_{2}^{'}$ . From this, the result will follow because $S_{1} \leq S_{2}^{'} \Rightarrow P (S_{1} > s) \leq P (S_{2}^{'} > s) = P (S_{2} > s)$ .

For serial dictatorship, the exchanged and nonexchanged processes evolve identically for agents preceding a₁ and a₂. In the nonexchanged process, agent a₁ then finds that his first $S_{1} - 1$ preferences are already taken; in the exchanged process, these same items are the first $S_{1} - 1$ preferences of a₂. Hence, $S_{2}^{'} \geq S_{1}$ .

For the Boston mechanisms, let R be the number of unsuccessful bids made by a₁ in the nonexchanged process. Then, the exchanged and nonexchanged processes evolve identically for the first R rounds, except that the bids of a₁ and a₂ are made in reversed order; this reversal has no effect on the availability of items to other agents. After these R rounds, a₁ (in the nonexchanged process) and a₂ (in the exchanged process) have reached the same point in their common preference order; in the next round, both will bid for the S₁th preference in this order. Hence, $S_{2}^{'} \geq S_{1}$ . □

Proof of Theorem 2.

For convenience, define $σ_{n} (s) = 0$ when n < s; this allows us to write $W_{n} (θ) = \sum_{s = 1}^{\infty} σ_{n} (s) S_{n} (s, θ)$ . For any fixed $s'$ , the finite sum $Y_{n} (s')$ defined by

Y_{n} (s') = \sum_{s = 1}^{s'} (σ_{n} (s) \frac{S_{n} (s, θ)}{n} - λ_{s} \int_{0}^{θ} q_{s} (ϕ) d ϕ)

has

Y_{n} (s') \overset{p}{\to} 0

n \to \infty

. We have

\frac{W_{n} (θ)}{n} - \sum_{s = 1}^{\infty} λ_{s} \int_{0}^{θ} q_{s} (ϕ) d ϕ = Y_{n} (s') + \sum_{s > s'} σ_{n} (s) \frac{S_{n} (s, θ)}{n} - \sum_{s > s'} λ_{s} \int_{0}^{θ} q_{s} (ϕ) d ϕ,

and so,

| \frac{W_{n} (θ)}{n} - \sum_{s = 1}^{\infty} λ_{s} \int_{0}^{θ} q_{s} (ϕ) d ϕ | \leq | Y_{n} (s') | + \sum_{s > s'} \frac{S_{n} (s, θ)}{n} + \sum_{s > s'} \int_{0}^{θ} q_{s} (ϕ) d ϕ

(21)

(because

0 \leq σ_{n} (s) \leq 1

). Note also that

\sum_{s = 1}^{s'} \frac{S_{n} (s, θ)}{n} \overset{p}{\to} \sum_{s = 1}^{s'} \int_{0}^{θ} q_{s} (ϕ) d ϕ

, whereas

\sum_{s = 1}^{\infty} \frac{S_{n} (s, θ)}{n} = \frac{⌊ n θ ⌋}{n} \to θ = \sum_{s = 1}^{\infty} \int_{0}^{θ} q_{s} (ϕ) d ϕ,

and so,

\sum_{s > s'} \frac{S_{n} (s, θ)}{n} \overset{p}{\to} \sum_{s > s'} \int_{0}^{θ} q_{s} (ϕ) d ϕ .

We can now establish the required convergence in probability. Let $ϵ > 0$ , and choose $s'$ so that $\sum_{s > s'} \int_{0}^{θ} q_{s} (ϕ) d ϕ < ϵ / 3$ . Then, (21) gives

P (| \frac{W_{n} (θ)}{n} - \sum_{s = 1}^{\infty} λ_{s} \int_{0}^{θ} q_{s} (ϕ) d ϕ | > ϵ) \leq P (| Y_{n} (s') | > ϵ / 3) + P (\sum_{s > s'} \frac{S_{n} (s, θ)}{n} > ϵ / 3) \to 0

n \to \infty

. □

Proof of Corollary 1.

Combine Theorem 2 with Corollary 6 (naive Boston), Corollary 8 (adaptive Boston), and Corollary 9 (serial dictatorship). □

Proof of Corollary 2.

Each such σ can be written as a finite nonnegative linear combination of k-approval rules. For each k-approval rule, Corollary 1 and Lemma 4 show that NB strictly beats SD. □

Proof of Corollary 3.

Combine Theorem 2 with Corollary 6 (naive Boston), Corollary 8 (adaptive Boston), and Corollary 9 (serial dictatorship). □

Proof of Corollary 4.

This follows directly from Corollary 3 and Remark 2. □

Proof of Theorem 3.

By Theorem 9, the asymptotic probability that the last agent obtains one of his first k choices is

P (R_{n} (1) \leq k) \to 1 - z_{k + 1}^{'} (1) .

The corresponding probability for the first agent is one. For other agents, this probability falls between the values for the first and last agents (Theorem 1). Hence, the asymptotic order bias is $z_{k + 1}^{'} (1)$ , which according to Theorem 8, can also be written $\prod_{j = 2}^{k + 1} (1 - ω_{j})$ . □

Proof of Theorem 4.

The probability that the last agent in ρ is matched to one of his first k preferences is $\sum_{s = 1}^{k} D_{A} (n, s)$ . According to Theorem 13, part (iv), the asymptotic limit of this quantity is $\sum_{s = 1}^{k} q_{s} (1)$ , where

q_{s} (1) = \sum_{r = 1}^{s} u_{r s} (y_{r}^{'} (1) - y_{r + 1}^{'} (1)) .

The asymptotic order bias is thus

\lim_{n} (1 - \sum_{s = 1}^{k} D_{A} (n, s)) = 1 - \sum_{s = 1}^{k} \sum_{r = 1}^{s} u_{r s} (y_{r}^{'} (1) - y_{r + 1}^{'} (1)) .

As noted in Remark 10, we have $y_{r}^{'} (1) = {(1 - e^{- 1})}^{r - 1}$ . The result follows. □

Proof of Theorem 5.

Let $ℓ_{n}$ denote the expected Borda utility of the last agent in ρ: that is,

ℓ_{n} = \sum_{s = 1}^{n} (\frac{n - s}{n - 1}) D_{A} (n, s) .

Then, for any s₀,

\underset{n}{\lim \inf} ℓ_{n} \geq \underset{n}{\lim \inf} (\frac{n - s_{0}}{n - 1}) \sum_{s = 1}^{s_{0}} D_{A} (n, s) = \sum_{s = 1}^{s_{0}} q_{s} (1),

where

q_{s} (1) = \lim_{n} D_{A} (n, s)

, as given by Theorem 9 (naive Boston) and Theorem 13 (adaptive Boston). Because

\sum_{s = 1}^{\infty} q_{s} (1) = 1

(see Remarks 7 and 12) and s₀ was arbitrary, we obtain

\lim_{n} ℓ_{n} = 1

. The order bias is

1 - ℓ_{n}

and hence, the result. □

Proof of Theorem 6.

From Theorem 14, we see that the first agent always gets his first choice, whereas the last agent gets each rank with probability $1 / n$ (this special case is obvious and does not require Theorem 14). Hence, the expected utility under k-approval for the last agent is k/n, and the expected utility under Borda for that agent is

\frac{1}{n} \sum_{j = 1}^{n} \frac{n - j}{n - 1} = \frac{1}{n (n - 1)} \sum_{j = 0}^{n - 1} j = \frac{1}{2} .

The result follows immediately by subtraction. □

Proof of Corollary 5.

This follows immediately from Theorem 6 because k is fixed and $n \to \infty$ . □

8. Conclusion

We conclude this paper with discussion of possible extensions to the work herein.

8.1. Robustness to the Model Assumptions

If we relax the strict random-market assumption on preferences, we should expect different results, although the relative performance of the three algorithms will likely not vary. For example, simulations (Freeman et al. 2021) with preferences drawn from the Mallows distribution show that for small values of the Mallows dispersion parameter, it is much harder to satisfy all agents or keep order bias or average rank low, but nevertheless, NB beats AB, which beats SD, over the entire range of parameters. It is also clear that the Boston mechanisms beat SD in egalitarian welfare; the last agent in particular fares considerably better.

We have studied only sincere behavior by agents. Strategic behavior under the Boston mechanisms does occur in practice and does cause welfare loss, but the social welfare cost of adopting a strategyproof alternative such as (random) serial dictatorship is often substantial, as shown, for example, in analysis of Harvard course matching (Budish and Cantillon 2012). Note that for symmetric heterogeneous preferences such as those provided by our random markets assumption, there is no incentive for agents to report their preferences untruthfully. Even if strategic behavior is a serious consideration in some situations, it is still important to analyze and compare the underlying algorithms thoroughly.

The k-approval utilities we have used here are widely used in assignment applications. For example, statistics, such as the fraction of school choice students obtaining one of their top three choices or their one favorite course, are commonly discussed. This makes sense in many practical situations because eliciting complete agent preferences over n items for large n is infeasible, and many agents will have only a few items they consider acceptable. Furthermore, we have seen that in a random market, a large fraction of agents obtains one of their first few choices. We have also seen that Borda utilities yield different results from the k-approval case, as would any utility function satisfying the conditions of Che and Tercieux (2018). However, we do not expect that the relative order of the algorithms with respect to utilitarian welfare (naive Boston beats adaptive Boston, which beats serial dictatorship) will change.

8.2. Ideas for Future Work

An obvious question that we did not answer here is what the expected rank of the item gained by a random agent is. For SD, the asymptotic answer $Θ (\log n)$ was derived by Frieze and Pittel (1995), and this was refined to an exact formula $((n + 1) H_{n} - n) / n \sim \log n$ by Knuth (1996). For the Boston mechanisms, Corollary 4 shows that the rank is o(n), but we suspect that it is much smaller. It is known (Nikzad 2022, Ortega and Klein 2022) that for the rank-maximizing mechanism RM (Featherstone 2020), which maximizes the number of agents receiving their first choice, then subject to that the number of agents receiving their second choice, etc., the expected average rank in a random market is asymptotically constant. Although similar to RM at first sight, naive Boston is not as strict because it makes a choice based on tiebreaking at the first round and hence, may diverge from RM even at the second round. Based on numerical simulation, we conjecture that the expected average ranks for naive Boston and adaptive Boston are each in fact $Θ (\log n)$ but smaller by a constant factor than that for SD.

Another important question concerns the expectation of the largest rank obtained by some agent (the egalitarian welfare). This coincides for NB with the number of rounds of the algorithm. The techniques of this paper do not allow us to answer this question. We conjecture based on the size of ω_r that for NB, the expected egalitarian welfare is $Θ (n)$ . Note that the analogous quantities for SD and RM are at least $n / 2$ and about $\log_{2} n$ , respectively (Ortega and Klein 2022).

A simple idea that will reduce order bias is to reverse the order in which agents choose at each round (or just at the second round). Quantifying the improvement via an analysis analogous to that in this paper is not easy because it is no longer clear that the worse-off agent will be the last one in the initial choosing order; indeed, preliminary analysis shows it is not. We leave further exploration of this variant for future work.

The Boston algorithms discussed here are specializations of algorithms used for school choice to the case where each school has a single seat and schools have a common preference order over applicants. Further analysis of school choice mechanisms in the general case, from the viewpoint of welfare and order bias, would be very desirable. It would also be interesting to study welfare and order bias in the multiunit assignment model used by Budish and Cantillon (2012).

The basic results on distribution of exit time and rank of the item received by an agent may be useful in other contexts. As noted by Knuth (1996), there is direct connection between the analysis here of SD and that of uniform hashing. Naive Boston corresponds to a form of hashing where if a slot is full, the item must go to the back of the queue and wait its turn to be rehashed.

The order bias of the Boston algorithms, although smaller than that of SD, is still rather large. Thus, if this fairness criterion is important, it makes sense to use a mechanism like top trading cycles, which is strategyproof and has zero order bias in this situation with respect to every scoring rule (Freeman et al. 2021). Note that because the top trading cycles mechanism (TTC) (with a randomly chosen endowment) is equivalent to the randomized version of SD, RSD (Abdulkadiroğlu and Sönmez 1998), and SD does not give up much in utilitarian welfare to NB, TTC may be a good choice if preferences of agents are well described by IC.

Acknowledgments

The authors acknowledge useful feedback by Nick Arnosti and Rupert Freeman.

References

Abdulkadiroğlu A, Sönmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689–701.Google Scholar
Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Google Scholar
Abdulkadiroğlu A, Che YK, Yasuda Y (2011) Resolving conflicting preferences in school choice: The “Boston mechanism” reconsidered. Amer. Econom. Rev. 101(1):399–410.Google Scholar
Abdulkadiroğlu A, Pathak PA, Roth AE, Sönmez T (2005) The Boston public school match. Amer. Econom. Rev. 95(2):368–371.Google Scholar
Budish E, Cantillon E (2012) The multi-unit assignment problem: Theory and evidence from course allocation at Harvard. Amer. Econom. Rev. 102(5):2237–2271.Google Scholar
Calsamiglia C, Fu C, Güell M (2020) Structural estimation of a model of school choices: The Boston mechanism vs. its alternatives. J. Polital Econom. 128(2):642–680.Google Scholar
Che YK, Tercieux O (2018) Payoff equivalence of efficient mechanisms in large matching markets. Theoret. Econom. 13(1):239–271.Google Scholar
Dur U, Mennle T, Seuken S (2018) First-choice maximal and first-choice stable school choice mechanisms. Tardos E, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (ACM, New York), 251–268.Google Scholar
Durrett R (2019) Probability: Theory and Examples, Cambridge Series in Statistical and Probabilistic Mathematics, 5th ed. (Cambridge University Press, Cambridge, UK).Google Scholar
Ergin H, Sönmez T (2006) Games of school choice under the Boston mechanism. J. Public Econom. 90(1–2):215–237.Google Scholar
Featherstone C (2020) Rank efficiency: Modeling a common policymaker objective. Working paper, Baylor University, Waco, TX., https://clayton-featherstone.github.io/.Google Scholar
Feller W (1970) An Introduction to Probability Theory and Its Applications, vol. 1, 3rd ed. (Wiley, New York).Google Scholar
Freeman R, Pritchard G, Wilson MC (2021) Order symmetry: A new fairness criterion for assignment mechanisms. Preprint, submitted July 20, https://doi.org/10.31235/osf.io/xt37c.Google Scholar
Frieze A, Pittel BG (1995) Probabilistic analysis of an algorithm in the theory of markets in indivisible goods. Ann. Appl. Probab. 5(3):768–808.Google Scholar
Hylland A, Zeckhauser R (1979) The efficient allocation of individuals to positions. J. Political Econom. 87(2):293–314.Google Scholar
Knuth DE (1996) An exact analysis of stable allocation. J. Algorithms 20(2):431–442.Google Scholar
Kojima F, Ünver MU (2014) The “Boston” school-choice mechanism: An axiomatic approach. Econom. Theory 55(3):515–544.Google Scholar
Mennle T, Seuken S (2021) Partial strategyproofness: Relaxing strategyproofness for the random assignment problem. J. Econom. Theory 191(2021):105144.Google Scholar
Miralles A (2009) School choice: The case for the Boston mechanism. Internat. Conf. Auctions Market Mechanisms Their Appl. (Springer, Berlin), 58–60.Google Scholar
Nikzad A (2022) Rank-optimal assignments in uniform markets. Theoret. Econom. 17(1):25–55.Google Scholar
Ortega J, Klein T (2022) A more efficient and egalitarian mechanism for school choice. Preprint, submitted July 15, https://arxiv.org/abs/2204.07255.Google Scholar
Pathak PA, Sönmez T (2008) Leveling the playing field: Sincere and sophisticated players in the Boston mechanism. Amer. Econom. Rev. 98(4):1636–1652.Google Scholar
Pycia M (2019) Evaluating with statistics: Which outcome measures differentiate among matching mechanisms? Working paper, University of Zurich, Zurich.Google Scholar
Shapley L, Scarf H (1974) On cores and indivisibility. J. Math. Econom. 1(1):23–37.Google Scholar

Volume 13, Issue 2

June 2023

Pages 181-319

Article Information

Metrics

Information

Received:May 18, 2022
Accepted:December 06, 2022
Published Online:January 24, 2023

Cite as

Geoffrey Pritchard, Mark C. Wilson (2023) Asymptotic Welfare Performance of Boston Assignment Algorithms. Stochastic Systems 13(2):247-270.

https://doi.org/10.1287/stsy.2022.0104

Keywords

Acknowledgments

The authors acknowledge useful feedback by Nick Arnosti and Rupert Freeman.

PDF download

Available Issues

Available Issues

Asymptotic Welfare Performance of Boston Assignment Algorithms

Abstract

1. Introduction

1.1. The Algorithms

1.2. Performance Measures

1.3. Random Markets

1.4. Assumptions on Agent Behavior

1.5. Description of Our Results

1.6. Literature Review

1.7. Outline of the Remainder of the Paper

2. Preliminaries

2.1. The Model

2.2. Evolution of Assignments by the Algorithms

2.3. Performance Measures

3. Main Results on Agent Satisfaction

3.1. Welfare

3.2. Order Bias

4. Technical Results and Proofs for Naive Boston

4.1. Groups of Agents

4.2. Individual Agents

5. Technical Results and Proofs for Adaptive Boston

5.1. Groups of Agents

5.1.1. The Rank of the Item Received.

5.2. Individual Agents

6. Technical Results and Proofs for Serial Dictatorship

6.1. Groups of Agents

6.2. Individual Agents

7. Remaining Proofs of Theorems

8. Conclusion

8.1. Robustness to the Model Assumptions

8.2. Ideas for Future Work

References

Volume 13, Issue 2

Article Information

Metrics

Information

Cite as

Keywords