Set notation for greatest $n$ in ordered subset

Question

I am trying to describe the following situation:

$ X = \{x_i \dots x_n\} $ This is the set of all job applicants.

$Y$ is a subset of $X$ where $M = 1$. Each $x_i$ has an associated $m_i$ that can be $\{0,1\}$ representing whether or not an applicant is "hireable".

Each applicant also has an "applicant strength rating" ($\alpha_i$). $Z$ would be the set I would get if I took $Y$, ordered it in decreasing $\alpha_i$ order, and chose the top $\beta$ individuals, with $\beta > 0$.

I would like to succinctly describe set $Z$. So far, I have:

$$ \forall ~ X \in \mathbb{N}^n, ~ X=\{x_1 \dots x_n\} \\ Y \subset {X | M = 1} \\ Z ={\rm argmax}_{Y, ~ |Y|=\beta}~\sum_{y \in Y} y $$

Answer 1

First, I reformulate the task a bit and make it a bit more concrete.

• Given is a set $X=\{x_1,\ldots,x_n\}$ of pairwise different elements, which is the set of job applicants.

• We consider a map $m$: \begin{align*} &m:X\to \{0,1\}\\ &m(x_i)=m_i\qquad\qquad \qquad 1\leq i\leq n \end{align*} which determines if a job applicant is hireable (i.e. $m_i=1$).

• We want to consider certain sets $Y\subseteq X$ of hireable job applicants, i.e. we consider \begin{align*} \color{blue}{Y\subseteq m^{-1}(1)=\{x\in X|m(x)=1\}\subseteq X} \end{align*} In order to appropriately select $Y$ we introduce a rating function $\alpha$: \begin{align*} &\alpha:X\to\mathbb{R_0^{+}}\\ &\alpha(x_i)=\alpha_i\qquad\qquad \qquad 1\leq i\leq n \end{align*}

Finally we want to select the top $\beta\in\mathbb{N}$ hireable job applicants, which have the best rating $Z$. We are therefore looking for \begin{align*} \color{blue}{Z=\underset{{Y\subseteq m^{-1}(1)}\atop{|Y|=\beta}}{\arg\max}\,\,\sum_{y\in Y}\alpha(y)} \end{align*}

Notes:

• Depending on the functions $m$ and $\alpha$ there may be more than one solution which results in $Z$.

• On the other hand, if there is only a small number $|m^{-1}(1)|$ of hireable job applicants, the condition on $\beta$ might be too strong, so that there is no solution at all.

Hint: The meaning of $M$ and its relationship with $X$ is not clear and is ignored in this answer. OPs notation $X\in\mathbb{N}^n$ is not admissible, since $X$ is not an ordered $n$-tuple of natural numbers.

Answer 2

Given your set up, we let:

$ X = \{x_i \dots x_n\} $

M = { $m_i \dots m_n$}

Let g: X $\rightarrow$ M

such that g($x_i$) = $m_i$

We'll call this the applicant Hireability function

$M_0$ = {$x_i$ | $g(x_i)$ = 0 }

Let Y $\subset$ X \ $M_0$ and |Y| > 0

Let A = { $a_i \dots a_n$}

Let h: Y $\rightarrow$ A

such that h($x_i$) = $a_i$

We'll call this the Applicant Strength Function

We define a sequence:

$b_0$ = smallest $a_i$ such that h($x_i$) = $a_i$

$b_{n+1}$ = smallest $a_i$ > $b_n$ such that h($x_i)$ = $a_i$

if $a_i$ = $a_j$ we order by the index, so if i < j then $a_i$ < $a_j$

So we have α nondecreasing sequence of terms:

Note: if you want a nonincreasing sequence instead, just let $b_0$ be the largest, instead of the smallest etc...

<$b_n$ | n < m> for some m$\in$ω

Let 0 < β and δ = m - β ≥ 0

Let z = { $x_i$ | h($x_i$) ≥ $b_δ$ }

Let's look at an example:

Let X = { $x_0$,$x_1$,$x_2$ }

For simplicity let's assume Y = X

Suppose

h($x_0$) = 1 = h($x_1$)

h($x_2$) = 2

So

$b_0$ = h($x_0)$ = 1

$b_1$ = h($x_1$) = 1

$b_2$ = h($x_2$) = 2

Suppose we wanted the applicant with the best strength score.

Let β = 1, δ = 3 - β = 2

Recall: z = { $x_i$ | h($x_i$) ≥ $b_δ$ }

So, z = { $x_i$ | h($x_i$) ≥ $b_2$ }

z = {$x_2$} As desired.