A solution concept forn-person noncooperative games

The paper describes a solution concept forn-person noncooperative games, developed jointly by the author and Reinhard Selten. Its purpose is to select one specific perfect equilibrium points=s (G) as the solution of any given noncooperative gameG. The solution is constructed by an inductive procedure. In defining the solutions (G) of gameG, we use the solutionss (G ^*) of the component gamesG ^* (if any) ofG; and in defining the solutions (G^*) of any such component gameG ^*, we use the solutionss (G ^**) of its own component gamesG ^** (if any), etc. This inductive procedure is well-defined because it always comes to an end after a finite number of steps. At each level, the solution of a game (or of a component game) is defined in two steps. First, aprior subjectiveprobability distribution p _i is assigned to the pure strategies of each playeri, meant to represent the other players' initial expectations about playeri's likely strategy choice. Then, a mathematical procedure, called thetracing procedure, is used to define the solution on the basis of these prior probability distributionsp _i . The tracing procedure is meant to provide a mathematical representation for thesolution process by which rational players manage to coordinate their strategy plans and their expectations, and make them converge to one specific equilibrium point as solution for the game     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

A stable approach to Newton's method for general mathematical programming problems inR n

The usual approach to Newton's method for mathematical programming problems with equality constraints leads to the solution of linear systems ofn +m equations inn +m unknowns, wheren is the dimension of the space andm is the number of constraints. Moreover, these linear systems are never positive definite. It is our feeling that this approach is somewhat artificial, since in the unconstrained case the linear systems are very often positive definite. With this in mind, we present an alternate Newton-like approach for the constrained problem in which all the linear systems are of order less than or equal ton. Furthermore, when the Hessian of the Lagrangian at the solution is positive definite (a situation frequently occurring), all our systems will be positive definite. Hence, in all cases, our Newton-like method offers greater numerical stability. We demonstrate that the convergence properties of this Newton-like method are superior to those of the standard approach to Newton's method. The operation count for the new method using Gaussian elimination is of the same order as the operation count for the standard method. However, if the Hessian of the Lagrangian at the solution is positive definite and we use Cholesky decomposition, then the order of the operation count for the new method is half that for the standard approach to Newton's method. This theory is generalized to problems with both equality and inequality constraints.     

Mathematical tables in Ptolemy's Almagest

This paper is a discussion of Ptolemy's use of mathematical tables in the Almagest. By focusing on Ptolemy's mathematical practice and terminology, I argue that Ptolemy used tables as part of an organized group of units of text, which I call the table nexus. In the context of this deductive structure, tables function in the Almagest in much the same way as theorems in a canonical work, such as the Elements, both as means of presenting acquired knowledge and as tools for producing further knowledge.     

The tracing procedure: A Bayesian approach to defining a solution forn-person noncooperative games

The paper proposes a Bayesian approach to selecting a particular equilibrium points ^* of any given finiten-person noncooperative game Γ as solution for Γ. It is assumed that each playeri starts his analysis of the game situation by assigning a subjective prior probability distributionp _j to the set of all pure strategies available to each other playerj. (The prior distributionsp _j used by all other playersi in assessing the likely strategy choice of any given playerj will be identical, because all these playersi will compute this prior distributionp _j from the basic parameters of game Γ in the same way.) Then, the players are assumed to modify their subjective probability distributionsp _j over each other's pure strategies systematically in a continuous manner until all of these probability distributions will converge, in an appropriate sense, to a specific equilibrium points ^* of Γ, which, then, will be accepted as solution. A mathematical procedure, to be called thetracing procedure, is proposed to provide a mathematical representation for this intellectual process of convergent expectations. Two variants of this procedure are described. One, to be called thelinear tracing procedure, is shown to define a unique solution in “almost all” cases but not quite in all cases. The other variant, to be called thelogarithmic tracing procedure, always defines a unique solution in all possible cases. Moreover, in all cases where the linear procedure yields a unique solution at all, both procedures always yield the same solution. For any given game Γ, the solution obtained in this way heavily depends on the prior probability distributionsp ₁,...,p _n used as a starting point for the tracing procedure. In the last section, the results of the tracing procedure are given for a simple class of two-person variable-sum games, in numerical detail.     

Multi-parametric optimizations for power dissipation characteristics of Stockbridge dampers based on probability distribution of wind speed

Power dissipation characteristics of Stockbridge dampers (SD) is one of the important indexes in anti-vibration work of transmission line. The study focuses on the optimization of the SD's power dissipation characteristics under the effect of multi-structure parameter coupling. The aeolian vibration of overhead transmission lines is uncertain and random in stochastic dynamics. According to Strouhal formula, the relationship between the vibration frequency of transmission lines and wind speed can be found out. Based on the Weibull wind speed probability distribution, the probability density function of the transmission line conductor and damper coupling system vibration frequency is derived. The SD is considered as a typical 2-dimension of stochastic dynamical system. Based on the random process generated by the power dissipation of the SD, the characteristics of power dissipation and SD's resonant frequencies are analyzed when the multi-structure parameters of the SD are coupled. And the diagrams of the power dissipation at various frequencies are obtained.Based on the probability density function of the vibration frequency of the overhead conductor and damper, the objective function, namely the mathematical expectation of power dissipation (E(PD)), of the optimizations for the SD's power dissipation under the coupling of multiple structural parameters is proposed for the first time according to the author's knowledge. Constraint conditions of the optimizations are built by the quantization processing. The energy dissipation characteristics of the dampers can be evaluated by E(PD), and the power dissipation of SD with different coupled dual structure parameters is optimized based on the proposed method. The optimal values or the optimal value intervals of different coupled dual structure parameters are found, which may provide practical data.     

The notion of variable quantities ω in Bolzano's early works

Amid the debate over infinitesimals, Bolzano introduced the alternative notion of variable quantities ω in his 1816 work on the binomial theorem. It has often been assumed that his 1817 definition of continuity using them is practically the modern one. This paper explores Bolzano's early mathematical works and diaries to gain insight into the subtleties in his definition of ω and some of his mathematical procedures. We show that those quantities are not clearly ‘proto-Weierstrassian’ and argue that Bolzano was in the process of refinement and increasing abstraction of the idea of quantity that eventually led to the development of a theory of real numbers.     

Cálculo de la función distancia para el método Level Set usando la formulación estabilizada USFEM/Rothe

In this work we use the Unusual Stabilized Finite Element Method (USFEM) associated to Rothe's method for solving the redistancing problem in the Level Set Method. Rothe's method is used first for advancing the solution in (pseudo)time and USFEM for solving the resulting steady advective–reaction problem in each time step. Several 2D problems are solved and results compared with SUPG scheme supplemented with a nonlinear discontinuity–capturing operator.     

Solution of a system of nonstrictly hyperbolic conservation laws

In this paper we study a special case of the initial value problem for a 2×2 system of nonstrictly hyperbolic conservation laws studied by Lefloch, whose solution does not belong to the class ofL ^∞ functions always but may contain δ-measures as well: Lefloch's theory leaves open the possibility of nonuniqueness for some initial data. We give here a uniqueness criteria to select the entropy solution for the Riemann problem. We write the system in a matrix form and use a finite difference scheme of Lax to the initial value problem and obtain an explicit formula for the approximate solution. Then the solution of initial value problem is obtained as the limit of this approximate solution.     

A model of incentive contracts for just-in-time delivery

A mathematical model is used to analyze how to structure on-time delivery incentives in a contract between a buyer and a single supplier of raw materials when early shipments are forbidden. The buyer's choice of incentives takes the supplier's cost-minimizing response to incentives into account. The least cost incentive a buyer can select is specified by a probability of on-time delivery and an incentive scheme to achieve that probability. These optimal solutions are characterized without specifying the flow time distribution. A Method of selecting incentives that can help buyers improve on-time delivery performance is provided; however, the limitations of incentives are also considered. Achieving exactly 100% on-time delivery is shown to be non-optimal and only feasible under specific conditions. When management can not specify the shortage cost, their selection of a desired probability of on-time delivery allows for the determination of an imputed shortage cost.     

A smoothing SAA method for a stochastic mathematical program with complementarity constraints

A smoothing sample average approximation (SAA) method based on the log-exponential function is proposed for solving a stochastic mathematical program with complementarity constraints (SMPCC) considered by Birbil et al. (S. I. Birbil, G. Gürkan, O. Listes: Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res. 31 (2006), 739–760). It is demonstrated that, under suitable conditions, the optimal solution of the smoothed SAA problem converges almost surely to that of the true problem as the sample size tends to infinity. Moreover, under a strong second-order sufficient condition for SMPCC, the almost sure convergence of Karash-Kuhn-Tucker points of the smoothed SAA problem is established by Robinson’s stability theory. Some preliminary numerical results are reported to show the efficiency of our method.     

Solutions to the Constrained Flowshop Sequencing Problem

If the flowshop sequencing problem is constrained so that job profiles are maintained independently of other work on the shop, then a range of new problem solutions are possible. Using geometrical relationships between the cumulative process times, a slope matching method has been devised which generally provides better results than Palmer's method and Gupta's algorithm. Secondly, it has been possible to reformulate the flowshop sequencing problem in terms of the travelling salesman problem. This has enabled the performance of the slope matching, Palmer and Gupta methods to be compared against a non-heuristic solution. Finally, provided that expressing a job in terms of the slopes of the cumulative start and end times is satisfactory, this enables in n-job, M-machine flowshop to be converted into an equivalent n-job 2 machine flowshop to which the use of Johnson's method will provide optimal sequences.     

Decoding Cardano's Liber de Ludo Aleae

Written in the 16th century, Cardano's Liber de Ludo Aleae was, in its time, an advanced treatment of the probability calculus. At the same time it could be viewed as a gambling manual. Several commentators on the book have concluded that it is a mishmash of several, sometimes contradictory, results and statements written over an approximate 40-year period. In the current paper the Liber de Ludo Aleae is examined as a Renaissance text written in the intellectual milieu of humanism. A close examination of the book shows that it was heavily influenced by Aristotle's Ethics, in particular Aristotle's concept of justice. By reading the Liber de Ludo Aleae in this way, it is shown that there is an internal consistency to the work with a common thread of justice (ius) and knowledge (scientia) running through it. These themes are examined in detail. It is also argued that some of Cardano's probability calculations related to dice might have been taken from a printed version of the late medieval poem De Vetula.     

Green's Function in Some Contributions of 19th Century Mathematicians

Many questions in mathematical physics lead to a solution in terms of a harmonic function in a closed region with given continuous boundary values. This problem is known as Dirichlet's problem, whose solution is based on an existence principle—the so-called Dirichlet's principle. However, in the second half of the 19th century many mathematicians doubted the validity of Dirichlet's principle. They used direct methods in order to overcome the difficulties arising from this principle and also to find an explicit solution of the Dirichlet problem at issue. Many years before, one of these methods had been developed by Green in 1828, which consists in finding a function—called a Green's function—satisfying certain conditions and appearing in the analytical expression of the solution of the given Dirichlet problem. Helmholtz, Riemann, Lipschitz, Carl and Franz Neumann, and Betti deduced functions similar to Green's function in order to solve problems in acoustics, electrodynamics, magnetism, theory of heat, and elasticity. Copyright 2001 Academic Press.Molte questioni fisico matematiche conducono a una soluzione in termini di una funzione armonica in una regione chiusa con dati valori continui al contorno. Questo problema è noto come problema di Dirichlet, la cui soluzione si basa su un principio di esistenza, il cosiddetto principio di Dirichlet. Tuttavia, nella seconda metà del diciannovesimo secolo, molti matematici cominciarono a mettere in dubbio la validità del principio di Dirichlet. Sia per superare le difficoltà sorte da tale principio, sia per trovare una soluzione esplicita del problema di Dirichlet dato, essi presero ad adoperare metodi diretti. Molti anni prima, uno di questi metodi era stato sviluppato da Green nel 1828 e consiste nel trovare una funzione, detta funzione di Green, che soddisfa certe condizioni e mediante la quale si rappresenta analiticamente la soluzione del problema di Dirichlet in questione. Helmholtz, Riemann, Lipschitz, Carl e Franz Neumann, e Betti dedussero delle funzioni simili alla funzione di Green allo scopo di risolvere problemi di acustica, elettrodinamica, magnetismo, teoria del calore ed elasticità. Copyright 2001 Academic Press.Nombreuses questions de physique mathématique mènent à une solution en termes d'une fonction harmonique dans une région fermée avec des valeurs continus donnés sur la frontière. Ce problème est connu comme problème de Dirichlet, la solution duquel est fondée sur un principe d'existence, le principe de Dirichlet. Cependant dans la seconde moitié du dix-neuvième siècle plusieurs mathématiciens mirent en doute la validité du principe de Dirichlet. Alors ils employèrent des méthodes directes soit pour surmonter le difficultés nées de ce principe, soit pour déduire une solution explicite du problème de Dirichlet en question. Avant plusieurs annèes une de ces méthodes a été développée par Green en 1828 et consiste à trouver une fonction, dite fonction de Green, qui satisfait certaines conditions et moyennant laquelle on représente analytiquement la solution du problème de Dirichlet donné. Helmholtz, Riemann, Lipschitz, Carl et Franz Neumann, et Betti déduisirent des fonctions semblables à la fonction de Green pour résoudre de problèmes d'acoustique, électrodynamique, magnétisme, théorie de la chaleur et élasticité. Copyright 2001 Academic Press.MSC 1991 subject classifications: 01A55, 31-03.     

A new method of solving nonlinear mathematical programming problems involving r-invex functions

A new approach to a solution of a nonlinear constrained mathematical programming problem involving r-invex functions with respect to the same function η is introduced. An η-approximated problem associated with an original nonlinear mathematical programming problem is presented that involves η-approximated functions constituting the original problem. The equivalence between optima points for the original mathematical programming problem and its η-approximated optimization problem is established under r-invexity assumption.     

Mathematics and Dialectics in the Soviet Union: The Pre-Stalin Period

During the 1920s, Soviet Marxist theorists paid less attention to developments in mathematics in their own country than to various manifestations of “mathematical idealism” in the West. Their criticism concentrated on set-theoretical studies, the theory of probability, mathematical logic, and the foundations of mathematics. Because of their disunity, the Marxist scholars did not present an obstacle to the work of mathematicians, dominated by the much-heralded Moscow school of mathematics, strong in the theory of functions of a real variable and its applications to topology and several other branches of mathematics. The end of the decade was marked by the beginning of Stalinist pressure to establish full ideological control over all branches of mathematics.Copyright 1999 Academic Press.MSC 1991 subject classifications: 01A60; 01A72; 01A74; 01A80.