Initially Something simple but that could evolve and become more complex. The definition of social institution could be: a system that achieves higher utility levels which could have individually. Then the system should be able to degenerate and that some individuals are worse. I guess if space of needs and capabilities of the agents is wide then it will emerge complex institutions. Obviously, trade is the first intitution and the Pareto criteria the main basis.
From a CS perspective I think this aligns with the idea of emergence engineering - an open question in ABM. Other than the common attributes of agents such as being autonomous, interactive and situated in some manner, it's really hard to pick behaviours and attributes that will guarantee emergence to occur, even if we calibrate the model later.
Perhaps I misunderstand... Have a look at the link for more information on engineering emergence. Hope this is useful.
Reciprocity as an axiom for interactions ( do unto others as one would wish to be treated). Inspired by Adam Smith and the individualism of the enlightenment.
Parallel processing of information (think of changes in order of magnitude when we moved from tape programmed computers of yesteryears, to the multiple core processors of today, and onwards to the quantum computers of the future).Inspired by the limits of neoclassical economics and the rise of irrationality or bounded rationality rooted in the work of Herbert Simon. How human beings have augmented their ability to make sense of the flood of knowledge and to compensate for a lack of wisdom.
A set of recursive rules that embody core beliefs or governance structures (think of the emergence and collapse of capitalistic society, in contrast to the steady decline of communism in history.And perhaps the socialism of the future as prophesied by Joseph Schumpeter).
Memory for adaptation and a store for rules (think culture, writing and education. All serving to transfer memories to the next generation. Without which the system is trapped in the ever-present).Past, present and future states are made possible through memory. Inspired by institutional economics and the memetic theory of culture.