1
$\begingroup$

Motivation

In a particular board game, players start the game with a country and a special ability. Two players cannot have the same country or the same special ability. Analysis has shown that certain country-ability combinations are better than others. The combinations have been evaluated with an integer where higher integers are better. I want an algorithm to randomly sample a possible game with a certain number of players and that is "balanced", i.e., no two players' combination value difference exceeds a certain delta threshold.

Problem Statement

You are given $X=\{x_1, \dots, x_n\}$, $Y=\{y_1, \dots, y_n\}$, and $T=X \times Y \rightarrow \mathbb Z$.

Given $k$ and $d$, randomly sample a set $\{(a_1, b_1), \dots, (a_k, b_k)\} \subset X \times Y$ such that $a_1, \dots, a_k$ are pairwise distinct, $b_1, \dots, b_k$ are pairwise distinct, and $|T(a_j, b_j)-T(a_i, b_i)| \leq d$ for all $i,j$.

$\endgroup$
7
  • $\begingroup$ I don't want to include $(1, 2)$ and $(1,3)$ because as stated in the motivation, players can have neither the same country, nor the same special ability. I realize $(1, 2)$ and $(1,3)$ are normally considered distinct, but I don't know the correct word for what I want. $\endgroup$ Feb 18, 2022 at 20:27
  • $\begingroup$ So in other words, it is not good enough for the combinations to be pairwise distinct, each of the components of the combinations must also be pairwise distinct. So if $k=3$ and we were considering $\{(a_1, b_1), (a_2, b_2), (a_3, b_3)\}$, it must be true that $a_1 \neq a_2 \neq a_3$ and $b_1 \neq b_2 \neq b_3$ $\endgroup$ Feb 18, 2022 at 20:39
  • $\begingroup$ Got it. Your current requirements are fine. I've edited the question accordingly. $\endgroup$
    – D.W.
    Feb 18, 2022 at 20:53
  • $\begingroup$ A follow-up question: What are the requirements on the algorithm? The first thought is that maybe you want an efficient algorithm; but there is no hope for an efficient algorithm in general, because you ask for all possible solutions, and there may be exponentially many possible solutions. My second thought is that maybe you don't care about efficiency, but then a trivial algorithm is to enumerate all $(|X| \cdot |Y|)^k$ subsets and check which ones meet your requirements; but that is probably too slow and too obvious. Maybe you would be happy with an algorithm that only finds one solution? $\endgroup$
    – D.W.
    Feb 18, 2022 at 20:54
  • $\begingroup$ Or maybe you want an output-sensitive algorithm, whose running time is polynomial in the number of solutions? Or a polynomial-delay algorithm, that outputs solutions one at a time, with at most polynomial "delay" (running time) between each pair of solutions outputted? $\endgroup$
    – D.W.
    Feb 18, 2022 at 20:55

1 Answer 1

1
$\begingroup$

All solutions have the following form: pick a lower limit $\ell$; let $E = \{(x,y) : x \in X, y \in Y, \ell \le T(x,y) \le \ell+d\}$; finally pick a subset $S$ of $E$ of size $k$ with no repeats in the first coordinate or second coordinate. The latter step can be viewed as the problem of finding a matching of size $k$ in a bipartite graph, where we view $X,Y$ as the two vertex sets and $E$ as the set of edges.

So, if you want to find one solution, there is a polynomial-time algorithm: enumerate all possible values $\ell$ of $T(X,Y)$; for each such $\ell$, form a graph with edges $E$ as above, find a maximum-cardinality matching in this bipartite graph using standard algorithms, and check whether its cardinality is at least $k$.

If you want to find all solutions, then you'll need an algorithm to find all cardinality-$k$ matchings in a bipartite graph. I don't know how to solve that problem efficiently. (Note that there can be exponentially such matchings, so the best you could hope for is a polynomial-delay algorithm.) A trivial but extremely slow algorithm is to enumerate all subsets of $k$ edges and check whether it is a matching (with early pruning), but there might be much better algorithms.

Perhaps the reason you are asking for all solutions is that you have some other constraints you want to impose on a solution, and your thought was to enumerate all solutions and look for one that meets your other constraints. If so, it might be better to formulate this as a constraint solution problem that includes all constraints from the start.

Your subsequent clarification indicates that you want to sample a random solution. I don't know whether there is an efficient algorithm to sample uniformly at random from a matching of cardinality $k$. I would not be surprised if there are sophisticated algorithms, that sample approximately uniformly at random, based on MCMC or other techniques, but this is now an advanced area of the field that is beyond my knowledge. I believe it is known that there are efficient algorithms that can approximately count the number of perfect matchings, and from this it should follow that there are efficient ways to sample approximately uniformly at random from these matchings (pick an edge $e \in E$, count the number of perfect matchings that do include $e$ and the number that don't include $e$, and then randomly choose whether to include $e$ via a biased coin flip with heads probability chosen based on those two numbers, and continue from there). I don't know if this extends to approximately counting the number of cardinality-$k$ matchings or approximately randomly sampling from these matchings.

I can give you a heuristic method for randomly sampling a matching that might work well enough in practice, but I don't think it comes with any theoretical guarantees. Pick a random hash function $h:E \to [0,1]$ that hashes each edge to a real number in the range $[0,1]$. Pick a threshold $t \in [0,1]$. Set $E' = \{e \in E : h(e) \le t\}$. Check whether there is a cardinality-$k$ matching in $E'$. Now do binary search on $t$ to find the smallest $t$ that $E'$ contains a cardinality-$k$ matching, and output this matching. If you're lucky, this might work well enough: it should always find a cardinality-$k$ matching, and I suspect that the resulting matching might be random enough for your purposes (but there are no guarantees of randomness, and I think the resulting distribution on matchings is not uniform).

$\endgroup$
2
  • $\begingroup$ If I understand correctly, this will not uniformly pick a solution, so this wouldn't work for my purposes. I had actually considered something similar to this at some point and abandoned it for that reason. Thanks! $\endgroup$ Feb 18, 2022 at 21:24
  • 1
    $\begingroup$ @redmoncoreyl, I've updated my answer based on your clarifications to the problem. In the future, if you already know of a candidate solution that you've rejected, could you include that in your question and why you rejected it, so we don't waste time telling you something you already know, and so that we have an opportunity to build on the progress you've already made? Also it may help to describe the problem you actually want solved. $\endgroup$
    – D.W.
    Feb 18, 2022 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.