1
$\begingroup$

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 :)

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Giskard
    Commented Mar 7, 2022 at 17:31
  • $\begingroup$ 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... $\endgroup$ Commented Mar 7, 2022 at 17:55
  • 1
    $\begingroup$ The set in your definition of the utility function need not be finite, it can be countably infinite. $\endgroup$ Commented Mar 7, 2022 at 18:14
  • $\begingroup$ I didnt quite understand, if the set would be countably infinite, then the function might never return a value $\endgroup$ Commented Mar 7, 2022 at 18:17
  • 1
    $\begingroup$ @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$. $\endgroup$ Commented Mar 7, 2022 at 22:07

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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