Past exam of the MSc in advanced computer science course of the University of Oxford / 2023 / Computational game theory / 1

Under the expected utility hypothesis, use positive affine uniqueness of affine preference representations to normalize the extreme outcomes to $u({\omega }_1)=1$ and $u({\omega }_4)=0$. The stated indifference relations then giveThe two lotteries have expected utilitiesHence ${\ell }_2\succ {\ell }_1$, with normalized expected utility difference $3/100$. Equivalently, substitution reduces them to lotteries with probabilities $0.45$ and $0.48$ of the better extreme outcome. The inference uses the independence axiom for lottery preferences; the three displayed outcome comparisons alone would not determine preferences over all compound lotteries without the expected utility hypothesis.

Yes: the stated order has an expected utility representation. For outcomes whose monetary amounts are $1,2,4$, respectively, chooseThenSince $12/5>9/5>3/2>4/5$, this utility function gives exactly the required strict preferences.

The distinction is that the expected utility hypothesis does not by itself require the utility function to increase with monetary amount. This nonmonotone monetary utility ranks the outcome paying 2 below the outcome paying 1. If increasing monetary utility were imposed as an additional assumption, the stated order would fail: ${\ell }_3\succ {\ell }_4$ requires $u(1)>u(2)$ becauseThat additional monotonicity assumption is not printed in this part.

For the intended finite representation, put $m=|S|<\infty$. For each $T\subseteq S$, form the mintermA Boolean valuation satisfies ${\chi }_T$ exactly when its selected subset is $T$. Therefore the weighted formula utility representationrepresents $u$ exactly: at the Boolean valuation for $T$, only that minterm contributes, with weight $u(T)$. This proves completeness and the bound of $2^{|S|}$ rules simultaneously. Zero-weight rules may be omitted. The bound counts rules; writing each minterm also requires $O(m)$ symbols in Big O notation.

For the computational question, assume rule weights are rational numbers encoded in binary. This makes exact equality of sums a finite computational task. With this conventional encoding, equivalence of weighted formula utility representations is co-NP-complete.

For membership, the complement has a short witness: a Boolean valuation on the variables occurring in either rule base. Evaluate each propositional formula, sum the weights of satisfied rules, and accept the witness if the sums differ. Propositional formula evaluation takes polynomial time. Exact sums of binary rational numbers also have polynomially bounded bit lengths: the product of their denominators has bit length at most the sum of the input denominator lengths. Thus non-equivalence lies in NP, and equivalence lies in co-NP.

For hardness, take a Boolean satisfiability problem instance $\theta$ and constructThe first utility function is one at satisfying Boolean valuations and zero elsewhere, while the second is always zero. ConsequentlyThe unsatisfiable Boolean formula problem is co-NP-complete, as the complement of the NP-complete Boolean satisfiability problem. The construction is a polynomial-time reduction, proving hardness even with the single weight $1$.

Two qualifications matter in the literal wording. First, unrestricted real weights have no specified finite encoding, so a standard bit-complexity classification needs the encoding assumption above. Second, the problem says only that $S$ is nonempty. If infinite $S$ is allowed while rule bases remain finite, its completeness claim is false. For $S=\mathbb{N}$, take $u(T)=1$ when $T$ is infinite and $u(T)=0$ when $T$ is finite. A finite rule base mentions only a finite subset $F$ of the variables. The Boolean valuations for $\varnothing$ and $\mathbb{N}\setminus F$ agree on all those variables but have different required values. No such rule base represents this $u$. Thus the construction answers the intended finite-set question and identifies the missing hypothesis in the unrestricted statement.