A discrete cost sharing model with technological cooperation

This article proposes a setting that allows for technological cooperation in the cost sharing model. Dealing with discrete demands, we study two properties: additivity and dummy. We show that these properties are insufficient to guarantee a unit-flow representation similar to that of Wang (Econ Lett 64:187–192, 1999). To obtain a characterization of unit flows, we strengthen the dummy axiom and introduce a property that requires the cost share of every agent to be non-decreasing in the incremental costs generated by their demand. Finally, a fairness requirement as to the compensation of technological cooperation is examined.     

The Serial Property and Restricted Balanced Contributions in discrete cost sharing problems

We show that the Serial Poperty and Restricted Balanced Contributions characterize the subsidy-free serial cost sharing method (Moulin (1995)) in discrete cost allocation problems. This research has been partially supported by the Universidad del País Vasco (project UPV 00031.321-15352/2003), MCyT under projects BEC2003-08182 and SEJ2004-07554, and by the Generalitat Valenciana under project GRUPOS04/13.     

A ranking model for the greedy algorithm and discrete convexity

Generalizing the idea of the Lovász extension of a set function and the discrete Choquet integral, we introduce a combinatorial model that allows us to define and analyze matroid-type greedy algorithms. The model is based on a real-valued function v on a (finite) family of sets which yields the constraints of a combinatorial linear program. Moreover, v gives rise to a ranking and selection procedure for the elements of the ground set N and thus implies a greedy algorithm for the linear program. It is proved that the greedy algorithm is guaranteed to produce primal and dual optimal solutions if and only if an associated functional on ${\mathbb{R}^N}$ is concave. Previous matroid-type greedy models are shown to fit into the present general context. In particular, a general model for combinatorial optimization under supermodular constraints is presented which guarantees the greedy algorithm to work.     

Preference ranking of discrete multiattribute instances

This paper presents a procedure for preference ranking of discrete multiattribute instances based on the observations that (1) a difficult question could be answered in terms of answers to a sequence of easier ones, (2) in general, the decision maker's preferences can easily be expressed only relative to pairs of instances that differ over one attribute, and (3) the decision maker is able and willing to express his uncertainty regarding a quantity via a subjective probability distribution. The procedure is illustrated through a hypothetical situation.     

Consistency requirements and pattern methods in cost sharing problems with technological cooperation

Using the discrete cost sharing model with technological cooperation, we investigate the implications of the requirement that demand manipulations must not affect the agents’ shares. In a context where the enforcing authority cannot prevent agents (who seek to reduce their cost shares) from splitting or merging their demands, the cost sharing methods used must make such artifices unprofitable. The paper introduces a family of rules that are immune to these demand manipulations, the pattern methods. Our main result is the characterization of these methods using the above requirement. For each one of these methods, the associated pattern indicates how to combine the technologies in order to meet the agents’ demands. Within this family, two rules stand out: the public Aumann–Shapley rule, which never rewards technological cooperation; and the private Aumann–Shapley rule, which always rewards technology providers. Fairness requirements imposing natural bounds (for the technological rent) allow to further differentiate these two rules.     

On the serial cost sharing rule

In this paper we study a solution for discrete cost allocation problems, namely, the serial cost sharing method. We show that this solution can be computed by applying the Shapley value to an appropriate TU game and we present a probabilistic formula. We also define for cost allocation problems a multilinear function in order to obtain the serial cost sharing method as Owen (1972) did for the Shapley value in the cooperative TU context. Moreover we show that the pseudo average cost method is equivalent to an extended Shapley value. Received April 2000/Revised January 2003 RID="*" ID="*"  Authors are indebted to two anonymous referees for especially careful and useful comments. This research has been partially supported by the University of the Basque Country (projects UPV 036.321-HA197/98, UPV 036.321-HA042/99) and DGES Ministerio de Educación y Ciencia (project PB96-0247).     

Optimal cost sharing for capacitated facility location games

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.     

The core extraction axiom for combinatorial geometries

Let D be a dependent set in a combinatorial geometry G(S). The core of D is the set {x ∈ D:D<x is independent}. An order filter F of subsets of S is the set of dependent sets of a geometry iff for all D∈F, either core D is empty or core D∈F. This new cryptomorphism is particularly useful in the study of extensions and strong maps.     

New techniques for cost sharing in combinatorial optimization games

Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.     

Heterogeneous cost sharing, the directional serial rule

The directional serial rule is introduced as a natural serial extension, generalizing the Moulin–Shenker cost sharing rule to heterogeneous cost sharing models. It is the unique regular rule compatible with the radial serial principle. In particular, this shows the incompatibility of the serial principle with differentiability of a cost sharing rule as a function of the individual demands.I would like to thank the editor and the referee for their comments which have been most useful.     

The Hausdorff separation axiom for fuzzy topological spaces

We develop a theory of α-Hausdorff fuzzy topological spaces which is compatible with α-compactness and fuzzy continuity, and for α a certain type of member of a given lattice we obtain characterizations of the α-Hausdorff subspaces of the fuzzy unit interval, the fuzzy open unit interval, and the fuzzy real line. In route we give an easy proof of the Fuzzy Tychonov Theorem for α-compactness and extend the theory of one-point α-compactifications.     

The structure of iterative methods for symmetric linear discrete ill-posed problems

The iterative solution of large linear discrete ill-posed problems with an error contaminated data vector requires the use of specially designed methods in order to avoid severe error propagation. Range restricted minimal residual methods have been found to be well suited for the solution of many such problems. This paper discusses the structure of matrices that arise in a range restricted minimal residual method for the solution of large linear discrete ill-posed problems with a symmetric matrix. The exploitation of the structure results in a method that is competitive with respect to computer storage, number of iterations, and accuracy.     

The shrinking principle and the axiom of choice

The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different principle formulated by Vaught.     

Computational methods for discrete hidden semi-Markov chains

We propose a computational approach for implementing discrete hidden semi-Markov chains. A discrete hidden semi-Markov chain is composed of a non-observable or hidden process which is a finite semi-Markov chain and a discrete observable process. Hidden semi-Markov chains possess both the flexibility of hidden Markov chains for approximating complex probability distributions and the flexibility of semi-Markov chains for representing temporal structures. Efficient algorithms for computing characteristic distributions organized according to the intensity, interval and counting points of view are described. The proposed computational approach in conjunction with statistical inference algorithms previously proposed makes discrete hidden semi-Markov chains a powerful model for the analysis of samples of non-stationary discrete sequences. Copyright © 1999 John Wiley & Sons, Ltd.     

Iterative methods for stabilized discrete convection-diffusion problems

In this paper we study the computational cost of solving theconvection-diffusion equation using various discretization strategiesand iteration solution algorithms. The choice of discretizationinfluences the properties of the discrete solution and alsothe choice of solution algorithm. The discretizations consideredhere are stabilized low-order finite element schemes using streamlinediffusion, crosswind diffusion and shock-capturing. The latter,shock-capturing discretizations lead to nonlinear algebraicsystems and require nonlinear algorithms. We compare variouspreconditioned Krylov subspace methods including Newton-Krylovmethods for nonlinear problems, as well as several preconditionersbased on relaxation and incomplete factorization. We find thatalthough enhanced stabilization based on shock-capturing requiresfewer degrees of freedom than linear stabilizations to achievecomparable accuracy, the nonlinear algebraic systems are morecostly to solve than those derived from a judicious combinationof streamline diffusion and crosswind diffusion. Solution algorithmsbased on GMRES with incomplete block-matrix factorization preconditioningare robust and efficient.