In the article E.R. Gafarov, A.A. Lazarev, F. Werner, Single machine scheduling problems with financial resource constraints: Some complexity results and properties, Mathematical Social Sciences, 62 (2011), 7–13, the following mistake is found in Section 3.2, where the authors consider the problem denoted as 1|NR, dj = d, gj = g| Tj and claim that it is NP-hard. In the proof, a reduction from the Partition Problem was used which is not polynomial, since M exponentially depends on n. However, it is not difficult to correct this proof. The main idea of using Mn−i+1 was that the processing time of a job belongs to a pair with the smallest number being greater than the total sum of the processing times of all jobs from the pairs with larger numbers, e.g., for the job V2: p2 ≫ n i=2(p2i−1 + p2i). Instead of using p2i = Mn−i+1, where M = (n bj)n (see the definition of the instance given in (3) on page 11), we can consider, e.g., p2i = 2n • 2n−i+1M, where M = (n bj). In this case, the reduction will be polynomial in the input length, if we suppose that all digits used are coded in a binary system with approximately 2n zero–one symbols per digit.
This note shows that the egalitarian Dutta and Ray (1989) solution for transferable utility games is self-antidual on the class of exact partition games. By applying a careful antiduality analysis, we derive several new axiomatic characterizations. Moreover, we point out an error in earlier work on antiduality and repair and strengthen several related characterizations on the class of convex games.
This paper analyzes bankruptcy games with nontransferable utility as a generalization of bankruptcy games with monetary payoffs. Following the game theoretic approach to NTU-bankruptcy problems, we study some appropriate properties and the core of NTU-bankruptcy games. Generalizing the core cover and the reasonable set to the class of NTU-games, we show that NTU-bankruptcy games are compromise stable and reasonable stable. Moreover, we derive a necessary and sufficient condition for an NTU-bankruptcy rule to be game theoretic.
In this article, the fairdivision problem for two participants in the presence of both divisible and indivisibleitems is considered. Three interrelated modifications of the notion of fairdivision–profitably, uniformly and equitably fairdivisions–were introduced. Computationally efficient algorithm for finding all of them was designed. The algorithm includes repetitive solutions of integer knapsack-type problems as its essential steps. The necessary and sufficient conditions of the existence of proportional and equitable division were found. The statements of the article are illustrated by various examples.
In the bilateral assignment problem, source a holds the amount ra of resource of type a, while sink i must receive the total amount xi of the various resources. We look for assignment rules meeting the powerful separability property known as Consistency: “every subassignment of a fair assignment is fair”. They are essentially those rules selecting the feasible flow minimizing the sum ∑i,aW(yia), where W is smooth and strictly convex.
This paper seeks answers to two questions. First, if a greater social activity of an individual enhances oblique (i.e. to non-relatives) transmission of her cultural traits at the expense of vertical (i.e. to children) transmission as well as family size, which behavior is optimal from cultural evolution standpoint? I formalize a general model that characterizes evolutionarily stable social activity. The proposed model replicates the theory of Newson et al. (2007) that fertility decline is caused by increasing role of oblique cultural transmission. Second, if social activity is a rational choice rather than a culturally inherited trait, and if cultural transmission acts on preferences rather than behaviors, which preferences survive the process of cultural evolution? I arrive at a very simple yet powerful result: under mild assumptions on model structure, only preferences which emphasize exclusively the concern for social prestige, i.e. extent to which one’s cultural trait has been picked up by others, survive.
By extending manipulability indices defined for single-valued social choice rules to the multi-valued case, we explore the degree of manipulability of seven multi-valued social choice rules. Our analysis is based on computational experiments.
We consider single machine scheduling problems with a non-renewable resource. These types of problems have not been intensively investigated in the literature so far. For several problems of these types with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), we present some complexity results. Particular attention is given to the problem of minimizing total tardiness. In addition, for the so-called budget scheduling problem with minimizing the makespan, we present some properties of feasible schedules.
A game with restricted cooperation is a triple (N,v,Ω), where N is a finite set of players, Ω⊂2N is a nonempty collection of feasible coalitions such that N∈Ω, andv:Ω→R is a characteristic function. The definition implies that if Ω=2N, then the game(N,v,Ω)=(N,v) is the classical transferable utility (TU) cooperative game.
The class of all games with restricted cooperation Gr with an arbitrary universal set of players is considered. The prenucleolus and the prekernel for games with restricted cooperation are defined in the same way as the prenucleolus and the prekernel for classical TU games. Necessary and sufficient conditions for the collection Ω to imply the single-valuedness of the prenucleolus are obtained. Axiomatic characterizations of the prenucleolus and of the prekernel for the class with a balanced collection of feasible coalitions Ω are given.
In the collection Ω there may be identical players belonging to the same coalitions. In that case, the set of symmetric preimputations is defined as those where identical players have equal payoffs. The symmetric prenucleolus, being the nucleolus w.r.t. the set of symmetrical preimputations, is defined and characterized.