faq 75268118

Testing for Nash equilibrium?

by Andrew A Campbell on 2016-07-28 19:23:14

---

In the mastsim/examples/equil folder, the README.txt file mentions using this toy network for testing for Nash equilibrium. 

Of course I am aware that MATSim solves for a much more complex equilibrium state than the simple static routing described by Wardrop's first principle. But I am curious about whether it is achievable for large simulations.

Is anyone aware of efforts to test for Nash (i.e. Wardrop's first principle) routing equilibrium in larger simulations? I have scanned the literature but can cannot find any papers specifically documenting this.

Thank you.

---

Comments: 1

---

Re: Testing for Nash equilibrium?

by Kai Nagel on 2016-07-29 13:20:41

Dear Andy,

Not really.  We normally look at scorestats.png (in the output directory), and if that is sufficiently horizontal, we assume that for this number of iterations the type of problem we are looking at becomes sufficiently relaxed.

Clearly, this is quite some abuse of theory; convergence of a projection of the state space is a necessary but not a sufficient condition of convergence of the whole system. 

Unfortunately, as far as I know, a concept of "closeness to Nash equilibrium" is also not well defined – one can construct pathological situations where all individuals can only improve by small amounts when switching strategy but the system is still arbitrarily large away from the true Nash equilibrium state.  Having said this, one could extract the score difference between the selected and the best plan of each individual agent.  There are at least the following caveats:

• Standard MATSim goes for an SUE, not a NE, so agents no selecting the best plan is totally normal.
• You can only check if agents use the best plan in their plan set (= effective choice set).  Since we are unable to construct exact best reply algorithms, we never know how far away from the truly best plan this is.  (Even the router, which is a clear-cut computer science algorithms, operates on 15min time bins, and in consequence only finds a "good" but not the "exactly best" route.)

Our book http://matsim.org/the-book contains some chapters on "understanding matsim", and there on the (Monte Carlo sampling) theory that we think applies.

Pls let us know if you make any progress in terms of understanding this issue.

Best wishes

Kai