Effective algorithms for homogeneous utility functions.
arXiv:1801.00777v1 [] 29 Dec 2017

Alexander Shananin

∗

Sergey Tarasov

†

tweets: I am an economist so I can ignore
computational constraints.
I am a computer scientist, so I can ignore
gravity.
Lance Fortnow, a computer scientist

Abstract
Under the assumption of (positive) homogeinity (PH in the sequel) of the corresponding
utility functions, we construct polynomial time algorithms for the weak separability, the collective consumption behavior and some related problems. These problems are known to be at
least N P -hard if the homogeinity assumption is dropped.
Keywords: the utility function, the economic indices theory, the collective axiom of revealed
preference, the weak separability property, the class of the differential form of the demand.

1

Introduction

Globalization of the world economics results in structural changes that seems to fell out of the scope of
the traditional indicators such as, for instance, domestic product, and it seems that new instruments
like statistics panel should be involved in analysis. In this setting some already studied problems of
economics theory are becoming highly relevant. This paper is mainly motivated by the two following
questions.
1. Is it possible to describe structural changes within the framework of the traditional Pareto’s
theory of rational representative consumer (or its generalizations) for the case of several consumers?
2. How to analyze the segmentation of consumer’s market and how to compute statistics panel?
In economics literature this question is often referred to as separability problem.
Recall that Pareto’s theory assumes that the demand can be described within the model of
a rational representative consumer maximizing his utility function under the budget constraints
wherein the utility is postulated to be well-behaved, i. e. it is assumed to be concave, increasing, nonsatiated (nonnegative) maps from Rn+ to R+ continuous up to the boundary. Within the framework of
economic indices it is necessary to make another requirement and postulate that utility is PH. Indeed
(see, e. g. [10]), money balance of the consumer goods in the initial range and in the aggregated
∗
†

e-mail:
e-mail:

alexshan@yandex.ru Supported in part by RFBR grant 17-01-00507
serge99meister@gmail.com Supported in part by RFBR grant 17-07-00300

1

indicators is equivalent to Euler’s identity for the utility function. On the other hand, in economic
literature PH-assumption is criticized both from theoretical and empirical grounds. In theory, the
Engel curves for the PH-utility function should be rays, and this contradicts the intuition on demand
saturation with the growth of income of the household. Empirical studies of individual households
also show that their Engel curves are not rays.
Nevertheless, in some important settings PH can be justified. For instance, in the neoclassical
theory of consumer demand PH-assumption is verified in [11]. Namely, it is reasonable to assume
that PH holds not for an individual household but for the whole group of households with comparable
incomes (in other words, groups with similar living standards). Especially, the size of a particular
group varies as changes of income of an individual household result in modification of its consumer
behavior and possible transitions to different groups. This pattern leads to an essential nonlinearity
of Engel curves. And it turns out that the validity of PH-assumption for the cumulative consumer
behavior strongly depends on the redistribution of prices under changes of incomes of social groups,
and, in particular, whether these changes could be described by the Bergsonian social welfare function.
In this paper for the case of PH-utilities we construct effective algorithms bypassing exaustive
search for some important problems of the revealed preference theory that are NP-hard in the nonhomogeneous setting. In this respect the main message of the paper is that models allowing for
PH utility can be analyzed essentially faster, which may be essential for, say, monitoring or similar
purposes.
The organization of the paper is as folows. In the next section we recall some standard facts
of the revealed preference theory. The third and the fourth sections are devoted to the desciption
and justification of the algorithms for the weak separability and, respectively, for the collective
consumption behavior problems.
For convenience the details of some proofs are moved to the Appendix.

2

The revealed preference theory

Let us recall some standard facts from the revealed preference theory.
The rationality problem consists in the following: given the market statistics for a certain period
of time S = {{pt , q t }, pt = (pt1 , . . . , ptn ) ∈ Rn+ , q t = (q1t , . . . , qnt ) ∈ Rn+ , t = 1, . . . , T } (here pt and q t
are the bundles of prices and the corresponding quantities of goods purchased at time t, respectively),
to find whether the statistics can be rationalized, where rationalization means the existence of a
certain (concave) utility function f : Rn+ → R+ usually called the index of goods, which is consistent
with S. By definition, a utility function f (·) is consistent with market statistics S if
q t ∈ Argmax {f (q) | pt q ≤ pt q t , q ≥ 0},

t = 1, . . . , T.

Hereinafter we assume that utility functions are well-behaved, i. e. they are assumed to be
concave, increasing, non-satiated (nonnegative) maps from Rn+ to R+ continuous up to the boundary.
Besides that we assume that utilities satisfy an additional more restrictive reqiurement of positive
homogeneity (PH)1 . The results of this paper may provide a convincing argument in favour of this
choice, if the model involved allows for it: if we drop homogeneity assumption then all the problems
listed below are hard from the point of the complexity theory as they are known to be at least NP hard and may be even harder, say, belong to the complexity class ∃R-hard. Additionally, numerical
1

This property is also referred to as homotheticity in economics literature, but it seems that our choice is more
suitable, as not only level sets of the PH utilities ought to be homothetic, but, e. g., Euler identity should also hold.

2

results (see, for instance, [9]) show that the usage of PH utility functions are more adequate and
produce essentialy less noise.
Recall that by the homogeneous Afriat’s theorem (see, e.g. [1, 17]) the statistics S is rationalizable in the class of the well-behaved PH utilities iff the following system of linear inequalities is
consistent
λt pt q t ≤ λτ pτ q t , λt > 0, λτ > 0, t, τ = 1, . . . , T.
(1)
PT
Evidently, we can assume that the additional normalization condition holds i=1 λi = 1.
The particular utility function can be recovered from an arbitrary solution of (1) by the formula
f (x) = min λt pt x.
t=1,...,T

(2)

Now we remind two fundamental problems of the revealed preference theory and prove that for
PH ulilities each of these problems can be solved effectively by a polynomial time algorithm. On the
other hand, under the standard setting not assuming PH, these problems are proven to be at least
NP -hard, i. e. intractable for large enough inputs.

3

Weak separability

Assume that goods are partitioned into two (non intersecting) groups of, say, k q-goods and l y-goods.
Then the market statistics bundle can be written as S = {pt , xt ; q t , y t }t=1,...,T , here pt , xt are prices
and q t , y t are the corresponding volumes of purchases and thus {pt ; q t }t=1,...,T is a market statistics
bundle for q-goods and, respectively, {xt ; y t }t=1,...,T is a market statistics bundle for y-goods.
Assume that the overall statistics S is rationalizable by a well-behaved utility function u(q, y),
where q = {q t }, y = {y t}, t = 1, . . . , T .
We say that S is rationalizable by weak separability (in y-goods) if there exist a well-behaved
“micro” subutility function v(y) rationalizing statistics for y-goods and a well-behaved “macro (aggregated)” utility function ũ(q, v(y)), strictly increasing in v-variable, such that u(q, y) = ũ(q, v(y)).
This problem is studied in many publications, see, for instance, [2, 17, 14, 8, 5].
Necessary and sufficient conditions for (non homogeneous) weak separability are proven, e. g., in
[17, Theorem 3]. Furthemore, [17, Theorem 5] gives necessary and sufficient conditions for the case
of the so called “homothetic separability”, where the subutility function v(y) is additionally assumed
to be PH (homothetic). Unfortunately, both characterizations are expressed by a set of quadratic
inequalities and moreover are intractable from the point of view of complexity theory. It is proved
in [5, 6] that testing weak separability is NP -complete.
We prove that if we assume complete PH-separability, i. e. that not only subutility is PH
but macro utility is also PH, then testing weak separability can be reduced to convex program that
can be solved by an effective polynomial time algorithm.
The following necessary and sufficient conditions for complete PH-separability can be obtained
along the same lines as the corresponding conditions for homothetic separability in [17, Theorem 5].
For convenience the details of the proof are moved to the Appendix.

3

λt xt y t ≤ λτ xτ y t ,
λt > 0, λτ > 0
k
l
k
l
X
X
X
X
t t
t t
τ t
µ t λτ (
pi qi +
xi yi ) ≤ µτ (λτ
pi qi + λt
xti yit )
i=1

i=1

i=1

T
X

(3)
(4)

i=1

λi = 1

(5)

i=1

t, τ = 1, . . . , T.

(6)

Let us show how to put the system involved into convex form.
For convenience we use capital letters for all constant parameters except indices and denote the
def
logarithm of some [positive] parameter x by x̃. For instance, αf
λt = log α λt . We rewrite the system
using this notation.
λ̃t + log(X t Y t ) ≤ λ̃τ + log(X τ Y t )

µ̃t + λ̃τ + log(
+ log[exp(λ̃τ )

k
X

i=1
k
X

Pit

Piτ

Qti

+

l
X

(7)

i=1

Qti

+ exp(λ̃t )

i=1

T
X

Xit Yit ) ≤ µ̃τ +
l
X

Xit Yit ]

(8)

i=1

exp(λ̃i ) = 1

(9)

i=1

t, τ = 1, . . . , T.
Now the lhs of (8) is already convex. To fix the rhs we substitute for eachP
λi its expression from
the normalization condition (5). We obtain a function of the form log[const − r exp(Lr )], where Lr
are affine forms of λei and thus the function involved is concave. At last we need to fix the problem
with the normalization equality (5) and this is done by adding a new nonnegative slack variable γ.
Finally, we get the convex program
γ → min
λ̃t + log(X Y ) ≤ λ̃τ + log(X τ Y t )
t

µ̃τ + λ̃t + log(

k
X
i=1

Pit Qti +

l
X

(10)
(11)

t

Xit Yit ) ≤ µ̃τ + log[(1 −

T
X

exp(λ̃i ))

i=1, i6=τ

i=1

(1 −

T
X

i=1, i6=t

4

k
X

Piτ Qti +

(12)

i=1

exp(λ̃i ))

l
X
i=1

Xit Yit ]

(13)

T
X

exp(λ̃i ) + γ ≤ 1, γ ≥ 0

(14)

i=1

t, τ = 1, . . . , T.
And we conclude that the statistics S is weakly separable iff the optimum of the related convex
program is zero. Moreover, we can use modern effective polynomial-time routines to solve this
program. To be a bit more exact by “effective” we mean a procedure which solves the approximate
version of the convex program involved within the accuracy ε in time poly(max(L, log Rε )), where L
is the length of the input and R is the so called localization radius. By definition, if the program
is consistent then at least one solution should fall into the ball of radius R with the center at the
origin.
By construction we have proved the following theorem.
Theorem 1. There is an effective polynomial time algorithm to solve weak separability problem
Remark 1. PH-separability is equivalent to the so called indirect weak separability (IWS) (see,
e. g. [3, 5]) and as a by product IWS for PH utilities can be solved by an effective algorithm.
Let us define the generalized separability problem as a problem of checking whether there
exists some separable partition of the market statistics2 .
Corollary 1. The generalized PH-separability problem belongs to NP .

4

Collective rationality

Afriat’s theorem mentioned above is an effective tool to test whether the market statistics can be
rationalized. But how could violation of rationality be dealt, for instance, in the case of some
essential ongoing structural changes? In view of the uprecedented and unexpected changes of the
modern economics this question seems to acquire the status of a real challenge of crucial importance.
One of the approaches to deal with this problem is the collective revealed preference rationality
model introduced in [4]. It consists in partitioning of the initial (nonrationalizable) market statistics
bundle into a certain number of, say k, rationalizable bundles of the same cardinality, having the
same initial price subbundles but different goods subbundles that componentwise sum to the initial
goods subbundle. In other words, we want to represent the utility as a k-dimensional vector function
def
such that each component is a well-behaved
utility function for the statistics Sα = {pt , α q t }, t =
Pk PH
1, . . . , T , where for all i ∈ {1, . . . , n} α=1 α qit = qit . Using analogy with smooth setting3 we call
minimal such k the discrete class number of the demand form.
By the homogeneous Afriat’s theorem4 we can express collective rationality by the following
2

Evidently, to avoid trivial solutions we should assume that the required partition should be balanced, i. e.,
comparable to the size of the statistics.
3
In [11] this parameter is related to the E. Cartan’s class number of the differential form of the demand. Loosely
speaking, it is equal to the minimal number of the independent variables (functions) needed to express the form.
4
This problem becomes intractable [16] if we drop homogeneity assumption (and use the standard Afriat’s conditions).

5

system.
α

λt

n
X

pti α qit

≤

α

λτ

i=1

n
X

pτi α qit ,

α = 1, . . . k

i=1

k
X

α t
qj

= qjt ,

j = 1, . . . , n,

α=1

t, τ = 1, . . . , T.
As above, we use capital letters for all constant parameters except indices and denote the logarithm of some [positive] parameter x by x̃. After taking logarithms we obtain
αf
λt

+ log[

n
X
i=1

Pit

exp(αf
qit )]
k
X

α t
qj

≤

α
g
λτ

+ log[

= Qtj ,

n
X

Piτ α qit ],

α = 1, . . . k

(15)

i=1

j = 1, . . . , n,

(16)

α=1

t, τ = 1, . . . , T.
Now we can use almost the same trick as before to transform the resulting system into a convex
program.
Note that the lhs of (15) is already convex. To fix the rhs we substitute for each α qit its expression from the relevant balance condition from (16). We obtain a function of the form log[const −
P
αft
r exp(Lr )], where Lr are affine forms of qi and thus the function involved is concave. At last we
need to fix problem with balance equalities (16) and this is done by adding new nonnegative slack
variables γit , t = 1, . . . , T, i = 1, . . . , n. Finally, we get the convex program
T X
n
X

γit → min

t=1 i=1

αf
λt

+ log[

n
X
i=1

n
n
X
X
τ
t
t
ft ) exp(αf
α
g
exp(αf
qjt ))]
exp(P
q
)]
≤
λ
+
log[
P
(Q
−
τ
i
i
i
i
i=1

k
X
α=1

qit ) + γit ≤ Qti ,
exp(αf

γit ≥ 0
t, τ = 1, . . . , T,

j=1, j6=i

α = 1, . . . k,

i = 1, . . . , n.

By construction we proved the following theorem.
Theorem 2. The discrete class number of the demand form is less or equal to k iff the resulting
convex program has optimal solution zero.
As above we can use modern effective polynomial-time routines to solve the convex problem
involved for any k and thus not only can we identify the minimal k but we are able to retrieve some
required utility vector function as well.
6

References
[1] Afriat S. The construction of utility functions from expenditure data. //International Economic
Review. 8. N1. 66–67. 1967.
[2] Blackorby C., Primont D., and Russel R. Duality, Separability, and Functional Structure: Theory
and Economic Application. Amsterdam: North-Holland. 1979.
[3] Brown D.J., Shannon C. Uniqueness, stability, and comparative statics in rationalizable Walrasian markets. Econometrica 68, 1529–1540. 2000.
[4] Cherchye L., De Rock B., and Vermeulen F. The Collective model of household consumption: a
non parametric characterization. Econometrica. Vol. 75. No. 2. 553-574. 2007.
[5] Cherchye, L., Demuynk, T., De Rock, B., Hjertstrand P. Revealed preference tests for weak
separability: an integer programming approach. Journal of Econometrics. 186. 129–141. 2015.
[6] Echenique F. Testing for separability is hard. arXiv:1401.4499 [cs.GT]
[7] Heufer J., Hjertstrand P. Homothetic Efficiency: Theory and Applications, Journal of Business
& Economic Statistic. DOI: 10.1080/07350015.2017.1319372. 2017
[8] Fleissig A., Whitney G.A. A nonparametric test of weak separability and consumer preferences.
Journal of Econometrics. 147, 275281. 2008.
[9] Klemashev N., Shananin A. Inverse problems of demand analysis and their applications to
computation of positively-homogeneous KonüsDivisia indices and forecasting. Journal of Inverse
and Ill-Posed Problems. 2015.
[10] Kondrakov I., Pospelova L., and Shananin A. Generalized nonparametric method. Applications
to the analysis of commodity markets. In Russian. Proc. MIPT 2. 3245. 2010.
[11] Petrov A., Shananin A. Integrability conditions, Income distribution, and social structures.
Lecture notes in Economics and mathematical systems, 453. Springer. 1998.
[12] Shananin A., Tarasov S. Computing the class the differential demand form from discrete data.
Proc. MIPT conference. 2015.
[13] Smeulders, B., Cherchye, L., De Rock, B., Spieksma, F., Talla Nobibon, F. Complexity results for the weak axiom of revealed preference for collective consumption models. Journal of
Mathematical Economics. 58. 82–91. 2015.
[14] Swofford J.L., Whitney, G.A. A revealed preference test for weakly separable utility maximization with incomplete adjustment. Journal of Econometrics. 60, 235249. 1994.
[15] Talla Nobibon, F., Cherchye L., Crama, F, Demuynk, T., De Rock, B., and Spieksma, F.
Revealed preference tests of collectively rational consumption behavior: formulations and algorithms. Operations Research 64, 1197-1216. 2016.
[16] Talla Nobibon, F., Spieksma, F. On the complexity of testing the collective axiom of revealed
preference. Mathematical Social Sciences. 60. No. 2. 123–136. 2010.
7

[17] Varian H.R. Non-parametric tests of consumer behaviour. //The Review of Economic Studies.
1983, 50(1). 99–110. 1983.

5

Appendix

Proposition 1. Formulas (3)–(6) give necessary and sufficient conditions for complete PH-separability.
Proof. At first, recall that Euler’s homogeneous function theorem can be reformulated as follows
for the case of PH well-behaved functions f (·) : Rn+ → R+ . If x0 ∈ Rn+ and p ∈ ∂f (x0 ) then
px0 = f (x0 ).
Necessity. In the notation used above we need to prove the existence of the well-behaved PH
functions u0 (q, z) and u1 (y) such that
(q t , y t) ∈ Argmax[u0 (q, u1(y)) | pt q + xt y ≤ pt q t + xt y t , q ≥ 0, y ≥ 0], t = 1, . . . , T.

(17)

As PH well-behaved functions are monotonic then it follows from (17) that y t ∈ Argmax[u1 (y) |
xt y ≤ xt y t , y ≥ 0], t = 1′ . . . , T.
def
def
pq+sz
xy
Define the Young transforms: ν0 (p, s) =
inf
and ν1 (x) =
inf
.
u0 (q,z)
u1 (x)
{q≥0, z≥0 |, u0 (q,z)>0}

{y≥0 | u1 (x)>0}

By definition it holds
ν1 (xt )u1(y t )
ν1 (xτ )u1(y t )
ν0 (pt , ν1 (xt ))u0 (q t , u1 (y t))
ν0 (pτ , ν1 (xτ ))u0 (q t , u1 (y t))
t, τ

=
≤
=
≤
=

xt y t
xτ y t
pt q t + ν1 (xt )u1(y t )
pτ q t + ν1 (xτ )u1(y t )
1, . . . , T.

1
1
Now necessity follows as λt = ν1 (x
t ) , µt = ν (pt ,ν (xt )) t = 1, . . . , T are solutions of the system
0
1
(3)–(6).
def
t
t
Sufficiency. Set u1 (y) = min{λt xt | t = 1, .. . , T }. By
 definition y ∈ Argmax[u1 (y) | x y ≤
def

xt y t , y ≥ 0], t = 1, . . . , T. Set u0 (q, z) = min{µt pt q +

1
z
λt

| t = 1, . . . , T }.

Let q ≥ 0, y ≥ 0, pt q + xt y ≤ pt q t + xt y t . Then it holds
1
1
u1 (y t) =
u0 (q t , u1 (y t )),
λt
µt
1
1
1
u0 (q, u1(y)).
xt y ≥ u1 (y), pt q + xt y ≥ pt q + u1 (y) ≥
λt
λt
µt
pt q t + xt y t = pt q t +

And it follows that u0 (q t , u1 (y t)) ≥ u0 (q, u1(y)) and thus (17) holds.

8

