Aggregating multiple markets in microeconomics

The following technical note addresses the algorithm proposed in Chapter 3.2 of the
Oz Shy book “How to Price”. A common thread throughout the book is the
suggestion of pseudo-code algorithms designed to help the reader implement the
theory into working code. Unfortunately, this worthy idea is frequently less valuable
than it could be as no or little effort has been invested into pursuing a minimal
standard of algorithmic efficiency. We now point out the shortcomings of Algorithm
3.3 -in particular its exponential complexity- and suggest an alternative that
scales polynomially in the number of markets. Let us summarize the section
first:

A computer algorithm for M markets

We now proceed to describe a computer algorithm for selecting
the most profitable price when there are M markets, and where
each market is composed of homogeneous consumers with identical
maximum willingness to pay, as was already illustrated in Figure 3.3
for the example of M = 3 markets. The user must run Algorithm
3.2 before running Algorithm 3.3 for the purpose of generating and
storing the 2^M possible selections of markets that can be served.
Recalling Algorithm 3.2, the results are stored by the array of arrays
of binary variables Sel[i,l] of dimension 2 M ŒM, where i is the index
of a specific selection of markets, i = 0,1,…,2 M – 1, and l is a
specific market. Market l is served under selection i if Sel[i, l] = 1
and is not served if Sel[i, l] = 0.

In the following the basic formula for the profit is being illustrated in one
market.

• Y –> final profit in this market
• p –> price per product
• μ –> marginal cost
• q –> quantity of customers in this market
• ϕ_i –> fixed costs in this specific market
• ϕ –> production fixed cost (2000$)

We use the following sum formula.

(1)

So in order to calculate all possible market constellations [MC] 2^M possible  markets arise, as each market is being calculated and is added up with every potential market constellation. In the above-mentioned formula for the total income the price p corresponds to the lowest price of all included markets, therefore all customers of the included markets also want to buy the product. This process can be made more efficient by utilizing the following three observations.

1. Only markets corresponding to positive terms of the total sum Eq. (1) will
   be included
2. In every market the profit decreases monotonically with decreasing price
3. Therefore, once an individual market profit becomes non-positive, Y _i ≤ 0,
   it will remain so and its computation can be omitted.

So it is only the lower triangular matrix that is being computed as the markets have
been ordered decreasingly by the price level. Hence, only those markets need to be
calculated, which would also be willing to pay the particular price. This creates
possible markets as the worst-case scenario.. Within a market, the profit is now
calculated with price as the only variable. The values in the columns of the matrix
are therefore monotonically decreasing. The algorithm terminates the calculation for
a certain market as soon as the market internal profit is less than or equal to zero.
This creates a nearly banded matrix, as there is no need to calculate every
single market constellation anymore. Finally, the rows are added and the
maximum profit in that new column is selected. This creates a much more
efficient computing scheme which scales polynomially instead of exponenially:
O(M²) << O(2^M) where the multiplying constant of the M² term can be much less
than .

Small example proposed by Shy

As an introductory example, the calculation is to Oz Shy in Chapter 3.2 page 72 is
being displayed.

• Markets: M1 M2 M3
• Prices: 30$ 20$ 10$
• quantities: 200 600 200
• fixed costs: 1000$ 5000$ 0$
• production fixed costs: 2000$

This is an example with numbers for one calculation for one market with one price.
This calculation for each market and for each
price is shown in the table below. In the resulting profit column the fixed
costs of production with 2000$ were already subtracted. They don’t need
to be removed individually from each market anymore. (Prices are in $.)

---

Price	M1	M2	M3	profit	resulting profit
30	4000	0	0	4000	2000
20	2000	4000	0	6000	4000
10	0	-2000	1000	-1000	1000

---

Example with 15 markets

• Prices: 150 140 130 120 110 100 90 80 70 60 50 40 30 20 10
• quantities: 60 10 10 60 10 60 60 10 60 60 10 10 60 60 60
• fixed costs: 0 800 500 600 800 200 100 200 500 800 400 600 800 300 100

Exhaustive search proposed by Shy

After searching through all 2¹⁵ – 1 = 32767 possible market combinations, the
maximum profit was found to be 17950 by including markets 1,2,3,4,5,6,7 . This
took 16.25 secs.

Structured search proposed in this note

After searching through 116 possible market combinations, the maximum profit was
found to be 17950 by including markets 1,2,3,4,5,6,7 . This took 0 secs.

The search matrix is displayed here:

---

Price	M1	M2	M3	M4	M5	M6	M7	M8	M9	M10	M11	M12	M13	M14	M15	Profit
150	8700															6700
140	8100	550														6650
130	7500	450	750													6700
120	6900	350	650	6300												12200
110	6300	250	550	5700	250											11050
100	5700	150	450	5100	150	5500										15050
90	5100	50	350	4500	50	4900	5000									17950
80	4500	-50	250	3900	-50	4300	4400	550								15800
70	3900		150	3300		3700	3800	450	3400							16700
60	3300		50	2700		3100	3200	350	2800	2500						16000
50	2700		-50	2100		2500	2600	250	2200	1900	50					12250
40	2100			1500		1900	2000	150	1600	1300	-50	-250				8250
30	1500			900		1300	1400	50	1000	700			700			5550
20	900			300		700	800	-50	400	100			100	600		1850
10	300			-300		100	200		-200	-500			-500	0	200	-2700

---