1

Topic: Re: Pioneers and vodka

Hello, Kodt, you wrote: the Question: to what strategy the leader should adhere to maximize the advantage a minus costs? Well and accordingly, what pioneers should undertake? About scorings of pioneers from successful drinking in different places you did not tell. I think that for the leader there will be optimal a casual choice of a place of check. The probability of a choice of each place should be different. It is possible to minimize both average and maximum losses from loss.

2

Re: Re: Pioneers and vodka

Hello, Kodt, you wrote: a zhyznennaja problem from the games theory. (Alexey Savvateeva's Video lecture perfectly is on a title, therefore do not look there, there a spoiler) In camp pioneers got a bottle of vodka and solved it  during a camp holiday. The leader guesses intentions of pioneers. Drinking is possible in several places. Visiting of various places of drinking attracts for the leader moral costs by which it is possible to measure quantitatively (in different places they different). If it catches pioneers behind drinking receives moral advantage which too is measured quantitatively and exceeds costs on visiting of any of places. The leader is obliged to check up at least one of places, but cannot check up more than one. For definiteness: let there are four places costs for which make 1, 2, 3 and 4 units. (For example, each unit are a half an hour, i.e. To check up the first refuge, the leader spends not enough time because it somewhere is close from  collection, and to the last refuge it is necessary to swarm up adjacent wood).> And advantage makes 5 units (so much time it is required on pottering with already drunk children). A question: to what strategy the leader should adhere to maximize the advantage a minus costs? Well and accordingly, what pioneers should undertake? Both choices - where to hide to pioneers and where to go to the leader - become simultaneously and single-valuedly. All is simple: the leader causes a platoon of policemen and they knit all in all possible places of drinking.

3

Re: Re: Pioneers and vodka

Hello, Kodt, you wrote: the Question in that, how looks allocation of probabilities. Let probabilities of a choice of pioneers are known and equal w_i Then target function of the leader looks as an average scoring gain (v) = sum ((gain_i*w_i - loss_i * (1-w_i)) *v_i) = sum ((5*w_i - loss_i * (1-w_i)) *v_i) v_i - probability components selected by the leader, gain_i = 5 for all i loss_i = {1 2 3 4}; This linear programming - to us needs to be found a maximum of the linear function at the linear restrictions. {0 <=v_i <=1, sum (v_i) = 1} - a convex polyhedron, therefore the decision will be or a) to coincide from one of edges b) will belong to it one of edges will concern one of peaks. We check up a case as the idle time. Let max (gain) it is not reached in one of peaks. Let target function in peaks reaches values G_i, Rassm. Such peak j in which G_j it is maximum among all peaks. Then going on one of edges on a step e we receive magnification gain. I.e. (1) gain (0. 010. 0) = G_j = 5*w_j - loss_j (1-w_j) (2) gain (0. e (1-e) 0. 0) = (5*w_j - loss_i (1-w_j)) (1 e) + (5*w_k - loss_k (1 w_k)) *e = G_j - eG_j + eG_k = G_j - e (G_j - G_k) At the given constants G_k it is not equal G_j at w_j, w_k unequal 0 (it is possible . A difference, substituting constants). Therefore G_j-G_k always it is more 0 => at leaving on an edge we receive reduction of target function instead of growth. Came to the contradiction, means all the same c). Wrote an unpretentious script that it to check up. At casually selected w_i, always we roll down to one of type points v_i = [0. 010. 0] Then did not withstand and watched film

4

Re: Re: Pioneers and vodka

Hello, Kodt, you wrote: Hello, andyp, you wrote: A>> let probabilities of a choice of pioneers are known and equal w_i A>> Then target function of the leader looks as average scoring A>> gain (v) = sum ((gain_i*w_i - loss_i * (1-w_i)) *v_i) = sum ((5*w_i - loss_i * (1-w_i)) *v_i) A>> v_i - probability components selected by the leader, A>> gain_i = 5 for all i A>> loss_i = {1 2 3 4}; the Leader incurs costs anyway, therefore the formula should be corrected. To remove a factor (1-w_i) from loss_i. Like all it is true. At pioneer probabilities w_i the leader can benefit with probability w_i or lose with probability 1-w_i if pioneers do not go to this point. Then averaged on probabilities of the leader to find an average scoring. It is possible to consider minimax loss then target linear ceases to be that is not so convenient. A>> this linear programming - to us needs to be found a maximum of the linear function at the linear restrictions. {0 <=v_i <=1, sum (v_i) = 1} - a convex polyhedron, therefore the decision will be or A>> a) to coincide from one of edges A>> b) to it will belong one of edges A>> will concern one of peaks. It not absolutely linear programming as it is necessary to maximize simultaneously gain on v (is the task of the leader) and to minimize on w (it is malicious intention of pioneers). It. I simply tried to prove that at ANY w_i from a simplex and coefficients from a condition, we receive v_i in peaks of a simplex for a maximum of target function of the leader at set w_i. I.e. v_i a type [0. 010. 0] at a maximum of target function of the leader. You about about a maximum on Neshu write (concept new to me which I just looked in  and understood from lecture as the games theory I do not know absolutely) - it too concerns maxima about which I spoke (one of them). Well or to search for the answer for function from 8-dimensional space (4 probabilities at the leader and 4 at pioneers) on a 2-dimensional estimation (a scoring of the leader, a scoring of pioneers). It is necessary to search for balance. That is, pioneers should  (to arrange the leader the probabilities w so that to the leader was all the same how to arrange the v), and the leader -  pioneers. Tried the following procedure by a script - a little bit we twist probabilities of the leader towards target function magnification, then we twist probabilities of pioneers towards magnification of their target function, again we twist probabilities of the leader, etc. It is impossible to quit on a maximum of Nesha. And a local maximum generally. How to search for the numerical decision by such multidimentional optimization, I do not know. A>> then did not withstand and watched film Suddenly, yes? Half.  in the first part to the same output came - at it the decision for v_i - [1000...] Truth without the linear programming. And so it is beautiful, yes

5

Re: Re: Pioneers and vodka

Hello, Kodt, you wrote: Then it is necessary gain_i = {5-1, 5-2, 5-3, 5-4} because in case of success (w_i*v_i) the leader spends a heap of time for searches and spares on sobering. Yes it is possible and so. Important that there is a Price of a scoring and the price of loss and there is an average scoring - actually a subject for optimization. At pioneers simply optimized sum (-v_i*w_i) - on your condition (they actually only pay for loss when them burned). A>> It. I simply tried to prove that at ANY w_i from a simplex and coefficients from a condition, we receive v_i in peaks of a simplex for a maximum of target function of the leader at set w_i. I.e. v_i a type [0. 010. 0] at a maximum of target function of the leader. You about about a maximum on Neshu write (concept new to me which I just looked in  and understood from lecture as the games theory I do not know absolutely) - it too concerns maxima about which I spoke (one of them). Here the error in the logician somewhere hid. Yes in my text a vagueness - it is necessary to read it so: "I simply tried to prove that at ANY w_i from a simplex and coefficients TAKEN from a condition..." . Certainly, generally the boundary can coincide with an edge or a simplex edge about what at once and wrote. It is a pity that muffledly quitted. The freebie with peaks was only for yours (well can still what) dial-ups . On the one hand, - it is valid, for any specific mixed strategy of pioneers the optimum of the leader will be on simplex boundary, and at least one peak (i.e. pure strategy) there gets. But focus that - besides default strategy, that is, fixings of losses, - for each specific strategy of pioneers this pure strategy of the leader will be different. Roughly speaking, it argmax (gain_i*w_i-loss_i * (1-w_i)). That is, to look, where () pioneers visit more often, and there and to go. If argmax ambiguous the boundary contains some peaks and has appropriate dimensionality. For this reason with a minimax did not begin to communicate. In . To radio engineering both (average loss and a minimax) have the right to life and are used. Or you minimize the worst loss, or - average. I about average wrote. But after all pioneers too not fools. If they know a train of thought of the leader (and know, in case of ambiguity he selects which pure strategy) they refine the mixed strategy, nullifying probability of a matching component. Then the leader enumerates argmax, selects other pure strategy, and pioneers and this component nullify. And so they get into a mess before, as pioneers will have a pure strategy, and the leader directly to them on a visit goes. And then to pioneers all roads from a hole - only upwards, and they for improving take any strategy - pure or mixed - at which that's it this component zero, on  a bast, make a fresh start. Pioneers not that what not fools. At all without knowing strategy of the leader (we assume that at us probability game) they always should estimate it on draws. The leader - it is similar. I.e. it will turn out that after strategy change one of the sides strongly loses any time, therefore she adapts and minimizes losses (maximizes a scoring, perhaps). Again we have balance for the selected strategy. It follows from this that such method of serial improvings - a basis of the linear programming - is unacceptable. As a matter of fact, it was from the very beginning clear. Game on opposition, and a merit function, satisfying both sides, almost everywhere is equal to zero (except default strategy when one of the sides surrenders and minimizes the losses). I also did not have anything when tried gradually changing  on coordinates to reach a stable state of all system - when a scoring of pioneers and the leader feeblly change. I.e. All worked so - pioneers and the leader adapted for strategy each other, then someone changed the a little to increase a scoring proceeding from strategy of the opponent, then other side adapted and too changed the strategy too a little to increase own scoring, etc. process to balance of Nesha did not converge. Generally to any balance did not converge - scorings of pioneers and the leader had oscillating character from draw number - probabilities in strategy were swung between components. It by the way for balance Not all is possible for +100 author of the analytical decision  modeling. It for was specific these values. It agree completely. PS and here if the leader was much more strongly  to find pioneers, its equilibrium scoring E would be equal G*w1-L1 = G*w2-L2 = G*w3-L3 = G*w4-L4 = E 4E = G - (L1+L2+L3+L4) E = (G - (L1+L2+L3+L4))/4 where G - the expected income at good luck, L1. . L4 - unconditional expenditures and if it above a default-min (L1, L2, L3, L4) =-L1 the leader will have the mixed strategy - with some probabilities to glance in everyone .  to count specific target function in simplex peaks (the blessing, is not enough of them) easier. If it different for all peaks - we have a maximum in peaks. It is identical to two peaks - on an edge, For 3 - on the verge. A polyhedron at us, thank God, the correct.

6

Re: Re: Pioneers and vodka

Hello, Kodt, you wrote: a zhyznennaja problem from the games theory. (Alexey Savvateeva's Video lecture perfectly is on a title, therefore do not look there, there a spoiler) In camp pioneers got a bottle of vodka and solved it  during a camp holiday. The leader guesses intentions of pioneers. Drinking is possible in several places. Visiting of various places of drinking attracts for the leader moral costs by which it is possible to measure quantitatively (in different places they different). If it catches pioneers behind drinking receives moral advantage which too is measured quantitatively and exceeds costs on visiting of any of places. The leader is obliged to check up at least one of places, but cannot check up more than one. For definiteness: let there are four places costs for which make 1, 2, 3 and 4 units. (For example, each unit are a half an hour, i.e. To check up the first refuge, the leader spends not enough time because it somewhere is close from  collection, and to the last refuge it is necessary to swarm up adjacent wood).> And advantage makes 5 units (so much time it is required on pottering with already drunk children). A question: to what strategy the leader should adhere to maximize the advantage a minus costs? Well and accordingly, what pioneers should undertake? Both choices - where to hide to pioneers and where to go to the leader - become simultaneously and single-valuedly. 1. We designate: - probability of a campaign of the leader in a place i through wi - probability of drinking by pioneers in a place i through pi - an amount of bonuses which the leader at capture of pioneers in a place i through bi (advantage receives a minus costs) 2. It is obvious that Sumy wi = 1, Sumy pi = 1 3. Balance Is necessary.  a bonus of the leader in all places it should be identical (besides, we should consider probability of that pioneers go to this place) probability to be caught in all places should be identical (certainly, we should consider probability of that the leader comes to this place) 3.  a bonus of the leader in a place i it is equal bi * wi * pi (a bonus we receive if the leader there went also pioneers too there went). Since  all places equally we receive b1 * w1 * p1 = b2 * w2 * p2 = b3 * w3 * p3... From this equality it is possible to express p2, p3 etc. In a general view pi = (b1/bi) * (w1/wi) * p1 For simplification we make changeover b1/bi = ci we receive pi = ci * (w1/wi) * p1 3. Probability of success action of pioneers i is equal in a place pi * (1 - wi) (pioneers there went, and the leader is not present) Since probability of all places is identical, we we receive p1 * (1 - w1) = p2 * (1 - w2) = p3 * (1 - w3)... From this equality it is possible to express p2, p3 etc. In a general view pi = (1-w1) / (1-wi) * p1 3 It is equated pi from 3 and 3 ci * (w1/wi) * p1 = (1-w1) / (1-wi) * p1, we reduce on p1 ci * (w1/wi) = (1-w1) / (1-wi), we express wi through w1 wi = ci * w1 / (1 - w1 + ci * w1) 3. It is obvious that the total of all wi equals to unit, therefore it is necessary to solve system of equations wi = ci * w1 / (1 - w1 + ci * w1) the TOTAL wi = 1 3 Solving system we receive values wi. Further similarly we solve system for pi (their total too is equal 1) pi = (1-w1) / (1-wi) * p1 the TOTAL pi = 1 we Receive the answer 4. Now the code import numpy as np from scipy.optimize import bisect # the initial data b_arr = np.array ([1,4]) # bonuses of the leader c_arr = np.min (b_arr) / b_arr # changeover b1/bi # the decision of system of equations for wi def calc_wi (w0, ci): return ci * w0 / (1 - w0 + ci * w0) def goal_sum_wi (w0): return np.sum (calc_wi (w0, c_arr)) - 1 w0 = bisect (goal_sum_wi, 0, 1) w_arr = calc_wi (w0, c_arr) # the decision of system of equations for pi def calc_pi (w0, p0, wi): return (1-w0) / (1-wi) * p0 def goal_sum_pi (p0): return np.sum (calc_pi (w0, p0, w_arr)) - 1 p0 = bisect (goal_sum_pi, 0, 1) p_arr = calc_pi (w0, p0, w_arr) # we deduce result print ("Bonuses of the leader:", b_arr) print ("Probability of a choice for the leader (strategy):", w_arr) print ("Probability of capture:", p_arr * w_arr) print ("Matozhidanie of bonuses for the leader:", p_arr * w_arr * b_arr) print () print ("Probability of a choice for pioneers (strategy):", p_arr) print ("Probability of successful drinking:", p_arr * (1 - w_arr)) print () print ("Total probability of capture:", np.sum (p_arr * w_arr)) print ("Total probability of successful drinking:" np.sum (p_arr * (1 - w_arr))) 5. Results Bonuses of the leader: [1 4] Probability of a choice for the leader (strategy): [0.66666667 0.33333333] Probability of capture: [0.44444444 0.11111111] Matozhidanie of bonuses for the leader: [0.44444444 0.44444444] Probability of a choice for pioneers (strategy): [0.66666667 0.33333333] Probability of successful drinking: [0.22222222 0.22222222] Total probability of capture: 0.555555555555 Total probability of successful drinking: 0.444444444445 Bonuses of the leader: [1 2 3 4] Probability of a choice for the leader (strategy): [0.40865732 0.25680033 0.18722686 0.1473155] Probability of capture: [0.12704082 0.06352041 0.04234694 0.03176021] Matozhidanie of bonuses for the leader: [0.12704082 0.12704082 0.12704082 0.12704082] Probability of a choice for pioneers (strategy): [0.31087373 0.24735332 0.22617985 0.21559311] Probability of successful drinking: [0.1838329 0.1838329 0.1838329 0.1838329] Total probability of capture: 0.264668384659 Total probability of successful drinking: 0.735331615347 Bonuses of the leader: [1 500] Probability of a choice for the leader (strategy): [0.95719303 0.04280697] Probability of capture: [0.91621849 0.00183244] Matozhidanie of bonuses for the leader: [0.91621849 0.91621849] Probability of a choice for pioneers (strategy): [0.95719303 0.04280697] Probability of successful drinking: [0.04097454 0.04097454] Total probability of capture: 0.918050926966 Total probability of successful drinking: 0.0819490730343 it is interesting that the probability of success of action somehow depends on bonuses of the leader. The variant of bonuses 1-4, strongly differs from a variant of bonuses 1-500. Any error in reasonings can eat?