Working with same-costs markets

The same-costs market is a special case of the college application problem in which all schools have the same application cost. In this case, the budget constraint reduces to a limit on the number of schools to which you can apply:

\[ \begin{align*} \text{maximize}\quad & v(\mathcal{X}) = \sum_{j\in \mathcal{X}} \Bigl( f_j t_j \prod_{\substack{i \in \mathcal{X}: \\ i > j}} (1 - f_{i}) \Bigr) \\ \text{subject to}\quad & \mathcal{X} \subseteq \mathcal{C}, ~~\lvert \mathcal{X} \rvert \leq h \end{align*}\]

Let's consider a random instance of this problem with $m = 15$ schools and $h = 5$.

using OptimalApplication
f = rand(15)
t = rand(15)
mkt = SameCostsMarket(f, t, 5)
SameCostsMarket{Float64}(15, [0.6929492338477166, 0.23345889156706534, 0.2669552763110947, 0.38534630253754654, 0.8397841336950277, 0.7819325591867324, 0.6479266222985787, 0.542632609590581, 0.017808901339023242, 0.8234648761275051, 0.4793799054195995, 0.699117320486753, 0.485048257686838, 0.48979844146302254, 0.13865149450475178], [0.021135469910246174, 0.07842509422736221, 0.2217094669357088, 0.27590635209003245, 0.341556276228109, 0.4308722795235074, 0.5171833135804801, 0.5758327181268589, 0.7340149801595189, 0.8244378194235714, 0.8289387162177277, 0.9516166246237489, 0.9748687436364761, 0.98110787514334, 0.9962161132525128], 5, [7, 5, 15, 14, 6, 13, 3, 11, 4, 2, 9, 10, 12, 1, 8])

Enumeration solver

We can solve this problem using optimalportfolio_enumerate:

X, v = optimalportfolio_enumerate(mkt)
([2, 10, 12, 1, 8], 0.956629189713785)

This function returns the optimal portfolio as a vector X of school indices, and its valuation v.

Warning

Enumeration algorithms have exponential time complexity and should only be used in small instances with m ≤ 20. Their intended use is to test the validity of more-efficient solvers.

The nestedness property

The optimal solutions for this special case of the college application problem satisfy a property called the nestedness property. When $\mathcal{X}_h$ denotes the optimal solution for a given market when the limit is $h$, we have

\[\mathcal{X}_1 \subset \mathcal{X}_2 \subset \dots \subset \mathcal{X}_m.\]

This means that there exists a permutation of the schools X such that X[1:h] gives the optimal portfolio of size $h$ for all $h$.

Efficient solvers

The functions applicationorder_list and applicationorder_heap produces this permutation X as well as a vector V indicating the utility associated with each optimum. When mkt.h < mkt.m, only the first mkt.h entries are computed. To verify the correctness of the nestedness property, however, let's make a copy of our market with mkt.h == 15 and check that the first $h = 5$ entries agree (up to permutation).

mkt_long = SameCostsMarket(f, t, 15)
X_long, V_long = applicationorder_list(mkt)
X_long[1:5], X
([2, 10, 1, 12, 8], [2, 10, 12, 1, 8])

The valuation should also be the same:

V_long[5], v
(0.9566291897137847, 0.956629189713785)

The output of applicationorder_heap is identical to that of applicationorder_list but the function uses a different internal data structure. In the vast majority of cases, the list version is faster.