Wikipedia:Reference desk/Archives/Mathematics/2014 October 22

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 22

Optimal strategy for moving on a graph

This problem originates from one aspect of designing a bot for playing the game of Reeelz, but it seems like a general problem that is worth exploring in abstract terms.

I am given a graph $G=(V,E)$, and a set $\{R_{1},R_{2},\ldots ,R_{m}\}$ of equivalence relations on V. Additionally I am given a function $f:V\to \mathbb {R}$. In the original application, $|V|=n=11^{7}=19,487,171$, every node is connected to $k=14$ others, the diameter of the graph is 35, there are $m=128$ relations, and f is roughly on the range [0, 20]. There is additional structure to the graph and relations in this application, but I doubt it is significant.

I then play a game as follows: I am placed at a random vertex in the graph. On every turn I can either:

• Step: Choose a vertex connected by an edge to the one I am currently in, and move to it.
• Spin: Choose a relation $R_{i}$, and move to a uniformly random vertex in the same equivalence class as the one I am in.

At any point I can stop the game, and my final score will be the value of f at the vertex on which I terminated, minus the number of turns I took. My goal is to maximize my expected score, and the way to do this is of course to reach a vertex which is as good as possible, in as few moves as possible.

The brute force way to solve this is to assign a score to every vertex, and iteratively update the score of every vertex to be the maximum of the vertex's score, the score of every neighbor minus 1, and for every relation, the average score of all equivalent vertices minus 1. It seems obvious to me that this will converge to the correct scores (from which it is easy to figure out the optimal strategy at every vertex), but every iteration is expensive, and it can take many iterations.

Is there a more efficient way to solve it? -- Meni Rosenfeld (talk) 20:49, 22 October 2014 (UTC)

You can try a Branch and boundish approach.

Rough idea: Ignore, for the moment, the second option offered in every turn to jump to a vertex in the same equivalence class. Now, for any vertex in the set $V_{20}=\{v:f(v)=20\}$, the max score is clearly 20 (and the optimal strategy is to stay there). For any neighboring vertex v', the score is at least $\max(f(v'),19)$. Similarly for the neighbor-of-the-neighbor etc. This will give you lower bounds on the score for each vertex pretty quickly. Similarly the upper bound for any vertex v is the maximum of $f(v)$; the function evaluated for all of its first order neighbors minus 1; the function evaluated for all of its first order neighbors minus 2 etc (Note that you will get rougher, but usable bounds, even if you you use only the p-neighborhood for any vertex, with p<<35, the diameter of the graph)

Now you can introduce back the second option (perhaps introducing only one $R_{i}$ at a time), and update these lower bound and upper bounds. May still require a few iterations to determine the true expected score for each vertex, but the bounds will help cull the non-productive branches in the decision tree. That culling should hopefully lead to a faster algorithm than the brute force aproach. Abecedare (talk) 21:35, 22 October 2014 (UTC)

Thanks. Well, the first step can be simplified into using Dijkstra's algorithm for finding the exact score for each vertex (without the equivalence class, which I've renamed "Spin" in the OP).

I'm not sure how exactly to find upper bounds with the possibility of spins, or how to use them for pruning without prohibitive overhead. However, your suggestion of introducing one equivalence at a time made me realize that if I do iterations normally but each time consider only the possibility of one random equivalence, I will probably get a much better ratio of (improvement in score estimates / work done). So with ~1000 easy iterations, plus some optimizations related to the specific application, I could get a good approximation with a reasonable amount of computation. -- Meni Rosenfeld (talk) 12:11, 23 October 2014 (UTC)

Yes, I see why the spin complicates the issue of computing useful/non-trivial upper bounds. Btw, approximately how many classes does an $R_{i}$ partition V into, and what is the range of sizes of these classes? Asking because, if the number of classes is say ~10, then the situation seems hopeless and you may just have to accept that Monte Carlo/probabilistic estimates are the best that can be done. But, if instead the class-size is say <10, maybe there is a some clever way out. Abecedare (talk) 14:24, 23 October 2014 (UTC)

For every j, there are ${\binom {7}{j}}$ equivalences that subdivide V into $11^{j}$ classes of $11^{7-j}$ elements each. So you have 7 relations with 11 classes of 1771561 elements, 7 relations with 1771561 classes of 11 elements, and everything in between.

I may as well add some more detail about the application: $V=(\mathbb {Z} _{11})^{7}$. Every relation is identified with a subset of indices, and two elements are equivalent under the relation if their entries in these indices are equal. Two vertices are connected by an edge if their entries are equal in all but one index, and in this index differ by 1.

In fact, for this instantiation of the problem, it is easy to show that it is never a good idea to do a step before a spin: You first do all of your spins, then all of your steps. This can simplify the solution somewhat (you can find the score of every vertex in absence of spins, and then when you reintroduce spins you can ignore the possibility of steps).

Of course, there are many more intricacies when you take into account all of the rules of the particular game, but the basic problem above is a start. -- Meni Rosenfeld (talk) 15:43, 23 October 2014 (UTC)

Numbers bad. Structure good. :)

Question about "for this instantiation of the problem, it is easy to show that it is never a good idea to do a step before a spin". Is this true for any f, or does it have to do with the particular f you are dealing with ? Don't expect you to provide the proof of course; just asking for my own curiosity and to see if I can derive the result in my own head. Abecedare (talk) 16:01, 23 October 2014 (UTC)

It's true for any f.

In fact, for this application you have to run the process for many different fs; that's the main reason I'm looking for a solution as efficient as possible. -- Meni Rosenfeld (talk) 18:03, 23 October 2014 (UTC)