On some approximately balanced combinatorial cooperative games

A model of taxation for cooperativen-person games is introduced where proper coalitions Are taxed proportionally to their value. Games with non-empty core under taxation at rate-balanced. Sharp bounds on in matching games (not necessarily bipartite) graphs are estabLished. Upper and lower bounds on the smallest in bin packing games are derived and euclidean random TSP games are seen to be, with high probability,-balanced for0.06.     

Bin packing games

We consider bin packing games introduced by Faigle and Kern (1993) and we restrict ourselves to the subclass of games for which all bins have unit capacity and all items are larger than 1/3. We adopt the taxation model of Faigle and Kern and we prove that for a tax-rate of = sk_7/1 the -core is always non empty. The bound is sharp, since for every < sk_7/1 there exist instances of the bin packing game within our sublass with an empty -core.     

Almost Stationary ∈-Equilibria in Zero-Sum Stochastic Games

We show the existence of almost stationary -equilibria, for all > 0, in zero-sum stochastic games with finite state and action spaces. These are -equilibria with the property that, if neither player deviates, then stationary strategies are played forever with probability almost 1. The proof is based on the construction of specific stationary strategy pairs, with corresponding rewards equal to the value, which can be supplemented with history-dependent -optimal strategies, with small > 0, in order to obtain almost stationary -equilibria.     

On stochastic games,II

In this paper, we consider positive stochastic games, when the state and action spaces are all infinite. We prove that, under certain conditions, the positive stochastic game has a value and that the maximizing player has an -optimal stationary strategy and the minimizing player has an optimal stationary strategy.The authors are grateful to Professor David Blackwell and the referee for some useful comments.     

On the set of proper equilibria of a bimatrix game

In this paper it is proved that the set of proper equilibria of a bimatrix game is the finite union of polytopes. To that purpose we split up the strategy space of each player into a finite number of equivalence classes and consider for a given >0 the set of all -proper pairs within the cartesian product of two equivalence classes. If this set is non-empty, its closure is a polytope. By considering this polytope as goes to zero, we obtain a (Myerson) set of proper equilibria. A Myerson set appears to be a polytope.     

Hermitian K-theory on a Theorem of Giffen

Let be an exact category with duality. In [1] a category () was introduced and the authors asserted that the loop space of the topological realization of () is homotopy equivalent to Karoubis U-theory space of when = (R), the category of finitely generated projective modules over a ring R with an involution if 2 is invertible in R. Unfortunately, their proof contains a mistake. We present a different proof which avoids their argument.Mathematics Subject Classifications (1991): 19DO6, 19G38, 11E70.     

Markov Games with Several Ergodic Classes

We consider Markov games of the general form characterized by the property that, for all stationary strategies of players, the set of game states is partitioned into several ergodic sets and a transient set, which may vary depending on the strategies of players. As a criterion, we choose the mean payoff of the first player per unit time. It is proved that the general Markov game with a finite set of states and decisions of both players has a value, and both players have -optimal stationary strategies. The correctness of this statement is demonstrated on the well-known Blackwell's example (Big Match).     

Über Extremalpunkte des numerischen Wertebereichs eines linearen Operators

For a bounded linear operator T in a Hilbert space denote by (T) the set of the extreme points of its numerical range W(T), and by K(T) the subset of the points of (T) which lie on the boundary of a disc being a spectral set for T in the sense of J. von Neumann. Each corner of W(T) belongs to K(T). This implies: K(T) is dense in (T) if T is compact and the convex hull of its spectrum contains W(T). If Re T0 and o (T) then a necessary and sufficient condition is given that O is a eigenvalue of T. This is applied to show that W(T) (T) is a subset of the point spectrum of T for a class of operators containing the hyponormal operators.     

Perturbation of the poles of the scattering matrix under variation of the boundary condition

The behavior of the poles z_n(), n=1,2,... of the scattering matrix of the operatorl u=–u(x), x , (u/n)+(x)u|=0 as 0 is considered. It is proved that |z_n()–z_n|=0(^(1/2)qn), where q_n is the order of the pole of the scattering matrix for the operator ₀u=–u, u/=0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 117, pp. 183–191, 1981.     

Functions with a finite dirichlet integral in a domain with cusp points on the boundary

Let be a domain in ⁿ, n >2, the boundary of which has a cusp point, pointing inside or outside the domain. The purpose of the paper is to characterize the traces on of the elements of the space H¹() of functions with a finite Dirichlet integral. As a consequence one establishes the existence of a linear continuous extension operator H¹ () H¹(ⁿ) under the presence of an interior cusp point on . Theorems on domains with cusps are proved with the aid of results on cylindrical domains. In the space of functions with a finite Dirichlet integral in the exterior or the interior of the cylinder one introduces the norm, depending on a small parameter and generating a norm of the trace on as an element of the quotient space. The latter is placed in correspondence with an explicitly described norm of functions on the boundary, uniformly equivalent relative to . One constructs an operator of extension of functions from the exterior of the cylinder to Rⁿ, preserving H¹, whose norm is uniformly bounded relative to . For the optimal operator of extension from the inside of the cylinder one finds the asymptotic behavior of the norm as 0. From these results there follow similar theorems on functions with a finite Dirichlet integral inside and outside a thin closed tube (of width ).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 126, pp. 117–137, 1983.     

On a Model Problem for the Orr–Sommerfeld Equation with Linear Profile

A model spectral problem of the form -i)y+xy= y on the finite interval [-1,1] with the Dirichlet boundary conditions is considered. Here is the spectral parameter and is positive. The behavior of the spectrum of this problem as 0 is completely investigated. The limit curves are found to which the eigenvalues concentrate and the counting eigenvalue functions along these curves are obtained.     

Construction of ɛ-nets

LetS be a set ofn points in the plane and let be a real number, 0<<1. We give a deterministic algorithm, which in timeO(n ^–2 log(1/)+ ^–8) (resp.O(n ^–2 log(1/)+ ^–10) constructs an-netNS of sizeO((1/) (log(1/))²) for intersections ofS with double wedges (resp. triangles); this means that any double wedge (resp. triangle) containing more thatn points ofS contains a point ofN. This givesO(n logn) deterministic preprocessing for the simplex range-counting algorithm of Haussler and Welzl [HW] (in the plane).We also prove that given a setL ofn lines in the plane, we can cut the plane intoO( ^–2) triangles in such a way that no triangle is intersected by more thann lines ofL. We give a deterministic algorithm for this with running timeO(n ^–2 log(1/)). This has numerous applications in various computational geometry problems.     

Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space

This paper considers discounted noncooperative stochastic games with uncountable state space and compact metric action spaces. We assume that the transition law is absolutely continuous with respect to some probability measure defined on the state space. We prove, under certain additional continuity and integrability conditions, that such games have -equilibrium stationary strategies for each >0. To prove this fact, we provide a method for approximating the original game by a sequence of finite or countable state games. The main result of this paper answers partially a question raised by Parthasarathy in Ref. 1.     

Die ɛ-Störung linearer und quadratischer Optimierungsaufgaben und ihre Anwendung auf das Hildreth-Verfahren

Zusammenfassung Durch eine -Störung in der Diagonalen der quadratischen Form kann man eine lineare oder quadratisch semidefinite Optimierungsaufgabe zu einer streng definiten quadratischen Aufgabe machen, so daß Lösungsverfahren, die die Formmatrix als nichtsingulär voraussetzen müssen, anwendbar werden. Bekanntlich konvergiert die Lösungx der -gestörten Aufgabe für 0 gegen den Lösungsvektorx ^m von minimalem Betrag der ursprünglichen Aufgabe. Wir zeigen darüber hinaus, daß im linearen Fall immer und im eigentlich quadratischen in gewissen Fällen schon für 0<<* die beiden Lösungenx undx ^m übereinstimmen. Im linearen Fall ist die obere Grenze * durch die Lösung eines linearen Ungleichungssystems gegeben.Im zweiten Abschnitt wenden wir dasHildreth-Verfahren mittels der -Störung auf lineare und quadratisch semidefinite Aufgaben an, diskutieren Konvergenz- und Genauigkeitsfragen und kommen zu dem Schluß, daß man in der Praxis sowohl bei Rechnung von Hand als auch bei maschineller Rechnung zu befriedigenden Ergebnissen kommt.

---

Summary Linear and quadratic semidefinite programming problems may be transformed into strongly definite quadratic problems by means of an -perturbation of the quadratic form so that procedures which presuppose the matrix of the form to be nonsingular, may be applied. As is well known, the solutionx of the -perturbated problem converges to the solutionx ^m of minimal length of the original problem as 0. We show that always in the linear case and in the quadratic case under certain circumstances, both solutionsx andx ^m are equal if 0 <<*. In the linear case, the upper limit * is given by the solution of a system of linear inequalities.In the second part of this paper we apply the method ofHildreth to linear and quadratic semidefinite programming problems by the -perturbation. We discuss questions of convergence and exactness, and conclude that in practice calculation by hand as well as by computer leads to satisfying results.

---

---

Der Verfasser ist Herrn Prof. Dr.W. Vogel, Bonn, für einen Hinweis zu Dank verpflichtet.

---

Vorgel. v.:H. P. Künzi     

An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

Errors in approximate solutions of Cauchy's problem for a first-order quasilinear equation

The proximity is investigated of the solution of Cauchy's problem for the equation u _t +((u))_x= u _xx ((u) > 0) to the solution of Cauchy's problem for the equation u_t+ ((u))_x= 0, when the solution of the latter problem has a finite number of lines of discontinuity in the strip 0 t T. It is proved that, everywhere outside a fixed neighborhood of the lines of discontinuity, we have |u–u| C, where the constant C is independent of. Similar inequalities are derived for the first derivatives of u–u.Translated from Matematicheskie Zametki, Vol. 8, No. 3, pp. 309–320, September, 1970.In conclusion we express our gratitude to L. A. Chudov for his valuable advice concerning this work.     

Controllability in Dimensions One and Two of Sobolev-Type Equations in Banach Spaces

We establish conditions necessary for -controllability in dimension one of first-order singular linear differential equation in Banach spaces. This result generalizes similar results for regular equations. For this class of equations, we show that the notion of -controllability in dimension two is more natural, and moreover, analogous necessary conditions are sufficient in the case of dimension two. Using an abstract approach, we derive sufficient conditions for the -controllability in dimension two of the Cauchy--Dirichlet problem for the Barenblatt--Zheltov--Kochina equation.     

Zur krümmungsverwandtschaft von zwangläufen in affinen ck — Ebenen II

In part I we have studied a map of osculating elements of an affine Cayley-Klein (CK-) plane into the Lie algebra A₄(²) of the aequiform transformations A₄(²) of the given plane A₂(, ²). If we use the real projective space P₃() over A₄(²) each osculating element defines a straight line in P₃(). We now give a one parameter motion in A₄(²) and study second order properties and their analogon in the Lie algebra and P₃(), respectively. We show that the wellknown relationship between the points of the moving frame and the osculating circles of the point paths in the fixed frame may be interpreted as part of a quadratic map of certain straight Lines of P₃(). An analogous result holds for the curvature of pairs of envelopes; the mapV induced in P₃() than is contained in a cubic relationship of straight lines.

---

---

Herrn Professor Oswal Giering zum 60. Geburtstag gewidmet     

A Five-term Exact Sequence for Opext of Crossed Modules in Lie Algebras

Extensions of crossed modules in Lie algebras with abelian kernel are studied, particularly backward and forward induced extensions and related properties. The set Opext((U, Q, ), (R, K, )) of congruence classes of extensions of (R, K, ) by (U, Q, ) is endowed with a K-vector space structure. This K-vector space appears in a five-term natural and exact sequence associated with an extension of crossed modules.2000 Mathematics Subject Classification: 17B56, 17B99, 18G99     

A certain periodic control problem for differential equations with impulses in the space of bounded numerical sequences

One considers the differential equation dx/dt=f(t, x) with the impulse action ¦_t=t_i=H_i(t_i,x) in the space of bounded numerical sequences, where f(t, x), H_i(t, x) are T-periodic, countable-dimensional vector-valued functions, is a positive parameter. One gives conditions for the existence of a control (₁,₂) such that the solution of the equation dx/dt=f(t, x)–₁ with impulse action x¦_t=t_i=H_i(t_i,x)–₂ assuming for t= the value x=x₀, be T-periodic.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 2, pp. 271–275, February, 1990.