Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.     

Moral coherence,moral worth and explanations of moral motivation

Moral internalism and moral externalism compete over the best explanation of the link between judgment and relevant motivation but, it is argued, they differ at best only verbally. The internalist rational-conceptual nature of the link’ as accounted by M. Smith in The Moral Problem is contrasted to the externalist, also rational, link that requires in addition support from the agent’s psychological-dispositional profile; the internalist link, however, is found to depend crucially on a, similarly to the externalist, psychologically ‘loaded’ profile. It is also argued that the differentiation of the two competing explanations is insufficient partly because they both fail to consider crucial quantitative parameters of the judgment-motivation link. Such parameters become very important particularly in the light of Smith’s claim that this link is grounded on the observable “striking fact” where changes in the set of one’s moral beliefs systematically bring about changes in one’s moral behavior. Examples of algorithms measuring moral coherence and moral worth are provided to serve as evidence for what it comes down to, vis-à-vis the alleged fact, only a verbal dispute between the two camps. Finally, the ‘misfiring’ of these explanations is understood in connection to the irreducibility of concepts such as ‘moral worth’, and/or, ‘moral sensitivity’.     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

Smoothing algorithms for state–space models

Two-filter smoothing is a principled approach for performing optimal smoothing in non-linear non-Gaussian state–space models where the smoothing distributions are computed through the combination of ‘forward’ and ‘backward’ time filters. The ‘forward’ filter is the standard Bayesian filter but the ‘backward’ filter, generally referred to as the backward information filter, is not a probability measure on the space of the hidden Markov process. In cases where the backward information filter can be computed in closed form, this technical point is not important. However, for general state–space models where there is no closed form expression, this prohibits the use of flexible numerical techniques such as Sequential Monte Carlo (SMC) to approximate the two-filter smoothing formula. We propose here a generalised two-filter smoothing formula which only requires approximating probability distributions and applies to any state–space model, removing the need to make restrictive assumptions used in previous approaches to this problem. SMC algorithms are developed to implement this generalised recursion and we illustrate their performance on various problems.     

The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

This paper is concerned with the minimum cost flow problem. It is shown that the class of dual algorithms which solve this problem consists of different variants of a common general algorithm. We develop a new variant which is, in fact, a new form of the ‘primal-dual algorithm’ and which has several interesting properties. It uses, explicitly only dual variables. The slope of the change in the (dual) objective is monotone. The bound on the maximum number of iterations to solve a problem with integral bounds on the flow is better than bounds for other algorithms. This paper is part of the author's doctoral dissertation submitted at Yale University.     

Randomly generated polytopes for testing mathematical programming algorithms

Randomly generated polytopes are used frequently to test and compare algorithms for a variety of mathematical programming problems. These polytopes are constructed by generating linear inequality constraints with coefficients drawn independently from a distribution such as the uniform or the normal. It is noted that this class of ‘random’ polytopes has a special property: the angles between the hyperplanes, though dependent on the specific distribution used, tend to be equal when the dimension of the space increases. Obviously this structure of ‘random’ polytopes may bias test results.     

Quaternion Polar Representation with a Complex Modulus and Complex Argument Inspired by the Cayley-Dickson Form

We present a new polar representation of quaternions inspired by the Cayley-Dickson representation. In this new polar representation, a quaternion is represented by a pair of complex numbers as in the Cayley-Dickson form, but here these two complex numbers are a complex ‘modulus’ and a complex ‘argument’. As in the Cayley-Dickson form, the two complex numbers are in the same complex plane (using the same complex root of −1), but the complex phase is multiplied by a different complex root of −1 in the exponential function. We show how to calculate the ‘modulus’ and ‘argument’ from an arbitrary quaternion in Cartesian form.     

Test of symmetry of a one-dimensional distribution against positive biasedness

Summary Definitions of different strengths are given to the notion of ‘a positively biased random variable’. This notion is related to that of ‘a stochastically larger component of a two-dimensional random vector’, which was introduced previously by the authors. Properties of common rank tests of symmetry about zero against our specification of alternatives are studied in detail. The positive biasedness is extended to ‘positively more biased’. Test of symmetry of a two-dimensional random vector is also referred to.     

Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

ON AN EXTENSION OF ABEL-GONTSCHAROFF＇S EXPANSION FORMULA

We present a constructive generalization of Abel-Gontscharoff＇s series expansion to higher dimensions. A constructive application to a problem of multivariate interpolation is also investigated. In addition, two algorithms for constructing the basis functions of the interpolants are given.     

New decision rules for exact search in N-Queens

This paper presents a set of new decision rules for exact search in N-Queens. Apart from new tiebreaking strategies for value and variable ordering, we introduce the notion of ‘free diagonal’ for decision taking at each step of the search. With the proposed new decision heuristic the number of subproblems needed to enumerate the first K solutions (typically K = 1, 10 and 100) is greatly reduced w.r.t. other algorithms and constitutes empirical evidence that the average solution density (or its inverse, the number of subproblems per solution) remains constant independent of N. Specifically finding a valid configuration was backtrack free in 994 cases out of 1,000, an almost perfect decision ratio. This research is part of a bigger project which aims at deriving new decision rules for CSP domains by evaluating, at each step, a constraint value graph G _c . N-Queens has adapted well to this strategy: domain independent rules are inferred directly from G _c whereas domain dependent knowledge is represented by an induced hypergraph over G _c and computed by similar domain independent techniques. Prior work on the Number Place problem also yielded similar encouraging results.     

Iterative Thresholding Meets Free-Discontinuity Problems

Free-discontinuity problems describe situations where the solution of interest is defined by a function and a lower-dimensional set consisting of the discontinuities of the function. Hence, the derivative of the solution is assumed to be a ‘small’ function almost everywhere except on sets where it concentrates as a singular measure. This is the case, for instance, in crack detection from fracture mechanics or in certain digital image segmentation problems. If we discretize such situations for numerical purposes, the free-discontinuity problem in the discrete setting can be re-formulated as that of finding a derivative vector with small components at all but a few entries that exceed a certain threshold. This problem is similar to those encountered in the field of ‘sparse recovery’, where vectors with a small number of dominating components in absolute value are recovered from a few given linear measurements via the minimization of related energy functionals. Several iterative thresholding algorithms that intertwine gradient-type iterations with thresholding steps have been designed to recover sparse solutions in this setting. It is natural to wonder if and/or how such algorithms can be used towards solving discrete free-discontinuity problems. The current paper explores this connection, and, by establishing an iterative thresholding algorithm for discrete free-discontinuity problems, provides new insights on properties of minimizing solutions thereof.     

Potential,value, and coalition formation

In this paper, a simple probabilistic model of coalition formation provides a unified interpretation for several extensions of the Shapley value. Weighted Shapley values, semivalues, weak (weighted or not) semivalues, and the Shapley value itself appear as variations of this model. Moreover, some notions that have been introduced in the search of alternatives to Shapley’s seminal characterization, as ‘balanced contributions’ and the ‘potential’ are reinterpreted from this point of view. Natural relationships of these conditions with some mentioned families of ‘values’ are shown. These reinterpretations strongly suggest that these conditions are more naturally interpreted in terms of coalition formation than in terms of the classical notion of ‘value.’      

Is There a Conceptual Connection Between Intentionality and Consciousness?

It is argued that Searle’s argument for the thesis that there is a conceptual connection between intentionality and consciousness suffers from serious ambiguities. Searle’s argument is reconstructed as consisting of three premises that contain the notions of aspectual shape and irreducible subjectivity. Having identified two different readings of ‘aspectual shape’ and ‘irreducibly subjective,’ I conclude that each version of Searle’s argument incorporates at least one false premise. This paper is a descendant of a paper presented at the Wittgenstein Symposium at Kirchberg am Wechsel in August 2004. I would like to thank the reviewer of this journal for his/her helpful comments on a previous draft.     

An ‘Emergent Model’ for Rate of Change

Does speed provide a ‘model for’ rate of change in other contexts? Does JavaMathWorlds (JMW), animated simulation software, assist in the development of the ‘model for’ rate of change? This project investigates the transference of understandings of rate gained in a motion context to a non-motion context. Students were 27 14–15 year old students at an Australian secondary school. The instructional sequence, utilising JMW, provided rich learning experiences of rate of change in the context of a moving elevator. This context connects to students’ prior knowledge. The data taken from pre- and post-tests and student interviews revealed a wide variation in students’ understanding of rate of change. The variation was mapped on a hypothetical learning trajectory and interpreted in the terms of the ‘emergent models’ theory (Gravemeijer, Math Think Learn 1(2):155–177, 1999) and illustrated by specific examples from the data. The results demonstrate that most students were able to use the ‘model of’ rate of change developed in a vertical motion context as a ‘model for’ rate of change in a horizontal motion context. A smaller majority of students were able to use their, often incomplete, ‘model of’ rate of change as a ‘model for’ reasoning about rate of change in a non-motion context.     

Predicting syzygies over monomial relations algebras

We show that all projective resolutions over a monomial relations algebra Λ simplify drastically at the stage of the second syzygy; more precisely, we show that the kernel of any homomorphism between two projective left Λ-modules is isomorphic to a direct sum of principal left ideals generated by paths. As consequences, we obtain:

Ploucquet’s “Refutation” of the Traditional Square of Opposition

In the 18th century, Gottfried Ploucquet developed a new syllogistic logic where the categorical forms are interpreted as set-theoretical identities, or diversities, between the full extension, or a non-empty part of the extension, of the subject and the predicate. With the help of two operators ‘O’ (for “Omne”) and ‘Q’ (for “Quoddam”), the UA and PA are represented as ‘O(S) – Q(P)’ and ‘Q(S) – Q(P)’, respectively, while UN and PN take the form ‘O(S) > O(P)’ and ‘Q(S) > O(P)’, where ‘>’ denotes set-theoretical disjointness. The use of the symmetric operators ‘–’ and ‘>’ gave rise to a new conception of conversion which in turn lead Ploucquet to consider also the unorthodox propositions O(S) – O(P), Q(S) – O(P), O(S) > Q(P), and Q(S) > Q(P). Although Ploucquet’s critique of the traditional theory of opposition turns out to be mistaken, his theory of the “Quantification of the Predicate” is basically sound and involves an interesting “Double Square of Opposition”. My thanks are due to Hanno von Wulfen for helpful discussions and for transforming the word-document into a Latex-file.