Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: symbolic linear programming, game theory and cylindrical algebraic decomposition
Replies: 0

 doctorleff@gmail.com Posts: 1 Registered: 10/20/13
symbolic linear programming, game theory and cylindrical algebraic decomposition
Posted: Oct 20, 2013 8:56 PM

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.)