# Environmental Modelling with Reverse Combinatorial Auctions: CRAB Software Modification for Sensitivity Analysis

Petr Fiala, Petr Šauer

► To cite this version:

Petr Fiala, Petr Šauer. Environmental Modelling with Reverse Combinatorial Auctions: CRAB Software Modification for Sensitivity Analysis. 12th International Symposium on Environmental Software Systems (ISESS), May 2017, Zadar, Croatia. pp.411-419, 10.1007/978-3-319-89935-0_34 hal-01852645

HAL Id: hal-01852645

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

Submitted on 2 Aug 2018

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
# Environmental modelling with reverse combinatorial auctions: CRAB software modification for sensitivity analysis

Petr Fiala, Petr Šauer

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

**Abstract.** This paper builds on reverse combinatorial auctions theory and its selected environmental applications, which were presented at ISESS 2013 and ISESS 2015. It provides an approach for calculating the sensitivity and proposals for necessary adjustments of Combinatorial Auction Body Software System (CRAB), which makes its use for the relevant decision-making tasks more user friendly. Two possibilities are suggested. The first approach is appropriate for cases with relatively small numbers of subjects, where it is possible to compute all feasible solutions ordered by total cost. In such cases it is possible to analyse changes of coalition structures with increasing the cost. The second one suggests modification of the CRAB software, which would make it possible to analyse cases with high numbers of feasible coalition structures located between the optimal coalition (i.e. the cost-effective one) and the structure consisting of individual projects. This approach is appropriate for complex real applications involving setting of cost levels.

**Keywords:** environmental management; decision-making; sensitivity analysis; reverse combinatorial auctions

## 1 Introduction

The paper builds on work published in ISESS 2013 [1] and in ISESS 2015 [2], where the general model of the theory of reverse combinatorial auctions and its selected environmental applications were presented. At the same time, we presented the results of laboratory experiments showing whether and to what extent the negotiating parties at auctions are able to approach the optimal result. The main practical goal of the paper was to contribute to increased cost-effectiveness of waste water cleaning projects [3], [4] in conditions where coalition solutions are possible.

The previous research results [1], [2], [5] have shown the need to deepen our research into sensitivity analysis of the resulting optimal solutions. Specifically, in terms of understanding how to study coalition structures in the space between the optimal solution and solutions in the form of individual projects, and how the change of feasible coalition structures changes achieved cost. This paper provides an approach for calculating the sensitivity and proposals for necessary adjustments of
CRAB software, which makes its use for the relevant decision-making tasks more user friendly.

## 2 Models of reverse combinatorial auctions in environmental applications

Before explaining the nature of the proposed approach of sensitivity analysis, we provide the basic model of reverse combinatorial auctions.

Supposed that m potential sellers $S_1, S_2, ..., S_m$ offer a set $R$ of r items, $j = 1, 2, ..., r$, to one buyer $B$; a bid made by the seller $S_h, h = 1, 2, ..., m$, would be defined as

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

where

$C \subseteq R$, is a combination of items,

$c_h(C)$ is the price offered by the seller $S_h$ for the combination of items $C$.

The constraints ensure that the procurement provides at least one set of all items. The objective is to minimise the buyer's cost, given the bids made by the sellers.

Binary variables are introduced for the model formulation:

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

The basic reverse combinatorial auctions model can be formulated as follows [6]:

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

subject to

$$\sum_{h=1}^{m} \sum_{C \subseteq R} y_h(C) \geq 1, \forall j \in R, \qquad (3)$$

$$y_h(C) \in \{0,1\}, \forall C \subseteq R, \forall h, h = 1, 2, ..., m. \qquad (4)$$

This basic model only considers the minimisation of costs, which is complemented by restrictions on environmental standards. In terms of mathematical formulations, inequalities are added that compare the pollution reduction achieved with the required limit values for five specific environmental parameters (5).

$$\sum_{h=1}^{m} \sum_{C \subseteq R} e_{hi}(C) y_h(C) \geq E_i. \qquad (5)$$

where $e_{hi}$ are pollution parameters of the projects and $E_i$ are the prescribed environmental standards for the parameters.
### 3 Sensitivity analysis

For further decision-making about the investment program that is realised in practice, it is important to learn how sensitive deviations from the optimised coalition structure would be to other feasible structures.

For small examples it is possible to compute and relatively easily analyse all solutions, with coalition structures from the first best (optimal) solution ranked by increasing cost. The optimal solution is computed by solving the problems (2) - (4). As a result, we get the so-called first-best solution. The optimal costs are denoted Z1. Generally, we get the i-th solution by solving the problems (2) - (4) with an added constraint

$$ \sum_{h=1}^{m} \sum_{C \subseteq R} c_h(C)y_h(C) \geq Z_{i-1} + \varepsilon, \quad (6) $$

Where $\varepsilon$ is a small positive number.

In typical practical cases, the number of feasible coalition structures is huge. For this reason, it is not possible to analyse all of them individually, i.e. to follow the order of the second-best, third-best, etc. solutions.

We propose that sensitivity analysis, based on analysing coalition structures for specific cost levels, can still provide support for decision-making about the projects in such cases. The difference between costs for individual project structures and costs for the first best solution could be divided to several levels corresponding to politically acceptable deviations of the practical program from the first best solution. It is possible to work with quartiles, quintiles etc. in the space of all feasible solutions.

The solutions for the cost levels could be computed from the basic model (see formulas (2), (3), and (4)) adding constraints:

$$ \sum_{h=1}^{m} \sum_{C \subseteq R} c_h(C)y_h(C) \geq L_i, \quad i = 1, 2, \dots, n, \quad (7) $$

where $n$ is number of levels and $L_i$ are cost levels.

### 4 Suggestions for CRAB software modification

We have developed our own software tool, CRAB (Combinatorial Auction Body Software System)[7]. CRAB is a non-commercial software system for generating, solving, and testing combinatorial auction problems. The system solves problems using Balas' method or the primal-dual algorithm [8]. CRAB has several advantages over CATS software [9], in particular, CRAB generates problems faster; combinations are generated in a more predictable way and only in given subset of all items; CSV is used as the primary data format; there is fine-grained control over the generated problem; a linear problem solver is a part of CRAB; and it provides multiple out-
put formats. CRAB is implemented in Ruby, which enables us to quickly experiment with different approaches.

In the first phase of analysis, all combinations of goods in each package are gener-
ated (except empty set). This step is done for every package. In the second phase, the
file is transformed into the binary programming problem. The bundles correspond to
variables and bids correspond to prices of the objective function that is maximised.
The problem consists of automatic constraints for each good (each good can be sold
only once) and each buyer (buyer cannot get over his budget). The user of CRAB
software can change automatically generated constraints and add or remove additional
ones. The problem can be passed to the built-in binary programming solver to find out
the optimal solution for a given combinatorial auction. Afterwards, the transformed
model is passed to the Balas algorithm [8].

The CRAB architecture provides the possibility of extending the system, especially with respect to the implemented models and algorithms. For the sensitivity analyses, we modified the CRAB software according to the approaches for sensitivity analysis, (6) and (7), above.

A problem occurs when entering data for complex applications in optimisation of coalition solutions, such as in the construction of a waste water treatment plant (WWTP). This is particularly the case when appropriate variable names for multiple coalitions derive from the encoding of individual municipalities entering into these multiple coalitions. Experts generating sets of "promising" coalitions progress by identifying coalition-names on maps and not by the order of the municipalities in their list. Clarity is lost by this encoding, but this sequence has its own logic, because two coalitions comprising the same set of municipalities, but in a different order, may provide different solutions, for example, with a different location of the common WWTP. The software compares the same combination and warns the user in the report.

Currently we are working on improving user comfort when loading large data de-
scribing the real situation in the river basins and reservoirs, where there is a large
number of "promising" coalitions entering the optimisation calculations. The new
version should communicate better with conventional spreadsheets than is currently
the case.

5 Sensitivity analysis by CRAB software

Imagine a situation where four municipalities discharge their wastewater into a small river that flows into the reservoir intended for bathing (e. g. may be ranked in so called Bathing Water by the Directive 2006/7/EC [10]). If we want to restore the quality of water for bathing, it is necessary that all four municipalities built waste water treatment plant (WWTP). This can be done by each building an individual WWTP or, alternatively, it is possible to try to merge the villages into so-called multiple coalitions to build a common WWTP either for all or some of them.

We let the experts estimate the necessary costs for the construction of the WWTP for the "promising projects". These data are contained in Table 1.
<table><caption>**Table 1.** Estimated costs for the "promising projects"</caption><thead><tr><th>Project</th><th>Participated municipalities</th><th>Project costs</th></tr></thead><tbody><tr><td>Individual projects</td><td></td><td></td></tr><tr><td>1.</td><td>A</td><td>7500</td></tr><tr><td>2.</td><td>B</td><td>18000</td></tr><tr><td>3.</td><td>C</td><td>31000</td></tr><tr><td>4.</td><td>D</td><td>28000</td></tr><tr><td>Coalition projects</td><td></td><td></td></tr><tr><td>1.</td><td>AB</td><td>27750</td></tr><tr><td>2.</td><td>BC</td><td>41750</td></tr><tr><td>3.</td><td>BD</td><td>59000</td></tr><tr><td>4.</td><td>CD</td><td>65000</td></tr><tr><td>5.</td><td>BD</td><td>59000</td></tr><tr><td>6.</td><td>BCD</td><td>69000</td></tr><tr><td>7.</td><td>ABCD</td><td>82750</td></tr></tbody></table>

The optimal solution for the numerical example given by the CRAB software:

<table><caption>**Table 2.** Optimal solution computed by CRAB software</caption><caption>OPTIMAL SOLUTION</caption><tbody><tr><td>Total cost:</td></tr><tr><td>73000.00</td></tr><tr><td>Coalition structure:</td></tr><tr><td>1-member coalition: D</td></tr><tr><td>3-member coalition: ABC</td></tr></tbody></table>

Sensitivity analysis can be performed for the above example. The analysis is described above by the model (6). The problem has 9 solutions in our case. For the results, see Table 3.
<table><caption>**Table 3.** Sensitivity analysis computed by CRAB software</caption><tr><td>1st Solution (=first best)<br/>Total cost: 73000.00<br/>Coalition structure:<br/>One 1-member coalitions: D<br/>One 3-members coalitions: ABC</td><td>6th Solution<br/>Total cost: 86750.00<br/>Coalition structure:<br/>1-member coalitions: C,D<br/>2-member coalitions: AB</td></tr><tr><td>2nd solution<br/>Total cost: 76500.00<br/>Coalition structure:<br/>1-member coalitions: A<br/>3-member coalitions: BCD</td><td>7th Solution<br/>Total cost: 90500.00<br/>Coalition structure:<br/>1-member coalitions: A,B<br/>2-member coalitions: CD</td></tr><tr><td>3rd Solution<br/>Total cost: 77250.00<br/>Coalition structure:<br/>1-member coalitions: A,D<br/>2-member coalitions: BC</td><td>8th Solution<br/>Total cost: 92750.00<br/>Coalition structure:<br/>2-member coalitions: AB, CD</td></tr><tr><td>4th Solution<br/>Total cost: 82750.00<br/>Coalition structure:<br/>4-member coalitions: ABCD</td><td>9th Solution (least efficient solution)<br/>Total cost: 97500.00<br/>Coalition structure:<br/>1-member coalitions: A,C<br/>2-member coalitions: BD</td></tr><tr><td>5th Solution<br/>Total cost: 84500.00<br/>Coalition structure:<br/>1-member coalitions: A,B,C,D</td><td></td></tr></table>

In practical cases, there are a large number of polluters, thus creating more complex models and calculations. In such cases, there are a large amount of feasible solutions. These situations can be solved in two ways:

1. In some cases, the solution of the entire case is divided into optimisation problems of sub-segments of river basin. A typical example is in a mountainous area, where it is possible to optimise the construction of wastewater treatment plants for each valley. For this situation, see the above numerical example.

2. If this is not possible, then one can work with "levels" between the cost of first best (optimal) solution and the cost of individual projects.

As a demonstration of the second case, we provide two practical applications from recreation lakes in the Czech Republic. Bathing water quality is an important issue in the EU (see Directive 2006/7/EC concerning the management of bathing water quality).
ty [10]). In both cases, multiple small municipalities should build their own WWTP or join one or more other municipalities and build a common WWTP. Solving these problems in small municipalities is quite costly in comparison to building and operating WWTPs in larger cities and requires support from public financial sources. Calculating the (theoretically) optimal solution could support political decision making about allocation of public funds in this area. In the case of cleaning phosphorus from water in a recreation lake, it is important that all polluters contribute to the project. In practice, they negotiate a common project proposal and apply for financial support. For assessing these proposals, it is useful to have the sensitivity analysis results available.

Lake Rozkoš is the first case. It is located in the Elbe River basin in Bohemia [11], [12], [13]. Two scenarios for achieving environmental targets (required status of the lake water) were formulated by specialists, together with an assessment of the investment and operating costs of the projects. The optimal solution (investment program) for 41 polluter-municipalities, where 166 coalitions were considered (41 individual WWTPs and 125 joint WWTPs), was computed. The results of the optimisation modelling presented in this paper have shown that over 20% of the costs could be saved where selected joint WWTPs are realised.

A sensitivity analysis was performed. Since the number of feasible coalition structures is huge (there are $2^{166}$ of them in the case of Rozkoš Lake), it would not be practical to analyse all of them (as it is done in our illustration presented above). For this reason, the difference (“space”) between costs for individual projects and costs for the first best (optimal) solution was initially divided into six levels corresponding to policy decisions about potential (politically acceptable) deviation of the practical program from the (theoretical) first best solution. The levels create borders of quintiles in the space of all potential (feasible) solutions. Level 1 was defined as the cost for the first best solution, level 6 as the cost for individual projects. Other levels are always about 20 percent higher than the previous level, where the second level was suggested as the politically acceptable one. These calculations provided a useful picture for better assessment of potential projects submitted in the region. For more details, see [5].

Lake Pastviny is the second case. This lake is located in east Bohemia, near the Polish border [14], [15]. The initial set of projects aimed at achieving the environmental standards required for bathing water in Lake Pastviny consists of 24 individual projects (WWTPs) and 131 multiple-coalition projects. These included 32 two-member coalitions, 38 three-member coalitions, 38 four-member coalitions, and 22 five-to-eight-member coalitions. The abatement costs, in the form of investment and operating costs, were assessed by the specialists for all of these projects. The analysis indicated a potential saving of annualised abatement costs of 6% in the case where half of the municipalities located in the lake watershed join specific coalitions and the rest build an individual WWTP.

In this case, the initial sensitivity analysis works with 4 costs levels. Level 1 was defined as the cost for the first best (optimal) solution, level 4 as the cost for individual projects. Other levels are always about 33 percent higher than the previous level. Moreover, here, the results provide a picture of how changing the coalition structure
by decreasing of the number of multiple-member coalitions leads to an increase of the
costs. For more details, see [16].

6 Conclusion

The paper is devoted to modification of the CRAB software for sensitivity analysis of solutions to combinatorial auction problems. The modification is used for analyses of coalition projects for the building of WWTPs.

We propose two possibilities. The first approach is appropriate for small examples,
where it is possible to compute all feasible solutions ordered by total cost. In such
cases, it is possible to analyse changes of coalition structures in terms of their increas-
ing cost.

The second suggested modification of the CRAB software makes it possible to analyse a high number of feasible coalition structures located between the optimal coalition (i.e. the cost-effective one) and the structure consisting of individual projects. This approach is appropriate for setting of cost levels in complex real applications, including multiple-round subsidy negotiations (see [17]). The proposed approach of sensitivity analysis can be used not only in the case of reverse combinatorial auctioning in cleaning waste waters; the waste water treatment issue was used as a typical practical application.

Two practical applications are presented in the paper, together with a discussion of their contribution to relevant decision-making processes. In both cases, it is possible to continue to more detailed sensitivity analysis, according to the concrete requirements of participants in the decision making process. This could be particularly useful when the projects are multiple-round negotiated with the authority and other stakeholders.

**Acknowledgement.** The paper was developed with the support of the Czech Science Foundation, GACR č. 16-01687S: "Novel approach to seeking cost/effective water pollution abatement: Developing reverse combinatorial auctions theory".

References

1. Šauer, P., Fiala, P., Dvořák, A.: Modelling of Environmental Risk Management under Information Asymmetry. In: Hřebíček, J., Schimak, G., Kubásek, M., Rizzoli, A.E. (eds.). Environmental Software Systems. Fostering Information Sharing [CD-ROM, online]. Neusiedl am See, 9.10.2013 – 11.10.2013. Vienna : Springer, 391–402, (2013).

2. Šauer, P., Fiala, P., Dvořák, A.: Water Pollution Reduction: Reverse Combinatorial Auc-
tions Modelling Supporting Decision-Making Processes. In: Denzer, R., Argent, R.M.,
Schimak, G., Hřebíček, J. (eds.). Environmental Software System. Infrastructures, Services
and Applications [online]. Melbourne, 25.03.2015 – 27.03.2015. London : Springer,
(2015).

3. Berbel, J., Martin-Ortega, J., Mesa, P.: A Cost-Effectiveness Analysis of Water-Saving Measures for the Water Framework Directive: the Case of the Guadalquivir River Basin in Southern Spain, Water Resou Manag 25 (2), 623–640, (2011).
4. CzGOV: Czech Government Regulation No. 401/2015 Coll., amending GR No. 61/2003 Coll., on Indicators and Values of Acceptable Pollution of Surface Water and Wastewater, Mandatory Elements of Permits for Discharging Wastewater into Surface Water and Sewerage Systems, and on Sensitive Areas (as amended by GR No. 229/2007 Coll.), (2011).

5. Šauer, P., Fiala, P., Dvořák, A., Kolínský, O.: Coalition Projects to Cut Back Costs of Cleaning Recreational Water Bodies: The Case of the Bohemian Lake Rozkoš, Polish Journal of Environmental Studies, forthcoming (2017).

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

7. Fiala, P., Kalčevová., J. Vraný J., CRAB—CombinatoRial Auction Body Software System, Journal of Software Engineering and Applications, 3/7, 718–722 (2010).

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

9. 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, Minneapolis, 448–457 (2000).

10. Directive 2006/7/EC of the European Parliament and of the Council of 15 February 2006 concerning the management of bathing water quality.

11. PL: Limnological findings and possibilities to improve current condition in the Lake Rozkoš (in Czech), Povodí Labe, s.p., Hradec Králové, (1999).

12. PL: Control order at the waterwork Rozkoš (in Czech), Povodí Labe, s.p., Hradec Králové, (2007).

13. VRV/PL: An Analysis of Importance of Impact of Eutrophication Pollution Sources at the River Basin of Water Lake Rozkoš (in Czech), Vodohospodářský rozvoj a výstavba a.s. nad Povodí Labe, s.p., Praha, (2013).

14. PL: Process Rules for Hydraulic Structure on the Divoká Orlice - Pastviny I. (in Czech), Povodí Labe s.p., Hradec Králové, (2009).

15. VIS: Basic strategy for attaining water quality for recreational purposes at Pastviny water reservoir (in Czech), Vodohospodářsko-inženýrské služby spol. s r.o. study for Povodí Labe, s.p., Hradec Králové, (2014).

16. Šauer, P., Dvořák, A., Fiala, P.: Improvement to green in-country tourism conditions: A case of the Czech recreation lake Pastviny. Journal of Environmental Protection and Ecology, 17/4, 1434–1442 (2016).

17. Šauer, P., Dvořák, A., Fiala, P. Negotiation between Authority and Polluters - Model for Support of Decision Making in Environmental Policy. Politická ekonomie, 46/6, 772-787 (1998).