1
$\begingroup$

If $f:2^{\Omega} \rightarrow \mathbb R _+$ is convex and nondecreasing, and is defined over the set $\Omega$ and $f(\varnothing) = 0$, is $f$ superadditive?

The convexity of $f$ is defined as,

$$f(S\cup T) + f(S\cap T) \geq f(S) + f(T), ~~~~\forall S, T \subseteq \Omega$$

Superadditivity is defined by,

$$f(S\cup T) \geq f(S) + f(T), ~~~~\forall S, T \subseteq \Omega$$

$\endgroup$
  • 1
    $\begingroup$ For the usual definition of superadditivity $S$ and $T$ should be restricted to disjoint sets. And a more conventional name for convexity of $f$ is supermodularity (equivalent to the concavity of its Lovász extension) $\endgroup$ – Dap Nov 10 '17 at 13:31
  • $\begingroup$ Can you share any reference? $\endgroup$ – Eval Nov 10 '17 at 13:33
  • 1
    $\begingroup$ Well, Wikipedia. Superadditivity is a common assumption in coalition games, so a reference would be Owen's "Game Theory". Supermodularity is sometimes studied in non-cooperative games, and is discussed in Fudenberg and Tirole's "Game Theory". $\endgroup$ – Dap Nov 10 '17 at 13:56
5
$\begingroup$

No. Define $\Omega = \{1\}$ and $f(\{1\}) = 1$. It is easy to check that $f$ is convex but not superadditive.

$\endgroup$
  • 1
    $\begingroup$ I didn't get it. Please elaborate. $\endgroup$ – Eval Nov 10 '17 at 13:11
  • $\begingroup$ $f(\lbrace 1 \rbrace \cup \lbrace \varnothing \rbrace) \geq f(\lbrace 1 \rbrace) + f(\lbrace \varnothing \rbrace) $, because, $f(\lbrace \varnothing \rbrace) = 0$. $\endgroup$ – Eval Nov 10 '17 at 13:20
  • 1
    $\begingroup$ @Eval $2^\Omega$ only contains the sets $\varnothing$ and $\{1\}$, so you can just check out all combinations and find that $f$ is convex but not superadditive. For example $$f(\{1\}\cup\{1\})=f(\{1\})=1\not\ge2=1+1=f(\{1\})+f(\{1\}),$$hence not superadditive. $\endgroup$ – M. Winter Nov 10 '17 at 13:20

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.