This paper introduces and characterizes a new class of solutions to cooperative bargaining problems that can be rationalized by generalized Gini orderings defined on the agents' utility gains. Generalized Ginis are orderings which can be represented by quasi-concave, nondecreasing functions that are linear in rank-ordered subspaces of Euclidean $n$-space. Our characterization of (multi-valued) generalized Gini bargaining solutions is based on a linear invariance requirement in addition to some standard conditions. Linear invariance requires that if the feasible set is changed by adding a constant to one agent's component of each vector of the feasible set (without changing the agent's rank order), the solution responds by adding the same constant to the corresponding agent's utility in the outcome of the problem. Weak linear invariance requires the solution to change in a parallel way if a constant is added to all components of each vector of the feasible set. In the two-person case, the generalized Gini bargaining solutions can be characterized by imposing weak linear invariance, whereas, for $n \geqslant 3$ agents, linear invariance is required. As a by-product of our main result, we show that the egalitarian bargaining solution is characterized if single-valuedness is required together with some of our axioms. The main focus of cooperative bargaining theory has been the characterization of single-valued solutions. The results of this paper demonstrate that relaxing this assumption enlarges the class of solutions considerably. Hence, single-valuedness is not merely an assumption of convenience but, rather, an assumption of substance.