STATISTICS · MACHINE LEARNING · SOCIOLOGY

STATISTICS · MACHINE LEARNING · SOCIOLOGY

I was reading Amartya Sen’s exposition of Buridan’s ass in his excellent essay “Behaviour and the Concept of Preference” and it got me thinking about the revealed preference approach with computationally bounded agents. Sen writes:

[Buridan’s] ass, as we all know, could not make up its mind between two haystacks; it liked both very much but could not decide which one was better. Being unable to choose, this dithering animal died ultimately of starvation. The dilemma of the ass is easy to understand, but it is possible that the animal would have agreed that it would have been better off by choosing either of the haystacks rather than nothing at all. Not choosing anything is also a choice, and in this case this really meant the choice of starvation. On the other hand, had it chosen either of the haystacks, it would have been presumed that the ass regarded that haystack to be at least as good as the other, which in this version of the story was not the case. The ass was in a real dilemma vis-a-vis the revealed preference approach.

The core idea I’m interested in here is whether computational bounds
restrict our ability to learn agents actual preferences since agents do
not actually make optimal decisions in practice. In this short post I
mostly just pose questios thinking about this issue through a classic
NP-hard problem (the knapsack problem), but the particular problem isn’t
really relevant. Really I start from the premises that: 1. there is
private preference information we want to infer from behaviour
alone

2. the agent is trying to solve a “hard” and so they approximate a
solution rather than solving it optimally 3. we can repeatedly ask the
agent to solve variants of the problem to observe their behaviour in
different situations and ask how well and how quickly we can learn the
agents private preferences (contrasted against the case where we know
the agent is playing optimally) and taking the ass’s perspective,
so-to-speak, we can also ask whether there are strategies an agent could
deploy in this repeated context which could signal its true preferences
under computational constraints.

Assume we have an agent which maximizes their utility under a budget
constraint *B* over a set *K* items denoted *S* with costs *c*_{1}, …, *c*_{K}
and private utilities *u*_{1}, …, *u*_{K}.
That is the agent optimizes the set *I*:

*I*^{*} = max_{I ⊆ S}∑_{i ∈ I}*u*_{i}
s.t.
∑_{i ∈ I}*c*_{i} ≤ *B*

That is the agent is playing a knapsack problem. We can observe the
costs of each item, the budget the agent operates under, and the set the
agent selects *I*^{*}.
We cannot observe the agents private utilities.

Now let’s assume we can query the agent with a given budget *b* ∈ ℝ and a given subset of elements
*s* ⊆ *S* and observe
their response *I*^{*}(*s*,*b*).
Note that in general we cannot recover an agent’s exact private
utilities: consider the case where *S* = {(*w*_{1}=1,*u*_{1}=1), (*w*_{2}=1,*u*_{2}=0)}.
Here we can only recover the fact that *u*_{1} > *u*_{2}
but cannot gain any more information. We must set our sights slightly
lower then and restrict our interest to being able to exactly
reconstruct the function *I*^{*} over all possible sets
and budgets.

This is clearly a question in the tradition of dicrete choice theory and computation and is interesting in its own right. It is far from trivial! Obviously we could query the product of all possible subsets and all possible budgets but it seems we should be able to do better than this given our knowledge of the problem.

In the spirit of Buridan’s ass I want to go further though and asking
another question. We know the optimization variant of the knapsack
problem is at least NP-hard, so we might not expect our agent to be able
to compute the optimal *I*^{*}. Instead we might
assume that our agent uses a deterministic unknown polynomial-time
algorithm *A* : 𝒫(*S*) × ℝ → 𝒫(*S*)
to select their set rather than always solving the full knapsack problem
above. We will assume *A* is in
a known class of algorithms 𝒜 Now we
can pose the really interesting questions:

This question what classes of approximation are query-recoverable in
better than worst case (enumerate all subsets and all budgets) time. For
example if we know *A* is a
1/2-approximation (e.g. the selected set is always at least half as good
as the optimal set) then maybe we can do better than worst case query
complexity. Or maybe not. It is not obvious to me!

This is of course the big question. Maybe the most interesting
starting place would be to consider with some arbitrarily small *ϵ* ∈ (0, 1] and let 𝒜 = *A* be a *known* (1−*ϵ*)-approximation where the
selected set is always at least 1 − *ϵ* as good as the optimal set. In
this highly restricted case can we recover *I*^{*}? This leads to the
next question:

Here we relax our dreams of recovering *I*^{*} and instead ask what
the best recoverable approximation will be for a given class. And of
course there are query complexity analogues of both (2) and (3).

These questions are quite important from the perspective of what we can learn about the preferences of computaionally bounded agents from their behavior alone. My intuition is that there are more negative than positive results here, but those negative results are important! It would imply that revealed preference approaches are seriously undermined by computational constraints. And of course positive results would also be welcome as they might lead to better econometric methods for studying people’s preferences.

Additionally we can flip the question on its head and ask whether there are ways an agent can select items to signal their preferences to an observer:

This last question is the least well formed of the four, but it would be particularly interesting if there were effective strategies computationally bounded agents could use to signal their preferences, especially if they involved deviating from the utility maximizing strategy!

In any case I think this is a super interesting direction for folks at the intersection of economics and computation to think in, offering both interesting puzzles and relevant conclusions. I have not seen any work doing something like this, but if anyone knows of anything please let me know!