5
$\begingroup$

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)

$\endgroup$
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ so, for I{a,b,c}={a↦True,b↦True,c↦True}. a∧b is true, so 5 is contributed. b is true, so 2 is contributed. c is true, so 4 is contributed. b∧¬c is false, so -2 not contributed. Total: 5+2+4 = 11. Correct? $\endgroup$ – Daulet Apr 17 '12 at 14:55
  • $\begingroup$ Indeed. 5+2+4=11 (not 0 as I originally wrote). $\endgroup$ – Dave Clarke Apr 17 '12 at 14:59
  • $\begingroup$ Thank you so much for clarification! I have a strait forward solution algorithm now. I will vote up once I have enough rep. $\endgroup$ – Daulet Apr 17 '12 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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