Given a square skew-symmetric matrix M, I need to find the vector x with minimal magnitude satisfying Mx ≤ 0 and xi ≥ 0 and ∑xi = 1.
Or to put it another way, the goal is to minimize f(x) = ½∑xi2 subject to h(x) = 1•x - 1 = 0 and gk(x) = mk•x ≤ 0 where mk is the kth row of M, as well as x ≥ 0.
I can write down the KKT conditions, but I am not sure how to solve them.
The idea here is to solve the symmetric game specified by M, and if more than one optimal strategy is available then to pick the one which minimizes the sum-of-squares of its probabilities. I can get *a* vector y satisfying all the constraints by running the simplex algorithm on M+1, but I don’t see how to find the SSQ-minimizing one.
My specific motivation is to implement the GT election method, which is game-theoretically optimal among all ranked voting systems in the sense that no other ranked system will pick winners who are preferred by more voters (in the long-term average) than those elected by GT.
Of course any optimal strategy has that property, but I am trying to implement the system described in the linked paper. More info on it is available here.
For the discussion of math. Duh.
1 post • Page 1 of 1
wee free kings