1
$\begingroup$

I am trying to transform a non-linear objective function into a linear one, in order to create a LP. How might I go about to do this (I have never taken a course in linear programming).

I have that I would like to maximize the following objective function: $\mu(\alpha)$, where $\mu(\alpha) = \min{U_i(\alpha)}$. $U_i(\alpha)$ denotes the expected utility for player $i$ in a correlated Nash equilibrium and $\alpha$ denotes the corresponding probability distribution played by the players.

The contrains I have so far are the following: $\sum_{a \in A} \alpha(a) = 1$, and $\alpha(a) \ge 0 $ for all $a \in A$. The other contraints that I have are the ones used for a standard correlated equilibrium, namely that: for each player $i$ and pairs of action $a_i^{1}$ and $a_i^{2}$, we have that: $\sum_{a \in A | a_i = a_i^{1} } [u_i(a) - u_i(a_i^{2}, a_{-i})]\alpha(a) \ge 0$.

The first 2 contraints are the ones requiring that $\alpha$ follows a proper probability distribution, and while the last sets are the ones that enforce the correlated equilibrium (by definition). How might I go about to modify this into an LP with the objective function I mentioned above. I know that it's not linear, so I need to change it somehow (and the LP ) appropriately.

Advice is appreciated :)

1 Answers 1

2

For those who are curious, I ended up realizing that I can define the non-linear objective function as a piece-wise set of linear and concave functions, then adding the appropriate constraint for each of these pieces in the original LP. The remainder of the work fell into place after that.