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.     

Sequencing Games with Slack Due Windows and Group Technology Considerations

We study sequencing situations in which the customers are initially sequenced to be served by a single server. We consider both slack due windows and group technology simultaneously. We introduce two division rules to divide among the customers the cost saving from resequencing the customers to follow the optimal sequence and characterize the rules axiomatically. Applying cooperative game theory to analyze the sequencing games corresponding to the sequencing situations, we use the theory’s solution concepts to solve the games.     

Cost allocation and convex data envelopment

This paper considers allocation rules. First, we demonstrate that costs allocated by the Aumann–Shapley and the Friedman–Moulin cost allocation rules are easy to determine in practice using convex envelopment of registered cost data and parametric programming. Second, from the linear programming problems involved it becomes clear that the allocation rules, technically speaking, allocate the non-zero value of the dual variable for a convexity constraint on to the output vector. Hence, the allocation rules can also be used to allocate inefficiencies in non-parametric efficiency measurement models such as Data Envelopment Analysis (DEA). The convexity constraint of the BCC model introduces a non-zero slack in the objective function of the multiplier problem and we show that the cost allocation rules discussed in this paper can be used as candidates to allocate this slack value on to the input (or output) variables and hence enable a full allocation of the inefficiency on to the input (or output) variables as in the CCR model.     

Obligation rules for minimum cost spanning tree situations and their monotonicity properties

We consider the class of Obligation rules for minimum cost spanning tree situations. The main result of this paper is that such rules are cost monotonic and induce also population monotonic allocation schemes. Another characteristic of Obligation rules is that they assign to a minimum cost spanning tree situation a vector of cost contributions which can be obtained as product of a double stochastic matrix with the cost vector of edges in the optimal tree provided by the Kruskal algorithm. It turns out that the Potters value (P-value) is an element of this class.     

Sequencing games without initial order

In this note we study uncertainty sequencing situations, i.e., one-machine sequencing situations in which no initial order is specified. We associate cooperative games with these sequencing situations, study their core, and provide links with the classic sequencing games introduced by Curiel et al. (Eur J Oper Res 40:344–351, 1989). Moreover, we propose and characterize two simple cost allocation rules for uncertainty sequencing situations with equal processing times.     

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.     

Good lattice rules based on the general weighted star discrepancy

We study the problem of constructing rank- lattice rules which have good bounds on the ``weighted star discrepancy'. Here the non-negative weights are general weights rather than the product weights considered in most earlier works. In order to show the existence of such good lattice rules, we use an averaging argument, and a similar argument is used later to prove that these lattice rules may be obtained using a component-by-component (CBC) construction of the generating vector. Under appropriate conditions on the weights, these lattice rules satisfy strong tractability bounds on the weighted star discrepancy. Particular classes of weights known as ``order-dependent' and ``finite-order' weights are then considered and we show that the cost of the construction can be very much reduced for these two classes of weights.

     

A study of simple rules for subcontracting in make-to-order manufacturing

We study a low volume component manufacturing operation facing order arrival rate greater than the service rate, thus necessitating subcontracting of some of the orders, for the case where order lead times are exogenous and highly variable. The major objective of the firm is to maximize capacity utilization and minimize tardiness (so as to minimize cost and maximize delivery reliability). Limiting the focus to operational decisions, we develop four heuristic decision rules with varying informational needs and complexity to determine when and which orders should be subcontracted. The performance of the decision rules over a range of environments is examined first under the assumption of perfect information. Then, we investigate the robustness of the policies for up to ±50% error in parameter estimates. The results show that, compared to simpler rules that do not seek to use the shop-workload information in making the subcontracting decision, the performance of the shop-workload feedback based decision rules (1) produce a superior performance, especially when the target utilization is high, and (2) are robust with up to ±50% error in parameter estimates.     

销售努力及双市场化期权下的三级供应链协调

本文针对需求随机且受到零售商销售努力影响的情况,研究了由制造商、分销商和零售商组成的三级供应链的协调问题。文章首先用双期权契约对三级供应链进行协调,即在制造商和分销商以及分销商和零售商之间都采用期权契约,发现在零售商独自承担努力成本的情况下仅通过双期权契约无法协调供应链。因此在双期权契约的基础上加入了努力成本共担契约,发现当期权价格满足某种线性关系以及零售商努力成本按特定比例分摊时,联合双期权契约和努力成本共担契约能顺利协调供应链。在此基础上,文章还引入了期权的市场化定价规则,研究了期权采用市场化定价规则对供应链协调产生的影响,研究表明,引入期权市场化定价规则增加了供应链协调需要满足的条件,降低了协调的可能性,且协调状态下的期权价格受到市场因素如利率、价格波动率等的影响。最后,文章给出了期权市场化定价规则下供应链协调的条件以及参数变化对协调的影响。     

马尔可夫排队模型中的合作问题分析

结合合作博弈理论,建立了合作条件下的马尔可夫排队模型.模型以多个提供同质服务的M/M/1马尔可夫排队系统达成协议形成联盟,共用一台服务器为顾客服务为研究重点,以机构维护服务器的成本与顾客在系统中排队等待的时间成本之和作为成本函数,得出形成联盟共用服务器可以降低总成本.最后给出总成本在形成联盟的机构中的分配规则.     

Truth-telling and Nash equilibria in minimum cost spanning tree models

In this paper we consider the minimum cost spanning tree model. We assume that a central planner aims at implementing a minimum cost spanning tree not knowing the true link costs. The central planner sets up a game where agents announce link costs, a tree is chosen and costs are allocated according to the rules of the game. We characterize ways of allocating costs such that true announcements constitute Nash equilibria both in case of full and incomplete information. In particular, we find that the Shapley rule based on the irreducible cost matrix is consistent with truthful announcements while a series of other well-known rules (such as the Bird-rule, Serial Equal Split, and the Proportional rule) are not.     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

A generalization of obligation rules for minimum cost spanning tree problems

Tijs et al. [23] introduce the family of obligation rules for minimum cost spanning tree problems. We give a generalization of such family. We prove that our family coincides with the set of rules satisfying an additivity property and a cost monotonicity property. We also provide two new characterizations for the family of obligation rules using the previous properties. In the first one, we add a property of separability; and in the second one, we add core selection.     

Effects of regulatory delays and uncertainty on pricing decisions

In this paper we introduce a simple decision rule that a single product firm may use for filing for a price change to offset variations of the marginal cost. We consider a regulatory body whose response to the price change request involves a time delay with an exponential distribution. Two possibilities regarding the response of the regulatory body are considered. In one case it is assumed to be a binary approval process in which the rate adjustment is either approved in its entirety or rejected. In the second case we consider a partial approval process with a more general distribution. Decision rules for each case are developed. Finally we derive a multi-stage decision rule in which filing decisions are continuously updated based on temporal variations of the cost function. The multi-stage pricing decision model assumes that marginal cost escalation satisfies a Markovian jump process.This work was completed while the authors were with Bell Laboratories, USA.     

Multi-group support vector machines with measurement costs: A biobjective approach

Support Vector Machine has shown to have good performance in many practical classification settings. In this paper we propose, for multi-group classification, a biobjective optimization model in which we consider not only the generalization ability (modeled through the margin maximization), but also costs associated with the features. This cost is not limited to an economical payment, but can also refer to risk, computational effort, space requirements, etc. We introduce a Biobjective Mixed Integer Problem, for which Pareto optimal solutions are obtained. Those Pareto optimal solutions correspond to different classification rules, among which the user would choose the one yielding the most appropriate compromise between the cost and the expected misclassification rate.     

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.     

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.     

Random weights, robust lattice rules and the geometry of the cbcrc algorithm

In this paper we study lattice rules which are cubature formulae to approximate integrands over the unit cube [0,1] ^s from a weighted reproducing kernel Hilbert space. We assume that the weights are independent random variables with a given mean and variance for two reasons stemming from practical applications: (i) It is usually not known in practice how to choose the weights. Thus by assuming that the weights are random variables, we obtain robust constructions (with respect to the weights) of lattice rules. This, to some extend, removes the necessity to carefully choose the weights. (ii) In practice it is convenient to use the same lattice rule for many different integrands. The best choice of weights for each integrand may vary to some degree, hence considering the weights random variables does justice to how lattice rules are used in applications. In this paper the worst-case error is therefore a random variable depending on random weights. We show how one can construct lattice rules which perform well for weights taken from a set with large measure. Such lattice rules are therefore robust with respect to certain changes in the weights. The construction algorithm uses the component-by-component (cbc) idea based on two criteria, one using the mean of the worst case error and the second criterion using a bound on the variance of the worst-case error. We call the new algorithm the cbc2c (component-by-component with 2 constraints) algorithm. We also study a generalized version which uses r constraints which we call the cbcrc (component-by-component with r constraints) algorithm. We show that lattice rules generated by the cbcrc algorithm simultaneously work well for all weights in a subspace spanned by the chosen weights ?? ⁽¹⁾, . . . , ?? ^(r). Thus, in applications, instead of finding one set of weights, it is enough to find a convex polytope in which the optimal weights lie. The price for this method is a factor r in the upper bound on the error and in the construction cost of the lattice rule. Thus the burden of determining one set of weights very precisely can be shifted to the construction of good lattice rules. Numerical results indicate the benefit of using the cbc2c algorithm for certain choices of weights.     

Fórmulas para el cálculo del factor de impacto de estructuras semienterradas en líneas de ferrocarril de alta velocidad

Underpasses are common in modern railway lines. Wildlife corridors and drainage conduits often fall into this category of partially buried structures. Their dynamic behavior has received far less attention than that of other structures such as bridges, but their large number makes their study an interesting challenge from the viewpoint of safety and cost savings. The bridge design rules in accordance with the Eurocode involve checks on stresses according to dynamic loading. In the case of underpasses, those checks may be as much as those for bridges. Therefore, simplified design rules may align the design effort with their cost. Such a set of rules may provide estimations of response parameters based on the key parameters influencing the result. This paper contains a proposal based on a parametric study.     

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.