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 c1, …, cK and private utilities u1, …, uK. That is the agent optimizes the set I:
I* = maxI ⊆ S∑i ∈ Iui s.t. ∑i ∈ Ici ≤ 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 = {(w1=1,u1=1), (w2=1,u2=0)}. Here we can only recover the fact that u1 > u2 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!