On the improvement of allocation rules for multi-armed bandit problem

In this note we present a method to modify allocation rules which is useful for multi-armed bandit problems also for the finite-horizon case. The method is based on monotonicity properties of the value function and the structure of certain optimal policies. It is applied to the well-known allocation rule of Bather (1985). The performance of improvement is investigated by a numerical case study     

The relation between non-bossiness and monotonicity

It is a well-known fact that in some economic environments, non-bossiness and monotonicity are interrelated. In this paper, we have presented a new domain-richness condition called weak monotonic closedness, on which non-bossiness in conjunction with individual monotonicity is equivalent to monotonicity. Moreover, by applying our main result to several types of economies, we have obtained characterizations in terms of non-bossiness.     

The outflow ranking method for weighted directed graphs

A ranking method assigns to every weighted directed graph a (weak) ordering of the nodes. In this paper we axiomatize the ranking method that ranks the nodes according to their outflow using four independent axioms. Besides the well-known axioms of anonymity and positive responsiveness we introduce outflow monotonicity – meaning that in pairwise comparison between two nodes, a node is not doing worse in case its own outflow does not decrease and the other node’s outflow does not increase – and order preservation – meaning that adding two weighted digraphs such that the pairwise ranking between two nodes is the same in both weighted digraphs, then this is also their pairwise ranking in the ‘sum’ weighted digraph. The outflow ranking method generalizes the ranking by outdegree for directed graphs, and therefore also generalizes the ranking by Copeland score for tournaments.     

Cross-ranking of Decision Making Units in Data Envelopment Analysis

Data Envelopment Analysis (DEA) is a mathematical model that evaluates the relative efficiency of Decision Making Units (DMUs) with multiple input and output. In some applications of DEA, ranking of the DMUs are important. For this purpose, a number of approaches have been introduced. Among them is the cross-efficiency method. The method utilizes the result of the cross-efficiency matrix and averages the cross-efficiency scores of each DMU. Ranking is then performed based on the average efficiency scores. In this paper, we proposed a new way of handling the information from the cross-efficiency matrix. Based on the notion that the ranking order is more important than individual efficiency score, the cross-efficiency matrix is converted to a cross-ranking matrix. A cross-ranking matrix is basically a cross-efficiency matrix with the efficiency score of each element being replaced with the ranking order of that efficiency score with respect to the other efficiency scores in a column. By so doing, each DMU assume the role of a decision maker and how they voted or ranked the other DMUs are reflected in their respective column of the cross-ranking matrix. These votes are then aggregated using a preference aggregation method to determine the overall ranking of the DMUs. Comparison with an existing cross-efficiency method indicates a relatively better result through usage of the proposed method.     

Nonmonotone Globalization Techniques for the Barzilai-Borwein Gradient Method

In this paper we propose new globalization strategies for the Barzilai and Borwein gradient method, based on suitable relaxations of the monotonicity requirements. In particular, we define a class of algorithms that combine nonmonotone watchdog techniques with nonmonotone linesearch rules and we prove the global convergence of these schemes. Then we perform an extensive computational study, which shows the effectiveness of the proposed approach in the solution of large dimensional unconstrained optimization problems.     

Exit criteria and monotonicity in compound quadrature of Gaussian type

Summary In this short note, for compound quadrature rules of Gaussian type, we prove stopping rules and monotonicity results based on Peano-kernel methods.     

Structured policies in the sequential design of experiments

A general control model under uncertainty is considered. Using a Bayesian approach and dynamic programming, we investigate structural properties of optimal decision rules. In particular, we show the monotonicity of the total expected reward and of the so-called Gittins-Index. We extend the stopping rule and the stay-on-a-winner rule, which are well-known in bandit problems. Our approach is based on the multivariate likelihood ratio order andTP ₂ functions.     

Tabu Search directed by direct search methods for nonlinear global optimization

In recent years, there has been a great deal of interest in metaheuristics in the optimization community. Tabu Search (TS) represents a popular class of metaheuristics. However, compared with other metaheuristics like genetic algorithm and simulated annealing, contributions of TS that deals with continuous problems are still very limited. In this paper, we introduce a continuous TS called Directed Tabu Search (DTS) method. In the DTS method, direct-search-based strategies are used to direct a tabu search. These strategies are based on the well-known Nelder–Mead method and a new pattern search procedure called adaptive pattern search. Moreover, we introduce a new tabu list conception with anti-cycling rules called Tabu Regions and Semi-Tabu Regions. In addition, Diversification and Intensification Search schemes are employed. Numerical results show that the proposed method is promising and produces high quality solutions.     

Comparison principle and analogues of the phragmen—lindelöf theorem for solutions of parabolic inequalities

It is well known that a Monotonicity Condition and a Coerciveness Condition principally lie in the basis of most results of the Theory of PDE's. The necessity of these important assumptions for the validity of a comparison principle and analogues of the Phragmen-Lindelöf theorem for solutions of quasilinear parabolic inequalities is discussed in the paper. In the first part of the work we introduce a new concept of monotonicity for nonlinear differential operators-nonlinear monotonicity concept-and on its basis we obtain new phenomena for solutions, subsolutions and supersolutions of the well-known quasilinear differential equations. In the second part we omit the current coerciveness condition and change it by a weaker one. In spite of this we obtain a series of new qualitative properties of solutions for wide classes of quasilinear parabolic inequalities. Most of these properties are also new for solutions of the well-known equations, which we consider in the paper.     

基于网络客户评论的产品口碑排序方法

电子商务时代,产品的网络口碑已成为消费者做购买决策的重要参考依据。本文利用客户评论信息,依据产品的评分及产品之间的对比投票数据,提出了一个新的产品口碑排序方法。首先利用产品两两间的对比投票计算各自的相对口碑,再采用贝叶斯平均方法修正原始客户评分,然后将二者结合得到产品的总口碑,进而对产品的网络口碑进行排序。实验数据采自第三方点评网站中的产品对比投票数据,实验结果表明本文提出的产品口碑排序方法具有较高的支持度,且与产品销量排序的相关性也很高。     

网页排序中的随机模型及算法

随着互联网规模的日益增长, 搜索引擎已经成为互联网上有效的信息获取工具. 而在众多搜索引擎的背后, 是信息检索技术, 也即网页排序算法在起作用. 网页排序包括重要性排序和相关性排序. 通过我们研究发现, 尽管这两类排序所依据的准则不同, 但是都可以通过建立适当的随机过程模型来研究. 对于网页重要性排序, 我们通过分析用户浏览网页的行为建立了Markov 骨架过程的框架. 基于该框架我们分析了三种不同的随机过程模型对用户行为模拟的合理程度, 并设计了名为BrowseRank 的一组新算法, 该算法可以根据用户上网行为来计算网页的重要性. 在网页相关性排序中, 我们主要针对排序结果联合问题建立了一个基于Markov 链的监督学习框架. 通过将传统方法的监督化, 使原来难于解决的问题变的易于学习, 将原来的NP- 难问题转化为一个半正定规划问题, 提高了效率.     

Modeling social services performance: a four-stage DEA approach to evaluate fundraising efficiency,capacity building,service quality,and effectiveness in the nonprofit sector

The Swedish electoral system exhibits significant levels of proportionality compared with the systems used in other countries. However, it has several deficiencies that could be corrected. Therefore, this paper (a) evaluates the current Swedish electoral system by identifying the imbalances in the representation of political parties and the sizes of the electoral constituencies that can occur and (b) presents two proposals for improvement that seek to correct the previously identified deficiencies. The first proposal consists of a slight modification of the current system that applies when parties get more seats than they proportionally deserve according to their global number of votes, as occurred in the 2010 election. In this case, the proposal includes a criterion so that the overrepresented parties return their excess seats. The second proposal relies on the implementation of biproportional allotments and on the replacement of the electoral thresholds of 4 % of the total votes nationwide and 12 % of the votes in a given constituency by a new threshold based on a reduction in the number of votes of the parties. The application of any of these proposals to the Swedish election held in 2010 reveals that the deficiencies in the representation of political parties are eliminated. Furthermore, the second proposal also corrects the deficiencies in the sizes of the electoral constituencies for Sweden.     

A new globalization technique for nonlinear conjugate gradient methods for nonconvex minimization

It is well-known that the HS method and the PRP method may not converge for nonconvex optimization even with exact line search. Some globalization techniques have been proposed, for instance, the PRP+ globalization technique and the Grippo-Lucidi globalization technique for the PRP method. In this paper, we propose a new efficient globalization technique for general nonlinear conjugate gradient methods for nonconvex minimization. This new technique utilizes the information of the previous search direction sufficiently. Under suitable conditions, we prove that the nonlinear conjugate gradient methods with this new technique are globally convergent for nonconvex minimization if the line search satisfies Wolfe conditions or Armijo condition. Extensive numerical experiments are reported to show the efficiency of the proposed technique.     

A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems

In this paper we propose a new algorithm for solving difficult large-scale global optimization problems. We draw our inspiration from the well-known DIRECT algorithm which, by exploiting the objective function behavior, produces a set of points that tries to cover the most interesting regions of the feasible set. Unfortunately, it is well-known that this strategy suffers when the dimension of the problem increases. As a first step we define a multi-start algorithm using DIRECT as a deterministic generator of starting points. Then, the new algorithm consists in repeatedly applying the previous multi-start algorithm on suitable modifications of the variable space that exploit the information gained during the optimization process. The efficiency of the new algorithm is pointed out by a consistent numerical experimentation involving both standard test problems and the optimization of Morse potential of molecular clusters.     

Neighborhood monotonicity, the extended Zermelo model, and symmetric knockout tournaments

In this paper, neighborhood monotonicity is presented as a natural property for methods of ranking generalized tournaments (directed graphs with weighted edges). An extension of Zermelo’s classical method of ranking tournaments is shown to have this property. An estimate is made of the proportion of ordered pairs that all neighborhood-monotonic rankings of symmetric knockout tournaments have in common. Finally, numerical evidence for the asymptotic behavior of the extended Zermelo ranking of symmetric knockout tournaments is presented.     

Circumstantial power: Optimal persuadable voters

Let us suppose that certain committee is going to decide, using some fixed voting rules, either to accept or to reject a proposal that affects your interests. From your perception about each voter’s position, you can make an a priori estimation of the probability of the proposal being accepted. Wishing to increase this probability of acceptance before the votes are cast, assume further that you are able to convince (at least) one voter to improve his/her perception in favor of the proposal. The question is: which voters should be persuaded in order to get the highest possible increase in the probability of acceptance? In other words, which are the optimal persuadable voters? To answer this question a measure of “circumstantial power” is considered in this paper, which is useful to identify optimal persuadable voters. Three preorderings in the set of voters, based on the voting rules, are defined and they are used for finding optimal persuadable voters, even in the case that only a qualitative ranking of each voter’s inclination for the proposal has been made.     

Statistical ranking and combinatorial Hodge theory

We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian, which is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We shall study the graph Helmholtzian using combinatorial Hodge theory, which provides a way to unravel ranking information from edge flows. In particular, we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the l ₂-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained—if this is large, then it indicates that the data does not have a good global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency in the ranking data arises locally or globally. When applied to statistical ranking problems, Hodge decomposition sheds light on whether a given dataset may be globally ranked in a meaningful way or if the data is inherently inconsistent and thus could not have any reasonable global ranking; in the latter case it provides information on the nature of the inconsistencies. An obvious advantage over the NP-hardness of Kemeny optimization is that HodgeRank may be easily computed via a linear least squares regression. We also discuss connections with well-known ordinal ranking techniques such as Kemeny optimization and Borda count from social choice theory.     

Model Based Comparison of Discounted Cumulative Gain and Average Precision

In this paper, we propose to explain Discounted Cumulative Gain (DCG) as the expectation of the total utility collected by a user given a generative probabilistic model on how users browse the result page ranking list of a search engine. We contrast this with a generalization of Average Precision, pAP, that has been defined in Dupret and Piwowarski (2010) [13]. In both cases, user decision models coupled with Web search logs allow to estimate some parameters that are usually left to the designer of a metric. In this paper, we compare the user models for DCG and pAP at the interpretation and experimental level.DCG and AP are metrics computed before a ranking function is exposed to users and as such, their role is to predict the function performance. In counterpart to prognostic metric, a diagnostic metric is computed after observing the user interactions with the result list. A commonly used diagnostic metric is the clickthrough rate at position 1, for example. In this work we show that the same user model developed for DCG can be used to derive a diagnostic version of this metric. The same hold for pAP and any metric with a proper user model.We show that not only does this diagnostic view provide new information, it also allows to define a new criterion for assessing a metric. In previous works based on user decision modeling, the performance of different metrics were compared indirectly in terms of the ability of the associated user model to predict future user actions. Here we propose a new and more direct criterion based on the ability of the prognostic version of the metric to predict the diagnostic performance.     

Merit functions and error bounds for constrained mixed set-valued variational inequalities via generalized f-projection operators

In this paper, we introduce and investigate a constrained mixed set-valued variational inequality (MSVI) in Hilbert spaces. We prove the solution set of the constrained MSVI is a singleton under strict monotonicity. We also propose four merit functions for the constrained MSVI, that is, the natural residual, gap function, regularized gap function and D-gap function. We further use these functions to obtain error bounds, i.e. upper estimates for the distance to solutions of the constrained MSVI under strong monotonicity and Lipschitz continuity. The approach exploited in this paper is based on the generalized f-projection operator due to Wu and Huang, but not the well-known proximal mapping.     

Bordism invariants of the mapping class group

We define new bordism and spin bordism invariants of certain subgroups of the mapping class group of a surface. In particular, they are invariants of the Johnson filtration of the mapping class group. The second and third terms of this filtration are the well-known Torelli group and Johnson subgroup, respectively. We introduce a new representation in terms of spin bordism, and we prove that this single representation contains all of the information given by the Johnson homomorphism, the Birman-Craggs homomorphism, and the Morita homomorphism.