Your question seems big and abstract.

Can you give a concrete numerical example of M?

Actually this question is not weird in mathematics or control theory. This is just a problem of dimension reduction, which means to study a model with reduced dimension but preserving certain same basic property. So Prof. Doran needs to give a clearer formulation of his question. There may be some old solutions.

I agree with Prof. Wilby. Sometimes a new problem itself is much more important than a new solution, even an appropriate solution is still unavailable.

James, I think that there are two separate problems in your question. The first maybe be better phrased as "can I develop a simple algorithm (SA) that emulates/simulates specific aspects of the behavior of a complex multi agent system (MAS)." The second question maybe be phased better as "given that SA is possible, can I develop an algorithm that would automatically derive SA from some formal definition of MAS and a definition of the simplification / optimization characteristics of interest."

Given your research question, I think you're primarily interested in the first question. You want to be able to create a large system of simple agents that express specific behaviors, specifically inter-agent communication behaviors, associated with a more complex MAS (e.g. humans). If that's correct, I'd suggest you look swarming agents and specifically at the NetLogo simulation package (https://ccl.northwestern.edu/netlogo/). For a computational modeling package, it's very simple to setup and use. There is robust theory behind swarming agents and both swarming agents and NetLogo have been used for publication grade research in a variety of fields. You can look at this page for a sampling of papers that have used NetLogo. It will give you a sense of what kind of research has been done using the tool.  https://ccl.northwestern.edu/netlogo/references.shtml 

It's also worth noting that the formal properties of multi-agent / multi-node communication have been studied in depth. It may be that some of the experiments  that you're considering have been already performed, but just not considered in the manner that you're suggesting.

One other note... if you use a modeling approach like NetLogo you'll have to be able to defend that your assumptions match observed / historic MAS (e.g. human) patterns. That leads to the second question about deriving the SA model from MAS behavior. If your MAS was already computationally defined, I'd say looking at a derivation algorithm might be interesting. But since your MAS is humans, that won't work. You'll need to define the SA from observational sources such as social science, psychology, and historical accounts.  =

You are right, the critical part is how you can define what "a simplification of a MAS" is. Even though this may be done, I suspect an algorithm "that should be applicable to ANY multi-agent system for ANY large-scale property" exists. That "large scale property" is an emergent phenomenon. It can't be deducible by looking at the system properties, agent specifications etc. but you need to run/simulate the system to find it. Even when you discover such a large scale property,  you can't say that behavior is observed as a result of this or that system property. That's what makes multi agent systems different and interesting. So the simplification algorithm you desired will be completely in the dark. It needs to detect some kind of reductionism to simplify the system but multi agent systems are exactly interesting because they resist reductionism.

My apologies if my original question came over as too vague. I believed it would be precise if filled in with precise standard computational definitions of MAS etc as I indicated. Some of the uncertainty may have come from different people meaning different things by “multi-agent systems” – I always mean a system that is specified or created within a computer and executed there.  (Contrast (social) multiple actor systems which for me are actual people in social contexts.)

Let me try to give a precise example.

Suppose we generate at random a multiple agent system M within a computer comprising a set of N inter-communicating agents each of which is a production system in the computer science sense.

[I give a definition of a production system below. See also the question I asked on RG on December 9th last – which involved a coupled pair of agents (production systems) —I have now associated some computer code with that question so everything there is made computationally precise -- though perhaps not easy reading!]

Suppose that M turns out to have the unlikely property, P, that on every execution cycle every agent sends just one output (ie wm memory element) to some other agent and receives just one input (ie wm memory element)  from  some other possibly different agent -- not necessarily the same agent in the same role on each cycle. So property P is just the one output and one input for each agent one each execution cycle.

Suppose now we want to simplify M, preserving the fact that it is a multiple-agent system (according to this definition), and also preserving the property P.  HOW might we do this?

One way is simply to delete rules at random from one or more agents and see if P remains the case.  If not, go back and try a different set of rule deletions. Repeat until P is preserved after deletion.

Probably there is a set of non-null rule deletions (we can reasonably call this set a simplification of M, I suggest) that preserves P and ultimately we shall find this set – but it might take a very long time...

This would be an easy algorithm to program I am sure. It also seems to me a boring and uninteresting algorithm!

What algorithm would be more interesting? I'm really interested in your answers!

Regards

Jim

##======= DEFINITION OF PRODUCTION SYSTEM =======##

In this context, a production system comprises a set of IF-THEN rules, a working memory, and an execution process including a conflict resolution convention

A working memory is a set of variable/value combinations with each variable appearing at most once

Here an IF-THEN rule is of the form {IF A/x & B/y & C/z … THEN write K/t to }

Execution process for a PS – REPEATEDLY, each rule in the PS is simultaneously tested -- if the IF part of a rule fully matches in the working memory then the variable/value combination of its THEN part is written to the specified working memory.

Two or more production systems interact if a rule of one can write directly to another. NB rules always match only on the working memory of their own PS.

A conflict resolution convention is needed when contradictory variable/value combinations (i.e. same variable, different values) can be simultaneously written to the same working memory. In this context an equi-probable random choice is to be made between the alternatives

Thanks for the explanation. Here is a link to the other question Prof. Doran mentioned:

https://www.researchgate.net/post/Can_anyone_suggest_an_algorithm_that_given_an_arbitrary_interacting_pair_of_production_systems_P1_and_P2_ENLARGES_the_rule_set_of_P1_to_MAXIMISE4

A colleague of mine with a background in evolutionary computation and myself with a background at self-organising systems have looked at this kind of problem before and have produced a number of ideas. A former Ph.D. student of his has taken these ideas and implemented some, albeit in a slightly less general form than we originally anticipated. I am not sure if the following papers are helpful to you, but they might at least serve as related work. You find the references to Abbas Sarraf's work in the first one.

https://www.researchgate.net/publication/260907352_Bring_it_on_Complexity%21_Present_and_future_of_self-organising_middle-out_abstraction?ev=prf_pub

https://www.researchgate.net/publication/260907275_Self-organized_middle-out_abstraction_of_complexity?ev=prf_pub

https://www.researchgate.net/publication/221035921_Self-organized_Middle-Out_Abstraction?ev=prf_pub

These papers all pertain to abstraction of repeated interaction patterns. The systems we had in mind are mostly of chemical or biological nature. If a body, e.g., has to be simulated, the level of observation is usually limited. We wanted to be able to simulate a body at all levels of observation, starting from molecular interaction, to cells, to tissue, to organs. Of course, this is utterly impossible if all interactions on all levels have to be regarded. Fortunately, most of these interactions are recurring and always exhibit the same side effects. If we can detect those interactions and find a suitable abstraction for them (i.e., check if the preconditions are there and then immediately instantiate the side effects without going through the complex interactions), we can save a lot of computational power. At the same time, these abstractions must be dissolved again if the preconditions are no longer valid so as to not lose any information.

We have had several versions of the algorithm running on much smaller systems than a body, but with good success. Unfortunately, time and money constraints have not allowed us to pursue our ideas further. Maybe they are useful to you now.

Chapter Bring It On, Complexity! Present and Future of Self-Organisi...

Article Self-organized middle-out abstraction of complexity

Conference Paper Self-organized Middle-Out Abstraction

An UPDATE

It has been suggested that the dumb MAS simplification algorithm previously proposed for a PS-MAS (see my answer of 12 days ago) can be improved and made more interesting by considering as  potential “simplifications” not just random deletions of rules, but rather replacements of pairs (or indeed other combinations) of rules by single equivalent rules e.g. two rules R1 {a&b&c => k} and R2 {a&b&d => k} can be replaced by the (assumed not already present) single rule R {a&b => k} PROVIDED that it is never the case that: [R executes when neither R1 nor R2 would have AND the consequence of R’s execution is to write k when k would not otherwise have been asserted].

Candidate simplifications can be selected heuristically.

It seems that each possible simplification must be checked over an entire execution history of the PS-MAS system (i.e. no quick proof of soundness) – which at first looks computationally heavy but is comparable with executing the system in the normal way.

Many thanks for answers from Mark and Jan-Philipp. Both very relevant in different ways. Mark helpfully and thought-provokingly broadens the perspective for me (though maybe doesn't distinguish as clearly as I would between the MAS itself and the code that implements it). Jan-Philipp's ideas certainly tie in, including with some undeveloped thoughts I had a while ago, so I will be following up the links he gives. Thanks again!

Best

Jim