Game Theory without Argmax [Part 1]

[-]rotatingpaguro2y90

Context-independence
We'll say that a consequentialist optimiser is context-independent if $Image (u) = Image (u^{'}) ⟹ ψ (u) = ψ (u^{'})$ .
Context-independence is a stronger condition than consequentialism — this condition says that, once we know which payoffs are achievable in the agent's task, then the only thing relevant to the optimality of a particular option is its payoff. For example, ${argmax}_{X}$ is context-independent, but ${better-than-average}_{π}$ is not.

Context-independence	We'll say that a consequentialist optimiser is context-independent if $Image (u) = Image (u^{'}) ⟹ ψ (u) = ψ (u^{'})$ . Context-independence is a stronger condition than consequentialism — this condition says that, once we know which payoffs are achievable in the agent's task, then the only thing relevant to the optimality of a particular option is its payoff. For example, ${argmax}_{X}$ is context-independent, but ${better-than-average}_{π}$ is not.

${a r g m a x}_{X}$ is not context-independent according to the given definition.

Consider tasks $u, u^{'} : {0, 1} \to {0, 1}$ , with $u (x) = x$ and $u^{'} (x) = 1 - x$ . Then $a r g m a x u = {1} \neq a r g m a x u^{'} = {0}$ , despite $Image u = Image u^{'}$ .

I guess the correct definition says $q (u) = q (u^{'})$ instead of $ψ (u) = ψ (u^{'})$ .

[-]Cleo Nardo2y30

Thanks v much! Can't believe this sneaked through.

[-]Alexander Gietelink Oldenziel2y86

Wow! Happy to see this exposition. I've been a fan of this framework for a while now. Happy to see it is finally percolating to the alignment community!

[-]Simon Fischer2y42

Typo: This should be ${argmax}_{R} (sin) = {2 π k + \frac{π}{2} | k \in Z}$ .

[-]Gurkenglas2y40

The power set part seems sus. Have you considered something more continuous?

[-]Cleo Nardo2y111

Yes!

In a subsequent post, everything will be internalised to an arbitrary category with enough structure to define everything. The words set and function will be replaced by object and morphism. When we do this, $P$ will be replaced by an arbitrary commutative monad $M$ .

In particular, we can internalise everything to the category Top. That is, we assume the option space $X$ and the payoff $R$ are equipped with topologies, and the tasks will be continuous functions $u : X \to R$ , and optimisers will be continuous functions $u : (X \to R) \to M (X)$ where $(X \to R)$ is the function space equipped with pointwise topology, and $M$ is a monad on Top.

In the literature, everything is done with galaxy-brained category theory, but I decided to postpone that in the sequence for pedagogical reasons.

[-]Noosphere891y20

(2) Moral antirealism.
The subjective account (again, read too literally) suggests that values are out there in the world, that the environment contains entities called utilities which all rational agents seek, that all conflict is disagreement, that correctness is a property of pebble heaps, that microeconomics is normative, and (most concerning of all) that the primary obstacle to building a safe superintelligence is writing down a utility function.
The objective account, I think, is more moral antirealist. It says, "The world contains only paperclips and happy humans, never utilities! The world contains only paperclip-maximisers and happy-human-maximisers, never utility-maximisers!"

Re the issue of the subjective account causing us to focus too much on moral realism and the idea that values are out there in the world, a few responses.

Moral Realism's problem is not exactly that there is no correct morality, but rather that there are far too many correct answers, such that you can pick and choose which morality you will follow, so there's no constraint on the agent's values unless provided by another source.
In one sense, values are out there in the world, since they are in the computer/brain, which is part of the world, whether they be computed by utility/reward functions or something else.
Utility is a variable like the number n is a variable, so we can always say that paperclips and happy humans are concrete instantiations of a utility, similar to how 47 is a concrete number, while the abstract concept of a number is n, which represents an arbitrary number.

Thus, whenever we say that something is a utility maximizer, we don't say about specific utility they are maximizing, but we can concretize the utility function by say that they are a paperclip maximizer, and say much more about that.

I do think there's too much focus on utility functions as a general class, but that's due to practical concerns like it being hard to prove what it's going to do, and people often assume on LW that their results go further than they do without naming what specific utility function it is maximizing.

[-]Antoine de Scorraille2y*20

Exercise 1:

The empty set is the only one. For any nonempty set X, you could pick as a counterexample: $a r g m a x_{X} (z e r o_{X}) = X$

Exercise 2:

The agent will choose an option which scores better than the threshold $α$ .

It's a generalization of satisficers, these latter are thresholders such as $u^{- 1} (α)$ is nonempty.

Exercise 3:

$m a j o r i t y_{X} = λ^{u : X \to R} . {x \in X | \forall x^{'} \in X, C a r d (u^{- 1} ({u (x)})) \geq C a r d (u^{- 1} ({u (x^{'})}))}$

Exercise 4:

I have discovered a truly marvelous-but-infinite solution of this, which this finite comment is too narrow to contain.

Exercise 5:

The generalisable optimisers are the following:

$a r g m i n_{X} = λ^{u : X \to R} . {x \in X | \forall x^{'} \in X, u (x) \leq u (x^{'}) ⟹ u (x^{'}) \leq u (x)}$

i.e. argmin will choose the minimal points.

$s a t i s f i c e_{s} = λ^{u : X \to R} . {x \in X | u (x) \geq u (s)}$

i.e. satisfice will choose an option $x \in X$ which dominates some fixed anchor point $s \in X$ . Note that since R is only equipped with a preorder, it means it might be a more selective optimiser (if not total, it's harder to get an option better then the anchor). More interestingly, if there are indifferent options with the anchor (some x / $x \geq s$ and $s \geq x$ ), it could choose it rather than the anchor even if there is no gain to do so. This degree of freedom could be eventually not desirable.

$r o c k_{S} = λ^{u : X \to R} . S$

$s a t i s f i c e_{S} = λ^{u : X \to R} . {x \in X | \forall s \in S, u (x) \geq u (s)}$

$m a j o r i t y_{X} = λ^{u : X \to R} . {x \in X | \forall x^{'} \in X, C a r d (u^{- 1} ({u (x)})) \geq C a r d (u^{- 1} ({u (x^{'})}))}$

Exercise 6:

Interesting problem.

First of all, is there a way to generalize the trick?

The first idea would be to try to find some equivalent to the destested element $⊥$ . For context-dependant optimiser such as better-than-average, there isn't.

A more general way to try to generalize the trick would be the following question:

For some fixed $ψ$ , $X_{l e g a l}$ and $u : X \to R$ , could we find some other $u^{'} : X \to R$ such as $ψ (u^{'}) = ψ (u)$ and $\forall x \in X_{l e g a l}, u^{'} (x) = u (x)$

i.e. is there a general way to replace values outside of $X_{l e g a l}$ without modify the result of the constrained optimisation?

Answer: no. Counter-example: The optimiser $m a j o r i t y_{X}$ for some infinite set X and finite nonempty sets $X_{l e g a l}$ and R.

So it seems there is no general trick here. But why bother? We should refocus on what we mean by constrained optimisation in general, and it has nothing to do with looking for some u'. What we mean is value outside $X_{l e g a l}$ are totally irrelevant.

How? For any of the current example we have here, what we actually want is not $ψ_{X} (u^{'})$ , but $ψ_{X_{l e g a l}} (u |_{X_{l e g a l}})$ : we only apply the optimiser on the legal set.

Problem: in the current formalism, an optimiser has type $(X \to R) \to X$ , so I don't see obvious way to define the "same" optimiser on a different X. $a r g m a x_{X}$ and the others here are implicitly parametrized, so it's not that a problem, but we have to specify this. This suggests to look for categories (e.g. $S e t$ for argmax...).

[-]rotatingpaguro2y10

I'd like to read your solution to exercise 6, could you add math formatting? I have a hard time reading latex code directly.

You can do that with the visual editor mode by selecting the math and using the contextual menu that appears automatically, or with $ in the Markdown editor.

There are $ in your comment, so I guess you inadvertently typed in visual mode using the Markdown syntax.

[-]Antoine de Scorraille2y20

It's fixed ;)

[-]Rubi J. Hudson2yΩ120

I think this part uses an unfair comparison:

Supposes that and $W^{+} = {w_{1}, \dots, w_{m}}$ are small finite sets. A task $f : X \to W^{+}$ can be implemented as dictionary whose keys lie in $X$ and whose values lie in $W^{+}$ , which uses $n log m$ bits. The functional $ψ : J^{P} (X, W^{+})$ can be implemented as a program which receives input of type $D i c t [X, W]$ and returns output of type $L i s t [X]$ . Easy!
In the subjective account, by contrast, the task $f : X \to R$ requires infinite bits to specify, and the functional $ψ : J^{P} (X, R)$ must somehow accept a representation of an arbitrary function $f : X \to R$ . Oh no! This is especially troubling for embedded agency, where the agent's decision theory must run on a physical substrate.

If X and W+ are small finite sets, then any behavior can be described with a utility function requiring only a finite number of bits to specify. You only need to use R as the domain when W+ is infinite, such as when outcomes are continuous, in which case the dictionaries require infinite bits to specify too.

I think this is representative of an unease I have with the framing of this sequence. It seems to be saying that the more general formulation allows for agents that behave in ways that utility maximizers cannot, but most of these behaviors exist for maximizers of certain utility functions. I'm still waiting for the punchline of what AI safety relevant aspect requires higher order game theory rather than just maximizing agents, particularly if you allow for informational constraints.

[-]Lorxus1y10

Likewise, higher-order game theory promises a normalisation of game theory.
I don't know why, but this smells correct to me.

I have the same intuition - I agree that this smells correct. I suspect that the answer has something to do with the thing where when you take measurements (for whatever that should mean) of a system, what that actually looks like is some spectactularly non-injective map from [systems of interest in the same grouping as the system we're looking at] to , which inevitably destroys some information, by noninjectivity.

So I agree that it smells right, to quantify over the actual objects of interest and then maybe you apply information-destroying maps that take you outside spacetime (into math) rather than applying your quantifiers outside of spacetime after you've already applied your map and then crossing your fingers that the map is as regular/well-behaved as it needs to be.

[-]rotatingpaguro2y10

infinatary

I can't find this term anywhere else, and "infinitary" means something else so I think it's not a typo, is it your own neologism? If not, where is it from?

[-]Cleo Nardo2y30

[-]rotatingpaguro2y10

Ah guess it's a typo then, and your use is a nonstandard one.

[-]rotatingpaguro2y10

Exercise 6:

I repeat the construction using each element of in turn in place of $⊥$ .

For each such $u^{'}$ , $ψ (u^{'})$ spits out a set. I pick the $u^{'}$ producing the set which is closer to $X_{l e g a l}$ .

For finite sets, I could look at the size of the intersection; more in general I'll need some metric on $P (X)$ to say what it means to be close to $X_{l e g a l}$ .

Does that make sense?

[-]Antoine de Scorraille2y*20

Even with finite sets, it doesn't work because the idea to look for "closest to " is not what we looking for.

Let $X = {A l i c e; B o b; C h a r l i e}$ a class of students, scoring within a range $R = {0; 1; 2; 3; 4; 5}$ , $u : X \to R$ . Let $ψ$ the (uniform) better-than-average optimizer, standing for the professor picking any student who scores better than the mean.

Let $X_{l e g a l} = {A l i c e; B o b}$ (the professor $ψ$ despises Charlie and ignores him totally).

If u(Alice) = 5 and u(Bob) = 4, their average is 4.5 so only Alice should be picked by the constrained optimisation.

Howewer, with your proposal, you run into trouble with u' defined as u'(Alice) = u(Alice), u'(Bob) = u(Bob), and u'(Charlie) = 0.

The average value for this u' is $(5 + 4 + 0) / 3 = 3$ , and both Alice and Bob scores better than 3: $ψ (u^{'}) = {A l i c e; B o b} = X_{l e g a l}$ . The size of the intersection with $X_{l e g a l}$ is then maximal, so your proposal suggests to pick this set as the result. But the actual result should be ${A l i c e}$ , because the score of Charlie is irrelevant to constrained optimisation.

[-]rotatingpaguro2y10

Ok, take 2.

If I understand correctly, what you want must be more like "restrict the domain of the task before plugging it into the optimiser," and less like "restrict the output of the optimiser."

I don't know how to do that agnostically, however, because optimisers in general have the domain of the task baked in. Indeed the expression for a class of optimisers is , with $X$ in it.

Considering better-than-average optimisers from your example, they are a class with a natural notion of "domain of the task" to tweak, so I can naturally map any initial optimiser to a new one with a restricted task domain: $J^{P} (X, R) \to J^{P} (X_{legal}, R)$ , by taking the mean over $X_{legal}$ .

But given a otherwise unspecified $ψ \in J^{P} (X, R)$ , I don't see a natural way to define a $ψ^{'} \in J^{P} (X_{legal}, R)$ .

Assuming there's no more elegant answer than filtering for that ( $ψ^{'} (u) = ψ (u) \cap X_{legal}$ ), then the question must be: is there another minimally restrictive class of optimisers with such a natural notion, which is not the one with the "detested element" $⊥$ already proposed by the OP?

Try 1: consequentialist optimisers, plus the assumption $u (X_{legal}) = u (X)$ , i.e., the legal moves do not restrict the possible payoffs. Then, since the optimiser picks actions only through $u^{- 1} (r)$ , for each r I can delete illegal actions from the preimage, without creating new broken outputs. However, this turns out to be just filtering, so it's not an interesting case.

Try 2: the minimal distill of try 1 is that the output either is empty or contains legal moves already, and then I filter, so yeah not an interesting idea.

Try 3: invariance under permutation of something? A task invariant under permutation of $x$ is just a constant task. An optimiser "invariant under permutation of $X$ " does not even mean something.

Try 4: consider a generic map $X \to J^{P} (X, R)$ . This does not say anything, it's the baseline.

Try 5: analyse the structure of a specific example. The better-than-average class of optimisers is $ψ (u : X \to R) = {x : u (x) \geq \sum_{r \in R} r / | R |}$ . It is consequentialist and context-independent. I can't see how to generalize something mesospecific here.

Time out.

How many options are optimal for the task?	Example
Typically there'll be a unique optimal option.	${argmax}_{C} (λ^{z \in C} (1 - \| z \|^{2})) = {0}$
Perhaps multiple options will be optimal.	${argmax}_{R} (sin) = {2 π k + \frac{π}{2} \| k \in Z}$
Perhaps no options are optimal, i.e. every option is strictly dominated by another.	${argmax}_{R} (exp) = \emptyset$
Perhaps every option is optimal, i.e. the task is a constant function.	${argmax}_{Z} (λ^{k \in Z} . sin (π \cdot k)) = Z$

$ψ : (X \to R) \to P (X)$	Remarks
$argmin =$ $λ^{u : X \to R} . {x \in X \| \forall x^{'} \in X, u (x) \leq u (x^{'})}$	This agent will choose an option $x \in X$ which minimises $u$ . In classical game theory, this type of optimiser is typically used to model the adversary to the agent modelled by $argmax$ .
${satisfice}_{s} =$ $λ^{u : X \to R} . {x \in X \| u (x) \geq u (s)}$	This agent will choose an option $x \in X$ which dominates some fixed option $s \in X$ . The option $s$ is called the anchor point. It might represent the "default" option, or the "do nothing" option, or the "human-approved" option. According to Herbert Simon, satisficing is an accurate model of human and institutional decision-making. Utility-satisficers are a kind of mild optimiser, which might be a safer way to build AI than a full-blown utility-maximiser.
$argmax- ϵ -slack =$ $λ^{u : X \to R} . {x \in X \| \forall x^{'} \in X, u (x) + ϵ \geq u (x^{'})}$	This agent will chooses an option $x \in X$ which maximises the function $u$ up to some fixed slack $ϵ > 0$ . Such agents behave like $argmax$ except that their utility $u (x) \in R$ is measured with finite precision.
$better-than-average =$ $λ^{u : X \to R} . {x \in X \| u (x) \geq E_{x^{'} \sim π} u (x^{'})}$	This agent will choose an option $x \in X$ which scores better than the average option, given that the option space is equipped with a distribution $π \in Δ (X)$ .
${rock}_{S} = λ^{u : X \to R} . S$	This agent will choose an option in a fixed subset $S \subseteq X$ , regardless of the task, e.g. DefectBot and CooperateBot.^[7] Using ${rock}_{S}$ , we can model a non-agents as a special (degenerate) case of agents.
${quant}_{ϵ} =$ $λ^{u : X \to R} . {x \in X : P_{x^{'} \sim π} [u (x^{'}) \geq u (x)] \leq ϵ}$	This agent will choose an option $x \in X$ in the top $ϵ$ quantile, given that the option space is equipped with a distribution $π \in Δ (X)$ . This is the possibilistic version of Jessica Taylor's quantiliser. Her original probabilistic version is a function $(X \to R) \to Δ X$ , and so wouldn't count as an optimiser according to Definition 2.^[8]
${satisfice}_{S} =$ $λ^{u : X \to R} . {x \in X \| \forall s \in S, u (s) \leq u (x)}$	This agent will choose an option $x \in X$ which dominates every anchor point in $S \subseteq X$ . As special cases, when $S = X$ we get ${argmax}_{X}$ , and when $S$ is a singleton set we get Simon's satisficer mentioned before. When the set of anchor points is smaller, then the resulting optimiser is less selective, i.e. more options will be optimal.
${thresh}_{α} = λ^{u : X \to R} . {x \in X \| u (x) \geq α}$	Exercise 2
Exercise 3	This agent will choose an option in the largest equivalence class, where two options are equivalent if they result in the same payoff.

Payoff space	Remarks
$R = [0, 1]$	An optimiser $ψ \in J^{P} (X, [0, 1])$ only needs to be well-defined for bounded utility functions $u : X \to [0, 1]$ .
$R = N$	An optimiser $ψ \in J^{P} (X, N)$ only needs to be well-defined for utility functions $u : X \to N$ .
$R = R \cup {- \infty, + \infty}$	An optimiser $ψ \in J^{P} (X, R \cup {- \infty, + \infty})$ must be well-defined for infinatary utility functions $u : X \to R \cup {- \infty, + \infty}$ . For example, $u (x)$ might be the expected total winnings of a gambler employing the gambling strategy $x \in X$ . The gambler themselves are modelled by an optimiser $ψ : (X \to R \cup {- \infty, + \infty}) \to P (X)$ . This functional $ψ$ is characterised by its attitude towards infinite expected profit/loss.
$R = Δ (R)$ , where $Δ$ is the distribution monad on $Set$ .	An optimiser $ψ \in J^{P} (X, Δ R)$ will choose options given a stochastic task $u : Γ \to Δ R$ . This is the type-signature of risk-averse and risk-seeking maximisers studied in behavioural microeconomics. The field of Portfolio Theory is (largely) the comparison of rival optimisers in $J^{P} (X, Δ R)$ .
$R$ is the Levi-Civita Field, an extension of the reals with infinitesimals.	The Levi-Civita field contains infinitesimals like $ϵ, ϵ^{2}, 2 ϵ + ϵ^{2}, \sqrt{ϵ}$ , as well as infinite values like $ϵ^{- 1}, ϵ^{- 2}, ϵ^{1 / 3} + ϵ^{- 1 / 3} + 2$ . In infinite ethics, we encounter tasks $u : X \to Levi-Civita Field$ , and we can model the infinitary ethicist by an optimiser $ψ \in J^{P} (X, Levi-Civita Field)$ . Exercise 4: Solve infinite ethics.
$R = R^{n}$	An optimiser $ψ \in J^{P} (X, R^{n})$ can model different multi-objective optimisers. For example, there's an optimiser which, given multi-objective task $u : X \to R^{n}$ , returns those options which are maximal according to the lexicographic ordering, and there's another optimiser which uses the product ordering instead.^[10] Later in this post, we'll encounter an optimiser in $J^{P} (X_{1} \times \dots \times X_{n}, R)$ which returns the nash equilibria of $n$ -player games, where a task for this optimiser is an $n$ -by- $n$ payoff matrix $u : X_{1} \times \dots \times X_{n} \to R$ . The field of cooperative bargaining is concerned with different optimisers $J^{P} (X + 1, R^{n})$ . A bargaining task $f : (X + 1) \to R^{n}$ parameterises both the feasibility set $F = {f (x) \in R^{n} : x \in X}$ and the disagreement point $d = f (⋆) \in R^{n}$ where $1 = {⋆}$ is the singleton set.
Any preorder $(R, \leq)$	Suppose that $R$ is any set equipped with a preorder $\leq$ .^[11] Then a function $u : X \to R$ will induce a preorder $\leq_{u}$ on $X$ via $x \leq_{u} x^{'} ⟺ u (x) \leq u (x^{'})$ . Let ${argmax}_{X} \in J^{P} (X, R)$ be the optimiser which chooses the maximal points of $\leq_{u}$ , i.e. options which aren't strictly dominated by any other options. Explicitly $λ^{u : X \to R} . {x \in X : \forall x^{'} \in X . u (x) \leq u (x^{'}) ⟹ u (x^{'}) \leq u (x)}$ If $\leq$ isn't total (i.e. the agent has incomplete preferences over the payoffs) then the resulting optimiser ${argmax}_{X}$ is less selective (i.e. more options are optimal). In the extreme case, where no options are comparable, then ${argmax}_{X}$ might choose any option.^[12] Exercise 5: Which optimisers $ψ \in J^{P} (X, R)$ defined in the previous table can be generalised to any preorder $(R, \leq)$ ?
$R = X$ , where $X$ is the option space of the agent.	Occasionally the same set $X$ will serve as both the option space and the payoff space. In this case, a task $u : X \to X$ represents some transformation of the underlying option space. There's an optimiser $fix : J^{P} (X, X)$ , which choices options which are fixed-points of $u : X \to X$ . That is, $fix = λ^{u : X \to X} . {x \in X \| u (x) = x}$ . We can use $fix$ to model a conservative agent who chooses options which remain untransformed by the task. Note that this optimiser is not consequentialist, because the optimality of an option is not determined by its payoff alone. For example, $0 \in {fix}_{R} (sin)$ but $π \notin {fix}_{R} (sin)$ , despite the fact that $sin (0) = sin (π)$ .

Property	Remarks
Totality	We'll say that an optimiser $ψ \in J^{P} (X, R)$ is total iff $ψ (u) \neq \emptyset$ for all $u : X \to R$ . Informally, this condition states that our model of the agent never "breaks down", i.e. regardless of the task the agent faces, there's always some optimal choice.
Selectivity	We'll say that an optimiser $ψ_{1}$ is (weakly) more selective than $ψ_{2}$ if and only if $\forall u : X \to R . ψ_{1} (u) \subseteq ψ_{2} (u)$ . This relation defines a partial order on $J^{P} (X, R)$ . For example, ${satisfice}_{A}$ is more selective than ${satisfice}_{B}$ whenever $B ⊊ A \subseteq X$ . Mild optimization, an approach for mitigating Goodhart's law, replaces $argmax$ with less selective optimisers.
Consequentialism	We'll say that an optimiser $ψ \in J^{P} (X, R)$ is consequentialist if $ψ = λ^{u : X \to R} . {x \in X \| u (x) \in q (u)}$ for some $q : (X \to R) \to P (R)$ .^[14] In other words, for any task $u : X \to R$ , if $u (x) = u (x^{'})$ then $x \in ψ (u) ⟺ x^{'} \in ψ (u)$ . This condition says that, once we know the agent's task, then the only thing relevant to the optimality of a particular choice is its payoff. For example, ${argmax}_{X}$ and ${better-than-average}_{π}$ are consequentialist, but ${rock}_{S}$ and $fix$ are not. This function $q$ says, for each task $u : X \to R$ , which payoffs would be acceptable to the agent, so $q = max$ is the quantifier for $ψ = {argmax}_{X}$ .
Context-independence	We'll say that a consequentialist optimiser $ψ = λ^{u : X \to R} . {x \in X \| u (x) \in q (u)}$ is context-independent if $Image (u) = Image (u^{'}) ⟹ q (u) = q (u^{'})$ . Context-independence is a stronger condition than consequentialism — this condition says that, once we know which payoffs are achievable in the agent's task, then the only thing relevant to the optimality of a particular option is its payoff. For example, ${argmax}_{X}$ is context-independent, but ${better-than-average}_{π}$ is not.
Filtered optimisation	Suppose that $ψ \in J^{P} (X, R)$ is an optimiser, and $X_{legal} \subseteq X$ is a subset of the options which are safe/valid/legal. Then we can define another optimiser $ψ^{'} = λ^{u : X \to R} . X_{legal} \cap ψ (u) \in J^{P} (X, R)$ who always chooses options in $X_{legal}$ . This operation captures the notion of filtering options after the agent has applied the optimisation. For example, if $X = R$ and $ψ = {argmax}_{R}$ then $ψ (cos) = {2 π k : k \in Z}$ , so if $X_{legal} = [0, 4 π]$ then $ψ^{'} (cos) = {0, 2 π, 4 π}$ .
Constrained optimisation	The filtering operation doesn't capture what we typically mean by optimisation within side-constraints. For example, if we change $X_{legal}$ to $[π / 4, π / 2]$ , then we would like the optimiser to choose $π / 4$ as this maximises $cos$ subject to the constraint $X_{legal}$ . The filtered optimisation would produce the emptyset, as none of the options optimal to ${argmax}_{R}$ are legal. Let's define constrained optimisation for an optimiser $ψ \in J^{P} (X, R)$ . Suppose that there is an element $⊥ \in R$ such that $⊥ \in u (ψ (u)) ⟹ Im (u) \subseteq {⊥}$ . Informally, this means that $ψ$ detests the payoff $⊥ \in R$ and would never chooses an option resulting in $⊥$ unless it must. For example, ${argmax}_{X} \in J^{P} (X, R \cup {- \infty, + \infty})$ detests the payoff $- \infty$ . We can defined constrained optimisation as follows: $ψ^{'} = λ^{u : X \to R} . ψ (u^{'})$ where $u^{'} : X \to R, x \mapsto {\begin{matrix} u (x) & if x \in X_{legal} ⊥ & otherwise \end{matrix}$ Exercise 6: How might we define constrained optimisation if there is no such $⊥ \in R$ ?
Supervision	Maybe the set of legal options $X_{legal} \in P X$ depends on the task $u : X \to R$ itself. This dependency itself corresponds to an optimiser $ψ_{legal} \in J^{P} (X, R)$ . We can define the filtered optimiser as $ψ^{'} : λ^{X \to R} . ψ_{legal} (u) \cap ψ (u)$ . We can define the constrained optimiser $ψ^{'} = λ^{u : X \to R} . ψ (u^{'})$ where $u^{'} : X \to R, x \mapsto {\begin{matrix} u (x) & if x \in ψ_{legal} (u) ⊥ & otherwise \end{matrix}$ The optimiser $ψ^{'}$ behaves like one agent $ψ$ being supervised by another agent $ψ_{safe}$ where the mode of supervision is filtering and constraining respectively.
Unanimity	For a collection of optimisers $Z \subseteq J^{P} (X, R)$ , we can define a single optimiser $λ^{u : X \to R} . ⋂ {ψ (u) : ψ \in Z}$ who will only choose an option if each constituent optimiser would also choose the option, forming a unanimous coalition of $Z$ . Dually, we can define the optimiser $λ^{u : X \to R} . ⋃ {ψ (u) : ψ \in Z}$ forming a unilateral coalition.
Shards	Suppose that $f : (X \to R) \to J^{P} (X, R)$ assigns an optimiser $f (u) : J^{P} (X, R)$ to each task $u : X \to R$ . In terms of $f$ , we can define the optimiser $ψ = λ^{u : X \to R} . f (u) (u) : J^{P} (X, R)$ by diagonalising — i.e. $ψ$ will match the optimiser $f (u)$ in each task $u : X \to R$ . This operation captures (somewhat) the notion of shards, or context-activated optimisation. For example, imagine an agent $ψ : J^{P} (X, R)$ who "plays it safe" by satisficing unless they can achieve sufficiently high payoff, i.e. $f (u) = {\begin{matrix} {argmax}_{X} & if max (u) \geq 100 {satisfice}_{s} & otherwise \end{matrix}$ Or imagine an agent who desires cheese whenever they are sufficiently close to cheese, but otherwise desires to run around aimlessly.

^{^}

The little $λ$ is from (simply-typed) lambda notion for introducing functions. If $sin : R \to R$ is the familiar sine function, then $λ^{x \in R} . sin (x^{2})$ is the function $R \to R$ which sends each $x \in R$ to $sin (x^{2}) \in R$ , so $(λ^{x \in R} . sin (x^{2})) (π^{3}) = sin (π^{6})$ . We can also use lambda notation to define higher-order functions, e.g. if ${double}_{X} = λ^{u : X \to X} . u \circ u$ then ${double}_{R} (sin) (π + 1) = sin (sin (π + 1))$ .

^{^}

Synonyms: actions, alternatives, behaviours, configurations, coordinates, hypotheses, moves, options, outputs, parameters, plays, policies, positions, strategies — or whatever else is being chosen due to the payoffs assigned to it.

^{^}

Scott Garrabrant has called $(X \to R) \to X$ the the type-signature of agency, and you can interpret this sequence as an expansion on his remark.

In response to Garrabrant, MrMind raises the objection that no map $ψ : (X \to R) \to X$ can be parametric in both $X$ and $R$ because there is no map $(0 \to 0) \to 0$ . Fortunately, this objection doesn't apply here, because we're looking for functions $ψ : (X \to R) \to P (X)$ , and there is a function $ψ : (\emptyset \to \emptyset) \to P (\emptyset)$ .

^{^}

The term higher-order game theory is coined in [Hedges 2015], presumably because functions of the form $f : (A \to B) \to C$ are often called higher-order functions. Throughout the article, I will only use the term in this sense.

Warning: The term higher-order game theory is also used in [Nisan 2021] to refer to "the study of agents thinking about agents thinking about agents..." — and [Diffractor 2021] calls this higher-level game theory. I will never use the term in this sense.

^{^}

Spoilers: As you'll see later, this is the definition of optimisation you need to ensure that the nash equilibrium between two optimisers is also an optimiser.

^{^}

Of course, if $ψ (u) = \emptyset$ , then this model of the agent and their task would be falsified by any observed option, and can be eliminated a priori.

We can also interpret $ψ (u) = \emptyset$ as the statement that the computer program implementing the agent's decision theory would throw an exception, or fail to halt, when given the input $u : X \to R$ .

^{^}

Discussed in Program Equilibrium in the Prisoner’s Dilemma via Lob’s Theorem and elsewhere.

^{^}

In tomorrow's post, $P$ will be generalised to an arbitrary commutative monad $M$ . When we let $M$ be the probability monad $Δ$ , then we get optimisers of type $(X \to R) \to Δ (X)$ which would include Taylor's original probabilistic quantiliser. But don't worry about that now!

^{^}

... and any set $X$ to model the agent's options, any function $u : X \to R$ to model the agent's task, and any functional $ψ : (X \to R) \to P (X)$ to model the agent's optimisation.

^{^}

When $R^{n}$ is equipped with the product ordering, the optimiser ${argmax}_{X} : J^{P} (X, R^{n})$ is the called the pareto optimiser which maps each multi-objective task $u : X \to R^{n}$ to the pareto-frontier. This is the least selective optimiser which cares about each objective $π_{i} \circ u : X \to R$ .

^{^}

A partial order $\leq$ is a relation on $X$ satisfying three rules:

(1) Reflectivity: $x \leq x$ .

(2) Transitivity: If $x \leq y$ and $y \leq z$ then $x \leq z$ .

(3) Anti-symmetry: If $x \leq y$ and $y \leq x$ then $x = y$ .

A preorder $\leq$ is a relation satisfying only reflectivity and transitivity. A preorder is the non-evil version of a partial order, because it's agnostic about ""identity"" between equivalent objects.

Now, we say an agent's preferences are incomplete when neither $x \leq y$ nor $y \leq x$ , and an agent's preferences are indifferent when both $x \leq y$ and $y \leq x$ but not $x = y$ . So a partial order represents preferences which might be incomplete but never indifferent, while a preorder represents preferences which might be both incomplete and indifferent. Agents with incomplete preferences have recently been proposed as a solution to the Shutdown Problem.

^{^}

Warning: There're another optimiser in $J^{P} (X, R)$ who chooses the maximum points of $\leq_{u}$ , i.e. options which weakly dominate all other options. Explicitly, $λ^{u : X \to R} . {x \in X : \forall x^{'} \in X . u (x^{'}) \leq u (x)}$ . This optimiser is qualitatively different, being more selective when its preferences are incomplete.

^{^}

In Science without Numbers (1980), Hartry Field attempted to reformulate Newtonian physics without quantification over mathematical objects. Instead, the formulae of his theory would quantify only over physical objects and regions of spacetime. He called this normalisation of Newtonian physics.

Likewise, higher-order game theory promises a normalisation of game theory.

I don't know why, but this smells correct to me.

^{^}

This property is called closedness in [Hedges 2015] because the set $ψ (u) \subseteq X$ is closed under the equivalence relation $x \sim x^{'} ⟺ u (x) = u (x^{'})$ for every $u : X \to R$ .

A function $q : (X \to R) \to P (R)$ is called a quantifier in the HOGT literature.

LESSWRONG
LW

LESSWRONG
LW

70

Game Theory without Argmax [Part 1]

70

Ω 18

70

Ω 18

(2) Moral antirealism.

Preface

The role of argmax

Generalising the functional

Generalising the payoff space.

Subjective vs objective optimisers

(1) Carve nature at its joints.

(2) Moral antirealism.

(3) Experimental independence

(4) No spooky reals.

Recovering utility functions

Some properties of optimisers

Recap

Next time...

Further reading