0
$\begingroup$

I am currently working on a problem which I assume mathematicians have already solved.

Setup: I have $N$ people standing in a line. Each of them is assigned with a different number between $1$ to $N$. All people in the line know their number and the number of each other in the line as well as the position of each other person relative to themselves.

Problem: I want to figure out the order of the people standing in the line but I only have some relative positions:

I can ask $M\leq N$ people to tell me their relative position to $r$ other people of their choice with an integer value between $-p$ to $p$ where $p$ indicates whether the other person is ahead of them in the line (positive value) or behind them (negative value), $0$ is their own position. E.g. for $p=1$ it would be a binary information behind/ahead. For $p=2$ one could differentiate between far ahead (+2) or close ahead (+1), or far behind (-2) and close behind (-1). Overall I get $M*r$ relative positions. To make things more interesting a portion $q<0.1$ of those $M*r$ is false information because the person lied.

Example: $N=5$, $M=5$, $r = 2$, $p = 1$, $q = 0.1$. The actual unknown line order is $[3,5,2,4,1]$.

I ask $M=5$ people to tell me $r=2$ relative positions.

  • #1 tells me that #5 is behind him, and #2 is behind him
  • #2 tells me that #4 is ahead of him, and #3 is behind him
  • #3 tells me that #1 is ahead of him, and #2 is behind him (the 2nd info is a lie)
  • #4 tells me that #1 is ahead of him, and #5 is behind him
  • #5 tells me that #4 is ahead of him, and #3 is behind him

Which algorithm or mathematical field can I apply to find the most probable actual order? It must be efficient to work for N>100, so trying all possible combinations is not an option I guess. Obviously, this problem will not be solvable for all kind of possible outcomes, but I want to determine how much information I need to be about 90% accurate with my prediction. I do not need any analytical model just an idea how this could be solved by an iterative method which is programmable.

I hope you got the idea, otherwise let me know.

Thanks

Update with topological sorting applied (q=0) Mathematica Example Code

$\endgroup$
6
  • 1
    $\begingroup$ The question as it is written doesn't have a unique answer... it's difficult to help you. However, I would just sort by average $p$ as a first initial guess, this could provide you with a statistical estimator. Unsure it meets your need though. $\endgroup$
    – PC1
    Commented Jun 24, 2022 at 16:32
  • 1
    $\begingroup$ To sort things based on partial information you need to use Topological Sorting. You also have the problem that there are inaccuracies in the pile; you will need to find a way to break cycles in the directed graph. Note that you will not likely be able to correctly suss out which entries are the actual lies, but any cycle in your directed graph will be guaranteed to have a lie in it. $\endgroup$
    – Dan Uznanski
    Commented Jun 24, 2022 at 16:33
  • $\begingroup$ @PC1 This was actually the first what I tried but it gives rather poor results depending on the sample. Also, I did not make any assumption how often someone is mentioned by others. By sorting with average $p$ people who are mentioned less are systematically biased. $\endgroup$
    – ScienceEnthusiast
    Commented Jun 24, 2022 at 16:41
  • $\begingroup$ @ScienceEnthusiast, the better approach would probably be to write a likelihood function for your observed data and try to maximize it. For this you would need to have some probabilistic description of your data (including the probability of having a false answer from someone). $\endgroup$
    – PC1
    Commented Jun 24, 2022 at 17:20
  • $\begingroup$ @DanUznanski Brilliant, topological sorting is exactly what I was looking for. It works great for q=0 (acyclic graph). But you are correct as soon as q > 0 it breaks down. Somehow this approach needs to be combined with a likelihood. I updated my initial post with a quick Mathematica code example which shows that it works without inaccuracies. $\endgroup$
    – ScienceEnthusiast
    Commented Jun 24, 2022 at 17:27

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .