On the balancedness of multiple machine sequencing games

This paper takes a game theoretical approach to sequencing situations with m parallel and identical machines. We show that in a cooperative environment cooperative m-sequencing games, which involve n players, give rise to m-machine games, which involve m players. Here, n corresponds to the number of jobs in an m-sequencing situation, and m corresponds to the number of machines in the same m-sequencing situation. We prove that an m-sequencing game is balanced if and only if the corresponding m-machine game is balanced. Furthermore, it is shown that m-sequencing games are balanced if m∈{1,2}. Finally, if m⩾3, balancedness is established for two special classes of m-sequencing games. Furthermore, we consider a special class of m-sequencing situations in a noncooperative setting and show that a transfer payments scheme exists that is both incentive compatible and budget balanced.     

Individual and group stability in neutral restrictions of hedonic games

We consider a class of coalition formation games called hedonic games, i.e., games in which the utility of a player is completely determined by the coalition that the player belongs to. We first define the class of subset-additive hedonic games and show that they have the same representation power as the class of hedonic games. We then define a restriction of subset-additive hedonic games that we call subset-neutral hedonic games and generalize a result by Bogomolnaia and Jackson (2002) by showing the existence of a Nash stable partition and an individually stable partition in such games. We also consider neutrally anonymous hedonic games and show that they form a subclass of the subset-additive hedonic games. Finally, we show the existence of a core stable partition that is also individually stable in neutrally anonymous hedonic games by exhibiting an algorithm to compute such a partition.     

A cooperative location game based on the 1-center location problem

In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We call these games the Minimum Radius Location Games (MRLG).We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ?_p metric spaces defined over R^d.     

Population equilibrium with support in evolutionary matrix games

In this paper we consider symmetric bimatrix games [A, A^T]. We use a matrix operator s(A), defined as the sum of the cofactors of the given matrix A, for finding the population equilibrium and its fitness in evolutionarily matrix games with all supported strategies, and to complete Bishop-Cannings Theorem.     

“Eventually revealing” repeated games with incomplete information

We consider two person zero-sum games with lack of information on one side given by two 2×2-matricesA ¹ andA ² for which val [pA ¹ +(1–p)A ²]=p valA ¹+(1–p) valA ². Using the approach developed by Heuer [1991] we give the explicit solution for all such finitely repeated games. It provides a supplement to the recent results on the limiting behavior of the value for these games (see Mertens, Sorin and Zamir [1990], De Meyer [1989], [1993]).We are grateful to the referees and the editor in charge for helpful and instructive comments and especially for the printed materials on the subject.     

k-Sided permutation games and multiprices of equilibrium

Here we generalize the permutation games due to Tijs, Parthasarathy, Potters and Rajendra Prasad, to k-sided permutation games. We study the existence of the core and we relate them with the k-sided assignment games just introduced and studied by Quint [Games Econ. Behav. 3 (1991) 487].     

On unit power integral bases of $$\mathbb{Z}\left[ {\sqrt[4]{m}} \right]$$

Let m ≠ 0 be an integer which is not a perfect square and consider number fields of the form \(\mathbb{Q}\left[ {\sqrt[4]{m}} \right]\). We characterize all orders of the form \(\mathbb{Z}\left[ {\sqrt[4]{m}} \right]\) which admit a unit power integral basis, i.e., there exists a unit ε such that 1, ε, ε ² and ε ³ is an integral basis of \(\mathbb{Z}\left[ {\sqrt[4]{m}} \right]\).     

Minimizing weighted earliness–tardiness and due-date cost with unit processing-time jobs

The classical single-machine scheduling and due-date assignment problem of Panwalker et al. [Panwalker, S.S., Smith, M.L., Seidmann, A., 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30(2) (1982) 391–399] is the following: All n jobs share a common due-date, which is to be determined. Jobs completed prior to or after the due-date are penalized according to a cost function which is linear and job-independent. The objective is to minimize the total earliness–tardiness and due-date cost. We study a generalized version of this problem in which: (i) the earliness and tardiness costs are allowed to be job dependent and asymmetric and (ii) jobs are processed on parallel identical machines. We focus on the case of unit processing-time jobs. The problem is shown to be solved in polynomial (O(n⁴)) time. Then we study the special case with no due-date cost (a classical problem known in the literature as TWET). We introduce an O(n³) solution for this case. Finally, we study the minmax version of the problem, (i.e., the objective is to minimize the largest cost incurred by any of the jobs), which is shown to be solved in polynomial time as well.     

New construction of complex manifold via conifold transition

For a generic anti-canonical hypersurface in each smooth toric Fano 4-fold with rank 2 Picard group, we prove there exist three isolated rational curves in it. Moreover, for all these 4-folds except one, the contractions of generic anti-canonical hypersurfaces along the three rational curves can be deformed to smooth threefolds which is diffeomorphic to connected sums of S3 ×S3 . In this manner, we obtain complex structures with trivial canonical bundles on some connected sums of S3 × S3 . This construction is an analogue of that made by Friedman [On threefolds with trivial canonical bundle. In: Complex Geometry and Lie Theory, volume 53 of Proc. Sympos. Pure Math., Amer. Math. Soc., Providence, RI, 1991, 103-134], Lu and Tian [Complex structures on connected sums of S3 × S3 . In: Manifolds and Geometry, Pisa, 1993, 284-293] who used only quintics in P4 .     

The canonical function game

The canonical function game is a game of length ω ₁ introduced by W. Hugh Woodin which falls inside a class of games known as Neeman games. Using large cardinals, we show that it is possible to force that the game is not determined. We also discuss the relationship between this result and Σ² ₂ absoluteness, cardinality spectra and Π₂ maximality for H(ω ₂) relative to the Continuum Hypothesis.     

Uniqueness of equilibrium points in bimatrix games

Bimatrix games are constructed having a given pair (x, y) as the unique equilibrium point within the class of all mixed strategy pairs whose nonzero components are the same as (resp., among) those of (x, y). In each case, necessary and sufficient conditions on (x, y) for the existence of such a game are obtained. All games having the first property are constructed. The work extends and complements recent (separate) works ofMillham [1972],Raghavan [1970] and the author. The methods and results are valid in the context of any ordered field.     

The diameter game

A large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given — usually monotone — property. Here we introduce the d‐diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2‐diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n^1/8/(lnn)^3/8. In addition, we investigate d‐diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Modified form of binary and ternary 3-point subdivision schemes

Binary 3-point scheme, developed by Hormann and Sabin [Hormann, K. and Sabin, Malcolm A., 2008, A family of subdivision schemes with cubic precision, Computer Aided Geometric Design, 25, 41-52], has been modified by introducing a tension parameter which generates a family of C¹ limiting curves for certain range of tension parameter. Ternary 3-point scheme, introduced by Siddiqi and Rehan [Siddiqi, Shahid S. and Rehan, K., 2009, A ternary three point scheme for curve designing, International Journal of Computer Mathematics, In Press, DOI: 10.1080/00207160802428220], has also been modified by introducing a tension parameter which generates family of C¹ and C² limiting curves for certain range of tension parameter. Laurent polynomial method is used to investigate the continuity of the subdivision schemes. The performance of modified schemes has been demonstrated by considering different examples along with its comparison with the established subdivision schemes.     

Dimension of complete simple games with minimum

Weighted majority games have the property that players are totally ordered by the desirability relation (introduced by Isbell in [J.R. Isbell, A class of majority games, Quarterly Journal of Mathematics, 7 (1956) 183–187]) because weights induce it. Games for which this relation is total are called complete simple games. Taylor and Zwicker proved in [A.D. Taylor, W.S. Zwicker, Weighted voting, multicameral representation, and power, Games and Economic Behavior 5 (1993) 170–181] that every simple game (or monotonic finite hypergraph) can be represented by an intersection of weighted majority games and consider the dimension of a game as the needed minimum number of them to get it. They provide the existence of non-complete simple games of every dimension and left open the problem for complete simple games.     

Condition-Sensitive Computation of Approximate Fixed Points

Let || || be a metric on [0, 1]ⁿ. Given is a continuous function ƒ: [0, 1]ⁿ → [0, 1]ⁿ presented as a black box that on input x outputs ƒ(x). Given also is natural number p. We are required to compute an approximate fixed point of ƒ, i.e., a point x in [0, 1]ⁿ such that ||ƒ(x), x|| ≤ 2^−p. For n ≥ 3, Hirsch, Papadimitriou, and Vavasis (1989, J. Complexity5, 379-416) show a deterministic lower bound of Ω((2^pM)^{n − 2}) for the problem, where M is the Lipschitz constant of the auxiliary function ƒ(x) − x. The exponential nature of this lower bound prompts us to seek conditions under which efficient algorithms exist, or more generally, seek efficient algorithms that are condition-sensitive. In this paper, we address this issue by defining a notion of condition number for the problem and presenting a simple condition-sensitive algorithm.     

On a conjecture by Ghahramani-Lau and related problems concerning topological centres

Let A be a Banach algebra, and consider A^** equipped with the first Arens product. We establish a general criterion which ensures that A is left strongly Arens irregular, i.e., the first topological centre of A^** is reduced to A itself. Using this criterion, we prove that for a very large class of locally compact groups, Ghahramani-Lau's conjecture (cf. [Lau 94] and [Gha-Lau 95]) stating the left strong Arens irregularity of the measure algebra M(G), holds true. (Our methods obviously yield as well the right strong Arens irregularity in the situation considered.)Furthermore, the same condition used above implies that every linear left A^**-module homomorphism on A^* is automatically bounded and w^*-continuous. We finally show that our criterion also yields a partial answer to a question raised by Lau-Ülger (Trans. Amer. Math. Soc. 348 (3) (1996) 1191) on the topological centre of the algebra (A^*⊙A)^*, for A having a right approximate identity bounded by 1.     

Games with Ordered Outcomes

We present a brief review of the most important concepts and results concerning games in which the goal structure is formalized by binary relations called preference relations. The main part of the work is devoted to games with ordered outcomes, i.e., game-theoretic models in which preference relations of players are given by partial orders on the set of outcomes. We discuss both antagonistic games and n-person games with ordered outcomes. Optimal solutions in games with ordered outcomes are strategies of players, situations, or outcomes of the game. In the paper, we consider noncooperative and certain cooperative solutions. Special attention is paid to an extension of the order on the set of probabilistic measures since this question is substantial for constructing the mixed extension of the game with ordered outcomes. The review covers works published from 1953 until now.     

Aggregate monotonic stable single-valued solutions for cooperative games

This article considers single-valued solutions of transferable utility cooperative games that satisfy core selection and aggregate monotonicity, defined either on the set of all games, G ^N , or on the set of essential games, E ^N (those with a non-empty imputation set). The main result is that for an arbitrary set of players, core selection and aggregate monotonicity are compatible with individual rationality, the dummy player property and symmetry for single-valued solutions defined on both G ^N and E ^N . This result solves an open question in the literature (see for example Young et?al. Water Resour Res 18:463?C475, 1982).     

On equilibria in finite games

We are concerned with Nash equilibrium points forn-person games. It is proved that, given any real algebraic numberα, there exists a 3-person game with rational data which has a unique equilibrium point andα is the equilibrium payoff for some player. We also present a method which allows us to reduce an arbitraryn-person game to a 3-person one, so that a number of questions about generaln-person games can be reduced to consideration of the special 3-person case. Finally, a completely mixed game, where the equilibrium set is a manifold of dimension one, is constructed.