Symbolic linear programming or cylindrical algebraic decomposition
I have two piecewise linear functions (PLA, PLB); They represent payoffs for a two-player game in Nash Equilibria theory. At the end, I provide more background on my application.
Sat1 = PLA(param1,param2...paramm,w11,w12...w1n); Sat2 = PLB(param1,param2...paramm,w21,w22...w2n); w11,w12...w1n,w21,w22...w2n are constrained to be between zero and ten. (The param1 to paramm are also constrained to a range, usually from zero to a positive number.)
I want to enumerate all the polygonal regions where both PLA and PLB are linear.
I assume, and will program in Maple, that I need to program the following. Let K be the kink points, where the piecewise linear functions change slope. Ki = fi (param1,param2...paramm,w11,w12...w1n,w21,w21...w2n); Find all the intersection points between the equations of the kink points.
Then set equalities Ki=Kj for each i != j. These divide the R(2n) space into regions. This would generate a bunch of points P of intersections, where each P is a function of param1 to paramm.
Then, I would enumerate each possible order of the Px along each of the Kink equations. I could symbolically create inequalities in the Parami that keep that order constant.
Of course, since the satisfaction or utility functions are linear in the w11,w12...w1n , w21,w22... w2n, the optimal values for each region would be at one of its vertices. This would give me a symbolic equation for the payoff for both players if they chose values for w11, w12... w1n, w21, w22, 2n that is a point in one of the regions.
If these correspond to a Pure Nash Equilibrium, than I would generate a set of inequalities that would keep it that way. That is, let w1x be a vector in Rn corresponding to the values of w at the vertex that is a Nash equilibrium. Also, at that vertex, let w2x be a vector in Rn corresponding to the values of w submitted by Player Two. Let Sat1 bet the utility or playoff function for player one and Sat2 be the utility or payoff function for player 2. Assume there are V other vertices; let v1i and v2i be the w vectors corresponding to each of the other intersection points,
In order for this to be pure equilibrium, then the Sat1(v1i,w2x) > Sat1(w1x,w2x) v1i != w1x and Sat2(w1x,v2i) > Sat1 (w1x,w2x) v2i != w2x. For each region, I simply generate these 2(n-1) inequalities. (For the moment, I am not sure what constraints one would generate for the mixed strategy equilibria.)
This is a problem in voting system design for parametric budgets. param1 to paramm represent properties of the voting system, the budget or the satisfaction function. One goal is to show that for various voting system, any game theory matrix (of a certain size) can be created by varying the param1 to paramm. This is to show that the voting system has no nice game theory properties.
Some of these are the satisfaction curves, the satisfaction for population (p) from each public good (i) = mpi * Goodi up to Satpi Goodi is (w11+w21) c1i + (w12+w22) c2i + (20-(w11+w21+w12+w22))c3i For population one and good set m11*(w11+w21) c1i + m11 ( w21+w22) c2i + m 11 (20 -(w11+w21+w12+ w12+w22))c3i = Sat1i
This corresponds to what I did for my dissertation rearch in symbolic math applications to mechanical engineering CAD/CAM. I generated inequalities that kept the object "similar" as the CAD/CAM user varied the parameters. (See References below)
Any insight would be appreciated; before I proceed to try the cylindrical algebraic decomposition routines in Mathematic and Maple. They seem to have support for the situation where the cylindrical decomposition is in terms of a subset of the variables which appear in the inequalities. That is they can do the decomposition parametrically.
Dr. Laurence Leff Associate Professor of Computer Science, Western Illinois University, Macomb IL 61455 on sabbatical
"A Working 2-D Symbolic CSG System Written in Maple" in Software Systems in Engineering ASME PD-59, 1994. (Presented at The Energy- Sources Technology Conference, New Orleans Louisiana, January 23- 26, 1994) (with Thompson, D., Trias, T., and Malik, Z.)
"Toward a Symbolic Math CAD/CAM System," published in the 1993 ASME International Computers in Engineering Conference (with Trias, T., Thompson, D., Kyaw, M.,.Malik, Z.) held in San Diego, CA on August 8-12, 1993
?A Symbolic CSG System Written in Maple V? published in the Second Annual Maple Summer Workshop and Symposium Ann Arbor, June 1993.
"Symbolic Math Applications to Constructive Solid Geometry and Finite Element Analysis" Computers and Structures, Vol 59, No. 3, 561-582, 1994 (with Yun, D. Y. Y.)