3
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ How large is $m$? What running time is required? What's the best algorithm you've got so far? $\endgroup$ – D.W. Mar 12 '16 at 22:20
2
$\begingroup$

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'$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.