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.9204956193361875, 0.4915506915713569, 0.9600864891363339, 0.031724308196933726, 0.9144216053402681, 0.19542584255890283, 0.9825495201129997, 0.12993522167538596, 0.44767238545300136, 0.6226752283541911, 0.168567574056956, 0.927743736362424, 0.7397577435450602, 0.43817635238380137, 0.8666984589048975], [0.15874121725019252, 0.1783714103284435, 0.19450137304184956, 0.2635755187827592, 0.30489861837382015, 0.3483581518244464, 0.42944709200338516, 0.6054024477689322, 0.6058130732707415, 0.6533430117689402, 0.7009071263775946, 0.7191349762310623, 0.7437947490987179, 0.7461658403394004, 0.7876304221278195], 5, [13, 3, 15, 9, 1, 4, 7, 11, 14, 6, 12, 5, 10, 2, 8])

Enumeration solver

We can solve this problem using optimalportfolio_enumerate:

X, v = optimalportfolio_enumerate(mkt)

([7, 5, 10, 2, 8], 0.7810264186554929)

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

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

([8, 5, 10, 2, 7], [7, 5, 10, 2, 8])

The valuation should also be the same:

V_long[5], v

(0.7810264186554929, 0.7810264186554929)

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.