Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. Moreover, we add a proportion constraint. That is, each player $s$ is assumed to contribute a percentage of $p_s$ of his utility to a goal that we require to be at least $P$ % of the total utility. We assume that these quantities are inversely related, that is: players with a large utility, have a small $p_s$. The problem is formulated as:
\begin{align} z_{BP}=\max \quad & \sum_{s \in \mathcal{S}} a_{s} \cdot y_{s} & \\ \text{s.t.} \quad & \sum_{s \in \mathcal{S}}y_s = R & \\ & \sum_{s \in \mathcal{S}} a_{s} \cdot y_{s}\cdot p_s \geq \sum_{s \in \mathcal{S}} a_{s} \cdot y_{s}\cdot P \\ & L \leq y_s \leq M & \forall s \in \mathcal{S} \end{align} where $y_s$ is the decision variable deciding the amount of resources assigned to player $s$.
We use Lagrangian relaxation to relax the difficult constraints, i.e. the constraint prescribing the minimum proportion of utilities. We are left with a simple knapsack problem, where we can just select the players with the highest score (utility corrected for constraint violation).
I was wondering whether there would be a way to estimate the Lagrange multiplier given the instance, without solving the problem and without using subgradient optimization. As the optimal solution without the proportion constraint is trivial, I suspect that there should be a way to estimate the 'price' of the constraint. For example by comparing the number of players with $p_s \geq P$ and the number of players with $p_s < P$, or the sum $\sum_{s \in \mathcal{S}:p_s < P} a_s$ and the sum $\sum_{s \in \mathcal{S}:p_s \geq P} a_s$.
