Archive

Archive for the ‘theory’ Category

Do we believe the Axiom of Choice ?

April 10th, 2011 No comments

Continuing on my series of posts from Israel, I’d like to share some exciting puzzle that I heard today from Omer Tamuz. I’ve learned before about the Axiom of Choice in a Measure Theory class, but never saw a so striking and counter-intuitive application of it. Ok, you might say the Banach–Tarski paradox is a pehaps better example – but since it’s proof is so complicated, it is not as striking as seeing how a simple application of it can generate un-intuitive results. First, let me present two puzzles:

Puzzle #0: There are n+1 people in a line, and each has a 0/1 number on his hat. Each player can look to the numbers of the players in front of him. So, if x_i is the number of player i, then player i knows x_{i+1},\hdots,x_n. Now, from i = 0 \hdots n the players will say his own number. Is there a protocol such that players 1,\hdots,n will get their own number right? (Notice that they hear what the players before him said).

Puzzle #1: Consider the same puzzle with an infinite number of players. I.e. there are x_i; i \in \mathbb{Z}_+ and player i knows x_j for all j > i. Show a protocol for all players, except the first to get the answer right?

Puzzle #2: Still the same setting, but now players don’t hear what the previous player said. Is there a protocol such that only a finite number of players get it wrong ? (notice that it needs to be finite, not bounded).

Puzzle #0 is very easy and the answer is simply parity check. Player 0 could  simply declares y = x_1 \otimes\hdots \otimes x_n where \otimes stands for XOR. Now, player 1 can for example reconstruct x_1 by y \otimes x_2 \otimes \hdots \otimes x_n. Now, player 2 can do the same computation and figure out x_1. Now, he can calculate x_2 = y \otimes x_1 \otimes x_2 \otimes \hdots \otimes x_n and so on… When we move to an infinite number of players, however, we can’t do that anymore because taking the XOR of an infinite number of bits is not well defined. However, we can still can solve Puzzles #1 and #2 if we believe and are willing to accept the Axiom of Choice.

Axiom of Choice: Given a family of sets \{ S_i \}_{i \in I} there is a set \{x_i; i \in I\} such that x_i \in S_i, i.e. a set that takes a representative from each element in the family.

It is used, for example to show that there is no measure \mu : 2^{[0,1)} \rightarrow \mathbb{R} that is shift invariant (say under addition modulo 1) and \mu([0,1)) = 1. The proof goes the following way: define the following equivalence relation on [0,1): x \sim y if x - y \in \mathbb{Q}. Now, consider the family of all the equivalence classes and invoke the Axiom of Choice. Let K be the set obtained. Now, we can write the interval as a disjoint union:

[0,1) = \cup_{x \in \mathbb{Q}} (K+x)

where all operations are modulo 1 and K+x = \{y+x; y \in K\}. Since it is an enumerable union, if such a measure existed, then: \mu([0,1)) = \sum_{x \in \mathbb{Q}} \mu(K+x) = \sum_{x \in \mathbb{Q}} \mu(K) which is either 0 if \mu(K) = 0 or \infty if \mu(K) >0.

This is kinda surprising, but more surprising is how we can use the exact same technique to solve the puzzles: first, let’s solve Puzzle #2: let S be the set of all infinite \{0,1\}-strings and consider the equivalence relation on S such that x \sim y if the strings differ in a finite number of positions. Now, invoke the axiom of choice in the equivalence classes and let S_0 be the set of representatives. Now, if F is the set of all strings with finite number of 1‘s and \otimes the operation such that z = x \otimes z if z_i = x_i \otimes y_i. We can therefore write:

S = \cup_{x \in F} (S_o \otimes x)

Now, a protocol the players could use is to look ahead and since they are seeing an infinite number of bits, they can figure out which equivalence class from S/\sim they the entire string is. Now, they take y \in S_0 the representative of this class and guess y_i. Notice that y will differ from the real string by at most a finite number of bits.

Now, to solve puzzle #1, the player 0 simply looks at x = x_1 x_2 \hdots and figure out the equivalence class he is and let y \in S_0 be the representative of this class. Now, since x and y differ by a finite number of bits, he can simply calculate XOR of x and y (now, since it is a finite number of them, XOR is well defined) and announce it. With this trick, it just becomes like Puzzle #0.

Categories: puzzles, theory Tags:

Submodular Allocation Problem

April 6th, 2011 No comments

I am in Israel for the Algorithmic Game Theory Semester in the Center for the Study of Rationality. It is great to both explore Jerusalem and learn about games and algorithms. I think it is a great opportunity to start blogging again. To start, I decided to write about simple and beautiful algorithm by Lehman, Lehman and Nisan on the allocation problem when players have submodular valuations.

Consider a set of m items and n agents. Each agent has a monotone submodular v_i valuation over the items,  i.e., v_i:2^{[m]} \rightarrow \mathbb{R} s.t. v_i(S) + v_i(T) \geq v_i(S \cap T) + v_i(S \cup T) for any subsets S,T of [m] and f(S) \leq f(T) for S \subseteq T. Now, the goal is to partition the items in n sets S_1, \hdots, S_n in order to maximize \sum_i v_i(S_i).

This problem is clearly NP-hard (for example, we can reduce from Maximum Coverage or any similar problem), but is has a very simples Greedy Approximation. The approximation goes as follows: start with all sets being empty, i.e., start with S_i = \emptyset, \forall i then for each item j, find the player i with maximum v_i(j \vert S_i) = v_i(S_i \cup \{j\}) - v_i(S_i) and add j to this player. This is a 2-approximation algorithm. The proof is simple:

Let S_1, \hdots, S_n be the sets returned by the algorithm and O_1, \hdots, O_n the optimal solution. Let also S_i^{<j} = S_i \cap \{1, 2, \hdots, j-1\} and O_i^{<j} = O_i \cap \{1, 2, \hdots, j-1\}. We can write:

\sum_i v_i(S_i) = \sum_i \sum_{j \in S_i} v_i(j \vert S_i^{<j})

if we added j to set S_i it means that v_i(j \vert S_i^{<j}) \geq v_k(j \vert S_k^{<j}) by the Greedy rule. Therefore we can write:

\sum_i v_i(S_i) \geq \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j}) \geq \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j} \cup O_k^{<j})

where the first inequality follows from the Greedy rule and the second follows from submodularity. Now, we can simply write:

\begin{aligned} \sum_i v_i(S_i) & \geq \frac{1}{2} \sum_i \sum_{j \in S_i} v_i(j \vert S_i^{<j}) + \frac{1}{2} \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j} \cup O_k^{<j}) \\ & \geq \frac{1}{2} \sum_i \sum_{j \in S_i} v_i(j \vert S_i^{<j} \cup O_i^{<j}) + \frac{1}{2} \sum_k \sum_{j \in O_k} v_k(j \vert S_k^{<j} \cup O_k^{<j}) \\ & \geq \frac{1}{2} \sum_i \sum_{j \in S_i \cup O_i} v_i(j \vert S_i^{<j} \cup O_i^{<j}) \\ & = \frac{1}{2} \sum_i v_i(S_i \cup O_i) \geq \frac{1}{2} \sum_i v_i(O_i) \end{aligned}

An improved algorithm was given by Dobzinski and Shapira achieving an 1 -\frac{1}{e} approximation using demand queries – that are used as a separation oracle for a suitable linear program.

Categories: theory Tags: ,

Walrasian Equilibrium I

February 15th, 2010 No comments

Currently I’ve been trying to understand more about the dynamics of markets and basic concepts of microeconomic theory and, as always, writing a blog post will help me to keep my ideas clear. First, why are markets interesting from a computer scientist/mathematician point of view?

  • Markets are multi-objective optimization problems: one can think of the possible state of a market some point in a space of possible {x = (x_1, \hdots, x_N) \in \Omega}. Each player of the market controls one variable, say {x_i} and is interested in maximizing one objective function {f_i(x)}. So, player {i} is trying to set {x_i = \text{argmax}_{x_i} f_i(x_i, x_{-i})}.
  • Markets are a computational model: one can think of a market as a way of performing a certain computation – as extracting some kind of information, as a prediction market, stock exchanges, … If we think of it as a computational device, we are asking the same questions: given those preferences which are implicit functions to each of the agents, calculate “fair” prices of items.
  • Markets are distributed systems where each part of the system has a selfish interest.

A market is composed by a set {L} of commodities, {I} of consumers and {J} of producers. Now, we describe how to characterize each of them:

  • Each consumer is defined by a set {X_i \subseteq {\mathbb R}^L} of commodities combinations he is interested (typically we take {X_i = {\mathbb R}^L_+}) and an utility function {u_i : X_i \rightarrow {\mathbb R}} expressing his interest for this bundle of commodities. Consumer {i} will try to maximize {u_i(\cdot)} in a further restricted {X_i}.
  • Each producer is define by a set {Y_j \subset {\mathbb R}^L} it has the capacity to produce.
  • Endowments: Each consumer comes to the market with an initial endowment {\omega_i \in {\mathbb R}^L}, so for {j \in L}, {\omega_{ij}} is the amount of commodity {j} that consumer {i} originally has. The initial total endowment of the market is given by {\overline{\omega} = \sum_{i \in I} \omega_i}, which is a vector indicating how much of each commodity originally exists in the market.
  • Shares: consumers have shares in the companies, so for {i \in I}, {j \in J}, consumer {i} has {\theta_{ij}} shares of company {j}, such that {\sum_i \theta_{ij} = 1}.

Something very crucial is missing in this picture: a way to compare commodities and something that makes exchanges possible: the answer to that is to attribute prices to the items. How to attribute prices to the items so that the market works fine? A price vector is a vector {p \in {\mathbb R}^L_+}. Consider the following scenario after prices {p_\ell, \ell \in L} are established to commodities:

  • by producing {y_j \in Y_j}, company {j \in J} gets profit {p \cdot y_j}, so each company will try to maximize its profit producing {y_j^* \in \text{argmax}_{y_j \in Y_j} p \cdot y_j}.
  • each consumer sells its initial endowment and gets the profit respective to the companies he owns. So, consumer {i} gets {w_i = p \cdot \omega_i + \sum_{j \in J} \theta_{ij} p \cdot y_j^*}.
  • now consumer {i} uses the money he has to buy the best bundle he can afford, which is {x_i^* = \text{argmax} \{u_i(x_i); x_i \in X_i, p \cdot x_i \leq w_i\}}.

The amount of commodities in the market must conserve, so that is possible only if we get:

\displaystyle \sum_{i \in I} x_i^* = \sum_{i \in I} \omega_i + \sum_{j \in J} y_j^*

First, it is not clear if such a price vector exists. If it exists, is it unique? If this is an equilibrium, is it the best thing for the consumers? How those prices can be set in practice without a centralized authority? Can people lie? Below, let’s collect a couple of questions I’ll try to answer (yes, no or unknown) in this and the following posts.

Question 1: Does a price vector {p \geq 0} always exist that generates an equilibrium?

Question 2: If it exists, is it unique?

Question 3: Can we describe an efficent method to find {p} ?

Question 4: Is it the best thing for the consumers in the following sense: if {(x^*,y^*,p)} is an equilibrium, are there feasible {(x,y)} such that {u_i(x_i) \geq u_i(x_i^*)} and for at least one consumer {u_i(x_i) > u_i(x_i^*)}? (This is called Pareto improvement)

Question 5: A central authority could use the knowledge about functions {u_i} and endowments {\omega_i} to calculate the price vector {p} using some method. Can consumers {i} be better off by lieing about their utility and endowments?

Question 6: How prices get defined without a central authority? Is there a dynamic/game-theoretical model to that?

For simplicity, let’s think of Exchange Economies, which are economies with no producers. Let’s define it formally:

Definition 1 An exchange economy is composed by a set of commodities {L} and a set of consumers {I} each with an utility {u_i : X_i \rightarrow {\mathbb R}} and an initial endowment {\omega_i \in {\mathbb R}^L_+}.

Definition 2 A price vector {p \in {\mathbb R}^L_+} is a Walrasian equilibrium for an exchange economy {(L, I, \{X_i, u_i, \omega_i\}_{i \in I})} if there is {x_i^* \in X_i} such that:

  1. {x_i^*} s.t. {u_i(x_i^*) = \max \{u_i(x_i); x_i \in X_i, p \cdot x_i \leq p \cdot \omega_i\}}
  2. {\sum_i x_i^* \leq \sum_i \omega_i}
  3. {p \cdot (\sum_i x_i^* - \omega_i)= 0}

The first condition says that each consumer is maximizing his utility given his prices, the second says that we can’t buy more commodities than what is available in the market and the third, called Walras’ Law, says that if there is surplus of a certain product, it should have price zero. It is by far the most unnatural of those, but it can be easily justifiable in some circumnstances: suppose we say that utilities are non-satiated if for each {x_i \in X_i} and {\epsilon > 0}, there is {x'_i \in X_i}, {\Vert x_i - x'_i \Vert < \epsilon} such that {u_i(x'_i) > u_i(x_i)}. If {u_i} are differentiable, that would mean {\nabla u_i \neq 0}, for example a linear function {u_i(x_i) = \sum_\ell u_{i\ell} x_{i\ell}} with some {u_{i\ell} > 0}. In that case, {\sum_i (p \cdot x_i^* - p \cdot \omega_i) < 0} and some player has money surplus and therefore he could increase his utility.

Now, we define for each price vector {p} the excess demand function {z_i(p) = x_i(p) - \omega_i} and {z(p) = \sum_i z_i(p)}. Now, under non-satiated utilities, by the last argument, we have that {p} is an equilibrium vector iff {z(p) \leq 0}. Actually, if {u_i} are also strong monotone, i.e., {u_i(x_i + \xi) \geq u_i(x_i)} for each {\xi \geq 0}, then it becomes: {p} is an equilibrium iff {z(p) = 0}, which means that the market clears:

\displaystyle \sum_i x_i^* = \sum_i \omega_i

The question that is easier to answer is Question 4 and it is sometimes refered as the First Fundamental Theorem of Welfare Economics:

Theorem 3 Given non-satiated preferences, each equilibrium {(x,p)} is Pareto, i.e. there is no other feasible allocation {x'} such that for all {i}, {u_i(x'_i) \geq u_i(x_i)} with the inequality strict for at least one component.

Proof: Suppose there were, since {u_i(x'_i) \geq u_i(x_i)} then {p \cdot x'_i \geq p \cdot \omega_i}, because if {p \cdot x'_i < p \cdot \omega_i} then we could improve the utility of {x'_i} still within the budget, contradicting the optimality of {u_i(x_i)} for that budget. And clearly {u_i(x'_i) > u_i(x_i)} implies {p \cdot x'_i > p \cdot \omega_i}.

Summing over {i}, we get {\sum_i p x'_i > \sum_i p \omega_i}, what is a contradiction, because since {x'} is feasible, {\sum_i x'_i \leq \sum_i \omega_i} and therefore {\sum_i p \cdot x'_i \leq \sum_i p \cdot \omega_i}. \Box

Now, let’s tackle Question 1. We assume linearly of utility: {u_i(x_i) = \sum_{\ell \in L} u_{i \ell} x_{i \ell}} for {u_{i \ell} > 0}. This gives us strong monotonicity and local nonsatiated preferences.

Theorem 4 Under linear utilities, there is always an equilibrium price vector {p}.

Consider the function {z} defined above: {z(p) = \sum_i (x_i(p) - \omega_i)} where {x_i(p)} is the bundle of best possible utility. Now, since we are using linear utilities we can’t guarantee there will be only one such bundle, so instead of considering a function, consider {x_i} and {z} as being correspondences: {x_i, z: {\mathbb R}^L_+ \rightarrow \mathcal{P}({\mathbb R}^L)}, i.e., {x_i(p) \subseteq {\mathbb R}^L_+} is the set of all allocations that maximize {u_i(x_i)} subject to {p\cdot x_i \leq p \cdot \omega_i}. Since {u_i} are linear functionals, we can calculate {x_i(p)} by a Fractional Knapsack algorithm: we sort commodities {\ell \in L} by {\frac{p_\ell}{u_{i\ell}}} and start buying in the cost-benefit order (the ones that provide more utility per buck spent). Most of the time there will be just one solution, but in points where {\frac{p_\ell}{u_{i\ell}} = \frac{p_k}{u_{i k}}}, then {x_i(p)} might be a convex region. This correpondence is upper hemicontinuous, which is the correspondence analogue to continuity for functions. As Wikipedia defines:

Definition 5 A correspondence {\Gamma : A \rightarrow B} is said to be upper hemicontinuous at the point {a \in A} if for any open neighbourhood {V} of {\Gamma(a)} there exists a neighbourhood {U} of a such that {\Gamma(x)} is a subset of {V} for all {x} in {U}.

It is not hard to see that {z} is upper hemicontinuous according to that definition. Our goal is to prove that there is one price vector {p} for which {\overline{\omega} \in x_i(p)} or: {0 \in z(p)}. To prove that we use Kakutani’s Fixed Point Theorem. Before we go into that, we’ll explore some other properties of {z}:

  • 0-Homogeneous: {z(\alpha p) = z(p), \forall \alpha > 0}
  • Walras’ Law: {p \cdot z(p) = 0}. For any {\sum_i (x_i - \omega_i) \in z(p)} we know {\sum_i (p \cdot x_i - p \cdot \omega_i) \leq 0} by the definition of {x_i}. So, if it not zero, some {i} has money surplus what is absurd given that preferences are strongly monotone.
  • Bounded: {z(p)} is bounded from below, i.e., {z_\ell(p) \geq -s, \forall p, \ell} for some {s > 0}. Simply take {s = \max \omega_i}
  • Boundary behavior: if {p^k \rightarrow p \neq 0} with {p_\ell = 0}, then {z_\ell(p^k) \rightarrow \infty}. That is clear from the fractional knapsack algorithm when one desirable item gets price zero.

Now, we are in shape for applying Kakutani’s Fixed Point Theorem:

Theorem 6 (Kakutani, 1941) If {f:A \rightarrow \mathcal{P}(A)} is an upper hemicontinuous correspondence such that {f(a)} is a convex non-empty set for all {a \in A} then {f} has a fixed point, i.e., {\exists x \in A} s.t. {x \in f(x)}.

Since prices are {0}-homogeneous, consider the simplex {\Delta = \{p \geq 0; \sum_\ell p_\ell = 1\}}, its relative interior {\Delta^0 = \{p > 0; \sum_\ell p_\ell = 1\}} and the boundary {\partial \Delta = \Delta \setminus \Delta^0}. Now we define the following price correcting correspondence {f:\Delta \rightarrow \mathcal{P}(\Delta)}.

If some price {p \in \Delta^0} is set, it generates demand {d \in z(p)}. For that demand, the price that would maximize profit would be {q}, i.e. {q\cdot d \geq q' \cdot d} for all {q' \in \Delta}. It is natural to re-adjust the prices to {q}. So we define for {p \in \Delta^0}:

\displaystyle f(p) = \{q \in \Delta; q \text{ is a best response price to some } d \in z(p)\}

and for {p \in \partial \Delta}:

\displaystyle f(p) = \{q \in \Delta; q \cdot p = 0\}

Now, I claim that this correspondence satisfies the conditions in Kakutani’s Theorem. We skip a formal proof of this fact, but this is intuitive for the interior {\Delta^0} – let’s give the intuition why this is true as we approach the boundary: if {\Delta^0 \ni p^k \rightarrow p \in \partial \Delta}, then {p^k_\ell \rightarrow 0}, therefore the demans explodes: {z_\ell(p^k) \rightarrow \infty} and as a result the best thing to do is to set the prices of those commodities much higher than the rest. Therefore, the price of the commodities whose demand explode are positive while the prices of the commodities where the price doesn’t get value zero.

Now, after waiving our hands about the upper continuity of {f}, we have by Kakutani’s Theorem a point {p \in \Delta} such that {p \in f(p)}. By the definition of {f} we must have {p \in \Delta^0} (because for {p \in \partial \Delta}, {p \notin f(p)}. Now, I claim {z(p) = 0}. In fact if {z(p) \neq 0}, still {p z(p) = 0} by Walras’ Law. So, if {z(p) \neq 0} then there is {\ell} with {z_\ell (p) < 0} and therefore {q_\ell = 0} for all {q \in f(p)}, and {f(p) \subseteq \partial \Delta}. For this reason {z(p) = 0}.

In the next blog post (or serie of blog posts, let’s see) we discuss issues related to the other questions: uniqueness, dynamics, game-theoretical considerations, …

Categories: theory Tags: , , ,