Competitive subset selection with two agents

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).     

Optimal constrained selection of a measurable subset

Necessary and sufficient conditions are given for a class of optimization problems involving optimal selection of a measurable subset from a given measure space subject to set function inequality constraints. Results are developed firstly for the case where the set functions involved possess a differentiability property and secondly where a type of convexity is present. These results are then used to develop numerical methods. It is shown that in a special case the optimal set can be obtained via solution of a fixed point problem in Euclidean space.     

A note on subset selection for matrices

In an earlier paper the authors examined the problem of selecting rows of a matrix so that the resulting matrix is as “non-singular” as possible. However, the proof of the key result in that paper is not constructive. In this note we give a constructive proof for that result. In addition, we examine a case where as non-singular as possible means maximizing a determinant and provide a new bound and a constructive proof for this case also.     

Bayesian subset selection for threshold autoregressive moving-average models

Optimal subset selection among a general family of threshold autoregressive moving-average (TARMA) models is considered. The usual complexity of model/order selection is increased by capturing the uncertainty of unknown threshold levels and an unknown delay lag. The Monte Carlo method of Bayesian model averaging provides a possible way to overcome such model uncertainty. Incorporating with the idea of Bayesian model averaging, a modified stochastic search variable selection method is adapted to consider subset selection in TARMA models, by adding latent indicator variables for all potential model lags as part of the proposed Markov chain Monte Carlo sampling scheme. Metropolis–Hastings methods are employed to deal with the well-known difficulty of including moving-average terms in the model and a novel proposal mechanism is designed for this purpose. Bayesian comparison of two hyper-parameter settings is carried out via a simulation study. The results demonstrate that the modified method has favourable performance under reasonable sample size and appropriate settings of the necessary hyper-parameters. Finally, the application to four real datasets illustrates that the proposed method can provide promising and parsimonious models from more than 16 million possible subsets.     

Empirical likelihood-based subset selection for partially linear autoregressive models

Based on the empirical likelihood method, the subset selection and hypothesis test for parameters in a partially linear autoregressive model are investigated. We show that the empirical log-likelihood ratio at the true parameters converges to the standard chi-square distribution. We then present the definitions of the empirical likelihood-based Bayes information criteria （EBIC） and Akaike information criteria （EAIC）. The results show that EBIC is consistent at selecting subset variables while EAIC is not. Simulation studies demonstrate that the proposed empirical likelihood confidence regions have better coverage probabilities than the least square method, while EBIC has a higher chance to select the true model than EAIC.     

Solving feature subset selection problem by a Parallel Scatter Search

The aim of this paper is to develop a Parallel Scatter Search metaheuristic for solving the Feature Subset Selection Problem in classification. Given a set of instances characterized by several features, the classification problem consists of assigning a class to each instance. Feature Subset Selection Problem selects a relevant subset of features from the initial set in order to classify future instances. We propose two methods for combining solutions in the Scatter Search metaheuristic. These methods provide two sequential algorithms that are compared with a recent Genetic Algorithm and with a parallelization of the Scatter Search. This parallelization is obtained by running simultaneously the two combination methods. Parallel Scatter Search presents better performance than the sequential algorithms.     

An effective procedure for feature subset selection in logistic regression based on information criteria

Computational Optimization and Applications - In this paper, the problem of best subset selection in logistic regression is addressed. In particular, we take into account formulations of the...     

Machine learning-based surrogate modeling for data-driven optimization: a comparison of subset selection for regression techniques

Optimization of simulation-based or data-driven systems is a challenging task, which has attracted significant attention in the recent literature. A very e     

Epidemics in two competing species

An SIS epidemic model in two competing species with the mass action incidence is formulated and analysed. Thresholds for the existence of boundary equilibria are identified and conditions for their local asymptotic stability or instability are found. By persistence theory, conditions for the persistence of either hosts or pathogens are proved. Using Hopf bifurcation theory and numerical simulations, some aspects of the complicated dynamic behaviours of the model are shown: the system may have zero up to three internal equilibria, may have a stable limit cycle, may have three stable attractors. Through the results on persistence and stability of the boundary equilibria, some important interactions between infection and competition are revealed: (1) a species that would become extinct without the infection, may persist in presence of the infection; (2) a species that would coexist with its competitor without the infection, is driven to extinction by the infection; (3) an infection that would die out in either species without the interinfection of disease, may persist in both species in presence of this factor.     

Counting polynomial subset sums

Let D be a subset of a finite commutative ring R with identity. Let \(f(x)\in R[x]\) be a polynomial of degree d. For a nonnegative integer k, we study the number \(N_f(D,k,b)\) of k-subsets S in D such that

$$\begin{aligned} \sum _{x\in S} f(x)=b. \end{aligned}$$

In this paper, we establish several bounds for the difference between \(N_f(D,k, b)\) and the expected main term \(\frac{1}{|R|}{|D|\atopwithdelims ()k}\), depending on the nature of the finite ring R and f. For \(R=\mathbb {Z}_n\), let \(p=p(n)\) be the smallest prime divisor of n, \(|D|=n-c \ge C_dn p^{-\frac{1}{d}}\,+\,c\) and \(f(x)=a_dx^d +\cdots +a_0\in \mathbb {Z}[x]\) with \((a_d, \ldots , a_1, n)=1\). Then

$$\begin{aligned} \left| N_f(D, k, b)-\frac{1}{n}{n-c \atopwithdelims ()k}\right| \le {\delta (n)(n-c)+(1-\delta (n))\left( C_dnp^{-\frac{1}{d}}+c\right) +k-1\atopwithdelims ()k}, \end{aligned}$$

answering an open question raised by Stanley (Enumerative combinatorics, 1997) in a general setting, where \(\delta (n)=\sum _{i\mid n, \mu (i)=-1}\frac{1}{i}\) and \(C_d=e^{1.85d}\). Furthermore, if n is a prime power, then \(\delta (n) =1/p\) and one can take \(C_d=4.41\). Similar and stronger bounds are given for two more cases. The first one is when \(R=\mathbb {F}_q\), a q-element finite field of characteristic p and f(x) is general. The second one is essentially the well-known subset sum problem over an arbitrary finite abelian group. These bounds extend several previous results.

     

Bargaining in competing supply chains with uncertainty

Substantial literature has been devoted to supply chain coordination. The majority of this literature ignores competition between supply chains. Moreover, a significant part of this literature focuses on coordination that induce the supply chain members to follow strategies that produce the equilibria chosen by a vertically integrated supply chain. This paper investigates the equilibrium behavior of two competing supply chains in the presence of demand uncertainty. We consider joint pricing and quantity decisions and competition under three possible supply chain strategies: Vertical Integration (VI), Manufacturer’s Stackelberg (MS), and Bargaining on the Wholesale price (BW(α), α is the bargaining parameter) over a single or infinitely many periods. We show that, in contrast to earlier literature, using VIVI (VI in both chains) is the unique Nash Equilibrium over one period decision, while using MSMS or BW(α)BW(α) may be Nash Equilibrium over infinitely many periods.     

A U-statistic test in competing risk models

We consider a situation in which systems are subject to failure from competing risks or could be censored from an independent censoring process. A procedure, based on a U-statistic, is proposed for testing the equality of two failure rates in the competing risks set. Under independence assumptions, the asymptotic distribution of the statistic is given and used to construct the test. To cite this article: N. Molinari, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Hamiltonian uniform subset graphs

The uniform subset graph G(n, k, t) is defined to have all k-subsets of an n-set as vertices and edges joining k-subsets intersecting at t elements. We conjecture that G(n, k, t) is hamiltonian when it is different from the Petersen graph and does possess cycles. We verify this conjecture for k − t = 1, 2, 3 and for suitably large n when t = 0, 1.     

On harvesting two competing populations

The problem of harvesting two competing populations is formulated in an optimal control setting. The maximum sustained rent (MSR) solution is introduced and is shown to be not only totally singular, but also to play a central role in solutions to the harvesting problem. It is further shown that nonsingular extremal subarcs must in general approach and leave the MSR along partially singular curves. A numerical example is introduced to demonstrate this phenomenon. In the case where the populations are driven onto the MSR in minimum time, however, the optimal control is shown to be bang-bang with at most one switch.The author is indebted to Professor D. H. Jacobson and Dr. D. H. Martin for helpful discussions during the preparation of this paper.     

Tightness in subset bounds for coherent configurations

Association schemes have many applications to the study of designs, codes, and geometries and are well studied. Coherent configurations are a natural generalization of association schemes, however, analogous applications have yet to be fully explored. Recently, Hobart [Mich. Math. J. 58:231–239, 2009] generalized the linear programming bound for association schemes, showing that a subset Y of a coherent configuration determines positive semidefinite matrices, which can be used to constrain certain properties of the subset. The bounds are tight when one of these matrices is singular, and in this paper we show that this gives information on the relations between Y and any other subset. We apply this result to sets of nonincident points and lines in coherent configurations determined by projective planes (where the points of the subset correspond to a maximal arc) and partial geometries.