Banzhaf Measures for Games with Several Levels of Approval in the Input and Output

An axiomatic characterization of ‘a Banzhaf score’ notion is provided for a class of games called (j,k) simple games with a numeric measure associated to the output set, i.e., games with n players, j ordered qualitative alternatives in the input level and k possible ordered quantitative alternatives in the output. Three Banzhaf measures are also introduced which can be used to determine a player's ‘a priori’ value in such a game. We illustrate by means of several real world examples how to compute these measures. Research partially supported by Grant BFM 2003-01314 of the Science and Technology Spanish Ministry and the European Regional Development Fund.     

Characterizing an optimal input in perturbed convex programming

When every feasible stable perturbation of data results in a non-improvement of the optimal value function, then we talk about an ‘optimal input’ or an ‘optimal selection of data”. In this paper we describe such data for convex programs using perturbed saddle points. Research partly supported by Natural Sciences and Engineering Council of Canada and le Ministère de l'Education du Québec (F.C.A.C.). Presented in part at the Third Symposium on Mathematical Programming with Data Perturbations, The George Washington University, Washington, D.C. (May 21–22, 1981).     

Generalized semi-infinite programming: A tutorial

This tutorial presents an introduction to generalized semi-infinite programming (GSIP) which in recent years became a vivid field of active research in mathematical programming. A GSIP problem is characterized by an infinite number of inequality constraints, and the corresponding index set depends additionally on the decision variables. There exist a wide range of applications which give rise to GSIP models; some of them are discussed in the present paper. Furthermore, geometric and topological properties of the feasible set and, in particular, the difference to the standard semi-infinite case are analyzed. By using first-order approximations of the feasible set corresponding constraint qualifications are developed. Then, necessary and sufficient first- and second-order optimality conditions are presented where directional differentiability properties of the optimal value function of the so-called lower level problem are used. Finally, an overview of numerical methods is given.     

On C *-Extreme Maps and *-Homomorphisms of a Commutative C *-Algebra

The generalized state space of a commutative C^*-algebra, denoted , is the set of positive unital maps from C(X) to the algebra of bounded linear operators on a Hilbert space . C^*-convexity is one of several non-commutative analogs of convexity which have been discussed in this context. In this paper we show that a C^*-extreme point of satisfies a certain spectral condition on the operators in the range of the associated positive operator-valued measure. This result enables us to show that C^*-extreme maps from C(X) into , the algebra generated by the compact and scalar operators, are multiplicative. This generalizes a result of D. Farenick and P. Morenz. We then determine the structure of these maps. This paper constitutes a part of the author’s Ph.D. thesis at the University of Nebraska-Lincoln.     

Connection admission control for constant bit rate traffic at a multi‐buffer multiplexer using the oldest‐cell‐first discipline

Consider an ATM multiplexer where M input links contend for time slots on an output link which transmits C cells per second. Each input link has its own queue of size B cells. The traffic is delay sensitive so B is small (e.g., B=20). We assume that each of the M input links carries Constant Bit Rate (CBR) traffic from a large number of independent Virtual Connections (VCs) which are subject to jitter. The fluctuations of the aggregate traffic arriving at queue i, i=1,...,M, is modeled by a Poisson process with rate λ_i. The Quality of Service (QoS) of one connection is determined in part by the queueing delay across the multiplexer and the Cell Loss Ratio (CLR) or proportion of cells from this connection lost because the buffer is full. The Oldest‐Customer(Cell)‐First (OCF) discipline is a good compromise between competing protocols like round‐robin queueing or serving the longest queue. The OCF discipline minimizes the total cell delay among all cells arriving at the contending queues. Moreover, the CLR is similar to that obtained by serving the longest queue. We develop QoS formulae for this protocol that can be calculated on‐line for Connection Admission Control (CAC). These formulae follow from a simple new expression for the exact asymptotics of a M/D/1 queue. This revised version was published online in June 2006 with corrections to the Cover Date.     

Invariants de classes : exemples de non-annulation en dimension supérieure

The so-called class-invariant homomorphism ψ measures the Galois module structure of torsors—under a finite flat group scheme G—which lie in the image of a coboundary map associated to an isogeny between (Néron models of) abelian varieties with kernel G. When the varieties are elliptic curves with semi-stable reduction and the order of G is coprime to 6, it is known that the homomorphism ψ vanishes on torsion points. In this paper, using Weil restrictions of elliptic curves, we give the construction, for any prime number p > 2, of an abelian variety A of dimension p endowed with an isogeny (with kernel μ _p ) whose coboundary map is surjective. In the case when A has rank zero and the p-part of the Picard group of the base is non-trivial, we obtain examples where ψ does not vanish on torsion points.

---

Résumé  Le class-invariant homomorphism permet de mesurer la structure galoisienne des torseurs—sous un schéma en groupes fini et plat G—qui sont dans l’image du cobord associé à une isogénie, de noyau G, entre des (modèles de Néron de) variétés abéliennes. Quand les variétés sont des courbes elliptiques à réduction semi-stable et que l’ordre de G est premier à 6, on sait que cet homomorphisme s’annule sur les points de torsion. Dans cet article, en nous servant de restrictions de Weil de courbes elliptiques, nous construisons, pour tout nombre premier p > 2, une variété abélienne A de dimension p munie d’une isogénie (de noyau μ _p ) dont le cobord est surjectif. Si A est de rang nul, et si la p-partie du groupe de Picard de la base est non triviale, nous obtenons ainsi un exemple où le class-invariant homomorphism ne s’annule pas sur les points de torsion.

     

Asymptotic height optimization for topical IFS, Tetris heaps, and the finiteness conjecture

Given an Iterated Function System (IFS) of topical maps verifying some conditions, we prove that the asymptotic height optimization problems are equivalent to finding the extrema of a continuous functional, the average height, on some compact space of measures. We give general results to determine these extrema, and then apply them to two concrete problems. First, we give a new proof of the theorem that the densest heaps of two Tetris pieces are sturmian. Second, we construct an explicit counterexample to the Lagarias-Wang finiteness conjecture for the joint spectral radius of a set of matrices.

RÉSUMÉ. Etant donné un système itéré de fonctions (IFS) topicales, vérifiant certaines conditions, nous montrons que les questions d'optimisation asymptotique de la hauteur sont équivalentes à la recherche des extrema d'une fonctionnelle continue, la hauteur moyenne, sur un certain espace compact de mesures. Nous présentons des résultats généraux permettant de déterminer ces extrema, puis appliquons ces méthodes à deux problèmes concrets. Premièrement, nous redémontrons que les empilements les plus denses de deux pièces de Tetris sont sturmiens. Deuxièmement, nous construisons un contre-exemple effectif à la conjecture de finitude de Lagarias et Wang sur le rayon spectral joint d'un ensemble de matrices.

     

On the choice of aggregation points for continuousp-median problems: A case for the gravity centre

In large scale location-allocation studies it is necessary to use data-aggregation in order to obtain solvable models. A detailed analysis is given of the errors induced by this aggregation in the evaluation of thep-median objective function. Then it is studied how to choose the points at which to aggregate given groups of demand points so as to minimise this aggregation error. Forp-median problems with euclidean distances, arguments are given in favour of the centre of gravity of the groups. These arguments turn out to be much stronger for rectangular distance. Aggregating at the centroid also leads to much higher precision bounds on the errors for rectangular distance. Some numerical results are obtained validating the theoretical developments. This research was partially done while the author was on visit at the Laboratoire d’Analyse Appliquée et Optimisation at the Université de Bourgogne, Dijon, France. Thanks to E. Carrizosa, B. Rayco and four anonymous referees for many thoughtful remarks.     

Residual flux-based a posteriori error estimates for finite volume and related locally conservative methods

We derive in this paper a posteriori error estimates for discretizations of convection–diffusion–reaction equations in two or three space dimensions. Our estimates are valid for any cell-centered finite volume scheme, and, in a larger sense, for any locally conservative method such as the mimetic finite difference, covolume, and other. We consider meshes consisting of simplices or rectangular parallelepipeds and also provide extensions to nonconvex cells and nonmatching interfaces. We allow for the cases of inhomogeneous and anisotropic diffusion–dispersion tensors and of convection dominance. The estimates are established in the energy (semi)norm for a locally postprocessed approximate solution preserving the conservative fluxes and are of residual type. They are fully computable (all occurring constants are evaluated explicitly) and locally efficient (give a local lower bound on the error times an efficiency constant), so that they can serve both as indicators for adaptive refinement and for the actual control of the error. They are semi-robust in the sense that the local efficiency constant only depends on local variations in the coefficients and becomes optimal as the local Péclet number gets sufficiently small. Numerical experiments confirm their accuracy. This work was supported by the GdR MoMaS project “Numerical Simulations and Mathematical Modeling of Underground Nuclear Waste Disposal”, PACEN/CNRS, ANDRA, BRGM, CEA, EdF, IRSN, France. The main part of this work was carried out during the author’s post-doc stay at Laboratoire de Mathématiques, Analyse Numérique et EDP, Université de Paris-Sud and CNRS, Orsay, France.     

A generalization of rational Bernstein–Bézier curves

This paper is concerned with a generalization of Bernstein–Bézier curves. A one parameter family of rational Bernstein–Bézier curves is introduced based on a de Casteljau type algorithm. A subdivision procedure is discussed, and matrix representation and degree elevation formulas are obtained. We also represent conic sections using rational q-Bernstein–Bézier curves. AMS subject classification (2000)  65D17     

Optimal Compensation with Hidden Action and Lump-Sum Payment in a Continuous-Time Model

We consider a problem of finding optimal contracts in continuous time, when the agent’s actions are unobservable by the principal, who pays the agent with a one-time payoff at the end of the contract. We fully solve the case of quadratic cost and separable utility, for general utility functions. The optimal contract is, in general, a nonlinear function of the final outcome only, while in the previously solved cases, for exponential and linear utility functions, the optimal contract is linear in the final output value. In a specific example we compute, the first-best principal’s utility is infinite, while it becomes finite with hidden action, which is increasing in value of the output. In the second part of the paper we formulate a general mathematical theory for the problem. We apply the stochastic maximum principle to give necessary conditions for optimal contracts. Sufficient conditions are hard to establish, but we suggest a way to check sufficiency using non-convex optimization.     

An envelope theorem and some applications to discounted Markov decision processes

In this paper, an Envelope Theorem (ET) will be established for optimization problems on Euclidean spaces. In general, the Envelope Theorems permit analyzing an optimization problem and giving the solution by means of differentiability techniques. The ET will be presented in two versions. One of them uses concavity assumptions, whereas the other one does not require such kind of assumptions. Thereafter, the ET established will be applied to the Markov Decision Processes (MDPs) on Euclidean spaces, discounted and with infinite horizon. As the first application, several examples (including some economic models) of discounted MDPs for which the et allows to determine the value iteration functions will be presented. This will permit to obtain the corresponding optimal value functions and the optimal policies. As the second application of the ET, it will be proved that under differentiability conditions in the transition law, in the reward function, and the noise of the system, the value function and the optimal policy of the problem are differentiable with respect to the state of the system. Besides, various examples to illustrate these differentiability conditions will be provided. This work was partially supported by Benemérita Universidad Aut ónoma de Puebla (BUAP) under grant VIEP-BUAP 38/EXC/06-G, by Consejo Nacional de Ciencia y Tecnología (CONACYT), and by Evaluation-orientation de la COopération Scientifique (ECOS) under grant CONACyT-ECOS M06-M01.     

Components of the Fundamental Category II

In this article we carry on the study of the fundamental category (Goubault and Raussen, Dihomotopy as a tool in state space analysis. In: Rajsbaum, S. (ed.) LATIN 2002: Theoretical Informatics. Lecture Notes in Computer Science, vol. 2286, Cancun, Mexico, pp. 16–37, Springer, Berlin Heidelberg New York, 2002; Goubault, Homology, Homotopy Appl., 5(2): 95–136, 2003) of a partially ordered topological space (Nachbin, Topology and Order, Van Nostrand, Princeton, 1965; Johnstone, Stone Spaces, Cambridge University Press, Cambridge, MA, 1982), as arising in e.g. concurrency theory (Fajstrup et al., Theor. Comp. Sci. 357: 241–278, 2006), initiated in (Fajstrup et al., APCS, 12(1): 81–108, 2004). The “algebra” of dipaths modulo dihomotopy (the fundamental category) of such a po-space is essentially finite in a number of situations. We give new definitions of the component category that are more tractable than the one of Fajstrup et al. (APCS, 12(1): 81–108, 2004), as well as give definitions of future and past component categories, related to the past and future models of Grandis (Theory Appl. Categ., 15(4): 95–146, 2005). The component category is defined as a category of fractions, but it can be shown to be equivalent to a quotient category, much easier to portray. A van Kampen theorem is known to be available on fundamental categories (Grandis, Cahiers Topologie Géom. Différentielle Catég., 44: 281–316, 2003; Goubault, Homology, Homotopy Appl., 5(2): 95–136, 2003), we show in this paper a similar theorem for component categories (conjectured in Fajstrup et al. (APCS, 12(1): 81–108, 2004). This proves useful for inductively computing the component category in some circumstances, for instance, in the case of simple PV mutual exclusion models (Goubault and Haucourt, A practical application of geometric semantics to static analysis of concurrent programs. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005 – Concurrency Theory: 16th International Conference, San Francisco, USA, August 23–26. Lecture Notes in Computer Science, vol. 3653, pp. 503–517, Springer, Berlin Heidelberg New York, 2005), corresponding to partially ordered subspaces of R ⁿ minus isothetic hyperrectangles. In this last case again, we conjecture (and give some hints) that component categories enjoy some nice adjunction relations directly with the fundamental category.      

A note on the regularity of reduced models obtained by nonlocal quasi-continuum-like approaches

The paper investigates model reduction techniques that are based on a nonlocal quasi-continuum-like approach. These techniques reduce a large optimization problem to either a system of nonlinear equations or another optimization problem that are expressed in a smaller number of degrees of freedom. The reduction is based on the observation that many of the components of the solution of the original optimization problem are well approximated by certain interpolation operators with respect to a restricted set of representative components. Under certain assumptions, the “optimize and interpolate” and the “interpolate and optimize” approaches result in a regular nonlinear equation and an optimization problem whose solutions are close to the solution of the original problem, respectively. The validity of these assumptions is investigated by using examples from potential-based and electronic structure-based calculations in Materials Science models. A methodology is presented for using quasi-continuum-like model reduction for real-space DFT computations in the absence of periodic boundary conditions. The methodology is illustrated using a basic Thomas–Fermi–Dirac case study.     

Local c- and E-optimal Designs for Exponential Regression Models

In this paper we investigate local E- and c-optimal designs for exponential regression models of the form . We establish a numerical method for the construction of efficient and local optimal designs, which is based on two results. First, we consider for fixed k the limit μ _i → γ (i = 1, ... , k) and show that the optimal designs converge weakly to the optimal designs in a heteroscedastic polynomial regression model. It is then demonstrated that in this model the optimal designs can be easily determined by standard numerical software. Secondly, it is proved that the support points and weights of the local optimal designs in the exponential regression model are analytic functions of the nonlinear parameters μ ₁, ... , μ _k . This result is used for the numerical calculation of the local E-optimal designs by means of a Taylor expansion for any vector (μ ₁, ... , μ _k ). It is also demonstrated that in the models under consideration E-optimal designs are usually more efficient for estimating individual parameters than D-optimal designs.     

Image segmentation by polygonal Markov Fields

This paper advocates the use of multi-coloured polygonal Markov fields for model-based image segmentation. The formal construction of consistent multi-coloured polygonal Markov fields by Arak–Clifford–Surgailis and its dynamic representation are specialised and adapted to our context. We then formulate image segmentation as a statistical estimation problem for a Gibbsian modification of an underlying polygonal Markov field, and discuss the choice of Hamiltonian. Monte Carlo techniques, including novel Gibbs updates for the Arak model, to estimate the model parameters and find an optimal partition of the image are developed. The approach is applied to image data, the first published application of polygonal Markov fields to segmentation problems in the mathematical literature. Work carried out under project PNA4.3 ‘Stochastic Geometry’. This research was supported by the EC 6th Framework Programme Priority 2 Information Society Technology Network of Excellence MUSCLE (Multimedia Understanding through Semantics, Computation and Learning; FP6-507752), and partially by the Foundation for Polish Science (FNP) and by the Polish Minister of Scientific Research and Information Technology, grant 1 P03A 018 28 (2005-2007) [the third author].     

只有产出(投入)BC~2模型中决策单元效率的几何刻画

在DEA方法中,DEA有效和弱DEA有效的决策单元位于生产前沿面上,非弱DEA有效的DEA无效决策单元位于生产可能集的内部而非生产前沿面上.通过引入生产可能集与生产前沿面移动的思想,证明只有产出(投入)的BC²模型评价下的决策单元的最优值与相应的生产前沿面的移动值存在倒数关系,以双产出(投入)情形图示说明,明确了决策单元在生产可能集中所处的位置.     

Estimation of nonlinear autoregressive models using design-adapted wavelets

We estimate nonlinear autoregressive models using a design-adapted wavelet estimator. We show two properties of the wavelet transform adapted to an autoregressive design. First, in an asymptotic setup, we derive the order of the threshold that removes all the noise with a probability tending to one asymptotically. Second, with this threshold, we estimate the detail coefficients by soft-thresholding the empirical detail coefficients. We show an upper bound on thel ₂-risk of these soft-thresholded detail coefficients. Finally, we illustrate the behavior of this design-adapted wavelet estimator on simulated and real data sets. Financial support from the contract ‘Projet d'Actions de Recherche Concertées’ nr. 98/03-217 from the Belgian government, and from the IAP research network nr. P5/24 of the Belgian State (Federal Office for Scientific, Technical and Cultural Affairs) is gratefully acknowledged.     

Optimal Paths And Costs Of Adjustment In Dynamic DEA Models: With Application To Chilean Department Stores

In this paper we propose a range of dynamic data envelopment analysis (DEA) models which allow information on costs of adjustment to be incorporated into the DEA framework. We first specify a basic dynamic DEA model predicated on a number of simplifying assumptions. We then outline a number of extensions to this model to accommodate asymmetric adjustment costs, non-static output quantities, non-static input prices, and non-static costs of adjustment, technological change, quasi-fixed inputs and investment budget constraints. The new dynamic DEA models provide valuable extra information relative to the standard static DEA models—they identify an optimal path of adjustment for the input quantities, and provide a measure of the potential cost savings that result from recognising the costs of adjusting input quantities towards the optimal point. The new models are illustrated using data relating to a chain of 35 retail department stores in Chile. The empirical results illustrate the wealth of information that can be derived from these models, and clearly show that static models overstate potential cost savings when adjustment costs are non-zero. This paper arises out the senior author's PhD thesis at the University of New England, Australia. The authors gratefully acknowledge Dr. George E. Battese for his comments on earlier drafts of this work.