Polyhedral structure of functions writable as a finite signed sum of max of linear functions For any two positive integers $k,n$ consider the space of functions writable as, 
$\sum_i \sigma_i \max \{ L_{i1},L_{i2},..,L_{ik} \}$ (a finite sum) where each $L_{*} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a linear function and $\sigma_i = \pm 1$.  


*

*Is some structure theorem known for this family of functions? Like if there is some classification theorem known about the polyhedral structure of these functions? Or some property is known that must be true for the polyhedral structure of such a function? Or if at least conditions are known when the polyhedral structure of such a function is a hyperplane arrangement? 

*Are there methods known by which one can test or prove that a given $\mathbb{R}^n \rightarrow \mathbb{R}$ function can or cannot be written in this form? (for some fixed $k$ and $n$). 

*Are conditions known when such a function can be re-written as, $\pm \max\{P_1,P_2,..,P_t\}$ for some $t$ s.t each $P_{*} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a linear function? 

EDIT : I had missed this $\sigma_i$ in the initial formulation of the question.  
 A: 
(I assume that by linear functions you mean affine functions, i.e. that you are not assuming $\ L_*(0) = 0$).

First of all, the class of your functions is contained in the class of all convex functions. Each convex function $\ Ł : \mathbb R^n\rightarrow\mathbb R\ $ (including your functions) admits a unique representation as follows:
$$ Ł\ = \ \max_{s\in S} Ł_s $$
where $\ S\subseteq \mathbb R^n\ $ is the set of all smooth arguments
$\ s\ $ (see below), and $\ Ł_s\ $ is the unique affine function such that
$\ Ł_s(s) = Ł(s),\ $ and
$$ \forall_{x\in\mathbb R^n}\quad Ł(x)\ge Ł_s(x) $$
The set $\ S\ $ is defined as the set of points $\ s\ $ for which such a (supporting) function is indeed unique.
Thus, your sum has got (or gotten) replaced by a single summand.

Some different $\ s\in S\ $ may lead to the same $\ Ł_s,\ $
  especially in the case of your finite expressions. The $\ \max\ $ function doesn't care. In the case of a finite expression, the number of the different functions $Ł_s$ will be finite.

In the case of a finite expression, take just one $\ s\ $ for each
$n$-domain around which the function is affine (i.e. $\ s\ $ should belong to that domain).

The question seemed a little bit vague to me, hence I didn't attempt any algorithmic considerations.

EDIT (more details):
The function (a finite sum) considered in the Question
$$ Ł\ :=\ \sum_i \max \{ L_{i1},L_{i2},..,L_{ik} \}$$
is convex, hence the set:
$$ C\ :=\ \{(x\ t)\in\mathbb R^n\times\mathbb R: Ł(x)\le t \} $$
is convex and closed. Thus the topological boundary
$$\ B\ :=\ \mathcal B (C)\ =\ \{(x\ t)\in\mathbb R^n\times\mathbb R: t=Ł(x) \} $$
(i.e. the graph of $Ł$) contains a dense subset $S\subseteq B$--dense in the boundary $B$--such that for every $\ (x\ t)\in S\ $ there exists exactly one $n$-plane $\ H\ $ such that $\ (x\ t)\in H\ $ and $\ C\ $ is on the one side of $\ H.\ $ Of course $\ t=Ł(x)\ $, and $\ H\ $ is the graph of a sum of the original affine functions $\ L_*.\ $ We see that there are only finitely many such affine functions simply because there are finitely many of the original affine functions to start from (the same affine plane will appear $\infty$-many times but it doesn't matter when they appear unde $\max$). Thus function $\ Ł\ $ is just one $\max$ of finitely many affine functions.
A further detail: each said $H$ is a graph of the sum of functions $L_*$ taken one from each summand (of expressions $\max$) of the original expression.

I truly believe that all this is basic and true. I am sorry if I am somehow blind or worse.

