# Proving that Every preference relation can be represented by utility function

Im looking the prove the following:

every preference relation ⪰ over finite/countable set X can be represented as a utility function u such that x1 ⪰ x2 <=> u(x1) ≥ u(x2)

At the first direction: x1 ⪰ x2 => u(x1) ≥ u(x2), i just built a utility function u that is defined to be:
u(xi) = |set of all xj such that xi ⪰ xj |

the function is well defined since set X is countable, and therefore there is a finite number of options (xj) that are less than xi.

Im struggling with proving the other direction... And so i hope that you can help me with that :)

• Hi! What exactly do you mean by "the other direction"? Seems like you have to prove that a $u$ representing $\succeq$ exists. You constructed a function $u$. Does it represent $\succeq$ or not? Commented Mar 7, 2022 at 17:31
• Well Im pretty much confused because i searched a lot on the web and yet everything I found is a prove to what you just wrote. Im trying to figure out if its the same as what Im trying to prove. Also, by "the other direction" - i mean to prove that from a function "u" i can create a preference relation i guess? im not quite certain, as im very confused by what is meant to be proven here... Commented Mar 7, 2022 at 17:55
• The set in your definition of the utility function need not be finite, it can be countably infinite. Commented Mar 7, 2022 at 18:14
• I didnt quite understand, if the set would be countably infinite, then the function might never return a value Commented Mar 7, 2022 at 18:17
• @StrugglingResearcher Exactly, or a value of $\infty$, which is not a real number. The usual trick is to use a weighted sum like $u(x_i)=\sum_{j:x_j\preceq x_i} 1/2^i$. Commented Mar 7, 2022 at 22:07

The following is a nice proof from Osborne and Rubinstein's Models in Microeconomic Theory. We want to prove that

Every preference relation on a finite set can be represented by a utility function.

Let $$X$$ be a finite non-empty set and let $$\succeq$$ be a preference relation on $$X$$. Next, let $$Y_0 = X$$ and let $$M_1$$ be the set of alternatives minimal with respect to $$\succeq$$ in $$Y_0$$, which is non-empty since it can be shown that any finite non-empty set admits at least one maximal and at least one minimal element with respect to a preference relation.

Next, for $$k \geq 1$$, define $$Y_k = Y_{k - 1} \setminus M_k$$ as long as $$Y_{k - 1}$$ is non-empty. As before, $$M_k$$ is the set of alternatives minimal with respect to $$\succeq$$ on $$Y_{k - 1}$$, and is non-empty as long as the latter is also non-empty.

Since by assumption $$X$$ is finite, there exists $$K \in \mathbb{N}$$ such that $$Y_K$$ is empty (while $$Y_{K - 1}$$ is non-empty). This means that every $$x \in X$$ is an element of $$M_k$$ for some $$k = 1, 2,\dots, K$$. Now define $$u : X \to \mathbb{R}$$ given by $$u(x) = k$$ for all $$x \in M_k$$ for some $$k = 1, 2,\dots, K$$. We claim that $$u$$ is a utility function for $$\succeq$$, i.e. for any alternatives $$a$$ and $$b$$ we have $$a \succeq b$$ if and only if $$u(a) \geq u(b)$$. To see that, note that $$u(a) = u(b)$$ if and only if $$a$$ and $$b$$ are both minimal with respect to $$\succeq$$ in $$Y_{u(a) - 1}$$, i.e. $$a \succeq b$$ and $$b \succeq a$$, so $$a \sim b$$.

Also, we have $$u(b) > u(a)$$ if and only if $$a$$ is minimal with respect to $$\succeq$$ in $$Y_{u(a) - 1}$$ but $$b$$ is not, hence $$b \succeq a$$ but $$a \nsucceq b$$ and so $$b \succ a$$. $$\square$$

Hope this helps.

Let $$X=\{x_1,\dots, x_n\}$$, we will use induction on size of $$X$$ to prove that utility representation exists.

Base step $$(|X|=1)$$:
In the base step $$X=\{x_1\}$$ and so utility representation exists trivially

Inductive Hypothesis $$(|X|=n-1)$$:
Suppose there exists a utility representation $$u': \{x_1, \dots, x_{n-1} \to \mathbb R\}$$

Inductive step:
We need to show that there exists a utility representation for $$\succeq$$ when $$|X|=n$$. We do this by exhausting all the possible cases.

1. Case 1: $$\exists x_j \in \{x_1, \dots, x_{n-1}\}$$ such that $$x_n \sim x_j$$.
Then we can define $$u: \{x_1, \dots, x_n\} \to \mathbb R$$ as: $$\forall x_i \in X, \quad u(x_i)=\begin{cases} u'(x_i) & \text{ if }x_i\neq x_n\\ u'(x_j) & \text{ if }x_i=x_n \end{cases}$$

2. Case 2: $$x_n \succ x_j, \forall x_j \in \{x_1, \dots, x_{n-1}\}$$. Then we can define $$u: \{x_1, \dots, x_n\} \to \mathbb R$$ as: $$\forall x_i\in X, \quad u(x_i)=\begin{cases} u'(x_i) & \text{ if }x_i\neq x_n \\ \displaystyle \max_{x_j \in \{x_1, \dots, x_{n-1}\}} u'(x_j)+1 & \text{ if }x_i=x_n \end{cases}$$

3. Case 3: $$x_j \succ x_n, \forall x_j \in \{x_1, \dots, x_{n-1}\}$$. Then we can define $$u: \{x_1, \dots, x_n\} \to \mathbb R$$ as: $$\forall x_i \in X, \quad u(x_i)=\begin{cases} u'(x_i) & \text{if }x_i\neq x_n \\ \displaystyle \min_{x_j \in \{x_1, \dots, x_{n-1}\}} u'(x_j)-1 & \text{if }x_i=x_n \end{cases}$$

4. Case 4: $$\exists x_j, x_k \in \{x_1, \dots, x_{n-1}\}$$ such that $$x_j \succ x_n \succ x_k$$

Let $$\alpha = \min\{u'(x_i): x_i \succ x_n\}$$ and $$\beta=\max\{u'(x_i): x_n \succ x_i\}$$. Then we can define $$u: \{x_1, \dots, x_n\} \to \mathbb R$$ as: $$u(x_i)=\begin{cases} u'(x_i) & \text{if }x_i\neq x_n \\ \frac{\alpha+\beta}{2} &\text{if } x_i=x_n \end{cases}$$

We have shown the existence of utility representation in each case. To finish the proof, we need to show that $$u: \{x_1, \dots, x_n\} \to \mathbb R$$ represents $$\succeq$$ on $$X$$, that is, show that for any $$x, y \in X, \quad x \succeq y \iff u(x) \geq u(y)$$.

The usefulness of this proof lies in the fact that it can be extended to the case where $$X$$ is countably infinite. Note that I do not take credit for the proof; This proof was shown to me by Professor Arunava Sen.