Buyers Who Must Have Two Items

An open problem on setting prices to optimize sales

Nina Balcan and Avrim Blum are top researchers in game theory, learning theory, and more generally the theory of algorithms. Nina is at Tech these days and Avrim is at CMU.

Today I want to talk about a simple, perhaps deceptively simple, question about the pricing of items.

The problem is due to Nina Balcan and Avrim Blum, who have a partial result that seems quite hard to improve. Avrim presented the result a few years ago at a talk at Tech. I could not follow any of the rest of his talk, because I had to play with the problem. It is one of those wonderful questions that is clean, simple to state, well motivated, but seems to be very hard to solve. I made no progress at all on the problem—and worse I missed the rest of his great talk.

The Problem

Here is their problem. You have a warehouse filled with items: you got this and that. Let’s use exciting names for the items and call them item , item , and so on. In total you have items, but even better your warehouse is filled with many identical copies of each item.

You company wants, of course, to sell these items to your customers. So far nothing unusual—that is what every company wants to do. The twist is that your customers have requests that pair two items together. Customer Alice may say: I wish to buy item and item and I will pay up to dollars for the pair. While customer Bob may say: I wish to buy item and item and I will pay up to dollars for the pair.

Coupling of items may be unusual but it is a plausible model. In real life people do sometimes couple their buying implicitly rather than explicitly as above. Think of Alice as wanting to buy a flat screen TV which is item , and also a set of cables to attach it to her entertainment system which is item . From her point of view having one is useless, while having both is priceless—well not exactly priceless, since she will only pay up to dollars total.

Your company must be able to handle these paired requests, and in the simplest manner possible. So you have decided to create a price for each item—what a radical idea. Every item from to will have a price in dollars. The catch is you wish to get the most money possible from your customers. You are lucky in that you know for every customer exactly what two items they want and the maximum price they will pay for the pair. A more realistic version might be an on-line problem, but here we are assuming that you see all the requests at once.

How do you price the items? The key issue is that if a customer wants items and for dollars here is what happens:

If the price of the two items together is less or equal to you get the sum of the two prices. If it is more than what the customer wants to pay you get zero.

Nothing. Zip. This is the cool part of this problem: the decision of what you get once you select prices is non-linear. This is why the problem seems to be hard, and why there are only approximations known.

The Problem Formally Stated

You are given an undirected graph . We will assume there are no multiple edges, although the general problem allows them. Each edge is assigned a positive weight, via a function . The weight of the edge should be thought of as the amount that a customer will pay for buying both items and . Your task is to final a price function so that the following sum is optimal:

Here is if and otherwise. This is the rule that you get money from a customer only if the price of the two items, is less than or equal to the amount they wish to pay, . And when you are paid you get , not the maximum the customer was willing to pay.

Approximate Solutions

There is a very simple and clever algorithm that is 2-OPT for the case when the graph is bipartite. The best general algorithm is 4-OPT, and uses the bipartite result. Balcan and Blum proved:

Theorem: For the pricing problem on a bipartite graph there is a deterministic algorithm that determines prices that yield a total payment within a factor of optimal.

Proof: Let be the bipartite graph, and let and be a partition of the vertices of the graph so all edges go between and only. Set all the prices for the vertices in to —essentially giving those items away. Then determine the optimal prices for the vertices on the left. Note that this is easy to do because now the pricing problem is on single items, not on pairs. Call the amount of dollars you get , since the money comes from the vertices. Then do the same to get by setting the prices for the vertices in to .

Assume that : this is okay by symmetry. Then the simple observation to finish the proof is that must be at least of the total optimal payment possible. So use pricing for .

How do Balcan and Blum use this for general graphs? Just give a random 2-coloring of the vertices, ignoring all edges between two endpoints of the same color, thus making the remaining graph bipartite. In expectation, this process loses at most half the optimal revenue—and can be made deterministic using pairwise independence. This gives a 4-approximation in general, and no better approximation is known.

Further Results

There is a hardness result that there is no -opt for the pricing problem unless , so we cannot expect a fast general solution that is exact. This result is in the pretty paper titled “On Hardness of Pricing Items for Single-Minded Bidders” by Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev, and Maxim Sviridenko.

Locally, at Tech, Shiva Kintali and Danupon Nanongkai have worked on the flip-side problem of trying to find better upper bounds. So far they have shown that some very special graphs have either exact polynomial time algorithms or good polynomial time approximation algorithms, in some cases an actual PTAS. Here is the list so far:

1. Paths have an optimal algorithm.
2. Cycles have an optimal algorithm.
3. Trees have a PTAS.
4. Graphs that are k-colorable graphs have a factor approximation.

For example, cycles are handled as follows: If in the optimal case some customer edge is not satisfied then try all deleted versions of the cycle and use the tree algorithm. If on the other hand in the optimal case all customers are satisfied, then we can easily reduce the problem to a linear programming problem.

Curiously while the result for paths is just a standard application of dynamic programming, the details are a bit messy. I would have guessed that a simple path would be “trivial,” but that appears not to be the case.

Open Problems

Is there a -opt for general graphs with ? Are there other interesting classes of graphs that have good approximation algorithms? There is a natural generalization to hypergraphs: in this case buyers wish to purchase multiple items or none.