Abstract:
The path-difference metric is one of the oldest distances for the comparison of fully resolved phylogenetic trees, but its statistical properties are still quite unknown. In this paper we compute the mean value of the square of the path-difference metric between two fully resolved rooted phylogenetic trees with $n$ leaves, under the uniform distribution. This complements previous work by Steel and Penny, who computed this mean value for fully resolved unrooted phylogenetic trees.

Abstract:
The Shapley Value and the Fair Proportion Index of phylogenetic trees have been frequently discussed as prioritization tools in conservation biology. Both indices rank species according to their contribution to total phylogenetic diversity, allowing for a simple conservation criterion. While both indices have their specific advantages and drawbacks, it has recently been shown that both values are closely related. However, as different authors use different definitions of the Shapley Value, the specific degree of relatedness depends on the specific version of the Shapley Value - it ranges from a high correlation index to equality of the indices. In this note, we first give an overview of the different indices. Then we turn our attention to the mere ranking order provided by either of the indices. We show that even though the chance of two rankings being exactly identical (when obtained from different versions of the Shapley Value) decreases with an increasing number of taxa, the distance between the two rankings converges to zero, i.e. the rankings are becoming more and more alike. Moreover, we introduce our software package FairShapley, which was implemented in Perl and with which all calculations have been performed.

Abstract:
For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley and Martin Shubik in 1954 \cite{SS54} and are widely studied in social choice theory as a measure of the "influence" of voters. The \emph{Inverse Shapley Value Problem} is the problem of designing a weighted voting scheme which (approximately) achieves a desired input vector of values for the Shapley-Shubik indices. Despite much interest in this problem no provably correct and efficient algorithm was known prior to our work. We give the first efficient algorithm with provable performance guarantees for the Inverse Shapley Value Problem. For any constant $\eps > 0$ our algorithm runs in fixed poly$(n)$ time (the degree of the polynomial is independent of $\eps$) and has the following performance guarantee: given as input a vector of desired Shapley values, if any "reasonable" weighted voting scheme (roughly, one in which the threshold is not too skewed) approximately matches the desired vector of values to within some small error, then our algorithm explicitly outputs a weighted voting scheme that achieves this vector of Shapley values to within error $\eps.$ If there is a "reasonable" voting scheme in which all voting weights are integers at most $\poly(n)$ that approximately achieves the desired Shapley values, then our algorithm runs in time $\poly(n)$ and outputs a weighted voting scheme that achieves the target vector of Shapley values to within error $\eps=n^{-1/8}.$

Abstract:
Following the original interpretation of the Shapley value (Shapley, 1953a) as a priori evaluation of the prospects of a player in a multi-person interaction situation, we propose a group value, which we call the Shapley group value, as a priori evaluation of the prospects of a group of players in a coalitional game when acting as a unit. We study its properties and we give an axiomatic characterization. Relaying on this valuation we analyze the profitability of a group. We motivate our proposal by means of some relevant applications of the Shapley group value, when it is used as an objective function by a decisionmaker who is trying to identify an optimal group of agents in a framework in which agents interact and the attained benefit can be modeled bymeans of a transferable utility game. As an illustrative examplewe analyze the problem of identifying the set of key agents in a terrorist network.

Abstract:
In this paper we extend the notion of Shapley value to the stochastic cooperative games. We give the definition of marginal vector to the stochastic cooperative games and we define the Shapley value for this game. Furthermore, we discuss the axioms of the Shapley value and give the proofs of these axioms.

Abstract:
This paper introduces a measure of uncertainty in the determination of the Shapley value, illustrates it with examples, and studies some of its properties. The introduced measure of uncertainty quantifies random variations in a player's marginal contribution during the bargaining process. The measure is symmetric with respect to exchangeable substitutions in the players, equal to zero for dummy player, and convex in the game argument. The measure is illustrated by several examples of abstract games and an example from epidemiology.

Abstract:
We propose the study of computing the Shapley value for a new class of cooperative games that we call budgeted games, and investigate in particular knapsack budgeted games, a version modeled after the classical knapsack problem. In these games, the "value" of a set $S$ of agents is determined only by a critical subset $T\subseteq S$ of the agents and not the entirety of $S$ due to a budget constraint that limits how large $T$ can be. We show that the Shapley value can be computed in time faster than by the na\"ive exponential time algorithm when there are sufficiently many agents, and also provide an algorithm that approximates the Shapley value within an additive error. For a related budgeted game associated with a greedy heuristic, we show that the Shapley value can be computed in pseudo-polynomial time. Furthermore, we generalize our proof techniques and propose what we term algorithmic representation framework that captures a broad class of cooperative games with the property of efficient computation of the Shapley value. The main idea is that the problem of determining the efficient computation can be reduced to that of finding an alternative representation of the games and an associated algorithm for computing the underlying value function with small time and space complexities in the representation size.

Abstract:
The search for similarity and dissimilarity measures on phylogenetic trees has been motivated by the computation of consensus trees, the search by similarity in phylogenetic databases, and the assessment of clustering results in bioinformatics. The transposition distance for fully resolved phylogenetic trees is a recent addition to the extensive collection of available metrics for comparing phylogenetic trees. In this paper, we generalize the transposition distance from fully resolved to arbitrary phylogenetic trees, through a construction that involves an embedding of the set of phylogenetic trees with a fixed number of labeled leaves into a symmetric group and a generalization of Reidys-Stadler's involution metric for RNA contact structures. We also present simple linear-time algorithms for computing it.

Abstract:
In a cooperative transferable utilities game, the allocation of the win of the
grand coalition is an Egalitarian Allocation, if this win is divided into equal
parts among all players. The Inverse Set relative to the Shapley Value of a
game is a set of games in which the Shapley Value is the same as the initial
one. In the Inverse Set, we determined a family of games for which the Shapley
Value is also a coalitional rational value. The Egalitarian Allocation of the
game is efficient, so that in the set called the Inverse Set relative to the Shapley
Value, the allocation is the same as the initial one, but may not be coalitional
rational. In this paper, we shall find out in the same family of the Inverse
Set, a subfamily of games with the Egalitarian Allocation is also a coalitional
rational value. We show some relationship between the two sets of
games, where our values are coalitional rational. Finally, we shall discuss the
possibility that our procedure may be used for solving a very similar problem
for other efficient values. Numerical examples show the procedure to get solutions
for the efficient values.

Abstract:
Many processes and models --in biological, physical, social, and other contexts-- produce trees whose depth scales logarithmically with the number of leaves. Phylogenetic trees, describing the evolutionary relationships between biological species, are examples of trees for which such scaling is not observed. With this motivation, we analyze numerically two branching models leading to non-logarithmic scaling of the depth with the number of leaves. For Ford's alpha model, although a power-law scaling of the depth with tree size was established analytically, our numerical results illustrate that the asymptotic regime is approached only at very large tree sizes. We introduce here a new model, the activity model, showing analytically and numerically that it also displays a power-law scaling of the depth with tree size at a critical parameter value.