[Solved]: Solving problems related to Marginal Contribution Nets

Problem Detail: 

So, I encoutered this problem in examination:

Consider the following marginal contribution net:

$\{a \wedge b\} \to 5$

$\{b\} \to 2$

$\{c\} \to 4$

$\{b \wedge \neg c\} \to −2$

Let $v$ be the characteristic function defined by these rules. Give the values of the following:

i) $v(\emptyset)$

ii) $v(\{a\})$

iii) $v(\{b\})$

iv) $v(\{a, b\})$

v) $v(\{a, b, c\})$

My answer is below, but I am not sure.

i) $v(\emptyset) = -2$

ii) $v(\{a\}) = 0 - 2$

iii) $v(\{b\}) = 2 - 2$

iv) $v(\{a, b\}) = 5 + 2 - 2$

v) $v(\{a, b, c\}) = 5 + 4 + 2 - 2$

If anybody knows how to solve this kind of problem, could you confirm?

Exact same problem is shown on page 4 of following paper: Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games (by Samuel Ieong and Yoav Shoham)

Asked By : daulet

Answered By : Dave Clarke

I got the following answer:

1. $v(\emptyset)=0$
2. $v(\{a\}) = 0$
3. $v(\{b\}) = 2-2 = 0$
4. $v(\{a,b\}) = 5+2-2 = 5$
5. $v(\{a,b,c\}) = 5+2+4 = 11$

Here's a general approach to doing this calculation. Consider a set $A\subseteq \{a,b,c\}$. Define a map $I_A:\{a,b,c\}\to\{\text{True},\text{False}\}$ as follows: $$I_A(x) = \left\{ \begin{array}{l@{~~}l} \text{True} & \mbox{if}~x\in A \\ \text{False} & \mbox{otherwise} \end{array}\right.$$ This is the so-called indicator function of set $A$.

Now take each element of the marginal contribution net and evaluate whether it is true or false given $I_A$. If it is true, add the contribution. If not, add no contribution. More explicitly, given element $\psi\to c$, add $c$ only if $I_A\models\psi$ holds.

Here the notation $I_A\models\psi$ simply means evaluate the truth of the formula $\psi$ given the assignment of the variables $\{a,b,c\}$ to true or false.

Consider $v(\{a,b\})$. This corresponds to the map $I_{\{a,b\}}=\{a \mapsto\text{True},b\mapsto\text{True},x\mapsto\text{False}\}$. Given this assignment of truth values, we can conclude that:

• $a\wedge b$ is true, so $5$ is contributed.
• $b$ is true, so $2$ is contributed.
• $c$ is false, so nothing is contributed.
• $b\wedge\neg c$ is true, so $-2$ is contributed.

Therefore the total contribution is $5+2-2=5$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1319

3.2K people like this

 Download Related Notes/Documents