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 minimum cost shortest-path tree game

A minimum cost shortest-path tree is a tree that connects the source with every node of the network by a shortest path such that the sum of the cost (as a proxy for length) of all arcs is minimum. In this paper, we adapt the algorithm of Hansen and Zheng (Discrete Appl. Math. 65:275?C284, 1996) to the case of acyclic directed graphs to find a minimum cost shortest-path tree in order to be applied to the cost allocation problem associated with a cooperative minimum cost shortest-path tree game. In addition, we analyze a non-cooperative game based on the connection problem that arises in the above situation. We prove that the cost allocation given by an ??à la?? Bird rule provides a core solution in the former game and that the strategies that induce those payoffs in the latter game are Nash equilibrium.     

Consistent cost sharing

A new concept of consistency for cost sharing solutions is discussed, analyzed, and related to the homonymous and natural property within the rationing context. Main result is that the isomorphism in Moulin and Shenker (J Econ Theory 64:178–201, 1994) pairs each additive and consistent single-valued mechanism with a corresponding monotonic and consistent rationing method. Then this answers the open question in Moulin (Econometrica 68:643–684, 2000; Handbook of social choice and welfare. Handbooks in economics, pp 289–357, 2002) whether such notion for cost sharing exists. The conclusion is that renown solutions like the average and serial cost sharing mechanisms are consistent, whereas the Shapley–Shubik mechanism is not. Average cost sharing is the only strongly consistent element in this class. The two subclasses of incremental and parametric cost sharing mechanisms are further analyzed as refinement of the main result.     

The implications of the ranking axiom for discrete cost sharing methods

In this paper, we study the Ranking property for discrete cost sharing methods. In the two-agent model, we characterize the set of methods satisfying this axiom: the symmetry of the flow representing the method is necessary and sufficient for Ranking. In higher dimensions (n ≥ 3), we identify strong implications of the axiom; however, we prove that these conditions are not sufficient to characterize Ranking. For the so-called elementary fixed flows, we derive a necessary and sufficient condition.     

Marginal cost price rule for homogeneous cost functions

Mirman and Tauman (1982) show that axioms of cost sharing, additivity, rescaling invariance, monotonicity, and consistency uniquely determine a price rule on the class of continuously differentiable cost problems as the Aumann-Shapley price mechanism. Here we prove that standard versions of these axioms determine uniquely the marginal cost price rule on the class of homogeneous and convex cost functions, which are, in addition, continuously differentiable. This result persists even if the cost functons are not required to be convex. Received: August 2001     

Two Approaches to the Problem of Sharing Delay Costs in Joint Projects

This paper concentrates on cost sharing situations which arise when delayed joint projects involve joint delay costs. The problem here is to determine fair shares for each of the agents who contribute to the delay of the project such that the total delay cost is cleared. We focus on the evaluation of the responsibility of each agent in delaying the project based on the activity graph representation of the project and then on solving the important problem of the delay cost sharing among the agents involved. Two approaches, both rooted in cooperative game theory methods are presented as possible solutions. In the first approach delay cost sharing rules are introduced which are based on the delay of the project and on the individual delays of the agents who perform activities. This approach is inspired by the bankruptcy and taxation literature and leads to five rules: the (truncated) proportional rule, the (truncated) constrained equal reduction rule and the constrained equal contribution rule. By introducing two coalitional games related to delay cost sharing problems, which we call the pessimistic delay game and the optimistic delay game, also game theoretical solutions as the Shapley value, the nucleolus and the -value generate delay cost sharing rules. In the second approach the delays of the relevant paths in the activity graph together with the delay of the project play a role. A two-stage solution is proposed. The first stage can be seen as a game between paths, where the delay cost of the project has to be allocated to the paths. Here serial cost sharing methods play a role. In the second stage the allocated costs of each path are divided proportionally to the individual delays among the activities in the path.     

Drop out monotonic rules for sequencing situations

This note introduces a new monotonicity property for sequencing situations. A sequencing rule is called drop out monotonic if no player will be worse off whenever one of the players decides to drop out of the queue before processing starts. This intuitively appealing property turns out to be very strong: we show that there is at most one rule satisfying both stability and drop out monotonicity. For the standard model of linear cost functions, the existence of this rule is established.     

The $$$$-seril cost shring rule

A new family of cost sharing rules for cost sharing problems is proposed. This family generalizes the family of \(\alpha \)-serial cost sharing rules (Albizuri in Math Soc Sci 60:24–29, 2010) which contains the serial cost sharing rule (Moulin and Shenker in Econometrica 60:1009–1037, 1992) among others. Every rule of the family is characterized by means of two properties.     

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.     

Strategy-proofness and public good provision using referenda based on unequal cost sharing

The paper studies strategy-proof cost sharing rules for public good provision based on referenda with different threshold quotas. By appropriately relaxing the assumptions of individual rationality and anonymity we provide a complete characterization of the family of quota rules with (possibly) unequal pricing. We prove that these quota rules are the only cost sharing rules satisfying four conditions: strategy-proofness, non-bossiness, weak continuity and weak anonymity. In addition, the specification of the degree to which individual rationality may be violated results in the selection of a specific “quota” for the referendum. While all these rules are “almost” always efficient when providing the public good and they are also almost everywhere coalitionally strategy-proof, only one family of rules from this class satisfies these two properties everywhere. The rules satisfying these two properties are Moulin’s Conservative Equal Costs Rule and unequal cost sharing variants of Moulin’s rule.     

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.     

Secure collaborative supply chain planning and inverse optimization – The JELS model

It is a well-acknowledged fact that collaboration between different members of a supply chain yields a significant potential to increase overall supply chain performance. Sharing private information has been identified as prerequisite for collaboration and, at the same time, as one of its major obstacles. One potential avenue for overcoming this obstacle is Secure Multi-Party Computation (SMC). SMC is a cryptographic technique that enables the computation of any (well-defined) mathematical function by a number of parties without any party having to disclose its input to another party. In this paper, we show how SMC can be successfully employed to enable joint decision-making and benefit sharing in a simple supply chain setting. We develop secure protocols for implementing the well-known “Joint Economic Lot Size (JELS) Model” with benefit sharing in such a way that none of the parties involved has to disclose any private (cost and capacity) data. Thereupon, we show that although computation of the model’s outputs can be performed securely, the approach still faces practical limitations. These limitations are caused by the potential of “inverse optimization”, i.e., a party can infer another party’s private data from the output of a collaborative planning scheme even if the computation is performed in a secure fashion. We provide a detailed analysis of “inverse optimization” potentials and introduce the notion of “stochastic security”, a novel approach to assess the additional information a party may learn from joint computation and benefit sharing. Based on our definition of “stochastic security” we propose a stochastic benefit sharing rule, develop a secure protocol for this benefit sharing rule, and assess under which conditions stochastic benefit sharing can guarantee secure collaboration.     

Consistency and monotonicity in sequencing problems

We explore the implications of consistency and monotonicity in sequencing problems. We first identify all rules satisfying Pareto indifference, individual rationality from random arrival, and consistency. Next, we ask whether there is a rule satisfying the three axioms together with either one of two monotonicity requirements, time monotonicity and cost monotonicity. As it turns out, the minimal transfer rule is the only rule satisfying Pareto indifference, individual rationality from random arrival, consistency together with either time monotonicity or cost monotonicity. We also investigate how the maximal transfer rule responds to changes in the service time and waiting cost.     

Optimal stopping problem with double reservation value property

This paper considers an optimal stopping problem with uncertain recall probability where some recall cost must be paid to accept a past offer. Recall cost is an important factor leading to value deterioration of an offer. However, it is assumed in all the conventional models so far presented that the value of a past offer does not change with time, and its original value is guaranteed even if the past offer is recalled at any time in the future. In the model of this paper, the value of a past offer decreases due to the recall cost. The purpose of this paper is to propose a model with such a recall cost factor and uncertain recall probability, and to examine the properties of its optimal decision rule. One of the most distinctive results in this study is that the optimal decision rule may have a seemingly counter-intuitive property, called the DRV (Double Reservation Value) property: the critical point of whether or not to stop the search by accepting an offer is not a single entity. An interpretation of why the property may appear in this model will be given. Furthermore, this paper examines the necessary and sufficient conditions required for the property to appear, and demonstrates that the recall cost is an essential factor to the appearance of the property. To illustrate the importance of considering the recall cost factor and uncertain recall probability, this paper also provides some practical implications to a decision maker confronted with a problem of M&A (Merger & Acquisition), using an actual case of the Ford–Daewoo deal.     

Limiting behavior of the search cost distribution for the move-to-front rule in the stable case

Move-to-front rule is a heuristic updating a list of n items according to requests. Items are required with unknown probabilities (or popularities). The induced Markov chain is known to be ergodic. A main problem is the study of the distribution of the search cost defined as the position of the required item. Here we first establish the link between two recent papers of Barrera and Paroissin and Lijoi and Pruenster that both extend the results proved by Kingman on the expected stationary search cost. By combining the results contained in these papers, we obtain the limiting behavior for any moments of the stationary search cost as n tends to infinity.     

Secret sharing schemes with partial broadcast channels

In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point channels to a combiner who will reconstruct the secret. In this paper, we assume no point-to-point channel exists and communication is only through partial broadcast channels. A partial broadcast channel is a point-to-multipoint channel that enables a sender to send the same message simultaneously and privately to a fixed subset of receivers. We study secret sharing schemes with partial broadcast channels, called partial broadcast secret sharing schemes. We show that a necessary and sufficient condition for the partial broadcast channel allocation of a (t, n)-threshold partial secret sharing scheme is equivalent to a combinatorial object called a cover-free family. We use this property to construct a (t, n)-threshold partial broadcast secret sharing scheme with O(log n) partial broadcast channels. This is a significant reduction compared to n point-to-point channels required in a conventional secret sharing scheme. Next, we consider communication rate of a partial broadcast secret sharing scheme defined as the ratio of the secret size to the total size of messages sent by the dealer. We show that the communication rate of a partial broadcast secret sharing scheme can approach 1/O(log n) which is a significant increase over the corresponding value, 1/n, in the conventional secret sharing schemes. We derive a lower bound on the communication rate and show that for a (t,n)-threshold partial broadcast secret sharing scheme the rate is at least 1/t and then we propose constructions with high communication rates. We also present the case of partial broadcast secret sharing schemes for general access structures, discuss possible extensions of this work and propose a number of open problems.      

A vertex oriented approach to the equal remaining obligations rule for minimum cost spanning tree situations

In this paper, we consider spanning tree situations, where players want to be connected to a source as cheap as possible. These situations involve the construction of a spanning tree with the minimum cost as well as the allocation of the cost of this minimum cost spanning tree among its users in a fair way. Feltkamp, Muto and Tijs 1994 introduced the equal remaining obligations rule to solve the cost allocation problem in these situations. Recently, it has been shown that the equal remaining obligations rule satisfies many appealing properties and can be obtained with different approaches. In this paper, we provide a new approach to obtain the equal remaining obligations rule. Specifically, we show that the equal remaining obligations rule can be obtained as the average of the cost allocations provided by a vertex oriented construct-and-charge procedure for each order of players.     

排序对策的一个新的收益分配准则

针对一个机器的排序问题,给出了排序问题中成本增加量的表达式,提出了收益分配的不小于成本增加量准则。针对一类特殊的排序问题,给出一个符合不小于成本增加量分配准则的解,并证明了它满足有效性,哑元性和单调性。结合一个算例,对本文的提出的方法进行了分析验证。     

Scattering for radial energy-subcritical wave equations in dimensions 4 and 5

In this paper, we consider the focusing and defocusing energy-subcritical, nonlinear wave equation in ?^1+d with radial initial data for d = 4,5. We prove that if a solution remains bounded in the critical space on its interval of existence, then the solution exists globally and scatters at ±∞. The proof follows the concentration compactness/rigidity method initiated by Kenig and Merle, and the main obstacle is to show the nonexistence of nonzero solutions with a certain compactness property. A main novelty of this work is the use of a simple virial argument to rule out the existence of nonzero solutions with this compactness property rather than channels of energy arguments that have been proven to be most useful in odd dimensions.