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.3325141454042928, 0.9165623434133431, 0.8204329703778147, 0.31622896813981294, 0.9376489012438782, 0.40010801219692327, 0.13561230859726803, 0.2683775043838885, 0.6920748427230924, 0.25250259754221194, 0.6501144095641596, 0.36398377515177016, 0.29937784707881254, 0.694079628237375, 0.22642711808455485], [0.008415847770283702, 0.03723973155865945, 0.08602605370563643, 0.09333700072186402, 0.1274701881589011, 0.14249666456297383, 0.20583898658119026, 0.3773090336353464, 0.5022704203304784, 0.67231279954171, 0.6727458895775149, 0.7052569519635613, 0.8457949614432259, 0.9099278045249979, 0.9331355193822031], 5, [2, 5, 7, 15, 3, 6, 9, 12, 13, 11, 8, 1, 10, 14, 4])

Enumeration solver

We can solve this problem using optimalportfolio_enumerate:

X, v = optimalportfolio_enumerate(mkt)

([13, 8, 10, 14, 4], 0.852451452929916)

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

([14, 8, 4, 10, 13], [13, 8, 10, 14, 4])

The valuation should also be the same:

V_long[5], v

(0.8524514529299161, 0.852451452929916)

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.