Combinatorial Optimization and Society
“the central problem in computer science: avoiding or minimizing the effects of the combinatorial explosion of possibilities in a search space” — J.A.Campbell
Campbell’s claim is too modest — the combinatorial explosion is not just the central problem in computer science, but in society as a whole.
The relevant branch of mathematics is graph theory, where the term ‘graph’ does NOT mean a plot or chart showing the change in one variable with respect to another but a picture of the links or interconnections joining a few points or nodes. The relevant branch of computer science is combinatorial optimization, in which such graphs are associated with a metric or measure of goodness or cost.
The most famous combinatorial optimization problem is the travelling salesman problem, in which the goal is to find the least expensive closed path joining a set of cities, and the overall cost is nominally the sum of the costs of each link (road, flight, etc.) between cities. This problem is too hard, and there are no algorithms guaranteed to find the best solution, but approximation algorithms exist for finding relatively good solutions. One of the best approximation algorithms is Lin’s 3-opt algorithm which starts with any closed path that joins all cities, then improves it by randomly choosing 3 cuts that divide the closed path into 3 parts, and then searching for the best way of rejoining the parts. This can be repeated over and over again until a solution that is good enough is found.
A problem more relevant to the organization of society is the bipartite matching problem. Technically the bipartite matching problem is simply to find a graph in which each node or point is connected to exactly one other node, but some applications assume that the nodes are first divided into two sets and the object is to connect each node in one set to exactly one from the other set. For example, one could divide humanity into males and females and discuss the bipartite matching problem of connecting each male to exactly one female — but the more more general problem is simply to make sure that each person is connected to exactly one other person, regardless of gender.
A bipartite matching problem can be weighted or non-weighted, and for social purposes we probably want to consider each possible link between nodes as having a cost or a value. On other pages I discuss the problem of costs or values, which can be very subjective, but for now I’ll simply assume that we have some way of estimating the cost or value of a link, which I’ll simply refer to as cost, but I will allow costs to be positive or negative real numbers — and will later extend this to complex numbers.
Most of the techniques or algorithms used for combinatorial optimization problems are rather authoritarian processes in which the program makes and breaks connections many times, without giving the vertices of the graph any choice over what edges might connect them, something real people are unlikely to accept.
I think the answer lies with parallel graph algorithms, or methods in which the graph is partitioned into smaller subgraphs which are then worked on in parallel. Part of that parallel processing is actually to be done by the people involved, who may be able to work effectively in solving difficult problems if matched with other individuals who have different error tendencies.
It is common in statistical analysis to compare the covariance or correlation of multiple variables but, when we are concerned with optimization and have a definition of optimal, it is more appropriate to talk about error-covariance, which considers the variables not simply in relation to one another, but relative to the correct or best answer. An essential idea part of my approach here is the possibility of minimizing error-covariance by matching individuals with co-workers and friends to produce teams which collectively make far fewer errors than any of the individuals working alone.
Here is an entirely non-technical comment about error-covariance which formerly headed up my home page:
There are people out there who share your interests but make very different kinds of mistakes than you do. It can be enormously to your advantage to associate or communicate with such people.
There are people out there who not only share your interests but make almost exactly the same kinds of mistakes that you do. It can be terribly to your disadvantage to associate or communicate with such people.
The Internet and the World Wide Web can make it easy to find people with the same interests as you, but currently it doesn’t provide much help in discriminating between the ones that can help you avoid mistakes and the ones that will provoke you to make even worse mistakes.
I intend this page to have a great many technical details, explained better, and eventually accompanied by source code and data for download. Until then, you might like to look at some of the pages in the Work-In-Progress section.
Copyright © 1998 Douglas P. Wilson
Copyright © 2009 Douglas Pardoe Wilson
Other relevant content:
Please see these web pages:
The main Social Technology page.
Find Compatibles , the key page, with the real solution to all other problems explained
Technological Fantasies , a page about future technology
Social Tech a page about Social Technology, technology for social purposes. I think I was the first person to use this phrase on the Internet, quite a long time ago.
Roughly corresponding to these web pages are the following blogs :
Social Technology the main blog, hosted on this site, with posts imported from the following blogger.com blogs, which still exist and are useable.
Find Compatibles devoted to matching people with friends, lovers, jobs, places to live and so on, but doing so in ways that will actually work, using good math, good algorithms, good analysis.
Technological Fantasies devoted to future stuff, new ideas, things that might be invented or might happen, such as what is listed above and below.
Sex-Politics-Religion is a blog about these important topics, which I have been told should never be mentioned in polite conversation. Alright that advice does seem a bit dated, but many people are still told not to bring up these subjects around the dinner table.
I believe I was the first person on the Internet to use the phrase Social Technology — years before the Web existed.
Those were the good old days, when the number of people using the net exceeed the amount of content on it, so that it was easy to start a discussion about such an upopular topic. Now things are different. There are so many web pages that the chances of anyone finding this page are low, even with good search engines like Google. Oh, well.
By Social Technology I mean the technology for organizing and maintaining human society. The example I had most firmly in mind is the subject of Find Compatibles , what I consider to be the key page, the one with the real solution to all other problems explained.
As I explained on my early mailing lists and later webpages, I find that social technology has hardly improved at all over the years. We still use representative democracy, exactly the same as it was used in the 18th century. By contrast, horse and buggy transporation has been replaced by automobiles and airplanes, enormous changes.
In the picture below you will see some 18th century technology, such as the ox-plow in the middle of the picture. How things have changed since then in agricultural technology. But we still use chance encounters, engagements and marriages to organize our home life and the raising of children.
I claim that great advances in social technology are not only possible but inevitable. I have written three novels about this, one preposterously long, 5000 pages, another merely very very long, 1500 pages. The third is short enough at 340 pages to be published some day. Maybe. The topic is still not interesting to most people. I will excerpt small parts of these novels on the web sometime, maybe even post the raw text for the larger two.
This site includes many pages dating from 1997 to 2008 which are quite out of date. They are included here partly to show the development of these ideas and partly to cover things the newer pages do not. There will be broken links where these pages referenced external sites. I’ve tried to fix up or maiintain all internal links, but some will probably have been missed. One may wish to look at an earlier version of this page , rather longer, and at an overview of most parts of what can be called a bigger project.
Type in this address to e-mail me. The image is interesting. See Status of Social Technology
Copyright © 2007, 2008, 2009, Douglas Pardoe Wilson
I have used a series of e-mail address over the years, each of which eventually became out of date because of a change of Internet services or became almost useless because of spam. Eventually I stuck with a Yahoo address, but my inbox still fills up with spam and their spam filter still removes messages I wanted to see. So I have switched to a new e-mail service. Web spiders should not be able to find it, since it is hidden in a jpeg picture. I have also made it difficult to reach me. The picture is not a clickable link. To send me e-mail you must want to do so badly enough to type this address in. That is a nuisance, for which I do apologize, but I just don’t want a lot of mail from people who do not care about what I have to say.
Copyright © 2009 Douglas Pardoe Wilson