3
$\begingroup$

In the process of computing Shapley values, I observed an interesting combinatorial constant. I am not exactly sure where such behavior comes. And here is the conjecture.

Notations

For any finite non-empty sequence of number $Q \subset \mathbb{R}$, I can construct a vector $C = (c_0, c_1, c_2, \cdots, c_{|Q|})$ using such a mapping $C(Q)$: $$ \sum_{i=0}^{|Q|} c_i x^ i = \prod_{q_i \in Q} (1+q_ix) $$

Given a sequence $A = a_1, a_2, \cdots, a_m $, denote $A_{\neg i}$ as $A \setminus \{a_i\}$. $|A| = m$ denotes size/length of $A$ is $m$. With size $m \in \mathbb{N}$, denote a constant vector $N(m)$ as $(1/{m-1 \choose 0}, 1/{m-1 \choose 1}, \cdots, 1/{m-1 \choose m-1 } )$. And $\langle\cdot, \cdot \rangle$ is the inner product operation.

Conjecture

For any finite non-empty sequence $A \subset \mathbb{R}$ with $|A| = m$, i conjecture if $0 \in A$ then:

$$ \sum_{i \in A} (1 - i) \langle C(A_{\neg i}), N(m) \rangle = m $$

I'm able to obtain consistent results from simulations, but I don't know how to prove it. Any help on a proof/dis-proof would be appreciated!

Example

For $A = 1, 2, 3$, the size $m$ is clearly 3.

$A_{\neg 1} = 2, 3$, $A_{\neg 2} = 1, 3$, $A_{\neg 3} = 1, 2$

$C(A_{\neg 1}) = (1, 5, 6)$, $C(A_{\neg 2}) = (1, 4, 3)$, $C(A_{\neg 3}) = (1, 3, 2)$.

$N(3) = (1, 0.5, 1)$

$$ (1-1)* \langle (1, 5, 6), (1, 0.5, 1) \rangle \\ + (1-2)* \langle (1, 4, 3), (1, 0.5, 1) \rangle \\ + (1-3)* \langle (1, 3, 2), (1, 0.5, 1) \rangle \\ = -15 $$ which is not $m$.

On the other hand: For $A=0, 2, 3$, the size $m$ is still 3.

$A_{\neg 0} = 2, 3$, $A_{\neg 2} = 0, 3$, $A_{\neg 3} = 0, 2$

$C(A_{\neg 0}) = (1, 5, 6)$, $C(A_{\neg 2}) = (1, 3, 0)$, $C(A_{\neg 3}) = (1, 2, 0)$.

$N(3) = (1, 0.5, 1)$

$$ (1-0)* \langle (1, 5, 6), (1, 0.5, 1) \rangle \\ + (1-2)* \langle (1, 3, 0), (1, 0.5, 1) \rangle \\ + (1-3)* \langle (1, 2, 0), (1, 0.5, 1) \rangle \\ = 3 $$ which is $m$.

$\endgroup$
15
  • $\begingroup$ So, if I'm correctly understanding your question, you are claiming that if $a_1, a_2, \ldots, a_m$ are $m$ numbers, and if $k$ is a nonnegative integer, then $\sum\limits_{i=1}^k \dfrac{e_k\left(a_1, a_2, \ldots, \widehat{a_i}, \ldots, a_m\right)}{\dbinom{m-1}{k}} - \sum\limits_{i=1}^k a_i \dfrac{e_{k-1}\left(a_1, a_2, \ldots, \widehat{a_i}, \ldots, a_m\right)}{\dbinom{m-1}{k-1}}$ equals $0$ when $k$ is positive and equals $m$ if $k = 0$. Here, $e_k$ means the $k$-th elementary symmetric polynomial (which is $0$ if $k$ is negative). This should be easy: compute each monomial's coefficient. $\endgroup$ Nov 24, 2021 at 23:07
  • $\begingroup$ And easy it is: The coefficient of a given monomial $a_{i_1} a_{i_2} \cdots a_{i_k}$ (with $i_1, i_2, \ldots, i_k$ being distinct) is $\dfrac{m-k}{\dbinom{m-1}{k}} - \dfrac{k}{\dbinom{m-1}{k-1}} = 0$. All other monomials have coefficient $0$ since they appear in neither of the two sums. $\endgroup$ Nov 24, 2021 at 23:10
  • $\begingroup$ not completely sure I follow the newly constructed term, but $ 0 \in A$ is the condition, basically at least one of $a_1, \cdots, a_m$ is 0. $\endgroup$
    – yupbank
    Nov 24, 2021 at 23:11
  • $\begingroup$ That condition isn't necessary. $\endgroup$ Nov 24, 2021 at 23:11
  • 1
    $\begingroup$ @yupbank: I will after tomorrow's FPSAC deadline. $\endgroup$ Nov 25, 2021 at 5:19

1 Answer 1

2
$\begingroup$

We can rewrite $$\sum_{i=0}^{|Q|} c_i x^ i = \prod_{q_i \in Q} (1+q_ix)$$ as $$c_i = \sum_{\substack{S \subseteq Q \\ |S| = i}} \prod_{q \in S} q$$

Then $$\sum_{a \in A} (1 - a) \langle C(A_{\neg a}), N(m) \rangle$$ can be split into two sums: $$\left(\sum_{a \in A} \langle C(A_{\neg a}), N(m) \rangle \right) - \left(\sum_{a \in A} a \langle C(A_{\neg a}), N(m) \rangle \right)$$ Call the first sum $L$ (for lower) and the second sum $U$ (for upper). Note that $L$ only contains terms with products of $0$ to $m-1$ elements of $A$, and $U$ only contains terms with products of $1$ to $m$ elements of $A$.

Consider a subset $S \subset A$ of size $0 < k < m$. It occurs in $L$ once for every $a \in A \setminus S$ and each time with weight $\binom{m-1}{k}^{-1}$ from the dot product, for a total weight of $(m-k)\binom{m-1}{k}^{-1} = \frac{(m-k)!k!}{(m-1)!}$; it occurs in $U$ once for every $a \in S$ and each time with weight $\binom{m-1}{k-1}^{-1}$ from the dot product, for a total weight of $k\binom{m-1}{k-1}^{-1} = \frac{(m-k)!k!}{(m-1)!}$; and so all of these terms cancel.

Therefore the only terms which survive are the term from $L$ corresponding to the subset of size $0$ and the term from $U$ corresponding to the subset of size $m$. The former occurs with weight $\frac{(m-0)!0!}{(m-1)!} = m$; the latter with weight $\frac{(m-m)!m!}{(m-1)!} = m$ (but negated because of the subtraction).

Therefore the sum evaluates to $$m\left(1 - \prod_{a \in A}a\right)$$

$\endgroup$
1
  • $\begingroup$ I'm sure Darij won't mind me answering, even though the argument is essentially the same as his. $\endgroup$ Nov 25, 2021 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.