In his book Inadequate Equilibria, Eliezer Yudkowsky introduces the concept of an inadequate equilibrium: A Nash equilibrium in a game where at least one Nash equilibrium with a larger payoff exists.
where NE(G) is the set of all Nash equilibria for the game
G and N is the set of all players.
The bound for the badness of any inadequate equilibrium is then given by
PoI(G)=maxs∈NE(G)∑i∈Nui(s)mins∈N E(G)∑i∈Nui(s)
This formalization has the problem of being sensitive to affine transformations of ui and becoming undefined if the worst Nash equilibrium (or the current Nash equilibrium) has payoff zero.
A slightly nicer formalization could be to define:
iff one can just pull coefficients out of a maximization/minimization
like that. Not sure though. (Negative affine transformations would flip
the function and select other points as maxima/minima).
If one can bound the price of anarchy and the price of stability, one
can also sometimes establish bounds on the price of inadequacy:
The Price of Inadequacy
In his book Inadequate Equilibria, Eliezer Yudkowsky introduces the concept of an inadequate equilibrium: A Nash equilibrium in a game where at least one Nash equilibrium with a larger payoff exists.
One can then formalize the badness of an inadequate equilibrium e similarly to the Price of Anarchy and the Price of Stability:
PoI(G, e)=maxs∈NE(G)∑i∈Nui(s)∑i∈Nui(e)
where NE(G) is the set of all Nash equilibria for the game G and N is the set of all players.
The bound for the badness of any inadequate equilibrium is then given by
PoI(G)=maxs∈NE(G)∑i∈Nui(s)mins∈N E(G)∑i∈Nui(s)
This formalization has the problem of being sensitive to affine transformations of ui and becoming undefined if the worst Nash equilibrium (or the current Nash equilibrium) has payoff zero.
A slightly nicer formalization could be to define:
PoI(G)=PoA(G)−PoS(G)=maxs∈S∑i∈Nui(s)mins∈NE(G)∑i∈Nui(s)−maxs∈S∑i∈Nui(s)maxs∈NE(G)∑i∈Nui(s)
Since we know that 1≤PoS≤PoA, under this definition PoI≥0.
Is this definition insensitive to positive affine transformations? I am not sure, but I have the intuition that it is, since
maxs∈S∑i∈Nα⋅ui(s)+βmins∈NE(G)∑i∈Nα⋅ui(s)+β−maxs∈S∑i∈Nα⋅ui(s)+βmaxs∈NE(G)∑i∈Nα⋅ui(s)+β=max s∈SαβN+α⋅∑i∈Nui(s)min s∈NE(G)αβN+α⋅∑i∈Nui(s)−max s∈SαβN+α⋅∑i∈Nui(s)max s∈NE(G)αβN+α⋅∑i∈Nui(s)=maxs∈S∑i∈Nui(s)mins∈NE(G)∑i∈Nui(s)−maxs∈S∑i∈Nui(s)maxs∈NE(G)∑i∈Nui(s)
iff one can just pull coefficients out of a maximization/minimization like that. Not sure though. (Negative affine transformations would flip the function and select other points as maxima/minima).
If one can bound the price of anarchy and the price of stability, one can also sometimes establish bounds on the price of inadequacy:
As an example, in network cost-sharing games, PoA≤k and PoS=Hk, so PoI≤k−Hk.