4
$\begingroup$

Let $\mathcal{A}$ be a set of convex subsets of $\mathbb{R}^n$ and for each $A\in\mathcal{A}$ let there be an affine linear map $f_A\colon \mathbb{R}^n\rightarrow\mathbb{R}$. Moreover, assume that for any $A,B\in \mathcal{A}$ and $v\in A\cap B$, it is $f_A(v)=f_B(v)$ (*).

I am interested in finding a necessary and sufficient condition on $\mathcal{A}$ such that for all choices of functions $(f_A)_{A\in\mathcal{A}}$ satisfying (*), there is an affine map $g$ such that $$g(v) = f_A(v) \text{ for all }A\in\mathcal{A}\text{ and }v\in A.\quad (1)$$

Motivation: this question arises in decision theory. One can think of the points in $A\in\mathcal{A}$ as utilities individuals could get under a certain condition, and the functions $f_A$ as aggregating these utilities into a social welfare function. There are results that for each of the sets $A\in\mathcal{A}$, the social welfare function is an affine linear function $f_A$ on the individual utilities. Moreover, I know that for two different sets, the functions need to coincide on their intersection. I now want to derive a necessary and sufficient condition for the social welfare function to be representable by one affine linear function of individual utilities for all sets in $\mathcal{A}$. I also know that all $A\in\mathcal{A}$ must be convex, although I haven't used that fact yet.

My own work: It is easy to find a counter-example that shows that some condition is needed. E.g., take two sets $A,B$ which are disjoint and both have full dimensionality in $\mathbb{R}^n$, two differing functions $f_A\neq f_B$ and $\mathcal{A}=\{A,B\}$.

As a means to finding such a condition I tried introducing sets $\Phi(A,B)\subseteq\mathbb{R}^n$ which include all points on which $f_A$ and $f_B$ must coincide. For instance, it is $f_A=f_B$ on $\mathrm{aff}(A\cap B)$ (where aff denotes the affine span) and hence $\mathrm{aff}(A\cap B)\subseteq\Phi(A,B)$. Also, $\Phi(A,B)\cap\Phi(B,C)\subseteq\Phi(A,C)$ for $A,B,C\in\mathcal{A}$, and $\Phi(A,B)$ is always an affine span.

A sufficient condition would be if for any strict subset $\mathcal{G}\subsetneq\mathcal{A}$, there is a condition $A\in\mathcal{A}\setminus\mathcal{G}$ with $$\mathrm{aff}(A)\cap\mathrm{aff}\left(\bigcup_{G\in\mathcal{G}}G\right)\subseteq \mathrm{aff}\left(\bigcup_{G\in\mathcal{G}}\Phi(A,G)\right).$$

Then we can inductively choose some function $g$ which fulfills (1) on $\mathcal{A}$ (or via some other method if $\mathcal{A}$ is uncountable). To illustrate the idea, assume there is such a function $g$ which works for a subset $\mathcal{G}\subsetneq \mathcal{A}$. Then the condition provides a set $A$ such that $g$ and $f_A$ are equal on $\mathrm{aff}(A)\cap\mathrm{aff}(\bigcup_{G\in\mathcal{G}}G)$. Hence, we can choose a new function $g'$ which equals both $f_A$ and $g$ on this set and extend this function as equal to $f_A$ on $\mathrm{aff}(A)$ and equal to $g$ on $\mathrm{aff}(\bigcup_{G\in\mathcal{G}}G)$. Then $g'$ fulfills (1) for $\mathcal{G}\cup\{A\}$.

Unfortunately, I have not been able to find a sufficient condition which is also necessary or to prove that the above condition is necessary.

$\endgroup$
15
  • $\begingroup$ If $\mathcal{A}$ contains a convex set $A$ with non-empty interior, then (1) is satisfied iff $g \Doteq f_A$ coincide with $f_B$ on $B$ for every $B$ in $\mathcal{A}$. $\endgroup$
    – Luc Guyot
    Oct 29, 2019 at 17:27
  • $\begingroup$ If every convex set $A$ of $\mathcal{A}$ has empty interior, then we may focus on the case $n = 1$ first. Here (1) is satisfied if and only if the points $(x_A, f_A(x_A))$ with $A = \{x_A\}$ lie on a same line (In particular, you have examples where all $\text{aff}(A)$ and all $f_A(\mathbb{R})$ are pariwise disjoint and (1) holds true). These two equivalences are rather tautological and I fail to see what kind of useful characterization one could derive in general. $\endgroup$
    – Luc Guyot
    Oct 29, 2019 at 17:27
  • $\begingroup$ Thanks, Luc Guyot! I am especially interested in conditions that do not involve the $f_A$ directly, as these are the objects I would like to prove something about, using only constraints on $\mathcal{A}$ (and the assumptions outlined in the first paragraph). I would be very happy about either necessary and sufficient constraints on $\mathcal{A}$ (no matter how involved or unintuitive) or maybe also about very simple and (as weak as possible) sufficient constraints. An example of a simple and sufficient one would be if the intersection of any two sets in $\mathcal{A}$ has a non-empty interior. $\endgroup$ Oct 30, 2019 at 18:00
  • 1
    $\begingroup$ Dear Johannes, thanks for your explanations. If I understand your question correctly, then there is no condition on $\mathcal{A}$, and on $\mathcal{A}$ only, which is equivalent to $(1)$. The reason is simple, and somehow you already mentioned it: you can find a set $\mathcal{A}$ for which $(1)$ holds true for some choice of the functions $f_A$ but doesn't for a different choice. Take your example with $\mathcal{A} = \{A, B\}$ or take $n = 1$ and $\mathcal{A} = \{\{0\}, \{1\}, \{2\}\}$. $\endgroup$
    – Luc Guyot
    Oct 30, 2019 at 20:44
  • 1
    $\begingroup$ $\Phi(A, B) = \bigcap_{f_A, f_B} \{v \in \mathbb{R}^n \, \vert \, f_A(v) = f_B(v)\}$ where the functions are (*)-compatible? $\endgroup$
    – Luc Guyot
    Oct 31, 2019 at 22:59

0

Your Answer

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

Browse other questions tagged or ask your own question.