Hi all,
We have a problem and appreciate if you guys could help us implementing it. Long story short, this is a GNEP (Generalized Nash Equilibrium Problem) in which each player tries to maximize its own profit subject to some constraints. Player k would maximize the following problem :
Max π_k =∑_r∑_s ∑_c∑_p f_(r,s,p.c) *((L_(p.k)^rs)/(L_p^rs ))
Subject to:
∑_c∑_p f(r,s,p,c) =Q(r,s) ∀r,s
∑_s∑_r∑_c∑_p f_(r,s,p,c)*ε_(r,s,j,p) ≤ C_j^k ∀j,k
f_(r,s,p,c) ≥ 0 ∀r,s,p,c
The problem is to finding optimal f_(r,s,p,c) . As we see above, variables corresponding to other players DO EXIST in both constraints and objective function of player k. To solving this GNEP we write Karush-Kuhn-Tucker (KKT) system of each k player with corresponding Lagrangian multipliers (τ(r,s),η(r,s) ,µ(j,k )). KKT conditions are then transformed into the following Linear Complementary problem(LCP):
0≤F_k (X)⊥ X^k≥0
We coded this problem into GAMS 24.1.2 and solve it using PATH solver.
Our GAMS code is:
positive variables
f(r,s,p,c)
tau(r,s)
eta(r,s)
mu(j,k)
;
equations
co1(r,s,p,k)
co2(r,s)
co3(r,s)
co4(j,k)
;
co1(r,s,p,k) . . (L_(r,s,p,k)/(L_(r,s,p) )-τ(r,s)+η(r,s)-∑_j ϱ_(j,k)* ε_(r,s,j,p) =g= 0 ;
co2(r,s) . . Q(r,s)-∑_c∑_p f_(r,s,p,c) =g= 0 ;
co3(r,s) . . ∑_c∑_p f_(r,s,p,c) -Q(r,s) =g= 0 ;
co4(j,k) . . C_(j,k)-∑_s∑_r∑_c∑_p f_(r,s,p,c)* ε_(r,s,j,p) =g= 0 ;
Model GAME /co1.f , co2.tau, co3.eta, co4.mu / ;
option mcp = path ;
solve GAME Using mcp ;
The model status is Locally Infeasible. Do you have any comments on this?
All the best,
Danesh
implementation problem
Re: implementation problem
Danesh,
Several things come to mind. First, are you setting initial values? This is hugely important in nonlinear optimization models, and also for MCP models (linear or not).
Looking at your optimization model, you have an equality constraint, but you formulate this as an inequality in the MCP. This is not consistent.
Have you thought about using JAMS to do this? It looks to me like your model is tailor-made to fit into JAMS as an equilibrium model. JAMS does the reformulation as a monolithic MCP mechanically.
It's not a bad exercise to do the transformation to MCP yourself, manually. It can be instructive. If you go this route, you should make the assumption that your derivation or implementation of the KKT conditions will be wrong in some way. This is what the pros do. So you need a method to help detect these errors and fix them. The attached PDF is a draft of an effort we made in that direction. It's not complete but the basic ideas are there.
You have multiple players. Don't start by deriving all the KKT conditions for all players in one go. Instead, select one player (say player 1) and the one to vary and fix the decisions of all other players. Now get the KKT conditions for player 1 correct and the MCP solving nicely. Repeat this exercise for the remaining players. Then solve the monolithic model.
Hope this helps,
-Steve
Several things come to mind. First, are you setting initial values? This is hugely important in nonlinear optimization models, and also for MCP models (linear or not).
Looking at your optimization model, you have an equality constraint, but you formulate this as an inequality in the MCP. This is not consistent.
Have you thought about using JAMS to do this? It looks to me like your model is tailor-made to fit into JAMS as an equilibrium model. JAMS does the reformulation as a monolithic MCP mechanically.
It's not a bad exercise to do the transformation to MCP yourself, manually. It can be instructive. If you go this route, you should make the assumption that your derivation or implementation of the KKT conditions will be wrong in some way. This is what the pros do. So you need a method to help detect these errors and fix them. The attached PDF is a draft of an effort we made in that direction. It's not complete but the basic ideas are there.
You have multiple players. Don't start by deriving all the KKT conditions for all players in one go. Instead, select one player (say player 1) and the one to vary and fix the decisions of all other players. Now get the KKT conditions for player 1 correct and the MCP solving nicely. Repeat this exercise for the remaining players. Then solve the monolithic model.
Hope this helps,
-Steve
-
3720487881
- User
- Posts: 5
- Joined: 3 years ago
Re: implementation problem
Hi Steve,
Attached please see my responses to the questions/issues you raised.
All the best,
Danesh
Attached please see my responses to the questions/issues you raised.
All the best,
Danesh
-
3720487881
- User
- Posts: 5
- Joined: 3 years ago
Re: implementation problem
Dear Steve,
I am wondering if you got a chance to look at what I have uploaded. The website recognized my questions as spam (!); so I had to upload them as a document.
All the best,
Danesh
I am wondering if you got a chance to look at what I have uploaded. The website recognized my questions as spam (!); so I had to upload them as a document.
All the best,
Danesh
Re: implementation problem
Danesh,
You should not take an equality and make it two inequalities. This is a bad idea computationally. Just use the equality with a free multiplier.
You asked me to elaborate, but there's a lot to say. Much of it is spelled out explicitly in the attached kkt.pdf document. In particular, if you read and understand this document, you will know what it means to formulate and solve KKT conditions for a single agent.
-Steve
You should not take an equality and make it two inequalities. This is a bad idea computationally. Just use the equality with a free multiplier.
You asked me to elaborate, but there's a lot to say. Much of it is spelled out explicitly in the attached kkt.pdf document. In particular, if you read and understand this document, you will know what it means to formulate and solve KKT conditions for a single agent.
-Steve