The College Application Problem

The college application problem straddles several methodological universes. Its stochastic nature recalls classical portfolio allocation models. However, the knapsack constraint renders the problem NP-complete, and necessitates combinatorial solution techniques. We also observe that the objective function is also a submodular set function, although our approximation results suggest that college application is a relatively easy instance of submodular maximization.

A problem similar to (1) arose in an equilibrium analysis of the American college market by Fu (2014), who described college application as a “nontrivial portfolio problem” (226). In computational finance, traditional portfolio allocation models weigh the sum of expected profit across all assets against a risk term, yielding a concave maximization problem with linear constraints (Markowitz 1952; Meucci 2005). But college applicants maximize the expected value of their best asset: If a student is admitted to her $j$th choice, then she is indifferent as to whether she gets into her $(j+1)$th choice. As a result, student utility is convex in the utility associated with individual applications. Risk management is implicit in the college application problem because, in a typical admissions market, college preferability correlates inversely with competitiveness. That is, students negotiate a tradeoff between attractive, selective “reach schools” and less preferable “safety schools” where admission is a safer bet (Jeon 2015). Finally, the combinatorial nature of the college application problem makes it difficult to solve using the gradient-based techniques associated with continuous portfolio optimization. Fu estimated her equilibrium model (which considers application as a cost rather than a constraint) by clustering the schools so that $m=8$, a scale at which enumeration is tractable. We pursue a more general solution.

The integer formulation of the college application problem can be viewed as a kind of binary knapsack problem with a polynomial objective function of degree $m$. Our branch-and-bound and dynamic programming algorithms closely resemble existing algorithms for knapsack problems (Martello and Toth 1990, § 2.5–6). In fact, by manipulating the admissions probabilities, the objective function can be made to approximate a linear function of the characteristic vector to an arbitrary degree of accuracy, a fact that we exploit in our NP-completeness proof. Previous research has introduced various forms of stochasticity to the knapsack problem, including variants in which each item’s utility takes a known probability distribution (Steinberg and Parks 1979; Carraway et al. 1993) and an online context in which the weight of each item is observed after insertion into the knapsack (Dean et al. 2008). Our problem superficially resembles the preference-order knapsack problem considered by Steinberg and Parks and Carraway et al., but these models lack the college application problem’s singular “maximax” form. Additionally, unlike those models, we do not attempt to replace the real-valued objective function with a preference order over outcome distributions, which introduces technical issues concerning competing notions of stochastic dominance (Sniedovich 1980). We take for granted the student’s preferences over outcomes (as encoded in the $t_{j}$-values), and focus instead on an efficient computational approach to the well-defined problem above.

We take special interest in the validity of greedy optimization algorithms, such as the algorithm that iteratively adds the school that elicits the greatest increase in the objective function until the budget is exhausted. Greedy algorithms produce a nested family of solutions parameterized by the budget $H$: If $H\leq H^{\prime}$, then the greedy solution for budget $H$ is a subset of the greedy solution for budget $H^{\prime}$. As Rozanov and Tamir (2020) remark, the knowledge that the optima are nested aids not only in computing the optimal solution, but in the implementation thereof under uncertain information. For example, in the United States, many college applications are due at the beginning of November, and it is typical for students to begin working on their applications during the prior summer because colleges reward students who tailor their essays to the target school. However, students may not know how many schools they can afford to apply to until late October. The nestedness property—or equivalently, the validity of a greedy algorithm—implies that even in the absence of complete budget information, students can begin to carry out the optimal application strategy by writing essays for schools in the order that they enter the optimal portfolio.

For certain classes of optimization problems, such as maximizing a submodular set function over a cardinality constraint, a greedy algorithm is known to be a good approximate solution and exact under certain additional assumptions (Fisher et al. 1978). For other problems, notably the binary knapsack problem, the most intuitive greedy algorithm can be made to perform arbitrarily poorly (Vazirani 2001). We show results for the college application problem that mirror those for the knapsack problem: When each $g_{j}=1$, the optimal portfolios are nested. This special case mirrors the centralized college application process in Korea, where there is no application fee, but students are allowed to apply to only three schools during the main admissions cycle. Unfortunately, the nestedness property does not hold in the general case, nor does the greedy algorithm offer any performance guarantee. However, we identify a fully polynomial-time approximation scheme (FPTAS) based on fixed-point arithmetic.

Finally, we remark that the objective function of (1) is a nondecreasing submodular function. However, our research employs more elementary analytical techniques, and our approximation results are tighter than those associated with generic submodular maximization algorithms. For example, a well-known result of Fisher et al. (1978) implies that the greedy algorithm is asymptotically $(1-1/e)$-optimal for the $g_{j}=1$ case of the college application problem, whereas we show that the same algorithm is exact. As for the general problem, an equivalent approximation ratio is achievable when maximizing a submodular set function over a knapsack constraint using a variety of relaxation techniques (Badanidiyuru and Vondrák 2014; Kulik et al. 2013). But in the college application problem, the existence of the FPTAS supersedes these results.

Section 2 introduces some additional notation and assumptions that can be imposed without loss of generality. We also introduce a useful variable-elimination technique and prove that the objective function is submodular.

In Section 3, we consider the special case where each $g_{j}=1$ and $H$ is an integer $h\leq m$. We show that an intuitive heuristic is in fact a $1/h$-approximation algorithm. Then, we show that the optimal portfolios are nested in the budget constraint, which yields an exact algorithm that runs in $O(hm)$-time.

In Section 4, we turn to the scenario in which colleges differ in their application fees. We show that the decision form of the portfolio optimization problem is NP-complete through a polynomial reduction from the binary knapsack problem. We provide four algorithms for this more general setup. The first is a branch-and-bound routine. The second is a dynamic program that iterates on total expenditures and produces an exact solution in pseudopolynomial time, namely $O(Hm+m\log m)$. The third is a different dynamic program that iterates on truncated portfolio valuations. It yields a fully polynomial-time approximation scheme that produces a $(1-\varepsilon)$-optimal solution in $O(m^{3}/\varepsilon)$ time. The fourth is a simulated-annealing heuristic algorithm that demonstrates strong performance in our synthetic instances.

In Section 5, we present the results of computational experiments that confirm the validity and time complexity results established in the previous two sections. We also investigate the empirical accuracy of the simulated-annealing heuristic.

In the conclusion, we identify possible improvements to our solution algorithms and introduce a few extensions of the model that capture the features of real-world admissions processes.

We refer to the set $\mathcal{X}\subseteq\mathcal{C}$ of schools to which a student applies as her application portfolio. The expected utility the student receives from $\mathcal{X}$ is called its valuation.

Given an application portfolio, let $p_{j}(\mathcal{X})$ denote the probability that the student attends $c_{j}$. This occurs if and only if she applies to $c_{j}$, is admitted to $c_{j}$, and is rejected from any school she prefers to $c_{j}$; that is, any school with higher index. Hence, for $j=0\dots m$,

where the empty product equals one and $f_{0}=1$. The following proposition follows immediately.

Next, we show that without loss of generality, we may assume that $t_{0}=0$.

Now, we present a variable-elimination technique that will prove useful throughout the paper.¹¹1We thank Yim Seho for pointing out this useful transformation. Suppose that the student has already resolved to apply to $c_{k}$, and the remainder of her decision consists of determining which other schools to apply to. Writing her total application portfolio as $\mathcal{X}=\mathcal{Y}\cup\{k\}$, we devise a function $w(\mathcal{Y})$ that orders portfolios according to how well they “complement” the singleton portfolio $\{k\}$. Specifically, the difference between $v(\mathcal{Y}\cup\{k\})$ and $w(\mathcal{Y})$ is the constant $f_{k}t_{k}$.

To construct $w(\mathcal{Y})$, let $\tilde{t}_{j}$ denote the expected utility the student receives from school $c_{j}$ given that she has been admitted to $c_{j}$ and applied to $c_{k}$. For $j<k$ (including $j=0$), this is $\tilde{t}_{j}=(1-f_{k})t_{j}+f_{k}t_{k}$; for $j>k$, this is $\tilde{t}_{j}=t_{j}$. This means that

The transformation to $\tilde{t}$ does not change the order of the $t_{j}$-values. Therefore, the expression on the right side of (5) is itself a portfolio valuation function. In the corresponding market, $t$ is replaced by $\tilde{t}$ and $\mathcal{C}$ is replaced by $\mathcal{C}\setminus\{k\}$. To restore our convention that $t_{0}=0$, we obtain $w(\mathcal{Y})$ by taking $\bar{t}_{j}=\tilde{t}_{j}-\tilde{t}_{0}$ for all $j\neq k$ and letting

where the second equality follows from Lemma 1. The validity of this transformation is summarized in the following theorem, where we write $v(\mathcal{X};\bar{t})$ instead of $w(\mathcal{Y})$ to emphasize that $w(\mathcal{Y})$ is, in form, a portfolio valuation function.

Now, we show that the portfolio valuation function is submodular. This result is primarily of taxonomical interest and may be safely skipped. Our solution algorithms for the college application problem are better than generic algorithms for submodular maximization, and we prove their validity using elementary analysis.

The expected utility associated with a single school $c_{j}$ is simply $\operatorname{E}[t_{j}Z_{j}]=f_{j}t_{j}$. It is therefore tempting to adopt the following strategy, which turns out to be suboptimal.

The basic error of the naïve algorithm is that it maximizes $\operatorname{E}\left[\,\sum t_{j}Z_{j}\,\right]$ instead of $\operatorname{E}\left[\max\{t_{j}Z_{j}\}\right]$. The latter is what Alma is truly concerned with, since in the end she can attend only one school. The following example shows that the naïve algorithm can produce a suboptimal solution.

Although the naïve algorithm is suboptimal, we can still find the optimal solution in $O(hm)$-time, as we will now show.

It turns out that the solution to Alma’s problem possesses a special structure: An optimal portfolio of size $h+1$ includes an optimal portfolio of size $h$ as a subset.

Applying the result above yields an efficient greedy algorithm for the optimal portfolio: Start with the empty set and add schools one at a time, maximizing $v(\mathcal{X}\cup\{k\})$ at each addition. Sorting $t$ is $O(m\log m)$. At each of the $h$ iterations, there are $O(m)$ candidates for $k$, and computing $v(\mathcal{X}\cup\{k\})$ is $O(h)$ using (3); therefore, the time complexity of this algorithm is $O(h^{2}m+m\log m)$.

We reduce the computation time to $O(hm)$ by taking advantage of the transformation from Lemma 2. Once school $k$ is added to $\mathcal{X}$, we eliminate it from the set $\mathcal{C}\setminus\mathcal{X}$ of candidates, and update the $t_{j}$-values of the remaining schools according to (7). Now, the next school added must be the optimal singleton portfolio in the modified market. But the optimal singleton portfolio consists simply of the school with the highest value of $f_{j}\bar{t}_{j}$. Therefore, by updating the $t_{j}$-values at each iteration according to (7), we eliminate the need to compute $v(\mathcal{X})$ entirely. Moreover, this algorithm does not require the schools to be indexed in ascending order by $t_{j}$, which removes the $O(m\log m)$ sorting cost. Algorithm 1 outputs a list $\mathtt{X}$ of the $h$ schools to which Alma should apply. The schools appear in the order of entry such that when the algorithm is run with $h=m$, the optimal portfolio of size $h$ is given by $\mathcal{X}_{h}=\{\mathtt{X[1]},\dots,\mathtt{X[h]}\}$. The entries of the list $\mathtt{V}$ give the valuation thereof.

It is possible to store $\mathcal{C}$ as a binary max heap rather than a list. The heap is ordered according to the criterion $i\geq j\iff f_{i}t_{i}\geq f_{j}t_{j}$, and by draining the heap and reheapifying at the end of each iteration, the computation time remains $O(hm)$. However, in our numerical experiments, whose results are reported in Section 5, we found the list implementation to be much faster, because it is possible to identify the entering school $k$ as the utility parameters are updated, which all but eliminates the cost of the $\operatorname*{arg\,max}\{\}$ operation.

The nestedness property implies that Alma’s expected utility is a discretely concave function of $h$.

Let us examine a fictional admissions market consisting of $m=8$ schools. The school data, along with the optimal solutions for each $h\leq m$, appear in Table 1.

Below are shown the first several iterations of Algorithm 1. The values of $f_{j}$, $t_{j}$, and their product are recorded only for the schools remaining in $\mathcal{C}$. $f*t$, where $(f*t)_{j}=f_{j}t_{j}$, denotes the entrywise product of $f$ and $t$. The school added at each iteration, underlined, is the one whose $f_{j}t_{j}$-value is greatest.

The output of the algorithm is $\mathtt{X}=[4,2,8,1,7,3,5,6]$, and the optimal $h$-portfolio consists of its first $h$ entries. The “priority” column of Table 1 shows the inverse permutation of $\mathtt{X}$, which is the minimum value of $h$ for which the school is included in the optimal portfolio. Figure 1 shows the value of the optimal portfolio as a function of $h$. The concave shape of the plot suggests the result of Theorem 5.

The optima for Ellis’s problem are not necessarily nested, nor is the number of schools in the optimal portfolio necessarily increasing in $H$. For example, if $f=(0.5,0.5,0.5)$, $t=(1,1,219)$, and $g=(1,1,3)$, then it is evident that the optimal portfolio for $H=2$ is $\{1,2\}$ while that for $H=3$ is $\{3\}$. In fact, Ellis’s problem is NP-complete, as we will show by a transformation from the binary knapsack problem, which is known to be NP-complete (Garey and Johnson 1979, § 3.2.1).

An intuitive extension of the greedy algorithm for Alma’s problem is to iteratively add to $\mathcal{X}$ the school $k$ for which $\bigl{(}v(\mathcal{X}\cup\{k\})-v(\mathcal{X})\bigr{)}/g_{k}$ is largest. But the construction above shows that the objective function of Ellis’s problem can approximate that of a knapsack problem with arbitrary precision. Therefore, in pathological examples such as the following, the greedy algorithm can achieve an arbitrarily small approximation ratio.

We might expect to obtain a better approximate solution to Ellis’s problem by solving the following knapsack problem (nevermind that it is NP-complete) as a surrogate.

However, upon inspection, this solution merely generalizes the naïve algorithm for Alma’s problem (Definition 3). In Ellis’s problem, because the number of schools in the optimal portfolio can be as large as $m-1$, the knapsack solution’s approximation coefficient is $1/(m-1)$ by analogy with (13). A tight example is as follows.

In summary, neither a greedy algorithm nor a knapsack-based algorithm solves Ellis’s problem to optimality.

A traditional approach to integer optimization problems is the branch-and-bound framework, which generates subproblems in which the values of one or more decision variables are fixed and uses an upper bound on the objective function to exclude, or fathom, branches of the decision tree that cannot yield a solution better than the best solution on hand (Martello and Toth 1990; Kellerer et al. 2004). In this subsection, we present an integer formulation of Ellis’s problem and a linear program (LP) that bounds the objective value from above. We tighten the LP bound for specific subproblems by reusing the conditional transformation of the $t_{j}$-values from Algorithm 1. A branch-and-bound routine emerges naturally from these ingredients.

To begin, let us characterize the portfolio $\mathcal{X}$ as the binary vector $x\in\{0,1\}^{m}$, where $x_{j}=1$ if and only if $j\in\mathcal{\{}X\}$. Then it is not difficult to see that Ellis’s problem is equivalent to the following integer nonlinear program.