Sunday 2 August 2015

Regret Minimization & Envy Freedom

(This post is meant to clarify a statement in my previous one.)

Envy Freedom obtains if no agent prefers another's outcome over his own. If that outcome has been arrived at only by fair means, we can call it 'Super-fair'.
Clearly, envy freedom will obtain only if one of the following obtain-
1) outcomes are identical
2) heterogenous outcomes reflect preference diversity- if I get half a cake and you get a whole one and I don't envy you it is because I am on a diet.
3) information asymmetry arises- I am so ignorant I don't get that a whole cake means more yummy goodness than half a cake.
4) preferences don't change such that Utility actually derives from a portfolio arising from a 'multiplicative weight  update algorithm' rather than the individual's own outcome- i.e. agents have a psychic hedge of a Saintly type.

A moment's thought will show (2) is transitory if preferences serve a Darwinian function- i.e. enable an organism to survive and propagate. If people who eat a full cake and have man-boobs get hot chicks and have more babies (this is my own reproductive strategy) then sooner or later no allocation such that some people get less cake will be envy-free.
Similarly (3) is transitory. Once someone explains to me that half a cake means less less yummy goodness, I start to cry my eyes out consumed by bitter envy. If that doesn't help, I get political- i.e. vote for a Varoufakis and help fuck things up for everybody.

Is there some way to prevent (2) and (3) from being transitory? That way, if an allocation is envy-free at time t, then 'fair' exchange based on it yields a 'super-fair', i.e. envy free, allocation at time t+1 and so on ad kalendas Graecas 

Subjectively, envy at what other people ended up getting compared to what we had to settle for could be linked to regret about our decisions.
Halpern & Pass write-
'Roughly speaking, the idea of regret in decision theory is that an agent chooses an action x that minimizes regret across states, where the regret of action x in a state S is the difference between the agent’s utility when he performs x in a state S and when he performs the act that gives the highest utility in state S.'
They introduce a concept of 'iterated regret minimization' in strategic games and show it is a better predictor of empirical results in games like Basu's Traveler's dilemma, the Centipede game, Nash bargaining and Bertrand Competition.
'To apply regret in a strategic-form game, we take the states to be the other players’ strategy choices. Iterated regret minimization takes this idea one step further: we see what inferences we can draw starting with minimal beliefs about the other players’ strategies, using only the fact that the other players are regret minimizer.'

Interestingly, there is a link between 'regret minimization' and Evolutionarily Stable States.
As a recent paper points out-
'Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced the whole of Life as we see it around us. There is a computational way to articulate the same amazement: “What algorithm could possibly achieve all this in a mere three and a half billion years?” In this paper we propose an answer: We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of sex become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known in computer science to be surprisingly powerful and versatile. MWUA maximizes a tradeoff between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution'

Hannan, of whose relationship with the Bengali, or speaking more broadly, Indian Statistical Tradition, I have written elsewhere, originated the MWUA approach. Perhaps, readers of the Mahabharata- in particular the Nalopakhyanam- will not be surprised that 'Multiplicative weight updates in a coordination game are equivalent to evolution under sex and weak selection.'

Since words like 'fairness' and 'envy' gain purchase as apparent solutions for a Social co-ordination game; perhaps we can say that Muth Rational agents can indeed agree that heterogenous outcomes are 'envy free' provided they are also 'regret minimizers'. There is a bit of Hegelian sleight of hand going on here but since it connects with genuine ongoing Scientific Research Programs involving open questions for Maths, maybe that's okay.

Interestingly, a meta-ethics founded on Dawkin's 'extended phenotype' is identical to one based on the Yoga Vasishta- essentially agents have a stake in each others Utilities.

The result, in the Mahabharata, is that the Ruling Class doesn't have to extirpate itself utterly in a war occasioned by envy, because the Just King has learnt statistical Game Theory- including, presumably, the MWUA- and understands that all Evolutionarily Stable Strategies are equal in Eusebia.

No comments: