Multiobjective Optimization in Economy

One of the areas within the Economics field where optimization problems are more prevalent is finance. Among the applications we could mention risk management, option pricing, assetliability management or portfolio management, to name a few. If we focus our attention on multiobjective optimization, we will see that financial multicriteria optimization problems are often transformed into simplified monoobjective versions than can be tackled using traditional approaches like linear, quadratic or robust optimization methods. In addition to that, the performance of most optimization methods is severely affected by real-world issues such as high dimensionality, constraints, shape of the Pareto front or the need for a good solution in a limited time frame. It is here, in complex financial problems, where MOEAs can make an impact [SCH04] [CHE02] (see Figure).

 Despite the growing interest, this area of application for MOEAs is still in an early stage. Indeed, the number of strong research groups is very limited and we consider that this represents a huge opportunity to catch a wave that reputed experts in MOEAs such as Coello [COE06], expect to see turned into a major driver of real world applications for these algorithms.

 

Our interest here is related to Economics plus Information and Communication Technologies (ICT). Nowadays, there is a growing demand of radio spectrum in order to offer new wireless services such as: mobile communication services, Digital Terrestrial Television (DTTV or DTT) or wireless access systems to broadband services. Hence, the spectrum management becomes a key factor in this industry and in the global economy [GRE07]. In this context, the telecommunication operators are going to be very influenced by the policies that national and international regulators establish as it will affect their costs, incomes, and hence, profits. On the one hand, the acquisition of the spectrum licenses is a cost for the operators, so they will try to minimize it. Nevertheless, if they don’t acquire enough spectrum to offer their services, this will be a fundamental limitation for their production and their profit maximization. Hence, operators will have to achieve the complex decision of determining the optimum spectrum demand which maximizes their profits, which will depend of the spectrum cost. Specifically, the analysis of these complex decisions and the demands to be done by the operators would be the environment to work with in this project.

The optimization problem that we try to achieve here is highly complex and broad since it includes variables from the business model of each operator and from the allocation mechanism. The main goal of this research is to give operators several optimization techniques that allow them to determine the optimum spectrum demand according to: a) their business model (to maximize profits); and b) the prices and properties of the spectrum (to minimize costs). The outcome of this research has a great value from several points of view. First of all, for the operators which are actually willing to acquire new spectrum licences. Second, for the regulator, it will surely be an advantage to know the operators incentives helping to do an efficient division and allocation of the spectrum. Solving this complex problem is a difficult task, so Intelligent Systems (IS) are required. Finally, this project could also be a scientific advance in a multidisciplinary area: IS applied to Economics and ICT.

Traditionally, the spectrum allocation has been done with combinatorial auctions. A combinatorial auction is an auction in which bidders can place bids on combinations of items, or “packages,” rather than just individual items. Simple combinatorial auctions have been used for many years in estate auctions, where a common procedure is to auction the individual items and then at the end to accept bids for packages of items. They have been used recently for truckload transportation, bus routes, industrial procurement, and in the allocation of radio spectrum for wireless communications.

Combinatorial auctions present a host of new challenges as compared to traditional auctions. Some of these challenges are computational, some economic, and some hybrid. An example of a computational problem is how to efficiently determine the allocation once the bids have been submitted to the auctioneer. This is called the winner determination problem (WDP). It can be stated as follows: given a set of bids in a combinatorial auction, find an allocation of items to bidders—including the possibility that the auctioneer retains some items—that maximizes the auctioneer’s revenue. This problem is difficult for large instances. Specifically, it is NP-complete, meaning that a polynomial-time algorithm to find the optimal allocation is unlikely ever to be found (source Wikipedia, see HIS 08 presentation for more information).

Some developed software is provided:

This application simulates and solves a Combinatorial Seal Bid auction. The Winner Determination Problem is solved by brute force and by an A* (Branch on Items (BOI)  implementation, see HIS 08 presentation for more information).

The application is easy to use. A parameters.txt must be defined (one is included as example in the zip file). This text file (parameters.txt) specifies the following values:

BIDDERS:5   (number of bidders that takes place in the auction)
LOTS:5  (number of lots/goods/spectrums which are selled)
NUM_EXPERIMENTS:100 (number of executions that the user wants to run the simulation)
SIGMA:1 (sigma value divided by 10 used for the Gaussian distribution used for the bidders' valuations)
SIGMA_PUJAS:1 (sigma value divided by 10 used for the Gaussian distribution used for the bidders' strategies) This value is usually around 1 and it only can be lower than 1, otherwise the bidders would incur in loses bidding over their valuation, which is not rational.

Once the values of the parameters.txt are determined, then the user can run the application (double click on CombinatorialAuction.exe). 

The main window has this appearance:

 Main Screen

At this stage, two things can be done:

  1. To generate automatically a new template with all the possible lot combinations and the bidders valuation for each one of them. It is ramdomly generated following a template created with the parameters specified in the parameters.txt file.
  2. To load a previously generated (automatically or manually) template filled with the bidders valuation.

Our advice is to generate the template the first time with the desired parameters and then to manually change the xls file generated. For example, I can automatically generate a template for 5 bidders and 3 lots and afterwards (closing this application) to modify with Excel/OpenOffice the template with my expected valuations. I can also remove combinations of lots which perhaps are not going to be selled or to set valuations equal to 0 for those bidders that are not interested in some goods.

The format of the template must be keeped the same (otherwise the application will fail during the load). The format is the described in the following:

Template format

This example is automatically generated for three lots and three bidders. In the column A all the possible combinations of 3 lots appear. In the following columns the valuations of each bidders are specified with 3 estimated values: minimum, center and maximum. Those values are used when the simulator extracts the bidders valuation with a the gaussian distribution.

Once the template filled with the valuations is done, the user can press the "load template" button, select the appropiate file and then the first-time estimated valuations are loaded.

Screen with Valuations loaded

After this step, the user must press the tab called "Auction". In this tab the bids that are going to send the bidders are calculated (for the first experiment).  

Bids of the auction

At this stage the user has two choices:

  • Pressing the "Run" button: it runs the force brute procedure for the selected bidders. This process can be very long. It has been only developed till 7 lots and it is run only one time (it does not take into account the NUM_EXPERIMENTS parameter). This process was developed in order to compare the correctness of the results and to measure computing times solving the WDP.
  • Pressing the "Run A*" button: it launches the A* BOI algorithm to solve the WDP as many times as specified in the NUM_EXPERIMENTS parameter. Each experiment re-estimates the valuations and the strategies played by the bidders (exactly in the same way as if we open the application and load the same template again).

After waiting for a while (it depends on the number of lots/bidders and experiments), a screen like this will appear:

End of the process

The blue bar which is in the lower part of the screen indicates the numer of experiment that is been runned. However, in long executions, sometimes the application lost it focus and it does not update the image (but it does not mean that it is hunged).

Finally the results of the execution, which had been automatically generated and stored in a ".xls" file, can be found in a file called "Exp_SealedBid<DATE>_<INTERNAL_NUMBER>.xls". The format can be seen in the following image:

Results format

The first column indicates the experiment number. The column B is the Seller Income. The following columns (C-E)  are the Prices paid by the bidders. The next 3 (F-H) are the revenues of the bidders (compared to sincere bidding). The column J indicates the eficiency of the auction. The columns from K to M are the strategies played by the bidders, and finally, in columns P and Q are the awarded items (the WDP solution), i.e. 123 would means that LOT A is awarded to bidder 1, LOT B to bidder 2 and LOT C to bidder 3. Other example to clarify this point, 113 would mean that bidder A is awarded with LOT AB and bidder 3 with LOT C. The last column is only the timestamp of each experiment.

Observations:

  • In this case, as the value of the parametr SIGMA_PUJA is 1, all the stratgies played are around 1 (rounded to one decimal, from 0.8 to 1.0).
  • As the valuations used for this example are almost the same, the user can see that the auction makes a very good distribution of the LOTS awarded to the bidders (in all the experiments run). 
  • The sum of the prices paid by the bidders is the seller income (although it is calculated independently).
  • The auction efficiency in this example was always 1 compared to SB.

System requirements:

Any Microsoft Windows Operative System with .net framework. For Linux/Mac a virtual machine with a Microsoft Operative System image must be installed.

Any application compatible with "xls" format.

  • [CHE02] S.-H. Chen, (Ed.). Evolutionary Computation in Economics and Finance. Heidelberg, Germany: Physica- Verlag (2002)
  • [COE06] C.A. Coello Coello, Evolutionary Multi-Objective Optimization in Finance, in Jean-Philippe Rennard (editor), Handbook of Research on Nature Inspired Computing for Economy and Management, pp. 74--88, Vol. I, Idea Group Reference, Hershey, UK (2006)
  • [GRE07] GRETEL (Grupo de Regulación de las Telecomunicaciones), La evolución de la gestión del espectro radioeléctrico. Ed. Colegio oficial de ingenieros de telecomunicación, 2007.
  • [SCH04] F. Schlottmann and D. Seese, Financial Applications of Multi-Objective Evolutionary Algorithms: Recent Developments and Future Research Directions, in Carlos A. Coello Coello and Gary B. Lamont (editors), Applications of Multi-Objective Evolutionary Algorithms, pp. 627--652, World Scientific, Singapore, 2004.