Skip to main content

What does it mean polynomials share Newton polytope?

I have trouble understanding the connection between polynomials and Newton polytopes. I will try to make a short introduction to my problem and hope you will catch on. In the end I will ask questions.

I have a game with n players: $1,2,...,n$.
The $i^{\text{th}}$ player has $d_i$ strategies and he allocates probabilities to them which we denote by $(p_1^{(i)},...,p_{d_i}^{(i)})$. So, it holds $\forall i,j : p_j^{(i)} \geq 0 \quad$ and $\quad \forall i : p_1^{(i)} + p_2^{(i)} + \cdots + p_{d_i}^{(i)} = 1 $.
We use $p_{d_i}^{(i)} = 1 - \sum_{j=1}^{d_i-1} p_j^{(i)}$.
The $i^{\text{th}}$ player has a payoff matrix $X^{(i)}$, which is an $n$-dimensional array of size $d_1 \times ... \times d_n$ and whose entries are rational numbers.

I have following polynomials:

$$\sum_{j_1=1}^{d_1} \cdots \sum_{j_{i-1}=1}^{d_{i-1}} \sum_{j_{i+1}=1}^{d_{i+1}} \cdots \sum_{j_n=1}^{d_n} \Big( X_{j_1 ... j_{i-1} k j_{i+1} j_n}^{(i)} - X_{j_1...j_{i-1}1j_{i+1}...j_n}^{(i)} \Big) \cdot p_{j_1}^{(1)} \cdots p_{j_{i-1}}^{(i-1)} p_{j_{i+1}}^{(i+1)} \cdots p_{j_n}^{(n)} $$

where $i=1,2,...n$ and $k=2,3,...,d_i$.

Consider the $d_i−1$ polynomials for a fixed upper index i. They share the same Newton polytope, namely, the product of simplices $$ \Delta^{(i)} = \Delta_{d_1 - 1} \times \cdots \Delta_{d_{i-1}-1} \times \{0\} \times \Delta_{d_{i+1}-1} \times \cdots \times \Delta_{d_n-1}. $$ Here $\Delta_{d_i-1}$ is the convex hull of the unit vectors and the origin in ${\mathbb R}^{d_i-1}$. Hence the Newton polytope $\Delta^{(i)}$ is a polytope of dimension $\delta - d_i + 1$, where $\delta=d_1+ \cdots + d_n - n$.

My questions are:

  1. What does it mean that this polynomials share Newton polytope, what does it even mean that a polynomial is supported ( or whatever is the word) by Newton polytope?
  2. And in this case why is $\Delta_{d_i-1} \subset {\mathbb R}^{d_i-1}$. Should it not be subset of ${\mathbb R}^{d_i}$ because $(p_1^{(i)},...,p_{d_i}^{(i)})$ is a point in that polytope.
  3. Why is the dimension if $\Delta^{(i)}$ $\delta-d_i+1$. I thought it is:

$$(d_1-1)+ \cdots + (d_{i-1}-1) + 1 + (d_{i+1}-1) + \cdots + (d_n-1) $$ \begin{align} &= (d_1 + \cdots + d_n) - d_i - (n-1)+1 \\ &=(d_1+ \cdots + d_n - n) - d_i + 2 \\ &= \delta - d_i + 2. \end{align} Thanks for your answers.

Petra
  • 41
  • 2