Understanding the concept of mass in a matching algorithm

77 Views Asked by At

Suppose we have two finite sets $\mathcal{K}\subseteq \mathbb{N}$ and $\mathcal{Q}\subseteq \mathbb{N}$.

Let $n\in \mathbb{N}$, $\gamma_K\geq 0$, $\gamma_Q\geq 0$

The cardinality of $\mathcal{K}$ is $[n \exp(\gamma_{K})]$ and the cardinality of $\mathcal{Q}$ is $[n \exp(\gamma_{Q})]$, where$[x]$ denotes the value of $x$ rounded to the nearest integer.

For example: impose $n=1$, $\gamma_K=1$, $\gamma_Q=1.4$. Then $\mathcal{K}$ has three elements and $\mathcal{Q}$ has four elements, e.g., $$ \mathcal{K}\equiv \{1,2,3\} $$ and $$ \mathcal{Q}\equiv \{1,2,3,4\} $$


Suppose that each element of $\mathcal{K}$ denotes a man, and each element of $\mathcal{Q}$ denotes a woman. Consider an algorithm pairing (according to some optimisation rules) the men in $\mathcal{K}$ with the woman in $\mathcal{Q}$. The output of the algorithm are some couples such that: (I) if $i\in \mathcal{K}$ is paired with $j\in \mathcal{Q}$, then $i$ and $j$ cannot be paired with other elements; (II) individuals on both sides can remain single.

Continuing the example above, a possible output of the algorithm is $(1,2), (2,3), (3,0), (0,1), (0,4)$, where $(i,j)$ denotes the couple formed by $i\in \mathcal{K}$ and $j\in \mathcal{Q}$, $(i,0)$ denotes that $i\in \mathcal{K}$ is single, $(0,j)$ denotes that $j\in \mathcal{Q}$ is single.


Question:

1) I want to write down what is the total mass of individuals. Some notes I am studying say that it is equal to $$\exp(\gamma_K)+\exp(\gamma_Q)$$ Why?

2) The same notes say that the mass of pairs matched by the algorithm (with the inclusion of singles) is between $$\exp(\max\{\gamma_K, \gamma_Q\})$$ and $$\exp(\gamma_K)+\exp(\gamma_Q)$$

Why?

I think I am not getting why the mass of men is $\exp(\gamma_K)$ and why the mass of women is $\exp(\gamma_Q)$. If I clarify this, then 1) and 2) become clearer.