# 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`

.

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.