The following test is on Theorem 3 of [][page 86]. The basis idea behind the theorem is the observation that if the sum of the smallest scores is less than , then the teams have lost at least points in the matches among others. Let and . Definition 25.37 An intervallum satisfying sequence is called loss satisfying, iff 25.38 (Lucz, Iványi, Sótér []) A football sequence is loss satisfying. Proof. See the proof of Theorem 3 in []. The following algorithm Loss-Test exploits Lemma . Input. : the number of teams ; : a bounded sequence of length . Output. : a logical variable. Its is , if the input vector is Landau type, and otherwise. Working variables. : variable; : vector of the loss coefficient; : sums of the values, global variables; : binomial coefficients, global variables. Loss-Test 1 2 FOR TO 3 4 IF 5 6 RETURN 7 8 RETURN In worst case Loss-Test runs in time, in best case in time. We remark that is in the following a global variable. The number of loss satisfying sequences will be denoted by . Testing of the draw-loss property In the previous subsection Loss-Test exploited the fact, that scores signalize draws, allowing the improvement of the upper bound of the sum of the scores. Let us consider the loss sequence . made a draw, therefore one is lost and so must hold implying that the sequence is not a football sequence. This example is exploited in the following definition and lemma. Let Definition 25.39 A loss satisfying sequence is called draw loss satisfying, if and only if Lemma 25.40 (Lucz, Iványi, Sótér []) A football sequence is draw loss satisfying. The assertion follows from the fact that small scores and remainders (mod 3) of the scores both signalize lost points and so decrease the upper bound . The following algorithm Draw-Loss-Test exploits Lemma . Input. : the number of teams ; : a loss satisfying sequence of length .
In this case the Kuhn-Tucker necessary conditions are: denotes the gradient at , and is a vector which has the same length as . If we formulate the () conditions for , we get an equality-inequality system which can be solved by computer methods. It is easy to see that () can also be rewritten to an nonlinear optimization task: If the optimal objective function is positive, the () system doesn't have a solution, and if the optimal objective function value is zero, any optimal solution is also a solution of the () system, so the equilibrium are among the optimal solutions. We know about the sufficiency of the Kuhn-Tucker conditions that if is concave in with all , the Kuhn-Tucker conditions are also sufficient, thus every solution of () gives an equilibrium. The formal algorithm is as follows: Kuhn–Tucker-Equilibrium 1 FOR TO 2 DO 3 4 the solution of the () optimum task 5 IF 6 THEN RETURN "there is no equilibrium" 7 ELSE RETURN () Example 27.8 Assume that production plant produce some water purification device sold into households. Let denote the quantity produced by the th production plant, let be the cost function of it, and let be the sale price, which depends on the total quantity to be put on the market. Furthermore, be is the capacity of the th production plant. Thus, the possible decision set is the closed interval, which can be defined by the conditions, so The objective function of the th production is the profit of that: Since is two-dimensional, is a two-element vector as well, and the () optimum task has the following form: Let's introduce the new variables, and for the sake of notational convenience be , then taking account of the last condition, we get the following problem: Let's notice that in case of optimum , so the last term of the objective function can be neglected. Consider the special case of , , , . The () problem is now simplified as follows: Using a simple computer program we can get the optimal solution: which is the equilibrium as well. Exercises