On the Team Selection Problem

We consider a team selection problem that requires to hire a team of individuals that maximizes a profit function defined as difference of the utility of production and the cost of hiring. We show that for any monotone submodular utility of production and any increasing cost function of the team size with increasing marginal costs, a natural greedy algorithm guarantees a 1 − log(a)/(a − 1)– approximation when a ≤ e and a 1 − a/e(a − 1)–approximation when a ≥ e, where a is the ratio of the utility of production and the hiring cost of a profit-maximizing team selection. We also consider the class of test-score algorithms for maximizing a utility of production subject to a cardinality constraint, where the goal is to hire a team of given size based on greedy choices using individual test scores. We show that the existence of test scores that guarantee a constant-factor approximation is equivalent to the existence of special type of test scores – so called replication test scores. A set of sufficient conditions is identified that implies the existence of replication test scores that guarantee a constant-factor approximation. These sufficient conditions are shown to hold for a large number of classic models of team production, including a monotone concave function of total production, best-shot, and constant elasticity of substitution production function. We also present some results on the performance of different kinds of test scores for different models of team production, and report empirical results using data from a popular online labour platform for software development.