A characterization of Kruskal sharing rules for minimum cost spanning tree problems

In Tijs et al. (Eur J Oper Res 175:121–134, 2006) a new family of cost allocation rules is introduced in the context of cost spanning tree problems. In this paper we provide the first characterization of this family by means of population monotonicity and a property of additivity.     

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.     

“Optimistic” weighted Shapley rules in minimum cost spanning tree problems

We introduce optimistic weighted Shapley rules in minimum cost spanning tree problems. We define them as the weighted Shapley values of the optimistic game v⁺ introduced in Bergantiños and Vidal-Puga [Bergantiños, G., Vidal-Puga, J.J., forthcoming. The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory. Available from: <http://webs.uvigo.es/gbergant/papers/cstShapley.pdf>]. We prove that they are obligation rules [Tijs, S., Branzei, R., Moretti, S., Norde, H., 2006. Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175, 121–134].     

Extended proportionality in division problems with multiple references

We consider an extension of the classic problem of division with claims to situations in which the characteristics of the agents are multi-dimensional. The proportional rule is the most prominent in the one-dimensional case, however there is no obvious way to define proportionality for the extended model. In this paper we introduce a property which generalizes proportionality, identify the family of rules satisfying it, and characterize a particular rule within this family on the basis of a property of symmetry.     

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.     

How to Distribute Costs Associated with a Delayed Project

In this paper we study how to distribute the cost caused by the delay of a project among the firms which are responsible for it. We present two rules, one based on serial cost sharing problems and the other, in game theory. Moreover, we introduce some desirable properties, inspired by well-known principles, and study which of them are satisfied by the rules.     

The reverse Talmud family of rules for bankruptcy Problems: A characterization

We characterize the reverse Talmud family of  rules for bankruptcy problems using consistency and additivity on a restricted domain of problems. The family includes several standard rules such as the constrained equal awards, constrained equal losses and reverse Talmud rules. This last rule is characterized by further imposing the mid-point property. Furthermore, each member of the RTAL-family is characterized using consistency and additivity on a domain in which that member is additive.     

Analysis and Construction of Multivariate Interpolating Refinable Function Vectors

In this paper, we shall introduce and study a family of multivariate interpolating refinable function vectors with some prescribed interpolation property. Such interpolating refinable function vectors are of interest in approximation theory, sampling theorems, and wavelet analysis. In this paper, we characterize a multivariate interpolating refinable function vector in terms of its mask and analyze the underlying sum rule structure of its generalized interpolatory matrix mask. We also discuss the symmetry property of multivariate interpolating refinable function vectors. Based on these results, we construct a family of univariate generalized interpolatory matrix masks with increasing orders of sum rules and with symmetry for interpolating refinable function vectors. Such a family includes several known important families of univariate refinable function vectors as special cases. Several examples of bivariate interpolating refinable function vectors with symmetry will also be presented.     

Inconsistency indices for pairwise comparisons and the Pareto dominance principle

We consider the problem of quantifying inconsistency in pairwise comparisons and valued-preferences. A wide range of indices have been proposed in the literature to perform this task, and two sets of conditions have been introduced to validate such indices. We summarize some criticisms from the literature and we add more evidence to show that neither of the two systems is adequate in its current formulation. Thanks to the widely accepted concept of weak Pareto dominance, we formulate a new property. We argue that a simple regularity condition and this new property can overcome the shortcomings of the two axiomatic systems, and represents a significantly simpler framework. Finally, we claim that, if we had resorted to strict Pareto dominance, we would have needed just one axiom.     

The Cost Distribution of Queue-Mergesort, Optimal Mergesorts, and Power-of-2 Rules

Queue-mergesort is introduced by Golin and Sedgewick as an optimal variant of mergesorts in the worst case. In this paper, we present a complete analysis of the cost distribution of queue-mergesort, including the best, average, and variance cases. The asymptotic normality of its cost is also established under the uniform permutation model. We address the corresponding optimality problems and we show that if we fix the merging scheme then the optimal mergesort as far as the average number of comparisons is concerned is to divide as evenly as possible at each recursive stage (top-down mergesort). On the other hand, the variance of queue-mergesort reaches asymptotically the minimum value. We also characterize a class of mergesorts with the latter property. A comparative discussion is given on the probabilistic behaviors of top-down mergesort, bottom-up mergesort, and queue-mergesort. We derive an “invariance principle” for asymptotic linearity of divide-and-conquer recurrences based on general “power-of-2” rules of which the underlying dividing rule of queue-mergesort is a special case. These analyses reveal an interesting algorithmic feature for general power-of-2 rules.     

Complexity of local search for the p-median problem

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0–1 local saddle points, and classical Karush–Kuhn–Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules.     

Sustainability in bankruptcy problems

This paper focuses on a new property for bankruptcy rules, calledsustainability, which requires that the agents with small enough claims be fully reimbursed. We show that the constrained equal-awards rule is the only rule that satisfies path independence and sustainability. Exploiting duality relations, we also provide a characterization of the constrained equal-losses rule, as the only one that satisfies composition and independence of residual claims (the dual property of sustainability).     

Multiple unit auctions with economies and diseconomies of scale

This paper discusses multiple unit auctions for industrial procurement where the cost structures of suppliers capture economies and diseconomies of scale caused by the nature of the production cost and the opportunity value of suppliers’ capacities. The problem of winner determination and demand allocation is proven to be NP-complete. We propose a binary tree algorithm with bounds (BTB) which efficiently exploits the model’s optimality properties. BTB outperforms general integer optimization software in computational time, especially with existence of substantial economies and diseconomies of scale. The algorithm complexity is linear in demand volume. This property allows for efficient handling of high volume auctions and thus leads to increased benefit for the overall system. Under the assumption of the myopic best response strategies, we investigate the behavior of suppliers and price dynamics for iterative (multiple round) bidding with appropriate allocation and stopping rules. The allocation rules, featured by several tie breakers for multiple optimal solutions to the allocation model in each round, are proposed to induce suppliers’ dominant strategies and to improve the system’s performance.     

An axiomatization of the Shapley value using a fairness property

In this paper we provide an axiomatization of the Shapley value for TU-games using a fairness property. This property states that if to a game we add another game in which two players are symmetric then their payoffs change by the same amount. We show that the Shapley value is characterized by this fairness property, efficiency and the null player property. These three axioms also characterize the Shapley value on the class of simple games. Revised August 2001     

模糊处理变结构神经网络日负荷预测方法研究

对于受不确定因素影响的日电力负荷,首次提出了基于模糊分类规则的变结构神经网络负荷预测模型,考虑从两方面改进预测精度,一个方面是通过模糊分类规则,使过去的负荷数据分为不同气候特征,选用同类特征数据进行预测,另一方面是通过神经网络变结构优化,确定最优网络和最优拟合逼近,从而得到最优的预测结果,这种新方法同时考虑了天气因素的影响和神经网络的最优确定,因此,较大提高了日负荷预测的精度。     

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.     

A family of rules for parameter choice in Tikhonov regularization of ill-posed problems with inexact noise level

We consider Tikhonov regularization of linear ill-posed problems with noisy data. The choice of the regularization parameter by classical rules, such as discrepancy principle, needs exact noise level information: these rules fail in the case of an underestimated noise level and give large error of the regularized solution in the case of very moderate overestimation of the noise level. We propose a general family of parameter choice rules, which includes many known rules and guarantees convergence of approximations. Quasi-optimality is proved for a sub-family of rules. Many rules from this family work well also in the case of many times under- or overestimated noise level. In the case of exact or overestimated noise level we propose to take the regularization parameter as the minimum of parameters from the post-estimated monotone error rule and a certain new rule from the proposed family. The advantages of the new rules are demonstrated in extensive numerical experiments.     

Efficient visit frequencies for polling tables: minimization of waiting cost

Polling systems have been used as a central model for the modeling and analysis of many communication systems. Examples include the Token Ring network and a communications switch. The common property of these systems is the need to efficiently share a single resource (server) amongN entities (stations). In spite of the massive research effort in this area, very little work has been devoted to the issue of how toefficiently operate these systems.In the present paper we deal with this problem, namely with how to efficiently allocate the server's attention among theN stations. We consider a framework in which a predetermined fixed visit order (polling table) is used to establish the order by which the server visits the stations, and we address the problem of how to construct an efficient (optimal) polling table. In selecting a polling table the objective is to minimize the mean waiting cost of the system, a weighted sum of the mean delays with arbitrary cost parameters. Since the optimization problem involved is very hard, we use an approximate approach. Using two independent analyses, based on a lower bound and on mean delay approximations, we derive very simple rules for the determination of efficient polling tables. The two rules are very similar and even coincide in most cases. Extensive numerical examination shows that the rules perform well and that in most cases the system operates very close to its optimal operation point.     

Distributive residuated frames and generalized bunched implication algebras

We show that all extensions of the (non-associative) Gentzen system for distributive full Lambek calculus by simple structural rules have the cut elimination property. Also, extensions by such rules that do not increase complexity have the finite model property, hence many subvarieties of the variety of distributive residuated lattices have decidable equational theories. For some other extensions, we prove the finite embeddability property, which implies the decidability of the universal theory, and we show that our results also apply to generalized bunched implication algebras. Our analysis is conducted in the general setting of residuated frames.     

Analysis of Fractional Covering of Some Supply Management Problems

We study a supply management problem with a linear cost function and its mixed integer program. A parametric family of such problems, possessing exponential L _k -coverings, is constructed. Besides, the NP-hard expansion of the family, which has the same property, is formulated.