A man was selling a cow in the market (computational solution)
As I already wrote , recently, when analyzing the structure of one specific service market, a rather interesting task was discovered, the solution of which at that time was not at all obvious to me, and, as the experience of the previous publication showed, it turned out to be not at all obvious to many local readers. By this decision, I owe a lot to your comments and advice. It seems quite instructive for me that the problem, at first glance, from the theory of mass service found a solution by attracting a field of knowledge far from it, thereby showing the unity of all branches of mathematics.
First of all, I would like to note that the arguments given below, although they give the right recommendations for action with sufficient accuracy for practice, and are conceptually correct, unfortunately, do not pretend to the simplicity of a qualitative description of the characteristic types of strategies. You can compare the proposed method of searching for a strategy with the solution of the quadratic equation by Newton's method: the result is correct, and the nature of the solution is hidden.
To begin with, let's try to find out if there is any way to act in the market without any loss for ourselves. The only reason for the loss is the need to bear the costs of keeping the cows. It is clear that the seller uses the most lean strategy when he has no more than one cow in the stall, and only after selling it does he order the next one. Using this approach, you need to sell the existing cow to the first buyer, belonging to any class, profitable from the point of view of the Man. It remains to decide which classes are recognized as cost-effective. For example, let's take two classes of buyers: representatives of the first let them appear on average 3 times per hour and give 1 rubles, and representatives of the second - 2 times and give 7. It’s easy to see that selling only the first class, you can earn 3 wheels for every hour of downtime , only to the second class of buyers - 14 rubles, and if you sell to any representative of these classes, then 14 + 3 rubles for each hour of paid downtime for a cow. Indeed, on average, 3 + 2 buyers will come for an hour of downtime, while on average 3 of them will be from the first class, and 2 from the second. From these considerations, we can conclude that a lean strategy will be optimal when the cow is sold to any buyer who gives a non-negative premium to the purchase price. If the average profit per hour is less than the cost of feed, then it hardly makes sense to stay on the market. From these considerations, we can conclude that a lean strategy will be optimal when the cow is sold to any buyer who gives a non-negative premium to the purchase price. If the average profit per hour is less than the cost of feed, then it hardly makes sense to stay on the market. From these considerations, we can conclude that a lean strategy will be optimal when the cow is sold to any buyer who gives a non-negative premium to the purchase price. If the average profit per hour is less than the cost of feed, then it hardly makes sense to stay on the market.
Let's now move on to a time-discrete analogue. To get a good approximation, we divide the time axis into such small equal intervals so that their value does not exceed 1/10 of the delivery time of cows from the village and at the same time the probability appears to at least one buyer, no matter what class, for such an interval did not exceed all that same 1/10. Another condition suggests itself, which should somehow limit the size of the discretization error of spending on relatively expensive feeds, as, for example, in the case of a very rich and rarely appearing buyer and a constantly available opportunity, if desired, to sell a cow very quickly at a purchase price. However, the condition for choosing such a small interval that during its course an average of 1/10 of the buyer appears, limits the responsiveness to the excess cow,
The next step in building an analogy is the transition from independent Poisson flows to dependent discrete customer flows. Suppose that in a continuous model the probability appears for an infinitely small period of time, the buyers of each category are treated as a: b: ...: h, and the probability appears for at least one buyer in the time interval obtained by splitting was equal to p, then in the discrete model at the beginning of each step we will conduct a one-time Bernoulli test for Success with probability p, and in the case of Success, some kind of test with many incompatible outcomes: one for each class of buyers and the same probability ratio between outcomes. Due to
It is time to describe the process of action in a discrete market. Let the delivery time T turn out to be divided into r intervals. The following is the order of actions within each partition interval, hereinafter referred to as rounds or moves. At the beginning of each tour, the Man receives the cows ordered for this time and pays for the feed of all his livestock, then it is determined by the tests described above whether the buyer came and what is the possible profit from him. At the end of the tour, the Peasant will have to perform two actions: sell the cow, or refuse the deal and order the necessary number of cows, which will be delivered to him exactly after r moves. On this move is completed and a new one begins.
In the described scheme of the functioning of the market, the condition of the guy at the time of decision
1) the number of cows he has in the stall,
2) the distribution of all the cows ordered by him in the nearest r turns,
3) the presence and class of the buyer at the current turn.
I must emphasize here that in 2) it is important not only the total number of cows in the order, but also their distribution according to the nearest moves for which the order is no longer possible.
Hypothetically, Muzhik has a countable number of possible states, but it seems quite obvious that there are such a number of cows M, having an order over which is not profitable regardless of the distribution of their delivery over r closest moves. As a result, the number of states that really participate in the game with any optimal strategy turns out to be finite.
Another almost obvious statement used below is the following: let's expand the class of acceptable strategies by allowing the peasant to act on the basis of random experiments, like tossing a coin. Such strategies in the theory of games are called mixed and allow you not to give the opponent an opportunity, having studied your play style quite well, to make your strategy more effective. It seems plausible that since there is no opponent in the described experiment, replacing all the results of tossing a coin with an “eagle” in any optimal strategy, you will not worsen the strategy itself.
I will finally turn to the description of the algorithm. We draw on paper separately all the permissible conditions of the Man at the beginning of the tour, when the cows have already arrived, and at the end before making a decision with the total number of available and ordered cows not exceeding M. Our goal will be to determine between these states directed ribs with cleverly chosen costs so that To solve the problem, it was possible to apply an algorithm for searching for a closed flow of unit power (the flow entering each vertex is equal to the flow coming from it, the sum over all vertices of the intensities of the incoming flows is 1) . So, we will consider some state at the beginning of the turn. From it we draw directed edges to the states possible at its end. Each such edge corresponds to the class of the incoming client or their complete absence. Assign these weights to the weights equal to their probabilities and costs equal to the magnitude of the cost of food. Now consider the conditions corresponding to the moment before making a decision on the sale and order. For each pair (order value, sell / no), draw an arrow in the state to which these actions will lead. We will not assign a fixed weight to these arrows, and we will set their value equal to the order price minus the order value. For most practical applications, it appears that you can order no more than one cow at a time. and we put their value equal to the order price minus the order value. For most practical applications, it appears that you can order no more than one cow at a time. and we put their value equal to the order price minus the order value. For most practical applications, it appears that you can order no more than one cow at a time.
We reduce the problem to the analysis of Markov chains. The choice of strategy with this approach corresponds to the assignment at each vertex corresponding to the state at the end of the turn of the probability weight to all edges emanating from it. Having found the limiting probability distribution (in non-degenerate cases, all the vertices are reachable and non-periodic), we determine the limiting probabilistic flow and from it the power of income or loss. A strategy will be optimal if it maximizes the power of income.
It is advisable to solve the search for the marginal flow and maximize profits simultaneously using the linear programming method, which, according to the average computational complexity, is significantly better than the direct search method, which is also applicable for solving a discrete problem, at least in theory.
I understood from the comments that the last paragraph requires clarification. If at some moment there is a probability distribution located in one or another state of the Markov chain, then the product of the probability of being in this state and the probability of transition to some other specific state - by definition, there is a value of the probability stream for the specified transition. If the chain has a limiting stationary distribution, then it is reasonable to call the corresponding probabilistic flow limiting. The naturalness of these definitions can be seen by observing, for example, the movement of bees between trees when an apiary is exposed in the garden. After sunrise, the proportion of bees on each tree will quickly come to almost constant values, just like the magnitude of the flows from one tree to another.
Now, as regards the application of the method for solving the linear programming problem: if the probabilistic flow on the constructed state graph is given by its values on each edge, then the only constraints in the form of inequalities are imposed on these quantities, consisting in the fact that they are all not less than zero. As for linear connections, they are as follows:
1) the total input stream to any vertex corresponding to the state at the beginning of the course is redistributed along the outgoing edges corresponding to the probability of the buyer arriving at a given class, in proportion to the probabilities for this class or the same, as indicated in the text above - the weight of the ribs;
2) the flows along the edges emanating from the vertices denoting the states at the end of the turn can be chosen by any one if only their sum is equal to the sum of the flows entering their vertex;
3) the sum of all components of the stream is 1.
Above, a method was given to assign all the edges of their costs. The scalar product of the flow vector and the cost vector acts as the objective function of the linear programming problem.
First of all, I would like to note that the arguments given below, although they give the right recommendations for action with sufficient accuracy for practice, and are conceptually correct, unfortunately, do not pretend to the simplicity of a qualitative description of the characteristic types of strategies. You can compare the proposed method of searching for a strategy with the solution of the quadratic equation by Newton's method: the result is correct, and the nature of the solution is hidden.
To begin with, let's try to find out if there is any way to act in the market without any loss for ourselves. The only reason for the loss is the need to bear the costs of keeping the cows. It is clear that the seller uses the most lean strategy when he has no more than one cow in the stall, and only after selling it does he order the next one. Using this approach, you need to sell the existing cow to the first buyer, belonging to any class, profitable from the point of view of the Man. It remains to decide which classes are recognized as cost-effective. For example, let's take two classes of buyers: representatives of the first let them appear on average 3 times per hour and give 1 rubles, and representatives of the second - 2 times and give 7. It’s easy to see that selling only the first class, you can earn 3 wheels for every hour of downtime , only to the second class of buyers - 14 rubles, and if you sell to any representative of these classes, then 14 + 3 rubles for each hour of paid downtime for a cow. Indeed, on average, 3 + 2 buyers will come for an hour of downtime, while on average 3 of them will be from the first class, and 2 from the second. From these considerations, we can conclude that a lean strategy will be optimal when the cow is sold to any buyer who gives a non-negative premium to the purchase price. If the average profit per hour is less than the cost of feed, then it hardly makes sense to stay on the market. From these considerations, we can conclude that a lean strategy will be optimal when the cow is sold to any buyer who gives a non-negative premium to the purchase price. If the average profit per hour is less than the cost of feed, then it hardly makes sense to stay on the market. From these considerations, we can conclude that a lean strategy will be optimal when the cow is sold to any buyer who gives a non-negative premium to the purchase price. If the average profit per hour is less than the cost of feed, then it hardly makes sense to stay on the market.
Let's now move on to a time-discrete analogue. To get a good approximation, we divide the time axis into such small equal intervals so that their value does not exceed 1/10 of the delivery time of cows from the village and at the same time the probability appears to at least one buyer, no matter what class, for such an interval did not exceed all that same 1/10. Another condition suggests itself, which should somehow limit the size of the discretization error of spending on relatively expensive feeds, as, for example, in the case of a very rich and rarely appearing buyer and a constantly available opportunity, if desired, to sell a cow very quickly at a purchase price. However, the condition for choosing such a small interval that during its course an average of 1/10 of the buyer appears, limits the responsiveness to the excess cow,
The next step in building an analogy is the transition from independent Poisson flows to dependent discrete customer flows. Suppose that in a continuous model the probability appears for an infinitely small period of time, the buyers of each category are treated as a: b: ...: h, and the probability appears for at least one buyer in the time interval obtained by splitting was equal to p, then in the discrete model at the beginning of each step we will conduct a one-time Bernoulli test for Success with probability p, and in the case of Success, some kind of test with many incompatible outcomes: one for each class of buyers and the same probability ratio between outcomes. Due to
It is time to describe the process of action in a discrete market. Let the delivery time T turn out to be divided into r intervals. The following is the order of actions within each partition interval, hereinafter referred to as rounds or moves. At the beginning of each tour, the Man receives the cows ordered for this time and pays for the feed of all his livestock, then it is determined by the tests described above whether the buyer came and what is the possible profit from him. At the end of the tour, the Peasant will have to perform two actions: sell the cow, or refuse the deal and order the necessary number of cows, which will be delivered to him exactly after r moves. On this move is completed and a new one begins.
In the described scheme of the functioning of the market, the condition of the guy at the time of decision
1) the number of cows he has in the stall,
2) the distribution of all the cows ordered by him in the nearest r turns,
3) the presence and class of the buyer at the current turn.
I must emphasize here that in 2) it is important not only the total number of cows in the order, but also their distribution according to the nearest moves for which the order is no longer possible.
Hypothetically, Muzhik has a countable number of possible states, but it seems quite obvious that there are such a number of cows M, having an order over which is not profitable regardless of the distribution of their delivery over r closest moves. As a result, the number of states that really participate in the game with any optimal strategy turns out to be finite.
Another almost obvious statement used below is the following: let's expand the class of acceptable strategies by allowing the peasant to act on the basis of random experiments, like tossing a coin. Such strategies in the theory of games are called mixed and allow you not to give the opponent an opportunity, having studied your play style quite well, to make your strategy more effective. It seems plausible that since there is no opponent in the described experiment, replacing all the results of tossing a coin with an “eagle” in any optimal strategy, you will not worsen the strategy itself.
I will finally turn to the description of the algorithm. We draw on paper separately all the permissible conditions of the Man at the beginning of the tour, when the cows have already arrived, and at the end before making a decision with the total number of available and ordered cows not exceeding M. Our goal will be to determine between these states directed ribs with cleverly chosen costs so that To solve the problem, it was possible to apply an algorithm for searching for a closed flow of unit power (the flow entering each vertex is equal to the flow coming from it, the sum over all vertices of the intensities of the incoming flows is 1) . So, we will consider some state at the beginning of the turn. From it we draw directed edges to the states possible at its end. Each such edge corresponds to the class of the incoming client or their complete absence. Assign these weights to the weights equal to their probabilities and costs equal to the magnitude of the cost of food. Now consider the conditions corresponding to the moment before making a decision on the sale and order. For each pair (order value, sell / no), draw an arrow in the state to which these actions will lead. We will not assign a fixed weight to these arrows, and we will set their value equal to the order price minus the order value. For most practical applications, it appears that you can order no more than one cow at a time. and we put their value equal to the order price minus the order value. For most practical applications, it appears that you can order no more than one cow at a time. and we put their value equal to the order price minus the order value. For most practical applications, it appears that you can order no more than one cow at a time.
We reduce the problem to the analysis of Markov chains. The choice of strategy with this approach corresponds to the assignment at each vertex corresponding to the state at the end of the turn of the probability weight to all edges emanating from it. Having found the limiting probability distribution (in non-degenerate cases, all the vertices are reachable and non-periodic), we determine the limiting probabilistic flow and from it the power of income or loss. A strategy will be optimal if it maximizes the power of income.
It is advisable to solve the search for the marginal flow and maximize profits simultaneously using the linear programming method, which, according to the average computational complexity, is significantly better than the direct search method, which is also applicable for solving a discrete problem, at least in theory.
I understood from the comments that the last paragraph requires clarification. If at some moment there is a probability distribution located in one or another state of the Markov chain, then the product of the probability of being in this state and the probability of transition to some other specific state - by definition, there is a value of the probability stream for the specified transition. If the chain has a limiting stationary distribution, then it is reasonable to call the corresponding probabilistic flow limiting. The naturalness of these definitions can be seen by observing, for example, the movement of bees between trees when an apiary is exposed in the garden. After sunrise, the proportion of bees on each tree will quickly come to almost constant values, just like the magnitude of the flows from one tree to another.
Now, as regards the application of the method for solving the linear programming problem: if the probabilistic flow on the constructed state graph is given by its values on each edge, then the only constraints in the form of inequalities are imposed on these quantities, consisting in the fact that they are all not less than zero. As for linear connections, they are as follows:
1) the total input stream to any vertex corresponding to the state at the beginning of the course is redistributed along the outgoing edges corresponding to the probability of the buyer arriving at a given class, in proportion to the probabilities for this class or the same, as indicated in the text above - the weight of the ribs;
2) the flows along the edges emanating from the vertices denoting the states at the end of the turn can be chosen by any one if only their sum is equal to the sum of the flows entering their vertex;
3) the sum of all components of the stream is 1.
Above, a method was given to assign all the edges of their costs. The scalar product of the flow vector and the cost vector acts as the objective function of the linear programming problem.