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   
      
   References   
      
   "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.)   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)