**Problem Detail:**

This question comes from economics. There is a market $M$ that contains $m$ items. There is a *value function* $v:2^M\to \mathbb{R}$, that assigns a monetary value to each "bundle" (- subset of $M$). The function is given by $2^m$ values - a value per bundle.

A *price-vector* $p$ is a vector that assigns to each item $x\in M$ a non-negative price $p_x$. Given a price-vector, the *net utility* of a bundle is its value minus its price, i.e:

$$ u(X) = v(X) - \sum_{x\in X}p_x$$

A bundle is called *demanded* if its net-utility is maximal - no bundle has larger net-utility.

A pair of bundles is called a *demand-pair* if there exists a price-vector such that both of these bundles are demanded (i.e, they have the same net-utility and it is maximal).

**I am looking for an algorithm that receives the valuation $v$ and finds all demand-pairs**.

For example, suppose there are $m=2$ items and the valuation function is:

$v(\emptyset)=0$, $v(\{x\})=2$, $v(\{y\})=3$, $v(\{x,y\})=4$.

Then:

- $\{y\}$ and $\{x,y\}$ are demand-pairs, because when $p_x=1,p_y=0$, both these bundles have net-utility 3, which is maximal.
- $\{\emptyset\}$ and $\{x,y\}$ are not demand-pairs, because if they have the same net-utility, then this utility must be 0. Then, necessarily $p_x+p_y=5$; but then either $p_x<2$ or $p_y<3$; but then either $\{x\}$ or $\{y\}$ (or both) have a net-utility of more than 0, so $\emptyset$ is not demanded.

###### Asked By : Erel Segal-Halevi

###### Answered By : D.W.

This can be solved in polynomial time, by solving $2^{2m}$ linear programs. (That might look exponential, but is polynomial in the size of the input, as the input size is $2^m$.)

Given a pair of bundles, you can check whether it is a demand-pair using linear programming; see below. So, you can apply this to all candidate pairs.

Suppose we have two bundles, $X,Y$, and we want to know if they are a demand-pair. Introduce a variable $p_x$ for each $x \in M$. It's easy to write a linear equality that expresses that $X,Y$ have the same net-utility: $u(X)=u(Y)$. Also, it's easy to write linear inequalities to express that no other bundle has higher net-utility: $u(X) \ge u(Z)$ for all other bundles $Z$. Each of those is a linear (in)equality on the variables $p_x$. We also have the inequalities $p_x \ge 0$. Now use linear programming to test whether all of those inequalities are simultaneously satisfiable; if they are, there exists a price-vector where $X,Y$ are simultaneously demanded.

As an optimization, note that $X,Y$ are a demand-pair for market $M$ iff they are a demand-pair for market $X \cup Y$: without loss of generality you can set the price of every item in $(X \cup Y) \setminus M$ to $+\infty$. Also, without loss of generality you can set the price of every item in $X \cap Y$ to 0. Consequently, $X,Y$ is a demand-pair for market $M$ iff $X'=X \setminus Y$ and $Y'=Y \setminus X$ are a demand-pair for market $X' \cup Y'$. This will make each linear program smaller and more efficient to solve. It also means that you only need to test pairs that have no common intersection, so it suffices to test at most $3^m$ pairs $X',Y'$.

Question Source : http://cs.stackexchange.com/questions/54379

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback