Games with finite resources

Games with Finite Resources as defined by Gale (1957) are two-person zero-sum N-stage games in which each player has N resources and may use each resource once and only once in the N stages. Gale's theorem on these games is generalized in several directions. First the payoff is allowed to be any symmetric function of the stage payoffs. Second, the players are allowed some latitude in choosing which game is being played. Applications are given to some open questions in the area of Inspection Games. Finally the payoff is allowed to be random, thus incorporating a result of Ross (1972) on Goofspiel. Application is made to a game-theoretic version of the Generalized House Selling Problem. Received August 1999/revised version March 2000     

Games of timing related to distribution of resources

The paper considers a class of zero-sum, two-person games which are related to distribution of resources. Each of the players is in possession of an amount of resource, to be distributed by him in the time interval [0, 1] according to an arbitrary measure. The payoff function is defined in such a manner that the games are a generalization of the so-called silent, nondiscrete duels. It is proven that these games have a value, and the optimal strategies for the players are found. The results of the paper bring to light new, essential elements, common to almost all games of timing on [0, 1].     

Games of timing with resources of mixed type

The paper considers a game of timing which is closely related to the so-called duels. This is a game connected with the distribution of resources by two players. Each of the players is in possession of some amount of resource to be distributed by him in the time interval [0, 1]. In his behavior, Player 1 is restricted by the necessity of taking all of his resources at a single point, while Player 2 has no restrictions. For the payoff function, defined as for duels, the game is solved; explicit formulas on the value of the game and the optimal strategies for the players are found.     

The discrete facility location problem with balanced allocation of customers

We consider a discrete facility location problem where the difference between the maximum and minimum number of customers allocated to every plant has to be balanced. Two different Integer Programming formulations are built, and several families of valid inequalities for these formulations are developed. Preprocessing techniques which allow to reduce the size of the largest formulation, based on the upper bound obtained by means of an ad hoc heuristic solution, are also incorporated. Since the number of available valid inequalities for this formulation is exponential, a branch-and-cut algorithm is designed where the most violated inequalities are separated at every node of the branching tree. Both formulations, with and without the improvements, are tested in a computational framework in order to discriminate the most promising solution methods. Difficult instances with up to 50 potential plants and 100 customers, and largest easy instances, can be solved in one CPU hour.     

Global behavior of a discrete haematopoiesis model with several delays

In this paper, we study the difference equation:

     

Incremental allocation of a discrete and convex resource to concave activities

The problem considered is that of the allocation of a given quantity of a discrete resource to activities described by concave return functions. The resource-consumption corresponding to each allocation is described by a convex function of the quantity allocated. An incremental solution algorithm is given, which specializes to the algorithm of Fox if the resource is linear, and to an algorithm of Katoh, Ibaraki and Mine if the return functions are linear.     

Basin-wide cooperative water resources allocation

The Cooperative Water Allocation Model (CWAM) is designed within a general mathematical programming framework for modeling equitable and efficient water allocation among competing users at the basin level and applied to a large-scale water allocation problem in the South Saskatchewan River Basin located in southern Alberta, Canada. This comprehensive model consists of two main steps: initial water rights allocation and subsequent water and net benefits reallocation. Two mathematical programming approaches, called the priority-based maximal multiperiod network flow (PMMNF) method and the lexicographic minimax water shortage ratios (LMWSR) technique, are developed for use in the first step. Cooperative game theoretic approaches are utilized to investigate how the net benefits can be fairly reallocated to achieve optimal economic reallocation of water resources in the second step. The application of this methodology to the South Saskatchewan River Basin shows that CWAM can be utilized as a tool for promoting the understanding and cooperation of water users to achieve maximum welfare in a river basin and minimize the potential damage caused by water shortages, through water rights allocation, and water and net benefit transfers among water users under a regulated water market or administrative allocation mechanism.     

Orthogonal polynomials of several discrete variables associated with negative polynomial distribution

A system of orthogonal polynomials of several discrete variables associated with the negative polynomial distribution is constructed and analyzed. The explicit form of the polynomials and the generating function are obtained.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 65, pp. 46–51, 1988.     

On asympotic behavior of solutions to several classes of discrete dynamical systems

In this paper, a new complete and simplified proof for the Husainov-Nikiforova Theorem is given. Then this theorem is generalized to the case where the coefficients may have different signs as well as nonlinear systems. By these results, the robust stability and the bound for robustness for high-order interval discrete dynamical systems are studied, which can be applied to designing stable discrete control system as well as stabilizing a given unstable control system.     

The Steiner ratio of several discrete metric spaces

Steiner's Problem is the “Problem of shortest connectivity”, that means, given a finite set of points in a metric space (X,ρ), search for a network interconnecting these points with minimal length. This shortest network must be a tree and is called a Steiner Minimal Tree (SMT). It may contain vertices different from the points which are to be connected. Such points are called Steiner points. If we do not allow Steiner points, that means, we only connect certain pairs of the given points, we get a tree which is called a Minimum Spanning Tree (MST). Steiner's Problem is very hard as well in combinatorial as in computational sense, but, on the other hand, the determination of an MST is simple. Consequently, we are interested in the greatest lower bound for the ratio between the lengths of these both trees:

which is called the Steiner ratio (of (X,ρ)). We look for estimates and exact values for the Steiner ratio in several discrete metric spaces. Particularly, we determine the Steiner ratio for spaces of words, and we estimate the Steiner ratio for specific graphs.     

Location of a discrete resource and its allocation according to a fractional objective

The problem considered is that of the location of a discrete resource and its allocation to activities with concave return functions in such a way as to maximize the ratio of ‘return’ to ‘cost’, the total cost being the sum of a fixed cost and linearly variable costs. It is assumed that each resource has an effectiveness of 0 or 1 against each activity. It is demonstrated that an optimal solution can be determined by the rounding to integers of the solution of an associated problem in continuous variables. Solutions with objective values arbitrarily close to the optimal value can be generated by resource-wise optimizations. An upper bound of the number of non-zero integer allocations in an optimal solution is derived.     

Application of functional analysis to models of efficient allocation of economic resources

The present paper studies existence and characterization of efficient paths in infinite-horizon economic growth models: the method used is based on techniques of nonlinear functional analysis on Hilbert spaces developed earlier by Chichilnisky. Necessary and sufficient conditions are given for the existence of positive competitive price systems in which the efficient programs maximize present value and intertemporal profit. Approximation of these competitive price systems by strictly positive ones with similar properties is studied. A complete characterization is also given of a class of welfare functions (nonlinear operators defined on consumption paths) for continuity in a weightedl ₂-norm.This research was supported by the National Science Foundation, Grant No. GS-18174. The authors thank K. Arrow, A. Gleason, F. Hahn, A. Majda, S. Marglin, T. Muench, L. Tartar, S. Karamardian, and the referees for helpful comments and suggestions.     

On max-min linear inequalities and Coalitional Resource Games with sharable resources

In a Coalitional Resource Game (CRG for brief), agents form coalitions to pool their resources in order to achieve certain goals, requiring the expenditure of these resources. A particular coalition is said to be successful, if the common resources of its members enable to achieve a set of goals that satisfies all members of the coalition. It is known that when resources are consumable it is NP-complete to decide whether a given coalition is successful. In this paper, we show a connection of CRGs with sharable resources and max-min linear systems of inequalities. This correspondence leads to polynomial algorithms for checking whether a given CRG admits a successful coalition and for several other problems whose counterparts for CRGs with consumable resources are hard. On the other hand, we prove that some problems concerning the structure of successful coalitions are hard also in the case of sharable resources.     

Multi-objective optimal allocation of resources to increase the seismic reliability of highways

To reduce the risk of disruption of lifeline systems during the emergency following an earthquake (or any other disaster) preventive interventions on the existing concerned facilities are necessary, but often hindered by the limitation of the available economic resources. In this paper, procedures for the optimal allocation of these resources are presented, with special reference to the case of road networks. It is assumed that the bridges are the only vulnerable elements, and an example of application on a specific network is developed in detail. In the first part of the paper, optimization with respect to several alternative objective functions is dealt with, while in the second part multi-objective optimization is tackled. The results obtained are compared and discussed.Dedicated to Haresh Shah on the occasion of his retirement from Stanford University.     

On a solution of the discrete resource allocation game

A discrete zero-sum two-person game of breaking attacks at defended posts (a Blotto game) is considered. An algorithm for finding a game solution in mixed strategies is described and generalized to games with budget constraints. In particular cases, explicit formulas for the value of the game and optimal strategies are obtained.     

Some integral and discrete inequalities in several independent variables

We improve the constants in some integral and discrete inequalities in n independent variables which are due to Agarwal and Sheng [1] and Agarwal and Pang [2].     

On a new system of discrete distributions and characterizations of several discrete distributions by equality of distributions

This paper deals with a new system of discrete distributions. It also gives several characterizations of the Waring (and hence the Yule) distribution (and its truncated versions), the super-Poisson, the discrete uniform and other discrete distributions by using this system and other such systems existing in the literature, and linear regression. Continuous analogues of the above results are also briefly discussed.     

Patient flow-based allocation of inpatient resources: A case study

The paper considers the allocation of inpatient resources such as beds, operating theatres and nursing staff to specialties within a hospital setting. It describes an allocation procedure that takes patient flows as its starting point and enables an evaluation of combined impacts on the different resources involved. The paper is written in the format of a case study, dealing with a hospital that had serious problems with the utilization of beds and was faced with many admission-stops. However, the method can be used to a wide range of resource management problems in hospitals and can contribute to improving flexibility in the use of hospital resources.     

Efficient methods for the allocation of resources in project networks

Summary The paper surveys available algorithms for resource allocation in project networks that appear computationally efficient. Three cases of resource allocation are considered: time-cost tradeoff, leveling of resources, and constrained resources. Practical analytical methods that guarantee optimal solutions exist only for the time-cost tradeoff problem. Heuristic procedures for problems with constraints on resources do not guarantee but come close to optimal solutions. Relative advantages of heuristic algorithms cannot be assessed in the absence of large scale empirical comparisons.

---

Zusammenfassung Die vorliegende Arbeit gibt einen Überblick über Algorithmen für die Verteilung der Ressourcen in Netzwerk-Projekten, die rechnerisch effizient erscheinen. Es werden 3 Fälle der Verteilung von Ressourcen betrachtet: time-cost tradeoff, leveling of resources und constrained resources. Praktische analytische Methoden, die optimale Lösungen garantieren, existieren nur für das time-cost tradeoff Problem. Heuristische Verfahren für Probleme mit Beschränkungen garantieren zwar keine optimalen Lösungen, führen aber eng an sie heran. Die relativen Vorteile, die durch heuristische Programme erzielt werden, können beim Fehlen empirischer Vergleichsmöglichkeiten großen Stils nicht abgeschätzt werden.

---

---

Vorgel. v.:G. Tintner.