# Water Pollution Reduction: Reverse Combinatorial Auctions Modelling Supporting Decision-Making Processes

Petr Šauer, Petr Fiala, Antonín Dvořák

► To cite this version:

Petr Šauer, Petr Fiala, Antonín Dvořák. Water Pollution Reduction: Reverse Combinatorial Auctions Modelling Supporting Decision-Making Processes. 11th International Symposium on Environmental Software Systems (ISESS), Mar 2015, Melbourne, Australia. pp.196-206, 10.1007/978-3-319-15994-2_19. hal-01328549

HAL Id: hal-01328549

https://inria.hal.science/hal-01328549

Submitted on 8 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Water Pollution Reduction: Reverse Combinatorial
Auctions Modelling Sup porting Decision-Making
Processes

Petr Šauer, Petr Fiala, Antonín Dvořák

University of Economics, Prague, Czech Republic
{sauer,pfiala,advorak}@vse.cz

**Abstract.** This paper presents a model that contributes to finding cost-effective solutions when making decisions about building wastewater treatment plants in the planning process defined in the Framework Directive 2000/60/EC of the European Parliament and of the European Council. The model is useful especially when construction and operation of joint wastewater treatment plants is possible for several (neighbouring) municipalities, where a huge number of theoretical coalitions is possible. The paper presents the model principles for one pollutant and for multiple pollutants, describes the CRAB software used for computing the optimal solutions and presents selected applications. It concludes that the computations can contribute directly to decision-making concerning environmental protection projects and also serve for calculating background models for economic laboratory experiments in the area.

**Keywords:** environmental protection · environmental management · decision-making · CRAB software · water pollution · combinatorial auctions

# 1 Introduction

There are still situations in the area of surface water quality that require solutions in the Czech Republic and other advanced countries, in spite of a noticeable improvement since the 1980s, as municipalities with more than 2000 equivalent inhabitants have had to ensure sewerage and wastewater treatment by the end of 2010 pursuant to the implemented Framework Directive 2000/60/EC of the European Parliament and of the Council [1]. It is important to respond to the need for timely adaptation to climate change in progress, secure drinking water sources, increasing demands for recreational water quality as a consequence of improving living standards, enhancements in nature protection, and creation of conditions for further scientific and technical development in water quality improvement.

Planning for river basins consists of a series of decisions leading to the implementation of appropriate water protection projects. A new planning process concerning waters is defined in the Directive 2000/60/EC, establishing a framework for Community action in the field of water policy. This Framework Directive has been progressively transposed into the Czech legal system by a series of legislative standards. This
fact has brought about a significant change to the whole system since 2004, and new
national documents in the area of water management planning have had to be devel-
oped. Planning concerning waters has become a systematic policy area managed by
the national government. Updates of the plans are made every 6 years.

Our modelling support relates to so-called *sub-catchment plans*. They define goals in protection of water as an environmental component (i.e., environmental goals) to be achieved in water bodies by 2015 or in the next two six-year planning periods. New functional forms of coordination of involved parties are being sought, i.e., not only those responsible for developing the plans but also other stakeholders, including professional and non-governmental organizations.

Increasing emphasis is placed on the economic efficiency of proposed and imple-
mented measures, not only due to the current economic situation. This is particularly
true in cases where a subsidy from public sources is offered to relevant projects (at the
national or EU level). There is a wealth of literature dealing with finding cost-
efficient solutions in wastewater treatment.

One of the ways of ensuring cost-effective solving of surface water quality prob-
lems is to find technical projects/designs shared by multiple polluters (so-called “coa-
lition designs”). A new strategy is being promoted: reducing the risks caused by in-
creasingly smaller sources. The specific feature of this strategy is that it allows im-
plementation of so-called coalition projects, i.e., joint projects implemented by multi-
ple polluters. A typical example is the construction and operation of joint wastewater
treatment plants for several (neighbouring) municipalities.

Auctions are important market mechanisms for the allocation of goods and ser-
vices. Reverse combinatorial auctions serve as a theoretical framework for the ap-
proach presented in the paper. Combinatorial auctions [4] are those auctions in which
bidders can place bids on combinations of items, so-called bundles. The advantage of
combinatorial auctions is that the bidder can express his preferences more fully. It is
possible to formulate single-sided combinatorial auctions, forward auctions and re-
verse auctions. In forward auctions, a single seller sells resources to multiple buyers.
In reverse auctions, a single buyer attempts to source resources from multiple suppli-
ers.

The paper intends to demonstrate the possibilities of model support to this deci-
sion-making process in two areas: (i) model support to finding a cost-effective solu-
tion to a given task of reducing pollution by a specified key pollutant. A typical ex-
ample is the task of reducing phosphorus emissions to a certain level to reduce eu-
trophication in surface waters; (ii) and model support to decision-making, which in-
cludes multiple criteria. The CRAB software [2], which makes it possible to compute
results for quite complex situations, is described, followed with a presentation of se-
lected applications.
## 2 Decision-Making Diagram

The simplified decision-making diagram for the planning process in the field of sewerage and wastewater treatment as described above is presented in Figure 1. The main decision-making stages are identified in it.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Diagram of the planner's (entire) workflow</figcaption></figure>
Based on the documents elaborated within the first analysis of the problem, it is decided if the solved problem is complex and requires optimization with using a combinatorial auction model. If yes, input data are collected and verified and it is decided whether they are of sufficient quality for the modeling. If yes, the optimal solution is calculated and is commented within the draft plan by experts and stakeholders. In the case the plan is approved, the stages of Environmental impact assessment procedure, the plan final approval and its publication follow.

The calculation model supporting the decision-making process is shown in steps 3-7 in particular. For a more detailed description of the whole process, see the Methodology for economic and environmental optimization of reducing pollution in water-courses approved by the Czech government [3].

# 3 Models for Calculating a Cost-Effective Solution with Environmental Criteria

## 3.1 Model with One Environmental Criterion

We propose to use a model for reverse combinatorial auctions searching for a cost-effective combination of projects to reduce pollution. We assume that one environmental indicator is reduced to the desired level for all the projects. Therefore, it is possible to focus on the cost side of the problem.

We present a reverse combinatorial auction [4] of projects with one authority and several polluters. Let us suppose that $m$ potential polluters $S_1, S_2, ..., S_m$ offer a set $R$ of $r$ projects, $j = 1, 2, ..., r$, to one buyer $A$.

A bid made by the polluter $S_h, h = 1, 2, ..., m$, is defined as

$$b_h = \{C, c_h(C)\},$$

where

$C \subseteq R$ is a combination of pollution sites, and

$c_h(C)$ is the price offered by the polluter $S_h$ for the combination $C$.

The objective is to minimise the buyer's costs given the bids made by polluters. Constraints establish that the procurement provides at least a set of all items.

Bivalent variables are introduced for the model formulation:

$y_h(C)$ is a bivalent variable specifying whether the combination $C$ is bought from the polluter $S_h$ ($y_h(C) = 1$).

The reverse combinatorial auction can be formulated as follows

$$\sum_{h=1}^{m} \sum_{C \subseteq R} c_h(C)y_h(C) \rightarrow \min$$

subject to

$$\sum_{h=1}^{m} \sum_{C \subseteq R} y_h(C) \geq 1, \quad \forall j \in R, \qquad (1)$$
$$y_h(C) \in \{0,1\}, \forall C \subseteq R, \forall h, h = 1, 2, \dots, m.$$

The objective function expresses the costs. The constraints ensure that the selection of projects includes all the pollution sites.

See section 5 for an illustration of this approach.

## 3.2 Model with Multiple Environmental Criteria

The basic model (1) can be extended for situations with multiple environmental criteria. We assume $k$ environmental indicators, $i = 1, 2, \dots, k$. A bid made by the polluter $S_h$ is extended by $e_{ih}(C)$ is the reduction in the environmental indicator $i$ offered by the polluter $S_h$ for the combination $C$.

The reduction in the environmental indicator $i$ in the whole region is given by the limits $E_i, i = 1, 2, \dots, k$. Then the environmental aspect of the problem can be modelled by a set of constraints

$$e_{ih}(C)y_h(C) \geq E_i, i = 1, 2, \dots, k. \quad (2)$$

In situations without limits, the problem can be extended in a multi-objective version of the problem (1) with a set of added objective functions

$$\sum_{h=1}^{m} e_{ih}(C)y_h(C) \rightarrow \max, i = 1, 2, \dots, k. \quad (3)$$

The multi-objective programming problem can be solved by corresponding approaches.

See section 5 for an illustrative example of this approach.

# 4 CRAB – Combinatorial Auction Body Software System

A need for an input problem generator arose during our research into combinatorial auctions. The CATS [5], software developed by Stanford University can be used for combinatorial auction problems, but it does not meet the specific needs of our problem. To satisfy our needs, we have developed our own software tool: CRAB [2]. This tool has several advantages comparing CATS, namely:

* fast problem generation,

* combinations are generated in a more predictable way,

* combinations are generated only in given subset of all items,

* CSV is used as the primary data format,

* fine-grained control over problem generated,

* built-in linear problem solver,

* multiple output formats.
This tool is implemented in Ruby. We choose Ruby for performance reasons, mainly for its dynamic, agile nature with enables us to quickly experiment with different approaches.

## 4.1 Overview

A combinatorial auction problem is given by the number of buyers and the number of all feasible combinations of goods – bundles. Prices of bundles – bids – and a budget are also needed for each buyer. The number of goods is read in the vector form where the number of vector components (comma separated) is equal to the number of bundles. Each vector component corresponds to the number of goods in the bundle.

All the combinations of goods in each bundle (except the empty set) are generated in the first phase. This step is done for every bundle. In this way, all the bundles are generated. The list of these bundles is saved in a file (\*.csv) – one bundle per row – and one column is prepared for each buyer. The first row contains a column label and the second row is given to the buyer's budget.

The user of the CRAB software can load the CSV file into a text editor or a spreadsheet and fill in the bids (i.e., the price offered by the buyer for a particular bundle) and budgets for each buyer. If the user uses CRAB only for tests, he/she can use automatically generated prices and budgets. In both cases, the final file has to be saved in the CSV format again.

In the second phase, the file is transformed into a binary programming problem. The bundles correspond to variables and the bids correspond to prices of the objective function that is being maximized. The problem consists of automatic constraints for each good (each good can be sold only once) and each buyer (a buyer cannot exceed his budget). The user is free to change the automatically generated constraints and remove or add (for example non-typical) constraints. All the data have to be saved in the CSV format again.

Finally, the problem can be passed to the built-in binary programming solver to find out the optimal solution for the given combinatorial auction. If so, the problem is transformed into a form with minimizing the objective function with non-negative prices and all the constraints in the "less or equal" form. Afterwards, the transformed model is passed to the Balas algorithm [6]. The CRAB architecture gives a possibility to extend the system, especially about the implemented models and algorithms.

## 4.2 Practical Use

CRAB can operate in two modes: (i) an interactive mode, and (ii) a command line mode. CRAB can be run in an interactive mode, which means that the user is prompted for data interactively. Contrary to interactive mode, the CRAB can operate in a command line mode, which means that all input data as well as all options have to be supplied on the command line.

The CRAB can generate combinatorial problems. The principal command is:
ruby crab.rb --output <outfile> generate --buyers <nb> --
bundles <bundlespec>

where `<nb>` is the number of buyers (non-negative integer value) and `<bundlespec>` is a vector specifying the number of items in each bundle. The number of bundles is determined by the dimension of the vector. The vector should be entered as a comma-separated sequence of positive integer values with no spaces in between. CRAB can also generate random prices for each bundle as well as a budget for each buyer.

The generated file is an ordinary CSV (Comma Separated Values) file and thus ed-
itable by almost every spreadsheet application. The first row contains only column
labels and no data. The second row contains a budget for each buyer. The rest of the
rows specifies bids of bundles given by each buyer.

The first two columns contain only labels and no data. The first column denotes the bundle, the second one denotes the particular goods combination within the bundle. A bundle is denoted by the ID of the first and last goods item in the bundle; the combination is denoted by a minus-separated list of goods IDs. The following columns contain the bids made by the buyers.

4.3 Transforming Combinatorial Auction to Binary Programming Problem

Once the combinatorial auction is generated, it can be transformed to the form of a
binary programming problem and passed to the binary programming solver after-
wards. The principal command for the combinatorial auction transformation is:

./ruby crab.rb --output <output file> transform --bids <input file>

where `<input file>` is the CSV file specifying the combinatorial auction. The
form of the input file must be the same as the output of the generate command. Op-
tionally, the user can use the `--format` option to specify the output format. CRAB
currently supports two output formats: (i) CSV (which is the default) and (ii) XA. The
first one is the one used by the built-in solver; the latter can be passed directly to the
XA integer solver [7].

The following command will transform the file `bids.csv` into a binary programming
problem, saving the output to a file named `problem.csv` using the CSV format.

./ruby crab.rb --output problem.csvs transform --bids bids.csv

The following command will create a binary programming problem specification
file as used by the XA solver:

./ruby crab.rb --output problem.lp transform --format xa --bids bids.csv
* all of the 20 individual projects (i.e., a situation where each of the municipalities would build its own wastewater treatment plant); they were coded as A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, D1, D2, D3, D4, E1, E2, E3, E4;

* all of the 14 "promising" coalition projects, i.e., costs of such coalition projects that cannot be excluded from the analysis beforehand for technical, economic, environmental, morphological, political or other reasons; they were coded as A1+A2, A3+A4, A3+A4+B1+B3, B2+B3, B2+B3+B4+C2, B4+C1+C2, C3+C4, C3+C4+D2, C3+C4+D1+D3, D1+D2+D3, D1+E1, D4+E2, D4+E2+E3.

The CRAB software was used. The calculated optimal solution is as follows:

* 7 individual projects: B1, C1, C3, C4, E1, E3, E4

* 3 two-member coalitions: A1 + A2, A3 + A4, D4 + E2

* 1 three-member coalition: D1 + D2 + D3

* 1 four-member coalition: B2 + B3 + B4 + C2

Total costs of coalition solutions = CZK 720,600 thousand

Total costs of individual solutions = CZK 1,212,400 thousand

Cost saving if the coalition solutions are applied = CZK 491,800 thousand; i.e., about 40%.

See the simplified case in section 5.2 for the design of the mathematical model of this exercise.

## 5.2 Case with Multiple Criteria

An ideal case, close to a practical situation, has been created and called the Powder Brook case. It is an illustrative application to a case of a small river basin with 4 municipalities polluting a brook with one tributary. In spite of some necessary simplifications, the authors have striven for maximum approximation to the real situation in one of the tributaries to the Elbe river basin in Bohemia (Czech Republic).

Environmental criteria entering the analysis in this case were adopted from pollution production monitored pursuant to Government Regulation No. 61/2003 Coll. [8], and ČSN 75 6401 [9], which specifies the daily production of BOD₅ at 0.06 kg/EI, Pₜotal at 0.0025 kg/EI, Nₜotal at 0.015 kg/EI, and N-NH₄⁺ at 0.011 kg/EI. These environmental parameters were adopted and modelled as a set of constraints (2) as described in section 3.2.

The mathematical model of the exercise for the analysis is as follows:

$$N = 6500 y_A + 16,250 y_B + 29,000 y_C + 32,750 y_D + 27,750 y_{AB} + 41,750 y_{BC} + 59,000 y_{BD} + 65,000 y_{CD} + 50,000 y_{ABC} + 69,000 y_{BCD} + 73,000 y_{ABCD} \rightarrow \text{min}$$

The optimum solution to this exercise:

$$y_A = 0, y_B = 0, y_C = 0, y_D = 0, y_{AB} = 0, y_{BC} = 0, y_{BD} = 0, y_{CD} = 0, y_{ABC} = 0, y_{BCD} = 0, y_{ABCD} = 1.$$

One coalition project – ABCD – should be implemented.
The total costs N = CZK 73,000 thousand = saving of CZK 11,500 thousand compared to individual projects (common practice; CZK 84,500 thousand).

The case was very simple (only 4 subjects-municipalities where the presented software is not actually needed) for two reasons: (i) it serves as an understandable illustration of the methodology mentioned above developed by the authors of this paper [3]; and (ii) the results served as a background model for economic laboratory experiments, which are mentioned in the discussion. The authors of this paper are currently working on quite sophisticated applications.

# 6 Discussion and Conclusion

The calculations using the CRAB software produce very usefully information for support of decision-making of a public authority (government) when finding the cheapest solutions to water pollution reduction in situations where coalition (common) projects exist and experts are able to assess all the important information. The result is a cost-effective solution, which, in complex situations, would be very difficult to find by traditional computational methods.

In reality, especially in situations where the polluters are offered some financial support from public funds (subsidies), there is an information asymmetry between the authority and the polluters. It means that the polluters do not tell the truth about their abatement costs and try to apply for as much as possible from the funds. In such situations, the calculation using the CRAB software can help to calculate the optimal solution for testing the polluters' behavior in the form of economic laboratory experiments. The experiments then test how close or far from the optimal solution the negotiated outcomes are. For more details about these experiments, see [10] and [11]. In other words, the laboratory experiments can help test alternative institutional settings in the field, including settings where multiple criteria are introduced. See [12] and [13] for a costs-effectiveness analysis of public spending on environmental protection when multiple criteria are applied in the Czech conditions. Computing optimal solutions would also be helpful when testing alternative settings with public participation in decision-making. See [14] and [15] for a discussion of public participation in decision-making, and [16] for a typical Czech research in this area.

# Acknowledgement

The paper was developed with the support of the Czech Science Foundation, grant no.13-07036S "Modelling of Negotiations in Environmental Policy under Information Asymmetry".

# References

1. Directive 2000/60/EC of the European Parliament and of the Council of 23 October 2000 establishing a framework for Community action in the field of water policy (2000)
2. Fiala, P., Kalčevová, J., Vraný, J.: CRAB – Combinatorial Auction Body Software System. Journal of Software Engineering and Applications 3, 718-722 (2010)

3. Šauer P., Dvořák A., Fiala P., Prášek J.: Methodology for economic and environmental optimisation of reducing pollution in watercourses, University of Economics & Ministry of Agriculture, certificate no. 79469/2013-MZe, Prague (2013)

4. Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)

5. Leyton-Brown, K., Pearson, M., Shoham, Y.: Towards a Universal Test Suite for Combinatorial Auction Algorithms. In the Proceedings of ACM Conference on Electronic Commerce (EC-00) (2000)

6. Balas, E.: An Additive Algorithm for Solving Linear Programs with Zero-one Variables. Operations Research 13, 517–46 (1965)

7. XA: Linear Optimizer System (2003), available at http://www.sunsetsoft.com/, [approached December 28, 2009]

8. Government Order of 29 January 2003 No 61/2003 Coll., on the indicators and values of permissible pollution of surface water and wastewater, mandatory elements of the permits for discharge of wastewater into surface water and into sewerage systems, and on sensitive areas (Czech Technological Norm; in Czech), (2003)

9. ČSN 75 6401 Sewage treatment plants for more than 500 of population equivalents.

10. Fiala, P., Šauer, P.: Application of Combinatorial Auctions on Allocation of Public Financial Support in the Area of Environmental Protection: Economic Laboratory Experiment (in Czech), Politická ekonomie, 59/3, 379–392 (2011).

11. Šauer, P., Fiala, P., Dvořák, A.: Environmental negotiation under information asymmetry: a laboratory experiment for coalitions of four parties. Actual Problems of Economics, 4/154, 544–550 (2014)

12. Soukopova, J., Struk, M.: Methodology for the Efficiency Evaluation of the Municipal Environmental Protection Expenditure, in: Hrebicek, J; Schimak, G; Denzer, R. (eds.) Environmental Software Systems: Frameworks of Environment, Book Series: IFIP Advances in Information and Communication Technology, Vol.359, 327-340 (2011)

13. Soukopova, J., Bakos, E.: Assessing the efficiency of municipal expenditures regarding environmental protection, in: Aravossis, K; Brebbia, C.A. (eds.): Environmental Economics and Investment Assessment III Book Series: WIT Transactions on Ecology and the Environment Vol.131,107-119 (2010)

14. Koontz, T.M, Johnson, E.M.: One size does not fit all: Matching breadth of stakeholder participation to watershed group accomplishments, Policy Sciences, Vol. 37/2, 185-204 (2004)

15. Priscoli, J.D.: What is public participation in water resources management and why is it important? Water International, Vol. 29/2,221-227 (2004)

16. Slavikova, L., Jilkova, J: Implementing the Public Participation Principle into Water Management in the Czech Republic: A Critical Analysis, REGIONAL STUDIES, Volume: 45, Issue: 4, Pages: 545-557 (2011).