Market-Oriented Programming and its Application to Power Load Management
Market-oriented programming is a new approach to design and implementation
of resource allocation mechanisms in computer systems. It has its roots
in different disciplines, such as economics and computer science (in particular
the area of multi-agent systems). This thesis is divided into two different
parts, focusing on: 1) central foundations and mechanisms of market-oriented
programming, and 2) the use of market-oriented programming in practical
Market-oriented programming is seen as a programming paradigm based
on abstractions such as prices and demands. Concepts, terminology and
theory from micro-economics form the foundations of the paradigm. Central
aspects of these foundations are investigated and some new insights are
presented. Furthermore, some relations between standard optimization/resource
allocation approaches and markets are described, and novel theorems are
introduced. A plethora of algorithms (some stemming from mathematical
optimization and numerical analysis, and some new) for the main computational
problem of market-oriented programming - the computation of general equilibrium
- are described, analyzed and compared. Some issues of self-interested
agents in market-oriented programming are also investigated.
A published, and generally recognized, market-oriented approach to the
application building climate control is analyzed in some detail. A new
approach to this application, based on market-oriented programming, is
introduced and shown to be superior to the analyzed approach in many ways.
The case study pinpoints a number of potential pitfalls as well as advantages
of market-oriented approaches to this and other applications.
A second investigated application is power load management, i.e. the
management of loads at the customers' side for obtaining more efficient
energy systems management. The basis of the application is described and
a new market-oriented approach is introduced and analyzed. The approach
is shown to have a number of advantages compared to existing approaches
to this problem.
The main conclusion of the thesis is that there are some potential pitfalls
of market-oriented programming, but when used with care it provides a
highly natural and efficient means for resource allocation in computer
Context and Main Research Issues
The research presented in this thesis has been performed in the research
group Societies of Computation (SoC) at the University of Karlskrona/Ronneby,
Sweden and I have been registered as a graduate student at Lund Institute
of Technology and Lund University, Sweden. The work has been managed as
a sub-project (sub-project 8) of the Information/Society/Energy/System project
- the ISES project - of EnerSearch AB. The ISES project is a multi-disciplinary
project with Ph.D. students and professors from, e.g., computer science,
business administration and electrical engineering. EnerSearch AB is a research
company owned by IBM Utility & Energy Services and Sydkraft AB. Sponsors
of EnerSearch AB include ABB Network Partner, Electricite de France, IBM
Utility & Energy Services, IT Blekinge, PreussenElektra AG, and Sydkraft
AB. For more information refer to the EnerSearch
Today's energy utilities are facing major changes. Many countries are
deregulating the electricity market (and other energy markets) and at
the same time the possibilities to communicate with customers increase.
Major enablers are concepts for global data networks (such as the Internet)
and new communication technologies (such as power-line communication),
see further Chapter 9. With this as a background the main question, put
to the ISES project as a whole, is: "How can these new technologies
increase the competitiveness of an energy utility?"
Of course, there are many aspects of a question of the above type, and
nine different sub-projects deal with different issues. For example, one
fundamental issue is if the customers are interested in interacting with
the utility at all, and, if so, how. The main research issue of one ISES
sub-project (sub-project 1) is to try to find efficient communication
means by providing the customer with the right amount and form of information
based on categorization of different customers' information acquisition
and processing characteristics. Another sub-project (sub-project 5) deals
with estimation of the potential gain of automating certain parts of the
The task that was assigned to sub-project 8 (which I have been working
in) was to investigate distributed load management. As both computation
and communication power is getting cheaper, the number of micro-processors
residing close to the customer increases. Domestic appliances are evolving
into "smart equipment" capable of doing quite advanced computation
and communicating with the outside world. The research issue of the distributed
load management project has been to investigate how all this "smart
equipment" should be utilized and coordinated for efficient use of
the energy system, i.e. to perform distributed load management.
The approach taken is to investigate the applicability of multi-agent
systems, and market-oriented programming in particular, to load management.
The main questions considered have been:
- What are the basic principles and properties of market-oriented programming?
- What is the relation between market-oriented programming and other
(traditional) approaches, such as mathematical optimization and traditional
approaches to resource allocation? Most importantly, what are the properties
of the market outcome?
- Can market-oriented programming be efficiently implemented? In particular,
can it be efficiently implemented in a distributed environment?
- Are there any existing market-oriented programming approaches to
closely related applications?
- What would a market-oriented programming approach to load management
look like and what would the properties of such an approach be?
This thesis contributes to results on general aspects of market-oriented
programming as well as its use in particular applications.
The area of market-oriented programming is rather new and stems from
many different disciplines. Many of the contributions are integration
and comparisons of results from different disciplines, such as economics,
computer science (and in particular the area of multi-agent systems),
mathematical optimization, numerical analysis, and control theory, whereas
other contributions are new.
In more detail, the main contributions are:
- A survey of market-oriented programming and clarification of basic
concepts, such as relations between different tatonnement processes
and price-oriented and resource-oriented market algorithms, and issues
related to production in market-oriented programming. (Chapter 2.)
- Novel theorems for how a general class of resource allocation problems
can be decomposed into markets, both with perfect information and under
uncertainty. (Chapter 3.)
- A detailed study of algorithms for market-oriented programming. The
study includes the introduction of new algorithms for market-oriented
programming based on different standard algorithms from numerical analysis
and mathematical optimization, the introduction of a new algorithm CoTree,
particularly well suited for implementation in distributed environments,
and some comparisons between existing market algorithms and the ones
introduced in the thesis. (Chapter 4.)
- The introduction of a novel algorithm for obtaining feasible solutions
from intermediate results of a price-oriented algorithm. This is particularly
useful when using market-oriented programming in time critical environments.
- Investigation of the potential gains and losses of speculation in
market-oriented programming, both with perfect information and in the
case where the agents hold biased information. (Chapter 6.)
- Detailed studies of a published, and generally recognized, approach
to market-oriented building climate control. The study includes analysis
of critical factors for the success and pinpointing of drawbacks of
the approach. Furthermore, a novel approach to the same problem is introduced
which, in several respects, is superior to the original one. There is
also some general conclusions regarding the applicability of competing
multi-agent approaches to this problem. (Chapter 8.)
- Introduction and evaluation of a novel approach to direct load management.
The novel approach has a number of advantages compared to existing approaches,
and the major concepts also seem highly applicable to indirect load
management. (Chapter 9 - Chapter15 .)
The very general conclusion of the thesis is that market-oriented programming
is a very useful approach for resource allocation in distributed systems
in that it often can be efficiently implemented and that it often provides
a straightforward way to decompose large problems, and that it relies on
very natural abstractions, such as prices, supply and demand. In some more
detail, the main conclusions are:
- Market-oriented programming strongly rely on micro-economic theory
and hereby it can take advantage of a significant amount of available
terminology, theory and tools. Production in market-oriented programming
introduces some issues (such as the risk of deadlock) which are not
considered in standard economics, and which require special care. (Chapter
- Many general resource allocation/optimization problems can be decomposed
into markets. (Chapter 3.)
- Market-oriented programming can be efficiently implemented in many
settings. However, we believe that algorithms for multi-commodity markets
in distributed environments still can be significantly improved. (Chapter
4 and Chapter 5.)
- The gains of speculation in one-shot markets where the utility functions
are submitted at once are small already with a moderate number of agents.
It is clear that for the application of load management when negotiating
for an upcoming hour and when entire utility functions are submitted,
it is sufficient to impose local optimization rather than competitive
behavior. However, speculation when markets are iterated over time or
when iterated algorithms are used for single shot markets (which typically
are required on multi-commodity markets) is a complex issue, and the
difficulties should not be underestimated. (Chapter 6.)
- Even though market-oriented programming is appealing from many perspectives,
comparisons with existing alternatives are important. Exaggerated claims
about the benefits of market-oriented approaches will inevitably lead
to backlashes. (Chapter 8.)
- Market-oriented programming provides a very natural way to manage
many large distributed resource allocation problems, and when properly
used it leads to high quality outcomes. In particular, we have demonstrated
that both the application of climate control and load management can
be successfully managed with this approach. (Chapter 8 - Chapter 15.)
Most of the material in this thesis has been presented at different conferences,
workshops, and seminars, and published in different books, proceedings or
technical reports. Here is a complete list of the publications that contain
some material published in the thesis, and some comment on the respective
paper's connection to the thesis. The list is given in chronological order.
All co-authors to the above papers are of course important contributors
to this thesis. In addition, a note should be added on the LoadSched algorithm.
This algorithm has been developed by Arne Andersson and Eric Schenk in cooperation
with the author. The use of the term "we" in the thesis refers
to me and the co-authors of the different parts. It should be kept in mind,
though, that all co-authors have not been able to proof read all material
and there is no claim that all of them agree to everything in the thesis.
- Staffan Hägg, Fredrik Ygge, Rune Gustavsson and Hans Ottosson, DA-SoC:
A Testbed for Modelling Distribution Automation Applications Using Agent-Oriented
Programming, Proceedings of Modelling Autonomous Agents in a Multi-Agent
World (MAAMAW '94), Odense, Denmark, 1994.
In this paper an early version of the basic architecture used in
Chapter 10 was presented, though the work was at a very early stage.
- Staffan H ägg and Fredrik Ygge, Agent-Oriented Programming in
Power Distribution Automation - An Architecture, a Language, and their
Applicability, Joint licantiate thesis, Department of Computer Science,
Lund University, CODEN: LUTEDX/(TECS-3056)/1-183/(1995), 1995.
The thesis discuss the use of market-based approach to load management
in quite general terms.
- Fredrik Ygge and Eric Astor, Interacting Intelligent Software Agents
in Demand Management, Proceeding of Distribution Automation/Demand
Side Management (DA/DSM) '95, PennWell Conferences and Exhibitions,
Some important difficulties and opportunities related to market-oriented
approaches for load management were discussed in this paper. It is
one step in the direction towards the current market-oriented approach
to load management.
- Fredrik Ygge, Rune Gustavsson, and Hans Akkermans,Homebots: Intelligent
Agents for Decentralized Load Management, Proceeding of Distribution
Automation/Demand Side Management (DA/DSM) '96, pp. 597 - 610, PennWell
Conferences and Exhibitions, 1996.
The paper presents a two-commodity approach (with only one explicit
commodity) to load management. Even though without technical detail,
different load management scenarios are demonstrated.
- Elmar van Dijk, Rolf Raven, and Fredrik Ygge, SmartHome User Interface:
Controlling Your Home Through the Internet, Proceeding of Distribution
Automation/Demand Side Management (DA/DSM) '96, pp. 675 - 686, PennWell
Conferences and Exhibitions, 1996.
The paper describes the integration of domestic appliances and the
Internet, and is relevant for Chapter 9.
- Hans Akkermans, Fredrik Ygge, and Rune Gustavsson, HOMEBOTS: Intelligent
Decentralized Services for Energy Management, In J. F. Schreinemakers
(Ed.), Knowledge Management: Organization, Competence and Methodology,
Ergon Verlag, Wuerzburg, D, 1996.
This paper has many similarities with (iv) above, but is written
more for an audience with a knowledge management background.
- Fredrik Ygge and Hans Akkermans, Power Load Management as a Computational
Market, Proceeding of the Second International Conference on Multi-Agent
Systems (ICMAS) '96, pp 393 - 400. AAAI Press, 1996.
A two-commodity (with only one explicit commodity) approach to load
management was presented in some detail in. The paper is an important
base for both Chapter 4 and Chapter 9 - Chapter 15.
- Fredrik Ygge, A Framework for Computational Markets, Term paper
for the course: Graduate Course on Patterns and Frameworks, January
1997, available from this
This paper describes how OOP concepts, such as design patterns and
framework, can be utilized for the implementation of computational
markets. The paper is relevant for some discussion in Chapter 2.
- Fredrik Ygge and Hans Akkermans, Making a Case for Multi-Agent Systems,
Proceedings of the Eighth Modelling Autonomous Agents in a Multi-Agent
World (MAAMAW '97), pp. 156-176. Springer Verlag, 1997.
Chapter 8 is based on this paper.
- Tuomas Sandholm and Fredrik Ygge, On the Gains and Losses of Speculation
in Equilibrium Markets, Proceedings of the Fifteenth International
Conference on Artificial Intelligence (IJCAI '97), Morgan Kaufmann,
This paper essentially constitutes Chapter 6.
- Hans Akkermans and Fredrik Ygge, Smart Software as Customer Assistant
in Large-Scale Distributed Load Management, Proceeding of Distribution
Automation/Demand Side Management Europe (DA/DSM) '97, PennWell
Conferences and Exhibitions, 1997.
The scheduling problem is introduced together with other important
considerations, such as the transformation between customer preferences
and utility functions in a form useful on computational markets. It
also describes achieved results in a rather non-technical way. The
paper serves as background for Chapter 9 - Chapter 15.
- Fredrik Ygge, Power Load Management as a Multi-Commodity Market,
University of Karlskrona/Ronneby Research Report 1997:15, ISSN: 1103-1581.
Date: 18 November 1997.
This report is a first draft of Chapter 9 - Chapter 15.
- Fredrik Ygge and Hans Akkermans, Duality in Multi-Commodity Market
Computations, C. Zhang and D. Lukose, editors, Proceeding of the
Third Australian Workshop on Distributed Artificial Intelligence,
pages 65 - 78, Perth, Australia, 1 December 1997.
Introduction of the multi-commodity resource oriented algorithm
(Chapter 4) and the Proportion algorithm (Chapter 5).
- Arne Andersson and Fredrik Ygge, Managing Large Scale Computational
Markets, Proceedings of the 31st Hawaiian International Conference
on System Sciences, VOL VII - Software Technology Track, pages 4
- 13, Big Island Hawaii, 6-9 January, IEEE Computer Society, 1998.
Introduction of the CoTree algorithm (Chapter 4).
- Hans Akkermans, Rune Gustavsson and Fredrik Ygge, Pragmatics of Agent
Communication, Proceedings of KAW'98, Banff, Canada, 18 - 23
April, 1998. (In press.)
This paper focuses on agent communication and the market-oriented
load management approach in this thesis is used as an example. The
communication diagram style has (with some modifications) been used
in Chapter 9.
- Fredrik Ygge and Hans Akkermans, On Resource-Oriented Market Computations,
Proceedings of the Third International Conference on Multi-Agent
Systems, (ICMAS 98), Paris, France, August, 1998. (In press.)
A revised presentation of the resource-oriented multi-commodity
algorithm introduced (xiii) above.
- Fredrik Ygge and Hans Akkermans, Market Computations in Time-Critical
A revised presentation of the Proportion algorithm introduced in
"Duality in Multi-Commodity Market Computations" above.
- Fredrik Ygge, Hans Akkermans and Arne Andersson, A Multi-Commodity
Market Approach to Power Load Management, Submitted.
A revised and compressed version of the report "Power Load
Management as a Multi-Commodity Market". Furthermore, it introduces
the theorems presented in Chapter 3.
Outline of the Thesis
The thesis is divided into two parts. Part 1 deals with general issues related
to market-oriented programming and Part 2 describes the application of market-oriented
programming to two important applications.
Chapter 2 aims at clarifying the foundations of market-oriented programming
and to serve as an introduction to the other chapters in Part 1. Basic
terminology and concepts from economics are presented and some differences
between economics and market-oriented programming are described. The chapter
also gives an introduction to how general equilibrium theory can be applied
to actual resource allocation. The next chapter, Chapter 3, formally describes
how general resource allocation problems can be modeled as markets. Thus,
this chapter shows some fundamental relations between economics and mathematical
optimization/numerical analysis. The problem of actually computing a market
outcome is treated in Chapter 4. Here a large number of algorithms with
different properties are described and compared. One of the conclusions
of Chapter 4 is that a wide class of algorithms (price-oriented algorithms)
have a property which makes them useless as any-time algorithms. In Chapter
5 we introduce a novel approach to overcome this problem. Chapter 6, deals
with the issue of speculation in equilibrium markets. That is, can agents
gain (or lose) by revealing false preferences? The final chapter of Part
1, Chapter 7, gives a general summary of Part 1.
The first chapter in Part 2, Chapter 8, studies an existing market-oriented
approach to building climate control in some detail. The remaining chapters
of Part 2, Chapter 9 through Chapter 15, are dedicated to power load management.
Chapter 9 gives a short introduction to load management and describes
different issues important for future energy utilities. In Chapter 10
a multi-agent architecture for load management is introduced. The architecture
is then demonstrated on a specific load management example in Chapter
11. The issue of scheduling loads is discussed in Chapter 12. Another
example is then given in Chapter 13. Different general issues of simplifications
and generalizations, for, e.g., the incorporation of more complex load
models, are treated in Chapter 14. The final chapter of Part 2, Chapter
15, contains a summary discussion and conclusions regarding the market-oriented
approach to load management.
Finally Chapter 16 presents the conclusions of the thesis.
A word (or words) marked >like this appears in the glossary.
Terms appearing in the glossary are not marked this way every time they
occur, but rather when it is assumed to help the reader.
Market-oriented programming is seen as a new paradigm for design and implementation
of resource allocation mechanisms in computer systems. This thesis presents
some fundamental issues related to market-oriented programming and its application
to building climate control and power load management.
As shown in this thesis market-oriented programming has a multi-disciplinary
flavor. The approach stems mainly from economics and computer science
(in particular the area of multi-agent systems), but also other disciplines
such as traditional mathematical optimization, resource allocation and
numerical analysis, are of big importance. In this thesis we have showed
how market-oriented programming can benefit from the use of methods and
abstractions from other disciplines and what the relation between market-oriented
programming and some of these disciplines are. For example, in Chapter
3 we formally showed how a general class of optimization problems could
be transformed into corresponding market formulations.
One of the basic ideas in market-oriented programming is to use abstractions
from micro-economic theory for design and implementation of resource allocation
mechanisms. Thus, even though market-oriented programming and micro-economics
have much in common the objectives of the two different disciplines are
in many way different. The aim of micro-economics is to develop methods
that describes and formalizes human behavior. In market-oriented programming
the aim is, as stated above, to use the developed abstraction to design
and implement systems. This means that some questions are fundamentally
different whereas others are of common interest.
Even though the close relation to micro-economics provides us with very
useful theory and appealing concepts for market-oriented programming,
there are some potential problems. One is related to production. In standard
micro-economics the ordering of production is not considered. In market-oriented
programming, however, this can be a critical issue. As was discussed in
Chapter 2, different production dependencies can lead to dead-lock situations.
Another, and probably more important, danger is related to the association
between human agents and computational agents. An important conclusion
of this thesis is that the metaphor must not be taken too far. It is appealing
to use metaphors such as the "invisible hand", developed for
the human society, also for computer systems. However, as we have described
in this thesis, things are not that easy, and nice abstractions are of
little help if they are not used properly. For market-oriented approaches
to be generally accepted, in-depth studies of advantages and weaknesses
of multi-agent systems solutions versus conventional ones in practical
applications are needed. In Chapter 8, we offered one such study. Climate
control in large buildings is one application area where multi-agent systems,
and market-oriented programming in particular, have been reported to be
very successful. We have therefore constructed and implemented a variety
of market designs for this problem, as well as different standard control
engineering solutions. The chapter gives a detailed analysis and comparison,
so as to learn about differences between standard versus multi-agent systems
approaches, and yielding new insights about benefits and limitations of
A key question is: in what respect and to what extent are multi-agent
(and market-oriented) solutions better than their alternatives? We believe
that the building climate control application provides a nice opportunity
to study this question in more detail. It is practically very relevant,
it lends itself to alternative solutions, and it is quite prototypical
for a wide range of industrial applications in resource allocation (including
the power load management applications presented in Chapter 10 -- Chapter
15, the file allocation problem of Kurose and Simha, and the flow problems
investigated by Wellman).
We have therefore shed light over some potential dangers. In some detail
we have demonstrated that the suggested market-oriented approach indeed
outperformed standard local controllers. On the other hand we also demonstrated
that traditional controllers having access to the same data perform even
better. A positive result was, however, that we demonstrated how proper
utility functions and market mechanisms can provide an optimal scheme
from agents using only local data and communicating through prices and
On the positive side we also have that the agent and market approach
does give a highly intuitive and natural picture of problems in distributed
environments -- even when at a strictly algorithmic level it effectively
leads to the same end result as alternative approaches. We do believe
that this is a value in itself: for conceptual modeling, understanding,
explanation, and knowledge transfer. Moreover, models and pictures that
have conceptual simplicity are more easily generalized to more complicated
situations. Because of its focus on local information, communication and
action, the agent paradigm is more flexible than centralized approaches.
This does not show up very clearly in the building climate control application,
because the limited scope of this resource allocation problem. For example,
here the temperature was a uniform performance measure and all thermodynamic
processes are assumed to be equal. This will generally not be true in
reality, and that will necessitate a big modeling efforts in centralized
approaches as standard control engineering. For the present case, we have
shown that the multi-agent systems approach offers working solutions of
In Chapter 3 we showed that the market-metaphor does not only result
in optimal solution for the particular example of building climate control,
but for very general classes of resource allocation/optimization problems,
also in the presence of uncertainty. This formed the basis for our market-oriented
load management design of Chapter 10.
The applicability of market-oriented programming to load management
was discussed in Chapter 9-- Chapter 15. We introduced a novel approach
to load management based on local agents Homebots communicating through
market mechanisms. The approach was also demonstrated on a number of examples.
Our conclusion is that the approach is highly applicable to load management
and that it has a number of advantages compared to traditional approaches.
Main features of the approach is that it:
Having concluded that it is possible to design a load management system
as a market-oriented multi-agent system, and that the market outcome is
of very high quality the remaining question is if this market-outcome can
be efficiently computed or not. This issue was dealt with in detail in Chapter
4 and Chapter 5. The investigation showed that there is a plethora of available
algorithmic families from numerical analysis and mathematical optimization
that are highly applicable to this setting. We also introduced a novel algorithm
CoTree, particularly well suited for implementation in distributed environments.
- provides an integrated load management strategy for many different
types of loads and customer contracts,
- obtains a high quality solution (often the market outcome is a close
approximation of the true theoretical optimum),
- enables natural decomposition of the problem from a software engineering
perspective as well as from a computational perspective,
- gives the utility a view of the system based on the most natural
abstractions -- prices and demand, and
- provides a local estimate of the value of the customer contract,
i.e. gives an on-line cost/benefit analysis.
In concluding the conclusions, if there should be one single conclusions
for the thesis as a whole it should be this: Market-oriented programming
is very useful for the design and implementation of resource allocation
mechanisms in computer systems and highly applicable to applications such
as power load management, but it should be used with great care and expectations
should be well balanced.