This is not the document you are looking for? Use the search form below to find more!

0.00 (0 votes)

Algorithms for determining quality/cost/price tradeoffs in saturated markets are consid- 3 ered. A product is modeled by d real-valued qualities whose sum determines the unit cost of producing 4 the product. This leads to the following optimization problem: given a set of n customers, each of 5 whom has certain minimum quality requirements and a maximum price they are willing to pay, design 6 a new product and select a price for that product in order to maximize the resulting profit

- Added:
**August, 08th 2010** - Reads:
**200** - Downloads:
**5** - File size:
**196.47kb** - Pages:
**12** - content preview

- Username: monkey
- Name:
**monkey** - Documents:
**474**

Related Documents

Motorola is a company known around the world for mobile, wireless and broadband communications. Its vision is of 'seamless mobility', helping users to get and stay connected to the people, ...

Sales response models are widely used as the basis for optimizing the marketing mix or for allocation of the sales force. Response models condition on the observed marketing mix variables and focus ...

This paper investigates the relationship between Marketing Mix Strategy and Consumer Motives at major TESCO stores in Malaysia. A quantitative approach was used and the survey was conducted at TESCO ...

Marketing is the most significant function of enterprises in which unethical practices are experienced. Marketing executives’ decisions relating to product, price, place and promotion items ...

• Objectives: At the completion of this unit, students will be able to: 1. Define the concept of "position." 2. Define the elements of the marketing mix a. Product b. Price c. Place d. ...

The Marketing Mix« is a term used to describe the combination of tactics used by a business to achieve its objectives by marketing its products or services effectively to a particular target ...

Marketing Mix (4P); composed of Product, Price, Promotion and Place; is a set of tools that should be coherently designated to achieve a company's goals. In order to create brand equity and customer ...

The history of the marketing mix construct is largely unknown to many people in marketing. This paper traces the history of the emergence of the marketing mix construct, known today as the 4Ps. ...

Content Preview

1

ALGORITHMS FOR MARKETING-MIX OPTIMIZATION

2

Joachim Gudmundsson Pat Morin Michiel Smid

3

Abstract. Algorithms for determining quality/cost/price tradeoﬀs in saturated markets are consid-

4

ered. A product is modeled by d real-valued qualities whose sum determines the unit cost of producing

5

the product. This leads to the following optimization problem: given a set of n customers, each of

6

whom has certain minimum quality requirements and a maximum price they are willing to pay, design

7

a new product and select a price for that product in order to maximize the resulting proﬁt.

8

An O(n log n) time algorithm is given for the case, d = 1, of products having a single quality,

9

and O(n(log n)d+1) time approximation algorithms are given for products with any constant number,

10

d, of qualities. To achieve the latter result, an O(nkd−1) bound on the complexity of an arrangement

11

of homothetic simplices in Rd is given, where k is the maximum number of simplices that all contain

12

a single points.

13

½

ÁÒØÖÓ

ÙØ

ÓÒ

14

Revealed preference theory [13] is a method of determining a course of business action through the

15

review of historical consumer behaviour. In particular, it is a method of inferring an individual’s or a

16

group’s preferences based on their past choices. The marketing mix [10] of a product consists of the 4

17

Ps: Product, price, place, and promotion. In the current paper, we present algorithms for optimizing

18

the ﬁrst two of these by using data about consumers’ preferences. That is, we show how, given data on

19

consumer preferences, to eﬃciently choose a product and a price for that product in order to maximize

20

proﬁt.

21

Refer to Figure 1. A product P = (p, q1, . . . , qd) is deﬁned by a real-valued price, p, and

22

a number of real-valued orthogonal qualities, q1, . . . , qd. The market for a product is a collection

23

of customers C = {C1, . . . , Cn}, where Ci = (pi, qi,1, . . . , qi,d). A customer will purchase the least

24

expensive product that meets all her minimum quality requirements and whose price is below her

25

maximum price. That is, the customer Ci will consider the product P = (p, q1, . . . , qd) if p ≤ pi and

26

qj ≥ qi,j for all j ∈ {1, . . . , d}. The customer Ci will purchase the product if it has the minimum price

27

among all available products that Ci considers.

28

We consider markets that are saturated. That is, for every customer Ci there is an existing

29

product that satisﬁes Ci’s requirements and among all products that satisfy Ci’s requirements, Ci will

30

choose the least expensive product. From the point of view of a manufacturer introducing one or more

31

new products, this means that all customers are Pareto optimal, i.e., there are no two customers Ci

32

and Cj such that qi,k > qj,k for all k ∈ {1, . . . , d} and pi < pj. This is because no customer will

33

every purchase a product that is not Pareto optimal, since there is a lower-priced alternative that also

1

quality

q3 1

,

C3

q2 1

,

C2

q1 1

C

,

1

p1

p2

p3 price

Figure 1: A sample market with d = 1 and n = 3. A customer will consider any product that is in

their upper left quadrant.

34

satisﬁes all their minimum quality requirements. Therefore, every customer Ci can be replaced with

35

the (Pareto optimal) product that they purchase.

36

As an example, consider a market for computers in which an example customer Ci may be

37

looking for a computer with a minimum of 8 GB of RAM, a CPU benchmark score of at least 3000,

38

a GPU benchmark score of at least 2000, and be willing to pay at most $1500. In addition, there is

39

already a computer on the market which meets these requirements and retails for $1200. Thus, this

40

customer would be described by the vector (1200, 8, 3000, 2000). If a manufacturer introduces a new

41

product (1199, 8, 3500, 2000) (a computer with 8 GB of RAM, a CPU benchmark score of 3500 and a

42

GPU benchmark score of 2000 retailing for $1199) then this customer would select this new product

43

over their current choice.

44

By appropriately reparameterizing the axes, we can assume that the cost, cost(P ), of manufac-

45

turing a product P = (p, q1, . . . , qd) is equal to the sum of its qualities

d

46

cost(P ) =

qi .

i=1

47

The proﬁt per unit sold of P is therefore

48

ppu(P ) = p − cost(P ) .

49

In this paper we consider algorithms that a manufacturer can use when planning a new product to

50

introduce into an existing saturated market with the goal being to maximize the proﬁt obtained. More

51

precisely, given a Pareto-optimal market of customers M = {C1, . . . , Cn}, each having d qualities, the

52

ProductDesign(d) problem is to ﬁnd a product P ∗ ∈ Rd+1 such that

53

proﬁt(P ∗) = ppu(P ∗) × |{i : Ci purchases P ∗}|

54

is maximized.

55

The term marketing mix is probably the most famous phrase in marketing. Not surprisingly,

56

economists and market researchers have considered methods of optimizing the marketing mix in various

57

scenarios. As there are many diﬀerent models of the problem, it is diﬃcult to compare algorithms.

2

58

Most models of marketing-mix problems involve a constant number of real-valued input pa-

59

rameters. This sometimes leads to problems where the optimal solution is one of a constant number

60

of possible closed forms (see, e.g., Thomson and Teng’s optimal constant price model [12]). In other

61

cases, a closed form is not achievable, but a (sometimes approximate) solution can be obtained using

62

numerical optimization techniques (see, e.g., Balanchandran and Gensch [2], Thomson and Teng [12],

63

Naik et al. [11], Deal [6], Erickson [9]). In all cases, it is expected that the model parameters are derived

64

from real-world data, such as surveys or sales ﬁgures, and involves ﬁtting of the model parameters to

65

the available data.

66

The work in the current paper is diﬀerent from this previous work in several ways. For one, it

67

is one of the few works that deals primarily with the ﬁrst two P’s, product and pricing. Most existing

68

literature focuses on the marketing P’s, namely place and promotion, and to a lesser extent, pricing

69

of an existing product. Secondly, it deals directly with data about individual consumers rather than

70

aggregating this data so that it ﬁts a particular model of consumer behaviour.

71

We believe that this models very well what happens in online shopping for high cost products

72

such as computers, cameras, and televisions. In such markets, savvy consumers have good data available

73

about both the speciﬁcations and the cost of all available products so that marketing eﬀorts are

74

(arguably) less important than the quality and prices of the products. On the other hand, online

75

sellers such as Amazon have large amounts of data about users’ past purchases and can use this data

76

as input to the problem. In particular, these sellers know the speciﬁcations qi,1, . . . , qi,d and prices pi

77

of huge quantities of items sold and can use this data to advise a manufacturer that is designing a new

78

product.

79

In the remainder of the paper we give an O(n log n) time algorithm for ProductDesign(1)

80

(Section 2), and O(n(log n)d+1) time approximation schemes for ProductDesign(d) (Section 3 and

81

Section 4). Section 5 summarizes our results and concludes with directions for future research.

82

¾

ÇÒ

¹

Ñ

Ò×

ÓÒ

Ð

Ô

ÖÓ

ÙØ×

83

In this section, we consider the simplest case, when a manufacturer wishes to introduce a new product

84

in which the quality of a product has only one dimension. Examples of such markets include, for

85

example, suppliers to the construction industry in which items (steel I-beams, ﬁnished lumber, logs)

86

must have a certain minimum length to be used for a particular application. An overly long piece can

87

be cut down to size, but using two short pieces instead of one long piece is not an option.

88

Throughout this section, since d = 1, we will use the shorthand P = (p, q) for the product

89

being designed and qi for qi,1. Thus, we have a set of customers M = {(p1, q1), . . . , (pn, qn)} and we

90

are searching for a point P ∗ = (p∗, q∗) that maximizes

91

proﬁt(p∗, q∗) = (p∗ − q∗)|{i : p∗ ≤ pi and q∗ ≥ qi}| .

92

Our algorithm is an implementation of the plane-sweep paradigm [4]. The correctness of the

93

algorithm relies on two lemmas about the structure of the solution space. The ﬁrst lemma is quite

94

easy:

95

Lemma 1. The value (p∗, q∗) that maximizes proﬁt(p∗, q∗) is obtained when p∗ = pi and q∗ = qj for

96

some i, j ∈ {1, . . . , n}.

3

ppu = 0

quality (q)

(p′, q)

(p, q)

(p′, q′)

(p, q′)

price (p)

Figure 2: proﬁt(p, q) ≤ proﬁt(p, q′) implies that proﬁt(p′, q) ≤ proﬁt(p′, q′) for all p′ ≤ p.

97

Proof. First, observe the obvious bounds on p∗ and q∗:

98

min{pi : i ∈ {1, . . . , n}} ≤ p∗ ≤ max{pi : i ∈ {1, . . . , n}}

99

and

100

min{qi : i ∈ {1, . . . , n}} ≤ q∗ ≤ max{qi : i ∈ {1, . . . , n}} .

101

Consider the arrangement of lines obtained by drawing a horizontal and vertical line through each

102

customer (pi, qi) for i ∈ {1, . . . , n}. Within each cell of this arrangement, the function proﬁt(p, q) is

103

a linear function of p and q and it is bounded. Therefore, within a particular cell, the function is

104

maximized at a vertex. Since each vertex is the intersection of a horizontal and vertical line through a

105

pair of customers, the lemma follows.

106

The following lemma, illustrated in Figure 2, is a little more subtle and illustrates a manufac-

107

turer’s preference for lower-quality products:

108

Lemma 2. Let q′ ≤ q and let p be such that 0 < proﬁt(p, q) ≤ proﬁt(p, q′). Then, for any p′ ≤ p,

109

proﬁt(p′, q) ≤ proﬁt(p′, q′).

110

Proof. By deﬁnition, proﬁt(p, q) = a(p − q) and proﬁt(p, q′) = a′(p − q′), where a and a′ are the number

111

of customers who would consider (p, q) and (p, q′), respectively. These customers are all taken from the

112

set M≥ = {(pi, qi) ∈ M : pi ≥ p}.

113

Now, consider the customers in the set M ′ = {(pi, qi) ∈ M : p′ ≤ pi < p}. By the assumption

114

that customers are Pareto optimal, any customer (pi, qi) in M′ has qi ≤ q′, so all of these customers

115

will consider either (p′, q′) or (p′, q) if either one is oﬀered. Therefore,

proﬁt(p′, q′) = (a′ + |M ′|)(p′ − q′)

= a′(p′ − q′) + |M ′|(p′ − q′)

≥ a′(p′ − q′) + |M ′|(p′ − q)

since q > q′

= a′(p − q′) + a′(p′ − p) + |M ′|(p′ − q)

116

≥ a′(p − q′) + a(p′ − p) + |M ′|(p′ − q)

since a ≥ a′ and (p′ − p) < 0

≥ a(p − q) + a(p′ − p) + |M ′|(p′ − q)

by assumption

= a(p′ − q) + |M ′|(p′ − q)

= proﬁt(p′, q) ,

4

117

as required.

118

Lemma 2 allows us to apply the plane sweep paradigm with a sweep by decreasing price. It

119

tells us that, if a product (p, q′) gives better proﬁt than the higher-quality product (p, q) at the current

120

price p, then it will always give a better proﬁt for the remainder of the sweep. In particular, there will

121

never be a reason to consider a product with quality q for the remainder of the algorithm’s execution.

122

Let the customers be labelled (p1, q1), . . . , (pn, qn) in decreasing order of pi, so that pi+1 ≤ pi

123

for all i ∈ {1, . . . , n − 1}. At any point in the sweep algorithm, there is a current price p, which

124

starts at p = ∞ and decreases during the execution of the algorithm. At the start of the algorithm the

125

algorithm’s event queue Q, which is represented as a balanced binary search tree, is initialized to contain

126

the values pn, . . . , p1. At all times, the algorithm maintains a list L of qualities q∗1 > q∗2 > · · · > q∗m

127

such that proﬁt(p, q∗1) > proﬁt(p, q∗2) > · · · > proﬁt(p, q∗m). The quality q∗1 is the optimal quality for

128

the current price, p. By the time the algorithm terminates, the quality of the globally-optimal solution

129

will have appeared as the ﬁrst element in L. To complete the description of the algorithm, all that

130

remains is to show how L and Q are updated during the processing of events in the event queue.

131

There are two kinds of events in the event queue. Insertions occur at the values p1, . . . , pn.

132

Deletions, which we describe next, occur when the relative order of two adjacent items in L changes.

133

Consider a consecutive pair of the elements q∗i and q∗i+1 in L. When q∗i and q∗i+1 became adjacent in L,

134

it was at some price p = pt such that proﬁt(pt, q∗i) > proﬁt(pt, q∗i+1). Let ai and ai+1 be the number of

135

customers who would consider (pt, q∗i) and (pt, q∗i+1), respectively. Then,

136

proﬁt(pt, q∗i) = (pt − q∗i)ai

137

and

138

proﬁt(pt, q∗i+1) = (pt − q∗i+1)ai+1

139

Now, looking forward in time to a later step in the execution of the algorithm, when p = pt′, with

140

t′ > t, we ﬁnd that

141

proﬁt(pt′, q∗i) = (pt′ − q∗i)(ai + t′ − t)

142

and

143

proﬁt(pt′, q∗i+1) = (pt′ − q∗i+1)(ai+1 + t′ − t) .

144

We are interested in identifying the price pt′ where the inequality proﬁt(pt′, q∗i) > proﬁt(pt′, q∗i+1)

145

changes to proﬁt(pt′, q∗i) ≤ proﬁt(pt′, q∗i+1). When this happens, q∗i can be safely discarded from L

146

since, by Lemma 2, proﬁt(p, q∗i) will never again exceed proﬁt(p, q∗i+1) for the remainder of the sweep.

147

The value pt′ is a deletion event.

148

Note that Lemma 2 also allows for binary search on the value pt′. In particular, the interval

149

[pj, pj+1] containing pt′ can be found in O(log n) time, after which the value of pt′ can be obtained by

150

solving the linear equation

151

(pt′ − q∗i)(ai + t′ − t) ≤ (pt′ − q∗i+1)(ai+1 + t′ − t) ,

152

for t′. (The equation is linear because the values ai and ai+1 are constant in the interval (pj, pj+1).)

153

Thus, whenever two new elements become adjacent in L, we can add the appropriate deletion event to

154

Q in O(log n) time.

155

When processing an insertion event pi, we remove from the tail of L all values q∗j such that

156

proﬁt(pi, q∗j) ≤ proﬁt(pi, qi) and then append qi onto L. While deleting the elements of L, we also

5

157

remove all the associated deletion events from Q. Appending qi to L causes at most one new pair of

158

elements in L to become adjacent, so we add the appropriate deletion event to Q as described above.

159

The time to process the event pi is there O((ki + 1) log n), where ki is the number of elements that are

160

deleted from L.

161

When processing a deletion event that deletes q∗i from L, we simply delete q∗i from L and its (at

162

most two) associated deletion events from Q. This may cause a new pair of elements, q∗i−1 and q∗i+1,

163

in L to become adjacent, so we add the appropriate deletion event to Q. In this way, a deletion event

164

can be processed in O(log n) time.

165

Note that, after all the processing associated with an event pt is complete, the ﬁrst element, q∗1,

166

in L is the value that maximizes proﬁt(pt, q∗1). Thus, the algorithm need only keep track, throughout

167

its execution, of the highest proﬁt obtained from the ﬁrst element of L, and output this value at the

168

end of its execution. This completes the description of the algorithm.

169

Theorem 1. There exists an O(n log n) time algorithm for ProductDesign(1).

170

Proof. The correctness of the algorithm described above follows from 2 facts: Lemma 1 ensures that

171

the optimal solution is of the form (pi, q∗) for some i ∈ {1, . . . , n}, and Lemma 2 ensures that the

172

optimal solution appears at some point as the ﬁrst element of the list L.

173

The running time of the algorithm can be bounded as follows: The total number of deletion

174

events processed is at most n, since each such event removes some value qi from L for some i ∈

175

{1, . . . , n}. Thus, the cost of processing all deletion events is O(n log n). Similarly,

n

i=1 ki ≤ n since

176

ki is the number of elements deleted from L during the processing of pi. Thus, the time required to

177

handle all insertion events, and therefore the running time of the entire algorithm, is O(n log n)

178

The following theorem shows that a running time of Ω(n log n) is inherent in this problem, even

179

when considering approximation algorithms.

180

Theorem 2. Let M be an instance of ProductDesign(1) and (p∗, q∗) be a solution that maximizes

181

proﬁt(p∗, q∗). In the algebraic decision tree model of computation, any algorithm that can ﬁnd a solution

182

(p, q) such that 2 · proﬁt(p, q) > proﬁt(p∗, q∗) has Ω(n log n) running time in the worst-case.

183

Proof. We reduce from the integer Element-Uniqueness problem, which has an Ω(n log n) lower

184

bound in the algebraic decision tree model [14]: Given an array A = [x1, . . . , xn] containing n integers,

185

are all the elements of A unique?

186

We convert A into an instance of ProductDesign(1) in O(n) time as follows (refer to Figure 3).

187

For each xi, i ∈ {1, . . . , n} we introduce a customer (pi, qi) with pi = qi + 1/2 and qi = xi. If

188

there exists a value x in A that occurs 2 or more times, then the product (x + 1/2, x) gives a value

189

proﬁt(x + 1/2, x) ≥ 1. On the other hand, if there is no such x, then

190

1. any product (p, q) with p − q > 1/2 can not be sold to any customers and

191

2. any product (p, q) with p − q > 0 can be sold to at most 1 customer.

6

ppu = 0

ppu = 1/2

x2

x1

q

x3

x5

x4

p

Figure 3: Reducing Element-Uniqueness to ProductDesign(1,1).

192

Therefore, if all the elements of A are unique, then proﬁt(p∗, q∗) = 1/2, otherwise proﬁt(p∗, q∗) ≥ 1.

193

The result follows.

194

¿

Ò

Ö¹Ð

Ò

Ö

ÔÔ

ÖÓ

Ü

Ñ

Ø

ÓÒ

Ð

Ó

Ö

Ø

Ñ

Ó

Ö

Ñ

Ò×

ÓÒ

Ð

Ô

ÖÓ

ÙØ×

195

In this section, we consider algorithms for ProductDesign(2), in which products have 2 qualities. As

196

a baseline, we ﬁrst observe that, if we ﬁx the value of q2, then the optimal solution of the form (p, q1, q2)

197

can be found using a single application of the algorithm in Theorem 1. Therefore, by successively solving

198

the problem for each q2 ∈ {q2,1, . . . , q2,n} and taking the best overall solution we obtain an O(n2 log n)

199

time algorithm for ProductDesign(2).

200

More generally, ProductDesign(d) can be solved using O(nd−1) applications of Theorem 1

201

resulting in an O(nd log n) time algorithm. Unfortunately, these are the best results known for d ≥ 2,

202

and, as discussed in Section 5, we suspect that an algorithm with running time o(nd) will be diﬃcult

203

to achieve using existing techniques. Therefore, in this section we focus our eﬀorts on obtaining a

204

near-linear approximation algorithm.

205

Fix some constant ǫ > 0. Given an instance M of ProductDesign(d), a point P ∈ Rd+1 is a

206

(1 − ǫ)-approximate solution for M if proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗) for all P ∗ ∈ Rd+1. An algorithm

207

is a (high probability) Monte-Carlo (1 − ǫ)-approximation algorithm for ProductDesign(d) if, given

208

an instance M of size n, the algorithm outputs a (1 − ǫ)-approximate solution for M with probability

209

at least 1 − n−c for some constant c > 0.

210

Let r = max{ppu(Ci) : i ∈ {1, . . . , n}} and observe that r is the maximum proﬁt per unit

211

that can be achieved in this market. Let E = 1/(1 − ǫ) and let ℓ = ⌈logE n⌉ and observe that

212

ℓ = O(ǫ−1 log n).1 For each i ∈ {0, 1, 2, . . . , ℓ}, deﬁne the plane Hi = {(p, q1, q2) : p−q1 −q2 = r(1−ǫ)i}.

213

The following lemma says that a search for an approximate solution can be restricted to be contained

214

in one of the planes Hi.

215

Lemma 3. For any product P ∗ = (p∗, q∗1, q∗2), there exists a product P = (p, q1, q2) such that P ∈ Hi

216

for some i ∈ {0, . . . , ℓ} and proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗).

1 This can be seen by taking the limit limǫ→0+(ǫ/ log(E)) using one application of L’Hˆopital’s Rule.

7

q1

q1

q2

Hi

q2

∆i,2

C2

∆i,1

∆i,3

C1

C3

price

price

(a)

(b)

Figure 4: The intersection of Hi with customers’ quadrants is a set of homothetic equilateral triangles.

217

Proof. There are two cases to consider. If ppu(P ∗) ≤ r/n then proﬁt(P ∗) ≤ r, in which case we set

218

P = Ci where ppu(Ci) = r, so that P ∈ H0 and proﬁt(P ) = r ≥ proﬁt(P ∗) ≥ (1 − ǫ) proﬁt(P ∗), as

219

required.

220

Otherwise, r/n < ppu(P ∗) ≤ r. In this case, consider the plane Hi where i = ⌈logE(r/ ppu(P ∗))⌉.

221

Notice, that for any point P ∈ Hi, ppu(P ) ≥ (1 − ǫ) ppu(P ∗). More speciﬁcally, the orthogonal pro-

222

jection P = (p, q1, q2) of P ∗ onto Hi is a product with p ≤ p∗, q1 ≥ q∗1, and q2 ≥ q∗2. Therefore,

223

any customer who would consider P ∗ would also consider P , so proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗), as

224

required.

225

Lemma 3 implies that the problem of ﬁnding an approximate solution to ProductDesign(2)

226

can be reduced to a sequence of problems on the planes H0, . . . , Hℓ. Refer to Figure 4. Each customer

227

Cj considers all products in a quadrant whose corner is Cj. The intersection of this quadrant with

228

Hi is a (possibly empty) equilateral triangle ∆i,j. The customer Cj will consider a product P in Hi

229

if and only P is in ∆i,j. Thus, the problem of solving ProductDesign(2) restricted to the plane Hi

230

is the problem of ﬁnding a point contained in the largest number of equilateral triangles from the set

231

∆i = {∆i,j : j ∈ {1, . . . , n}}.

232

Note that the elements in ∆i are homothets (translations and scalings) of an equilateral triangle,

233

so they form a collection of pseudodisks and we wish to ﬁnd the deepest point in this collection of

234

pseudodisks. No algorithm with running time o(n2) is known for solving this problem exactly, but

235

Aronov and Har-Peled [1] have recently given a Monte-Carlo (1 − ǫ)-approximation algorithm for this

236

problem that runs in time O(ǫ−2n log n). By applying this algorithm to each of ∆i for i ∈ {1, . . . , ℓ},

237

we obtain the following result:

238

Theorem 3. For any ǫ > 0, there exists an O(ǫ−3n(log n)2) time high-probability Monte-Carlo (1 − ǫ)-

239

approximation algorithm for ProductDesign(2).

8

240

d

Ò

Ö¹Ð

Ò

Ö

ÔÔ

ÖÓ

Ü

Ñ

Ø

ÓÒ

Ð

Ó

Ö

Ø

Ñ

Ó

Ö

ÓÒ×Ø

ÒØ

241

In this section we extend the algorithm from the previous section to (approximately) solve ProductDesign(d)

242

for any constant value of d. The algorithm is more or less unchanged, except that the proof requires

243

some new results on the combinatorics of arrangements of homothets.

244

As before, let r = max{ppu(Ci) : i ∈ {1, . . . , n}} and let ℓ = ⌈logE n⌉. For each i ∈

245

{0, 1, 2, . . . , ℓ}, deﬁne the hyperplane Hi = {(p, q1, . . . , qd) : p −

d

i=1 qi = r(1 − ǫ)i}.

The follow-

246

ing lemma has exactly the same proof as Lemma 3.

247

Lemma 4. For any product P ∗ = (p∗, q∗1, . . . , q∗d), there exists a product P = (p, q1, . . . , qd) such that

248

P ∈ Hi for some i ∈ {0, . . . , ℓ} and proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗).

249

Again, each customer Cj deﬁnes a regular simplex ∆i,j in Hi such that Cj will consider P ∈ Hi

250

if and only if P ∈ ∆i,j. In this way, we obtain a set ∆i = {∆i,1, . . . , ∆i,n} of homothets of a regular

251

simplex in Rd and we require an algorithm to ﬁnd a ((1 − ǫ)-approximation to) the point that is

252

contained in the largest number of these simplices. The machinery of Aronov and Har-Peled [1] can be

253

used to help solve this problem, but not before we prove some preliminary results, the ﬁrst of which is

254

a combinatorial geometry result.

255

Lemma 5. Let ∆ be a set of n homothets of a regular simplex in Rd, for d = O(1), and such that no

256

point in Rd is contained in more than k elements of ∆. Then, the total complexity of the arrangement,

257

A(∆), of the simplices in ∆ is O(nkd−1).

258

Proof. We ﬁrst consider the simpler case in which the elements of ∆ are translates (without scaling) of

259

a regular simplex. Suppose that the total complexity of A(∆) is m. Then, by the pigeonhole principle,

260

there is some element T in ∆ whose surface is involved in m/n features of A(∆). (Note that this implies

261

that T intersects all the elements of a set ∆′ ⊆ ∆ with |∆′| = Ω((m/n)1/(d−1)), since otherwise there

262

are not enough elements in ∆′ to generate m/n features on the surface of ∆.)

263

Observe that, since the elements of ∆′ are all unit size and they all intersect T , that they are

264

all contained in a ball of radius O(1) centered at the center of T . Furthermore, since each element of

265

∆′ has volume Ω(1) this implies that some point must be contained in Ω((m/n)1/(d−1)) elements of ∆′.

266

Thus, we obtain the inequality k ≥ Ω((m/n)1/(d−1)), or, equivalently, m ≤ O(nkd−1), as required.

267

Now, for the case where the elements of ∆ are homothets (translations and scalings) of a regular

268

simplex, we proceed as follows. Suppose that |A(∆)| = rn. Our goal is to show that r = O(kd−1).

269

Label the elements of ∆ as T1, . . . , Tn in increasing order of size and consider the smallest element Ti

270

such that Ti contributes at least r features to A({Ti, . . . , Tn}). Such a Ti is guaranteed to exist, since

271

otherwise |A(∆)| ≤ rn.

272

Now, Ti intersects all the elements in some set ∆′ ⊆ {Ti+1, . . . , Tn} with |∆′| = Ω(r1/(d−1)).

273

Shrink each element T ′ in ∆′ so as to obtain an element T ′′ such that (a) the size of T ′′ is equal to

274

the size of Ti, (b) T ′′ ⊆ T ′, and (c) T ′′ intersects Ti. Call the resulting set of shrunken elements ∆′′.

275

Condition (a) and the packing argument above imply that there is a point p ∈ Rd that is contained in

276

Ω(r1/(d−1)) elements of ∆′′. Condition (b) implies that p is contained in Ω(r1/(d−1)) elements of ∆′ and

277

hence also ∆. Therefore, we conclude, as before, that r = O(kd−1), which completes the proof.

9

278

Lemma 5 is somewhat surprising, since the union of n homothets of a regular tetrahedron in,

Ê

Ñ

Ö

º

279

for example, R3 can easily have complexity Ω(n2). This fact makes it impossible to apply the “usual”

280

Clarkson-Shor technique [5] that relates the complexity of the ﬁrst k levels to that of the boundary of

281

the union (the 0-level).

282

Lemma 6. Let ∆ be a set of n homothets of a regular simplex in Rd such that no point of Rd is

283

contained in more than k simplices of ∆. Then the arrangement A(∆) of ∆ can be computed in

284

O(n(kd−1 + (log n)d)) time.

285

Proof. Computing the arrangement A(∆) can be done in the following way. Sort the elements of ∆ by

286

decreasing size and construct A(∆) incrementally by inserting the elements one by one. When inserting

287

an element T , use a data structure (described below) to retrieve the elements of ∆ that intersect T and

288

discard the elements that are smaller than T . The proof of Lemma 5 implies that there will be at most

289

O(k) such elements. The intersection of the surfaces of these O(k) elements with the surface of T has

290

size O(kd−1) and can be computed in O(kd−1) time using d + 1 applications of the standard algorithm

291

for computing an arrangement of hyperplanes in Rd−1 [7, 8]. Thus, ignoring the cost of ﬁnding the

292

elements that intersect T , the overall running time of the algorithm is O(nkd−1).

293

All that remains is to describe a data structure for retrieving the elements that intersect a given

294

simplex T ∈ ∆. In the following we describe a data structure that can be constructed in O(n(log n)d)

295

time and can answer queries in O(x + (log n)d) time, where x is the size of the output. This data

296

structure will be constructed once and queried n times. The total size of the outputs over all n queries

297

will be the O(|A(∆)|) = O(nkd−1).

298

Refer to Figure 5. Suppose that every element T ∈ ∆ is a homothet of the regular simplex V

299

whose vertices are v1, . . . , vd+1 and let n1, . . . , nd+1 be the inner normals of the faces of V where ni

300

is the face opposite (not incident on) vertex vi. For any T ∈ ∆, let ti be the image of vi under the

301

homothetic transformation that takes V onto T . Observe that, if h is a halfspace of Rd with inner

302

normal ni, then h intersects T if and only if h contains ti. Furthermore, every simplex T ∈ ∆ is the

303

intersection of d halfspaces hT1 , . . . , hT

where the inner normal of ht

d+1

i is ni. Therefore, a simplex T ∈ ∆

304

intersects a simplex T ′ ∈ ∆ if and only if hTi contains t′i for all i ∈ {1, . . . , d + 1}.

305

This implies that the elements of ∆ can be stored in a (d + 1)-layer range tree [3]. The ith layer

306

of this tree, for i ∈ {1, . . . , d + 1}, stores elements of ∆ ordered by the projection of ti onto ni. In this

307

way, the range tree can return the set of all simplices in ∆ that intersect a query simplex T ∈ ∆. The

308

size of this range tree is O(n(log n)d) and it can answer queries in time O(x + n(log n)d) where x is the

309

size of the query result. Since each simplex in ∆ is passed as a query to this data structure exactly

310

once, the total sizes of outputs over all n queries is equal to the number of pairs T1, . . . , T2 ∈ ∆ such

311

that T1 ∩ T2 = ∅. But the number of such pairs is certainly a lower bound on |A(∆)| so it must be at

312

most O(nkd−1). This completes the proof.

313

Lemma 6 can be used as a subroutine in the algorithm of Aronov and Har-Peled [1, Theorem 3.3],

314

to obtain the following Corollary.

315

Corollary 1. Let ∆ be a set of n homothets of a regular simplex in Rd such that some point p ∈ Rd is

316

contained in δ elements of ∆. Then there exists an algorithm whose running time is O(ǫ−2dn(log n)d−1+

317

n(log n)d) and that, with high probability, returns a point p′ ∈ Rd contained in at least (1 − ǫ)δ elements

318

of ∆.

10

# Document Outline

ALGORITHMS FOR MARKETING-MIX OPTIMIZATION

2

Joachim Gudmundsson Pat Morin Michiel Smid

3

Abstract. Algorithms for determining quality/cost/price tradeoﬀs in saturated markets are consid-

4

ered. A product is modeled by d real-valued qualities whose sum determines the unit cost of producing

5

the product. This leads to the following optimization problem: given a set of n customers, each of

6

whom has certain minimum quality requirements and a maximum price they are willing to pay, design

7

a new product and select a price for that product in order to maximize the resulting proﬁt.

8

An O(n log n) time algorithm is given for the case, d = 1, of products having a single quality,

9

and O(n(log n)d+1) time approximation algorithms are given for products with any constant number,

10

d, of qualities. To achieve the latter result, an O(nkd−1) bound on the complexity of an arrangement

11

of homothetic simplices in Rd is given, where k is the maximum number of simplices that all contain

12

a single points.

13

½

ÁÒØÖÓ

ÙØ

ÓÒ

14

Revealed preference theory [13] is a method of determining a course of business action through the

15

review of historical consumer behaviour. In particular, it is a method of inferring an individual’s or a

16

group’s preferences based on their past choices. The marketing mix [10] of a product consists of the 4

17

Ps: Product, price, place, and promotion. In the current paper, we present algorithms for optimizing

18

the ﬁrst two of these by using data about consumers’ preferences. That is, we show how, given data on

19

consumer preferences, to eﬃciently choose a product and a price for that product in order to maximize

20

proﬁt.

21

Refer to Figure 1. A product P = (p, q1, . . . , qd) is deﬁned by a real-valued price, p, and

22

a number of real-valued orthogonal qualities, q1, . . . , qd. The market for a product is a collection

23

of customers C = {C1, . . . , Cn}, where Ci = (pi, qi,1, . . . , qi,d). A customer will purchase the least

24

expensive product that meets all her minimum quality requirements and whose price is below her

25

maximum price. That is, the customer Ci will consider the product P = (p, q1, . . . , qd) if p ≤ pi and

26

qj ≥ qi,j for all j ∈ {1, . . . , d}. The customer Ci will purchase the product if it has the minimum price

27

among all available products that Ci considers.

28

We consider markets that are saturated. That is, for every customer Ci there is an existing

29

product that satisﬁes Ci’s requirements and among all products that satisfy Ci’s requirements, Ci will

30

choose the least expensive product. From the point of view of a manufacturer introducing one or more

31

new products, this means that all customers are Pareto optimal, i.e., there are no two customers Ci

32

and Cj such that qi,k > qj,k for all k ∈ {1, . . . , d} and pi < pj. This is because no customer will

33

every purchase a product that is not Pareto optimal, since there is a lower-priced alternative that also

1

quality

q3 1

,

C3

q2 1

,

C2

q1 1

C

,

1

p1

p2

p3 price

Figure 1: A sample market with d = 1 and n = 3. A customer will consider any product that is in

their upper left quadrant.

34

satisﬁes all their minimum quality requirements. Therefore, every customer Ci can be replaced with

35

the (Pareto optimal) product that they purchase.

36

As an example, consider a market for computers in which an example customer Ci may be

37

looking for a computer with a minimum of 8 GB of RAM, a CPU benchmark score of at least 3000,

38

a GPU benchmark score of at least 2000, and be willing to pay at most $1500. In addition, there is

39

already a computer on the market which meets these requirements and retails for $1200. Thus, this

40

customer would be described by the vector (1200, 8, 3000, 2000). If a manufacturer introduces a new

41

product (1199, 8, 3500, 2000) (a computer with 8 GB of RAM, a CPU benchmark score of 3500 and a

42

GPU benchmark score of 2000 retailing for $1199) then this customer would select this new product

43

over their current choice.

44

By appropriately reparameterizing the axes, we can assume that the cost, cost(P ), of manufac-

45

turing a product P = (p, q1, . . . , qd) is equal to the sum of its qualities

d

46

cost(P ) =

qi .

i=1

47

The proﬁt per unit sold of P is therefore

48

ppu(P ) = p − cost(P ) .

49

In this paper we consider algorithms that a manufacturer can use when planning a new product to

50

introduce into an existing saturated market with the goal being to maximize the proﬁt obtained. More

51

precisely, given a Pareto-optimal market of customers M = {C1, . . . , Cn}, each having d qualities, the

52

ProductDesign(d) problem is to ﬁnd a product P ∗ ∈ Rd+1 such that

53

proﬁt(P ∗) = ppu(P ∗) × |{i : Ci purchases P ∗}|

54

is maximized.

55

The term marketing mix is probably the most famous phrase in marketing. Not surprisingly,

56

economists and market researchers have considered methods of optimizing the marketing mix in various

57

scenarios. As there are many diﬀerent models of the problem, it is diﬃcult to compare algorithms.

2

58

Most models of marketing-mix problems involve a constant number of real-valued input pa-

59

rameters. This sometimes leads to problems where the optimal solution is one of a constant number

60

of possible closed forms (see, e.g., Thomson and Teng’s optimal constant price model [12]). In other

61

cases, a closed form is not achievable, but a (sometimes approximate) solution can be obtained using

62

numerical optimization techniques (see, e.g., Balanchandran and Gensch [2], Thomson and Teng [12],

63

Naik et al. [11], Deal [6], Erickson [9]). In all cases, it is expected that the model parameters are derived

64

from real-world data, such as surveys or sales ﬁgures, and involves ﬁtting of the model parameters to

65

the available data.

66

The work in the current paper is diﬀerent from this previous work in several ways. For one, it

67

is one of the few works that deals primarily with the ﬁrst two P’s, product and pricing. Most existing

68

literature focuses on the marketing P’s, namely place and promotion, and to a lesser extent, pricing

69

of an existing product. Secondly, it deals directly with data about individual consumers rather than

70

aggregating this data so that it ﬁts a particular model of consumer behaviour.

71

We believe that this models very well what happens in online shopping for high cost products

72

such as computers, cameras, and televisions. In such markets, savvy consumers have good data available

73

about both the speciﬁcations and the cost of all available products so that marketing eﬀorts are

74

(arguably) less important than the quality and prices of the products. On the other hand, online

75

sellers such as Amazon have large amounts of data about users’ past purchases and can use this data

76

as input to the problem. In particular, these sellers know the speciﬁcations qi,1, . . . , qi,d and prices pi

77

of huge quantities of items sold and can use this data to advise a manufacturer that is designing a new

78

product.

79

In the remainder of the paper we give an O(n log n) time algorithm for ProductDesign(1)

80

(Section 2), and O(n(log n)d+1) time approximation schemes for ProductDesign(d) (Section 3 and

81

Section 4). Section 5 summarizes our results and concludes with directions for future research.

82

¾

ÇÒ

¹

Ñ

Ò×

ÓÒ

Ð

Ô

ÖÓ

ÙØ×

83

In this section, we consider the simplest case, when a manufacturer wishes to introduce a new product

84

in which the quality of a product has only one dimension. Examples of such markets include, for

85

example, suppliers to the construction industry in which items (steel I-beams, ﬁnished lumber, logs)

86

must have a certain minimum length to be used for a particular application. An overly long piece can

87

be cut down to size, but using two short pieces instead of one long piece is not an option.

88

Throughout this section, since d = 1, we will use the shorthand P = (p, q) for the product

89

being designed and qi for qi,1. Thus, we have a set of customers M = {(p1, q1), . . . , (pn, qn)} and we

90

are searching for a point P ∗ = (p∗, q∗) that maximizes

91

proﬁt(p∗, q∗) = (p∗ − q∗)|{i : p∗ ≤ pi and q∗ ≥ qi}| .

92

Our algorithm is an implementation of the plane-sweep paradigm [4]. The correctness of the

93

algorithm relies on two lemmas about the structure of the solution space. The ﬁrst lemma is quite

94

easy:

95

Lemma 1. The value (p∗, q∗) that maximizes proﬁt(p∗, q∗) is obtained when p∗ = pi and q∗ = qj for

96

some i, j ∈ {1, . . . , n}.

3

ppu = 0

quality (q)

(p′, q)

(p, q)

(p′, q′)

(p, q′)

price (p)

Figure 2: proﬁt(p, q) ≤ proﬁt(p, q′) implies that proﬁt(p′, q) ≤ proﬁt(p′, q′) for all p′ ≤ p.

97

Proof. First, observe the obvious bounds on p∗ and q∗:

98

min{pi : i ∈ {1, . . . , n}} ≤ p∗ ≤ max{pi : i ∈ {1, . . . , n}}

99

and

100

min{qi : i ∈ {1, . . . , n}} ≤ q∗ ≤ max{qi : i ∈ {1, . . . , n}} .

101

Consider the arrangement of lines obtained by drawing a horizontal and vertical line through each

102

customer (pi, qi) for i ∈ {1, . . . , n}. Within each cell of this arrangement, the function proﬁt(p, q) is

103

a linear function of p and q and it is bounded. Therefore, within a particular cell, the function is

104

maximized at a vertex. Since each vertex is the intersection of a horizontal and vertical line through a

105

pair of customers, the lemma follows.

106

The following lemma, illustrated in Figure 2, is a little more subtle and illustrates a manufac-

107

turer’s preference for lower-quality products:

108

Lemma 2. Let q′ ≤ q and let p be such that 0 < proﬁt(p, q) ≤ proﬁt(p, q′). Then, for any p′ ≤ p,

109

proﬁt(p′, q) ≤ proﬁt(p′, q′).

110

Proof. By deﬁnition, proﬁt(p, q) = a(p − q) and proﬁt(p, q′) = a′(p − q′), where a and a′ are the number

111

of customers who would consider (p, q) and (p, q′), respectively. These customers are all taken from the

112

set M≥ = {(pi, qi) ∈ M : pi ≥ p}.

113

Now, consider the customers in the set M ′ = {(pi, qi) ∈ M : p′ ≤ pi < p}. By the assumption

114

that customers are Pareto optimal, any customer (pi, qi) in M′ has qi ≤ q′, so all of these customers

115

will consider either (p′, q′) or (p′, q) if either one is oﬀered. Therefore,

proﬁt(p′, q′) = (a′ + |M ′|)(p′ − q′)

= a′(p′ − q′) + |M ′|(p′ − q′)

≥ a′(p′ − q′) + |M ′|(p′ − q)

since q > q′

= a′(p − q′) + a′(p′ − p) + |M ′|(p′ − q)

116

≥ a′(p − q′) + a(p′ − p) + |M ′|(p′ − q)

since a ≥ a′ and (p′ − p) < 0

≥ a(p − q) + a(p′ − p) + |M ′|(p′ − q)

by assumption

= a(p′ − q) + |M ′|(p′ − q)

= proﬁt(p′, q) ,

4

117

as required.

118

Lemma 2 allows us to apply the plane sweep paradigm with a sweep by decreasing price. It

119

tells us that, if a product (p, q′) gives better proﬁt than the higher-quality product (p, q) at the current

120

price p, then it will always give a better proﬁt for the remainder of the sweep. In particular, there will

121

never be a reason to consider a product with quality q for the remainder of the algorithm’s execution.

122

Let the customers be labelled (p1, q1), . . . , (pn, qn) in decreasing order of pi, so that pi+1 ≤ pi

123

for all i ∈ {1, . . . , n − 1}. At any point in the sweep algorithm, there is a current price p, which

124

starts at p = ∞ and decreases during the execution of the algorithm. At the start of the algorithm the

125

algorithm’s event queue Q, which is represented as a balanced binary search tree, is initialized to contain

126

the values pn, . . . , p1. At all times, the algorithm maintains a list L of qualities q∗1 > q∗2 > · · · > q∗m

127

such that proﬁt(p, q∗1) > proﬁt(p, q∗2) > · · · > proﬁt(p, q∗m). The quality q∗1 is the optimal quality for

128

the current price, p. By the time the algorithm terminates, the quality of the globally-optimal solution

129

will have appeared as the ﬁrst element in L. To complete the description of the algorithm, all that

130

remains is to show how L and Q are updated during the processing of events in the event queue.

131

There are two kinds of events in the event queue. Insertions occur at the values p1, . . . , pn.

132

Deletions, which we describe next, occur when the relative order of two adjacent items in L changes.

133

Consider a consecutive pair of the elements q∗i and q∗i+1 in L. When q∗i and q∗i+1 became adjacent in L,

134

it was at some price p = pt such that proﬁt(pt, q∗i) > proﬁt(pt, q∗i+1). Let ai and ai+1 be the number of

135

customers who would consider (pt, q∗i) and (pt, q∗i+1), respectively. Then,

136

proﬁt(pt, q∗i) = (pt − q∗i)ai

137

and

138

proﬁt(pt, q∗i+1) = (pt − q∗i+1)ai+1

139

Now, looking forward in time to a later step in the execution of the algorithm, when p = pt′, with

140

t′ > t, we ﬁnd that

141

proﬁt(pt′, q∗i) = (pt′ − q∗i)(ai + t′ − t)

142

and

143

proﬁt(pt′, q∗i+1) = (pt′ − q∗i+1)(ai+1 + t′ − t) .

144

We are interested in identifying the price pt′ where the inequality proﬁt(pt′, q∗i) > proﬁt(pt′, q∗i+1)

145

changes to proﬁt(pt′, q∗i) ≤ proﬁt(pt′, q∗i+1). When this happens, q∗i can be safely discarded from L

146

since, by Lemma 2, proﬁt(p, q∗i) will never again exceed proﬁt(p, q∗i+1) for the remainder of the sweep.

147

The value pt′ is a deletion event.

148

Note that Lemma 2 also allows for binary search on the value pt′. In particular, the interval

149

[pj, pj+1] containing pt′ can be found in O(log n) time, after which the value of pt′ can be obtained by

150

solving the linear equation

151

(pt′ − q∗i)(ai + t′ − t) ≤ (pt′ − q∗i+1)(ai+1 + t′ − t) ,

152

for t′. (The equation is linear because the values ai and ai+1 are constant in the interval (pj, pj+1).)

153

Thus, whenever two new elements become adjacent in L, we can add the appropriate deletion event to

154

Q in O(log n) time.

155

When processing an insertion event pi, we remove from the tail of L all values q∗j such that

156

proﬁt(pi, q∗j) ≤ proﬁt(pi, qi) and then append qi onto L. While deleting the elements of L, we also

5

157

remove all the associated deletion events from Q. Appending qi to L causes at most one new pair of

158

elements in L to become adjacent, so we add the appropriate deletion event to Q as described above.

159

The time to process the event pi is there O((ki + 1) log n), where ki is the number of elements that are

160

deleted from L.

161

When processing a deletion event that deletes q∗i from L, we simply delete q∗i from L and its (at

162

most two) associated deletion events from Q. This may cause a new pair of elements, q∗i−1 and q∗i+1,

163

in L to become adjacent, so we add the appropriate deletion event to Q. In this way, a deletion event

164

can be processed in O(log n) time.

165

Note that, after all the processing associated with an event pt is complete, the ﬁrst element, q∗1,

166

in L is the value that maximizes proﬁt(pt, q∗1). Thus, the algorithm need only keep track, throughout

167

its execution, of the highest proﬁt obtained from the ﬁrst element of L, and output this value at the

168

end of its execution. This completes the description of the algorithm.

169

Theorem 1. There exists an O(n log n) time algorithm for ProductDesign(1).

170

Proof. The correctness of the algorithm described above follows from 2 facts: Lemma 1 ensures that

171

the optimal solution is of the form (pi, q∗) for some i ∈ {1, . . . , n}, and Lemma 2 ensures that the

172

optimal solution appears at some point as the ﬁrst element of the list L.

173

The running time of the algorithm can be bounded as follows: The total number of deletion

174

events processed is at most n, since each such event removes some value qi from L for some i ∈

175

{1, . . . , n}. Thus, the cost of processing all deletion events is O(n log n). Similarly,

n

i=1 ki ≤ n since

176

ki is the number of elements deleted from L during the processing of pi. Thus, the time required to

177

handle all insertion events, and therefore the running time of the entire algorithm, is O(n log n)

178

The following theorem shows that a running time of Ω(n log n) is inherent in this problem, even

179

when considering approximation algorithms.

180

Theorem 2. Let M be an instance of ProductDesign(1) and (p∗, q∗) be a solution that maximizes

181

proﬁt(p∗, q∗). In the algebraic decision tree model of computation, any algorithm that can ﬁnd a solution

182

(p, q) such that 2 · proﬁt(p, q) > proﬁt(p∗, q∗) has Ω(n log n) running time in the worst-case.

183

Proof. We reduce from the integer Element-Uniqueness problem, which has an Ω(n log n) lower

184

bound in the algebraic decision tree model [14]: Given an array A = [x1, . . . , xn] containing n integers,

185

are all the elements of A unique?

186

We convert A into an instance of ProductDesign(1) in O(n) time as follows (refer to Figure 3).

187

For each xi, i ∈ {1, . . . , n} we introduce a customer (pi, qi) with pi = qi + 1/2 and qi = xi. If

188

there exists a value x in A that occurs 2 or more times, then the product (x + 1/2, x) gives a value

189

proﬁt(x + 1/2, x) ≥ 1. On the other hand, if there is no such x, then

190

1. any product (p, q) with p − q > 1/2 can not be sold to any customers and

191

2. any product (p, q) with p − q > 0 can be sold to at most 1 customer.

6

ppu = 0

ppu = 1/2

x2

x1

q

x3

x5

x4

p

Figure 3: Reducing Element-Uniqueness to ProductDesign(1,1).

192

Therefore, if all the elements of A are unique, then proﬁt(p∗, q∗) = 1/2, otherwise proﬁt(p∗, q∗) ≥ 1.

193

The result follows.

194

¿

Ò

Ö¹Ð

Ò

Ö

ÔÔ

ÖÓ

Ü

Ñ

Ø

ÓÒ

Ð

Ó

Ö

Ø

Ñ

Ó

Ö

Ñ

Ò×

ÓÒ

Ð

Ô

ÖÓ

ÙØ×

195

In this section, we consider algorithms for ProductDesign(2), in which products have 2 qualities. As

196

a baseline, we ﬁrst observe that, if we ﬁx the value of q2, then the optimal solution of the form (p, q1, q2)

197

can be found using a single application of the algorithm in Theorem 1. Therefore, by successively solving

198

the problem for each q2 ∈ {q2,1, . . . , q2,n} and taking the best overall solution we obtain an O(n2 log n)

199

time algorithm for ProductDesign(2).

200

More generally, ProductDesign(d) can be solved using O(nd−1) applications of Theorem 1

201

resulting in an O(nd log n) time algorithm. Unfortunately, these are the best results known for d ≥ 2,

202

and, as discussed in Section 5, we suspect that an algorithm with running time o(nd) will be diﬃcult

203

to achieve using existing techniques. Therefore, in this section we focus our eﬀorts on obtaining a

204

near-linear approximation algorithm.

205

Fix some constant ǫ > 0. Given an instance M of ProductDesign(d), a point P ∈ Rd+1 is a

206

(1 − ǫ)-approximate solution for M if proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗) for all P ∗ ∈ Rd+1. An algorithm

207

is a (high probability) Monte-Carlo (1 − ǫ)-approximation algorithm for ProductDesign(d) if, given

208

an instance M of size n, the algorithm outputs a (1 − ǫ)-approximate solution for M with probability

209

at least 1 − n−c for some constant c > 0.

210

Let r = max{ppu(Ci) : i ∈ {1, . . . , n}} and observe that r is the maximum proﬁt per unit

211

that can be achieved in this market. Let E = 1/(1 − ǫ) and let ℓ = ⌈logE n⌉ and observe that

212

ℓ = O(ǫ−1 log n).1 For each i ∈ {0, 1, 2, . . . , ℓ}, deﬁne the plane Hi = {(p, q1, q2) : p−q1 −q2 = r(1−ǫ)i}.

213

The following lemma says that a search for an approximate solution can be restricted to be contained

214

in one of the planes Hi.

215

Lemma 3. For any product P ∗ = (p∗, q∗1, q∗2), there exists a product P = (p, q1, q2) such that P ∈ Hi

216

for some i ∈ {0, . . . , ℓ} and proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗).

1 This can be seen by taking the limit limǫ→0+(ǫ/ log(E)) using one application of L’Hˆopital’s Rule.

7

q1

q1

q2

Hi

q2

∆i,2

C2

∆i,1

∆i,3

C1

C3

price

price

(a)

(b)

Figure 4: The intersection of Hi with customers’ quadrants is a set of homothetic equilateral triangles.

217

Proof. There are two cases to consider. If ppu(P ∗) ≤ r/n then proﬁt(P ∗) ≤ r, in which case we set

218

P = Ci where ppu(Ci) = r, so that P ∈ H0 and proﬁt(P ) = r ≥ proﬁt(P ∗) ≥ (1 − ǫ) proﬁt(P ∗), as

219

required.

220

Otherwise, r/n < ppu(P ∗) ≤ r. In this case, consider the plane Hi where i = ⌈logE(r/ ppu(P ∗))⌉.

221

Notice, that for any point P ∈ Hi, ppu(P ) ≥ (1 − ǫ) ppu(P ∗). More speciﬁcally, the orthogonal pro-

222

jection P = (p, q1, q2) of P ∗ onto Hi is a product with p ≤ p∗, q1 ≥ q∗1, and q2 ≥ q∗2. Therefore,

223

any customer who would consider P ∗ would also consider P , so proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗), as

224

required.

225

Lemma 3 implies that the problem of ﬁnding an approximate solution to ProductDesign(2)

226

can be reduced to a sequence of problems on the planes H0, . . . , Hℓ. Refer to Figure 4. Each customer

227

Cj considers all products in a quadrant whose corner is Cj. The intersection of this quadrant with

228

Hi is a (possibly empty) equilateral triangle ∆i,j. The customer Cj will consider a product P in Hi

229

if and only P is in ∆i,j. Thus, the problem of solving ProductDesign(2) restricted to the plane Hi

230

is the problem of ﬁnding a point contained in the largest number of equilateral triangles from the set

231

∆i = {∆i,j : j ∈ {1, . . . , n}}.

232

Note that the elements in ∆i are homothets (translations and scalings) of an equilateral triangle,

233

so they form a collection of pseudodisks and we wish to ﬁnd the deepest point in this collection of

234

pseudodisks. No algorithm with running time o(n2) is known for solving this problem exactly, but

235

Aronov and Har-Peled [1] have recently given a Monte-Carlo (1 − ǫ)-approximation algorithm for this

236

problem that runs in time O(ǫ−2n log n). By applying this algorithm to each of ∆i for i ∈ {1, . . . , ℓ},

237

we obtain the following result:

238

Theorem 3. For any ǫ > 0, there exists an O(ǫ−3n(log n)2) time high-probability Monte-Carlo (1 − ǫ)-

239

approximation algorithm for ProductDesign(2).

8

240

d

Ò

Ö¹Ð

Ò

Ö

ÔÔ

ÖÓ

Ü

Ñ

Ø

ÓÒ

Ð

Ó

Ö

Ø

Ñ

Ó

Ö

ÓÒ×Ø

ÒØ

241

In this section we extend the algorithm from the previous section to (approximately) solve ProductDesign(d)

242

for any constant value of d. The algorithm is more or less unchanged, except that the proof requires

243

some new results on the combinatorics of arrangements of homothets.

244

As before, let r = max{ppu(Ci) : i ∈ {1, . . . , n}} and let ℓ = ⌈logE n⌉. For each i ∈

245

{0, 1, 2, . . . , ℓ}, deﬁne the hyperplane Hi = {(p, q1, . . . , qd) : p −

d

i=1 qi = r(1 − ǫ)i}.

The follow-

246

ing lemma has exactly the same proof as Lemma 3.

247

Lemma 4. For any product P ∗ = (p∗, q∗1, . . . , q∗d), there exists a product P = (p, q1, . . . , qd) such that

248

P ∈ Hi for some i ∈ {0, . . . , ℓ} and proﬁt(P ) ≥ (1 − ǫ) proﬁt(P ∗).

249

Again, each customer Cj deﬁnes a regular simplex ∆i,j in Hi such that Cj will consider P ∈ Hi

250

if and only if P ∈ ∆i,j. In this way, we obtain a set ∆i = {∆i,1, . . . , ∆i,n} of homothets of a regular

251

simplex in Rd and we require an algorithm to ﬁnd a ((1 − ǫ)-approximation to) the point that is

252

contained in the largest number of these simplices. The machinery of Aronov and Har-Peled [1] can be

253

used to help solve this problem, but not before we prove some preliminary results, the ﬁrst of which is

254

a combinatorial geometry result.

255

Lemma 5. Let ∆ be a set of n homothets of a regular simplex in Rd, for d = O(1), and such that no

256

point in Rd is contained in more than k elements of ∆. Then, the total complexity of the arrangement,

257

A(∆), of the simplices in ∆ is O(nkd−1).

258

Proof. We ﬁrst consider the simpler case in which the elements of ∆ are translates (without scaling) of

259

a regular simplex. Suppose that the total complexity of A(∆) is m. Then, by the pigeonhole principle,

260

there is some element T in ∆ whose surface is involved in m/n features of A(∆). (Note that this implies

261

that T intersects all the elements of a set ∆′ ⊆ ∆ with |∆′| = Ω((m/n)1/(d−1)), since otherwise there

262

are not enough elements in ∆′ to generate m/n features on the surface of ∆.)

263

Observe that, since the elements of ∆′ are all unit size and they all intersect T , that they are

264

all contained in a ball of radius O(1) centered at the center of T . Furthermore, since each element of

265

∆′ has volume Ω(1) this implies that some point must be contained in Ω((m/n)1/(d−1)) elements of ∆′.

266

Thus, we obtain the inequality k ≥ Ω((m/n)1/(d−1)), or, equivalently, m ≤ O(nkd−1), as required.

267

Now, for the case where the elements of ∆ are homothets (translations and scalings) of a regular

268

simplex, we proceed as follows. Suppose that |A(∆)| = rn. Our goal is to show that r = O(kd−1).

269

Label the elements of ∆ as T1, . . . , Tn in increasing order of size and consider the smallest element Ti

270

such that Ti contributes at least r features to A({Ti, . . . , Tn}). Such a Ti is guaranteed to exist, since

271

otherwise |A(∆)| ≤ rn.

272

Now, Ti intersects all the elements in some set ∆′ ⊆ {Ti+1, . . . , Tn} with |∆′| = Ω(r1/(d−1)).

273

Shrink each element T ′ in ∆′ so as to obtain an element T ′′ such that (a) the size of T ′′ is equal to

274

the size of Ti, (b) T ′′ ⊆ T ′, and (c) T ′′ intersects Ti. Call the resulting set of shrunken elements ∆′′.

275

Condition (a) and the packing argument above imply that there is a point p ∈ Rd that is contained in

276

Ω(r1/(d−1)) elements of ∆′′. Condition (b) implies that p is contained in Ω(r1/(d−1)) elements of ∆′ and

277

hence also ∆. Therefore, we conclude, as before, that r = O(kd−1), which completes the proof.

9

278

Lemma 5 is somewhat surprising, since the union of n homothets of a regular tetrahedron in,

Ê

Ñ

Ö

º

279

for example, R3 can easily have complexity Ω(n2). This fact makes it impossible to apply the “usual”

280

Clarkson-Shor technique [5] that relates the complexity of the ﬁrst k levels to that of the boundary of

281

the union (the 0-level).

282

Lemma 6. Let ∆ be a set of n homothets of a regular simplex in Rd such that no point of Rd is

283

contained in more than k simplices of ∆. Then the arrangement A(∆) of ∆ can be computed in

284

O(n(kd−1 + (log n)d)) time.

285

Proof. Computing the arrangement A(∆) can be done in the following way. Sort the elements of ∆ by

286

decreasing size and construct A(∆) incrementally by inserting the elements one by one. When inserting

287

an element T , use a data structure (described below) to retrieve the elements of ∆ that intersect T and

288

discard the elements that are smaller than T . The proof of Lemma 5 implies that there will be at most

289

O(k) such elements. The intersection of the surfaces of these O(k) elements with the surface of T has

290

size O(kd−1) and can be computed in O(kd−1) time using d + 1 applications of the standard algorithm

291

for computing an arrangement of hyperplanes in Rd−1 [7, 8]. Thus, ignoring the cost of ﬁnding the

292

elements that intersect T , the overall running time of the algorithm is O(nkd−1).

293

All that remains is to describe a data structure for retrieving the elements that intersect a given

294

simplex T ∈ ∆. In the following we describe a data structure that can be constructed in O(n(log n)d)

295

time and can answer queries in O(x + (log n)d) time, where x is the size of the output. This data

296

structure will be constructed once and queried n times. The total size of the outputs over all n queries

297

will be the O(|A(∆)|) = O(nkd−1).

298

Refer to Figure 5. Suppose that every element T ∈ ∆ is a homothet of the regular simplex V

299

whose vertices are v1, . . . , vd+1 and let n1, . . . , nd+1 be the inner normals of the faces of V where ni

300

is the face opposite (not incident on) vertex vi. For any T ∈ ∆, let ti be the image of vi under the

301

homothetic transformation that takes V onto T . Observe that, if h is a halfspace of Rd with inner

302

normal ni, then h intersects T if and only if h contains ti. Furthermore, every simplex T ∈ ∆ is the

303

intersection of d halfspaces hT1 , . . . , hT

where the inner normal of ht

d+1

i is ni. Therefore, a simplex T ∈ ∆

304

intersects a simplex T ′ ∈ ∆ if and only if hTi contains t′i for all i ∈ {1, . . . , d + 1}.

305

This implies that the elements of ∆ can be stored in a (d + 1)-layer range tree [3]. The ith layer

306

of this tree, for i ∈ {1, . . . , d + 1}, stores elements of ∆ ordered by the projection of ti onto ni. In this

307

way, the range tree can return the set of all simplices in ∆ that intersect a query simplex T ∈ ∆. The

308

size of this range tree is O(n(log n)d) and it can answer queries in time O(x + n(log n)d) where x is the

309

size of the query result. Since each simplex in ∆ is passed as a query to this data structure exactly

310

once, the total sizes of outputs over all n queries is equal to the number of pairs T1, . . . , T2 ∈ ∆ such

311

that T1 ∩ T2 = ∅. But the number of such pairs is certainly a lower bound on |A(∆)| so it must be at

312

most O(nkd−1). This completes the proof.

313

Lemma 6 can be used as a subroutine in the algorithm of Aronov and Har-Peled [1, Theorem 3.3],

314

to obtain the following Corollary.

315

Corollary 1. Let ∆ be a set of n homothets of a regular simplex in Rd such that some point p ∈ Rd is

316

contained in δ elements of ∆. Then there exists an algorithm whose running time is O(ǫ−2dn(log n)d−1+

317

n(log n)d) and that, with high probability, returns a point p′ ∈ Rd contained in at least (1 − ǫ)δ elements

318

of ∆.

10

- Introduction
- One-dimensional products
- A near-linear approximation algorithm for bidimensional products
- A near-linear approximation algorithm for constant d
- Conclusions

## Add New Comment