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' true preferences since agents do not actually make optimal decisions in practice. In this short post I mostly just pose questions thinking about this issue through a classic NP-hard problem (the knapsack problem), but the specific problem isn’t important. Really I start from the premises that:

- there is private preference information we want to infer from
behaviour alone

- the agent is trying to solve a “hard” problem and so they approximate a solution rather than solving it optimally
- 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 agent's private preferences (contrasted against the case where we know the agent is playing optimally where this is presumptively more straingtforward). 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, \dots, c_K\) and private utilities \(u_1, \dots, u_K\):

\[ \begin{align} I^* = \max_{I \subseteq S} &\sum_{i \in I} u_i \\ \text{ s.t. } &\sum_{i \in I} c_i \leq B \end{align} \]

That is the agent is playing a knapsack problem optimizing the subset of goods they buy with their budget. 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 \in \mathbb{R}\) and a given subset of elements \(s \subseteq 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 and instead aim to exactly reconstruct the function \(I^*\) over all possible sets and budgets.

This is clearly a question in the tradition of revealed preference 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 agents strategy.

In the spirit of Buridan’s ass I want to go further though, asking a trickier 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^*\) for all (sub)sets and budgets. Instead we might assume that our agent uses an unknown polynomial-time algorithm \(A: \mathcal{P}(S) \times \mathbb{R} \rightarrow \mathcal{P}(S)\) to select their set rather than solving the full knapsack problem above. We will assume \(A\) is in a known class of algorithms \(\mathcal{A}\) Now we can pose the really interesting questions:

This question gets at which classes of approximation are query-recoverable in better than worst case (enumerate all subsets and all budgets) queries. 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 \(\epsilon \in (0, 1]\) and let \(\mathcal{A} = A\) be a *known* \((1-\epsilon)\)-approximation where the
selected set is always at least \(1-\epsilon\) as good as the optimal set. In
this highly restricted case can we recover \(I^*\)? A particularly easy case would be to
take \(\mathcal{A} = A\) to be a mixture of
the optimal algorithm \(I^*\) and a
uniform strategy where with probability
\(P(1-\delta)\) the agent randomly selects elements until
they hit their budget constraint. In this case I
think we should be able to recover \(I^*\)
by classic results in statistical learning, but it is not really in the spirit
of our agent acting under computational constraints. And in fact it seems likely
that for many classes of algorithms we cannot in fact 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 \(\mathcal{A}\). 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!