7
$\begingroup$

This is an abstraction of a problem that has come up in my research.

Imagine we have $N$ wizards and $N$ hats. The hats have $C$ different colours. There are $n_1>0$ hats with the first colour, $n_2>0$ with the second and so on such that $\sum_{i=1}^C n_i=N$. Hats of the same colour are identical in all respects.

Wizards are powerless without their hat and have magical power $0$. Each hat provides a power up to a wizard. How each coloured hat affects a wizard varies from wizard to wizard. We can think of the wizards as the integers $1,\dots,N$ and each coloured hat as a function $f_i:[N]\to\mathbb N$ where $f_i(m)$ is the magical power of wizard $m$ when wearing any hat with colour $i$.

Question: For which $C$ can we find an efficient algorithm that assigns an allocation of hats to wizards such that each wizard wears one hat and their total power is maximised?

In other words, can we find a colouring $i:[N]\to[C]$, with $n_i$ instances of colour $i$, such that $\sum_{m=1}^N f_{i(m)}(m)$ is maximised?

For $C=1$ this is trivial, while $C=2$ is very similar to the Neyman-Pearson lemma with $f_1-f_2$ the likelihood function ratio. The optimal solution for $C=2$ is given by $\{$wizards wearing hat 1$\}=\{m\mid f_1(m)-f_2(m)>k\}$ with $k$ chosen such that this set is of size $n_1$ (there's a subtlety when there is no $k$ such that this is true due to collisions of $f_1-f_2$, but this is simple to solve). However, for $C=3$ I have no idea how to proceed and am not even sure if the problem is in P.

$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

This can be formulated as an integer program, optimizing a matching. Make a bipartite graph $B=(W,H)$, and let edge $wh$ have weight $W_{wh}$, the "power of wizard $w$ with hat $h$." Let $x_{ij}$ be $1$ if $ij$ is in the matching, and $0$ elsewhere.

We also want this to be a perfect matching $M$, so $\sum_{j \in H} x_{ij} = 1$ for any $i$, and $\sum_{i \in W}x_{ij} = 1$ for any $j$.

Then we have the integer program:

  • Maximize $\sum W_{wh}x_{wh}$, given:

    • $\sum_{j \in H} x_{ij} = 1$ for any $i$, and $\sum_{i \in W}x_{ij} = 1$ for any $j$,
    • and $x_{ij} \in \mathbb{Z}$.

The solutions to such a linear program will be integral, so just use regular linear program methods to get an integer solution.

$\endgroup$
3
  • $\begingroup$ Thanks William! To spell out your implicit logic, we can relax the integral constraint by considering the probability that each wizard wears a hat. We can solve this with the simplex algorithm (for example) and then note that any optimal solution will actually have an equivalently good solution where each probability is either 0 or 1. $\endgroup$
    – Alec Barns-Graham
    Commented Apr 19, 2021 at 14:40
  • 1
    $\begingroup$ Yep. The theory of integral programs enjoys totally unimodular matrices, as they will guarantee that any linear program with a totally unimodular matrix constraint (and one or two other conditions) will in fact have integral optima. Such a matrix for this kind of program is TU. $\endgroup$
    – While I Am
    Commented Apr 19, 2021 at 14:45
  • $\begingroup$ I must confess that the true case I'm interested in that I thought this would be a sufficient intuition pump for is when we have a probability distribution over wizards. We then assign hats by partitioning the space of wizards into $C$ components, $A_i$, such that $\mathbb P(A_i)=c_i\in[0, 1]$. Our goal is to maximise the expected power of the wizards, $\mathbb E_w(\sum_i 1_{A_i}f_i(w))$. (The reason I made an analogy to the Neyman-Pearson lemma for $C=2$ is hopefully now more clear). Sadly it's not clear to me how to generalise it in this way. $\endgroup$
    – Alec Barns-Graham
    Commented Apr 19, 2021 at 15:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .