Closure Operators: Complexity and Applications to
Classification and Decision-making.
HAMED HAMZE BAJGIRAN,
California Institute of Technology
FEDERICO ECHENIQUE,
California Institute of Technology
We study the complexity of closure operators, with applications to machine learning and decision theory. In
machine learning, closure operators emerge naturally in data classification and clustering. In decision theory,
they can model equivalence of choice menus, and therefore situations with a preference for flexibility. Our
contribution is to formulate a notion of complexity of closure operators, which translate into the complexity
of a classifier in ML, or of a utility function in decision theory.
CCS Concepts:
•
Applied computing
→
Economics
;
Economics
;
•
Computing methodologies
→
Clas-
sification and regression trees
.
Additional Key Words and Phrases: classification, menu choice, subjective state space
ACM Reference Format:
Hamed Hamze Bajgiran and Federico Echenique. 2022. Closure Operators: Complexity and Applications to
Classification and Decision-making.. In
Proceedings of the 23rd ACM Conference on Economics and Computation
(EC ’22), July 11–15, 2022, Boulder, CO, USA.
ACM, New York, NY, USA, 21 pages. https://doi.org/10.1145/
3490486.3538253
1 INTRODUCTION
We study the complexity of closure operators, with applications to machine learning and decision
theory in economics. Closure operators can be used to model a coarsening of reality. For example,
the set of all 16 subsets of the set
{
푎,푏,푐,푑
}
may be viewed as a fine-grained description of some
physical system. A coarser view could regard some subsets as equivalent, just like in the usual
topology on the real line, the rational numbers are “indistinguishable” from the real numbers in
the sense that their closure equals the reals. For example, all subsets of
{
푎,푐
}
in
{
푎,푏,푐,푑
}
could be
seen as equivalent, which a closure operator may capture by mapping the sets
{
푎
}
,
{
푐
}
, and
{
푎,푐
}
into
{
푎,푐
}
.
Such coarsening of reality emerges naturally in machine learning and in decision theory. In
machine learning, a
classifier
will decide that some individual data-points should be lumped together.
For example, the classifier can be applied to images of household pets, and classify them according
to species, without regard for color or size. An Irish Setter is indistinguishable from a Dachshund:
both are mapped into the class of dogs; while a canary and a parrot may be seen as distinct from
any dogs, but grouped together as birds.
In economic decision theory, an agent may be choosing a menu, or a store, from which to make
an ultimate choice. Someone who is in the market for a particular item, say a Canon 5D Mark III,
will regard any photography store that carries this model as equivalent: one store indistinguishable
from another as long as they have what the consumer is looking for. An agent choosing items in
This work is licensed under a Creative Commons Attribution International 4.0 License.
EC ’22, July 11–15, 2022, Boulder, CO, USA
©
2022 Copyright held by the owner/author(s).
ACM ISBN 978-1-4503-9150-4/22/07.
https://doi.org/10.1145/3490486.3538253
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
35
{
푎,푏,푐,푑
}
, with preferences
푎
≻
푏
≻
푐
≻
푑
, will consider all menus that contain
푎
as indifferent;
any menu that contains
푏
but not
푎
is also indifferent, and so on.
Closure operators are ideally suited to analyze these situations. In particular, we shall see that
closure operators can capture a desire for flexibility stemming from agents who are uncertain about
their preferences. If our agent is unsure of whether they rank
푎
over
푏
, or the other way around,
they may have a strict preference for a larger menu containing both options. For example they
may prefer
{
푎
}
over
{
푏
}
(as menus), but strictly prefer
{
푎,푏
}
over
{
푎
}
. A branch of decision theory
(one that started with the seminal paper of Kreps
[16]
) relies on closure operators as a modeling
device. In particular, the work of Dekel, Lipman, and Rustichini [7] uses the operator that maps a
set
퐴
⊆
R
푛
to its convex hull; and their key axiom is that agents are indifferent between
퐴
and its
convex hull.
Our starting point is a representation theorem for closure operators. We shall see that a closure
operator may be built up from more basic, or simpler, operators. In machine learning, it is natural
to think of a classifier as resulting from the composition of simple linear classifiers. We show that a
similar representation is possible, even in discrete settings where there is no language for talking
about linearity. In decision theory, some agents may have complex preferences over menus that
result from a desire for flexibility in choice. We shall see that such complex preferences can be
constructed from simpler operators that do not exhibit such a desire for flexibility.
Our representation theorem contains those of Richter and Rubinstein
[20]
and Chambers, Miller,
and Yenmez
[4]
as special cases, and relies on similar ideas. The main novelty in our work lies
in connecting the topologies arising from a closure operator, to those arising from its simplest
constituent operators; and in using this connection to formulate a notion of complexity. It is indeed
natural in machine learning to identify the complexity of a classifier with the number of different
simple classifiers needed to represent it: our paper formalizes this connection in the abstract model
of discrete data.
For decision theory, we shall see that the complexity of an operator is tied to the size of the
(subjective) state-space needed to represent an agent’s choices. As we wrote above, a preference for
flexibility emerges from uncertainty about future preferences. Such uncertainty can be represented
with a state space that is obtained (as in Kreps
[16]
) from the relevant operator. Indeed, Dekel,
Lipman, and Rustichini [7] write:
“the size of the subjective state space provides a measure of the agent’s uncertainty
about future contingencies.”
We show how to extend the approach in Dekel et. al, so that if their key axiom is applied to
an arbitrary closure operator, even in the discrete setting of our paper, a representation with a
preference for flexibility may be obtained. In this representation, we can bound the size of the
state-space through the representation of a closure operator in terms of simpler constituents.
2 LITERATURE REVIEW
Closure operators and their connections to topologies are a subject of study in mathematics (Ward
[22]
), but the literature that is closest to our work pertains to applications in economics and computer
science. Some of these applications are related to convex geometries and their representations.
The basic concepts of abstract convex geometry and combinatorial convex hull operator are
developed in Edelman and Jamison
[10]
. Convex hull operators are a class of closure operators with
an extra
anti-exchange
property
1
. In decision theory, Koshevoy
[15]
studies the connection between
the combinatorial convex hull operators and the path-independent choice functions. The closest
1
We say that
푓
satisfies the anti-exchange property if given any closed set
퐴
and two unequal points
푥,푦
∈
푋
\
퐴
, then
푥
∈
푓
(
퐴
∪
푦
)
implies that
푦
∉
푓
(
퐴
∪
푥
)
.
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
36
papers to ours are Richter and Rubinstein
[20]
and Chambers et al
. [4]
. Richter and Rubinstein
[20]
provide a characterization of a combinatorial convex hull operator through a set of primitive
orderings. Using their representation, Richter and Rubinstein
[20]
propose a notion of competitive
equilibrium in an abstract environment. Chambers et al
. [4]
extends the result of Richter and
Rubinstein
[20]
and relates it to the Kreps
[16]
model of preferences for flexibility in decision theory.
They provide the main characterization of closure operators by weak orders.
In the context of dynamic choice, and preferences for flexibility, following Kreps
[16]
, Dekel,
Lipman, and Rustichini
[7]
, and Gul and Pesendorfer
[12]
, a rather extensive literature in economics
studies different aspects of choice over menus. The closest related papers are those of Nehring
and Puppe
[19]
, Kopylov
[13]
, Kopylov
[14]
, and Gorno
[11]
. Nehring and Puppe
[19]
provides a
more refined Pareto representation of the Krepsian model. They provide the connection to the
representation by Aizerman and Malishevski
[1]
of choice correspondences satisfying the heritage
and outcast properties, which is another route for proving Claim 1 in Richter and Rubinstein
[20]
;
that every convex geometry is generated by a set of primitive ordering.
2
Kopylov
[13]
determines
the number of positive and negative states in the setting of Dekel, Lipman, and Rustichini
[7]
. Gorno
[11]
shows that any preference ordering in Kreps’ setting has a representation as a Dekel-Lipman-
Rustichini representation. Finally, Kopylov
[14]
proposes a combinatorial model of subjective states.
By relaxing the axioms of Kreps, he presents a weaker model of coherent aggregation.
Our application to classification problems in machine learning is related to the link between
closure operators and Galois connections, and their applications in formal concept theory. Generally,
there are different applications of lattice theory for studying general hierarchical concepts. For an
overview of representations and applications to closure systems and formal concept theory see
Caspard and Monjardet
[3]
, Domenach and Leclerc
[9]
, Bertet et al
. [2]
, and Davey
[6]
. In our paper,
we focus on a simple model with a new complexity notion, its decision-theoretic and conceptual
interpretations, and how it may be computed efficiently.
3 MODEL AND PRELIMINARIES
3.1 Preliminary definitions and notational conventions
Let
푋
be a set. We denote the set of all subsets of
푋
by
2
푋
. A binary relation on
푋
is 1) a
weak
order
on
푋
if it is complete and transitive (meaning that it orders all elements of
푋
); 2) a
partial
order
if it is reflexive, transitive and anti-symmetric (
∀
푥,푦
∈
푋
if
푥
⪰
푦
and
푦
⪰
푥
then
푥
=
푦
); 3) a
total order
if it is a complete partial order.
Let
⪰
be a partial order on
푋
. We say that two elements
푥,푦
with
푥
⪰
푦
or
푦
⪰
푥
are
ordered
, or
comparable
, by
⪰
. A subset
푌
of
푋
is a
chain
if it is totally ordered by
⪰
, and an
anti-chain
if no
two of its elements are ordered by
⪰
. An element
푥
∈
푋
is said to be an
upper bound
of
푌
if
푥
⪰
푎
for every
푎
∈
푌
. We denote the
least upper bound
, or
join
, of
푌
(if it exists) by
Ô
푌
. Similarly, we
denote the
greatest lower bound
or
meet
of
푌
by
Ó
푌
. The partially ordered set
푋
is a
lattice
if,
for all
푥,푦
∈
푋
, the set
{
푥,푦
}
has a join and a meet: denoted by
푥
∨
푦
and
푥
∧
푦
respectively.
We introduce some concepts from discrete geometry that may be viewed as analogues to concepts
in convex analysis: see Richter and Rubinstein
[20]
for an earlier application of these ideas to
economics. Denote the set of all weak orders on
푋
by
R
. The
support function
of
퐴
⊆
푋
is the
function
ℎ
퐴
:
R →
2
푋
defined by
ℎ
퐴
(⪰)
=
{
푥
∈
퐴
|
푥
⪰
푦
∀
푦
∈
퐴
}
. Similarly, we may define
the
support half-space
of
퐴
≠
∅
with respect to
⪰∈ R
by
퐻
(⪰
,ℎ
퐴
)
=
{
푥
∈
푋
|
ℎ
퐴
(⪰) ⪰
푥
}
. By
definition, we set
퐻
(⪰
,ℎ
∅
)
=
∅
.
2
In a nutshell, the heritage property states that if
퐴
⊆
퐵
, then
푓
(
퐴
) ⊇
푓
(
퐵
)∩
퐴
. When imposed on a choice function, this
property is the
훼
property of Sen
[21]
. The outcast property states that if
푓
(
퐴
) ⊆
퐵
⊆
퐴
, then
푓
(
퐴
)
=
푓
(
퐵
)
. This property
is a weaker form of property
훽
of Sen
[21]
. Note, however, that our paper takes closure operators as primitive, not choice.
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
37
Observe the analogy with convex analysis. Here the set
R
serves the same role as the dual of
푋
(the set of continuous linear functionals), when
푋
is a Euclidean space.
One final notational convention is that we denote the indicator function for a set
퐶
⊆
푋
by
1
퐶
.
So
1
퐶
(
푥
)
=
1
if
푥
∈
퐶
and
1
퐶
(
푥
)
=
0
otherwise.
3.2 Closure operators
The paper is a study of a special kind of functions defined on the subsets of a finite set
푋
; functions
of the form
푓
: 2
푋
→
2
푋
that have the properties of closure operators in topology [17]:
Definition 1.
A
closure operator
on
푋
is a map
푓
: 2
푋
→
2
푋
that satisfies the following
properties:
(1)
Extensivity
:
퐴
⊆
푓
(
퐴
)
and
푓
(∅)
=
∅
.
(2)
Idempotence
:
푓
(
푓
(
퐴
))
=
푓
(
퐴
)
.
(3)
Monotonicity
:
퐴
⊆
퐵
implies
푓
(
퐴
) ⊆
푓
(
퐵
)
.
3
As applications of our theory, we shall discuss in detail two concrete interpretations of closure
operators below, but in the abstract one may think of the operator as a model of imperfect perception.
The closure operator describes a coarse perception of reality: one that does not distinguish between
퐴
and
푓
(
퐴
)
. The use of closure operators in topology follows this interpretation, as
푓
(
퐴
)
consists
of the points that are arbitrarily close to the elements of
퐴
.
The following are examples of closure operators:
(1)
The
identity operator
is the closure operator
퐼
: 2
푋
→
2
푋
such that
퐼
(
퐴
)
=
퐴
for every
퐴
∈
2
푋
.
(2)
The
trivial closure operator
is defined as the closure operator
푓
: 2
푋
→
2
푋
such that
푓
(
퐴
)
=
푋
for every nonempty
퐴
∈
2
푋
.
(3)
A
binary classifier
is an operator
푓
퐶
, associated to a set
퐶
⊆
푋
. So that
푓
퐶
(∅)
=
∅
, and for
nonempty
퐴
,
푓
퐶
(
퐴
)
=
퐶
if
퐴
⊆
퐶
and
푓
퐶
(
퐴
)
=
푋
otherwise.
(4) Given a function
푢
:
푋
→
R
,
푓
푢
(
퐴
)
=
{
푥
∈
푋
:
푢
(
푥
) ≤
max
{
푢
(
푥
′
)
:
푥
′
∈
퐴
}}
is the
strategically rational
operator defined from the function
푢
.
Of the preceding examples, binary classifiers
(3)
and strategically rational
(4)
operators will play
an important role in the paper. It is worth discussing these two classes of closure operators in some
detail before proceeding.
First note that a binary classifier gives rise to closed sets
푆
(
푓
퐶
)
=
{∅
,퐶,푋
}
, which are the smallest
kind of non-trivial topology possible. In our paper, we shall think of these as simple classifiers.
Binary classifiers are, moreover, a special case of strategically rational operators: Indeed for a given
퐶
⊆
푋
we may define
푢
=
1
푋
\
퐶
, and observe that
푓
퐶
=
푓
푢
.
Turning to strategically rational operators, one may interpret
푢
:
푋
→
R
as a utility function,
and
max
{
푢
(
푥
)
:
푥
∈
퐴
}
as the best utility achievable from a set
퐴
⊆
푋
of possible choices. Then
푓
푢
(
퐴
)
is the largest set of choices that an agent with utility
푢
would consider to be as good as
choosing from
퐴
. In particular, if
푓
푢
(
퐴
)
=
푓
푢
(
퐵
)
then the agent is equally happy choosing an item
from
퐴
as from
퐵
.
The “strategic rationality” terminology is borrowed from Kreps
[16]
, and will be useful when
we talk about applications to decision theory. It suggests an agent who is forward looking, and
identifies a menu with the element they plan to choose from the menu. Alternatively, strategically
rational operators can be seen as abstract counterparts to the simple linear classifiers used in
3
Kuratowski imposes
푓
(
퐴
∪
퐵
)
=
푓
(
퐴
)∪
푓
(
퐵
)
, a stronger property than monotonicity.
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
38
machine learning: we shall also emphasize this interpretation when we talk about applications to
machine learning.
Finally note that all that matters about
푢
in the definition of
푓
푢
is the weak order represented
by
푢
; that is,
푥
⪰
푦
iff
푢
(
푥
) ≥
푢
(
푦
)
. In other words, if
푢
=
ℎ
◦
푣
, for a strictly monotone increasing
function
ℎ
:
R
→
R
, then
푓
푢
=
푓
푣
. In the rest of the paper, we shall therefore write
푓
⪰
for strategically
rational closure operators, where it will be understood that
⪰
is a weak order over
푋
. Observe that
these coincide with the supporting half-spaces we introduced above.
Definition 2.
A set
퐴
⊆
푋
is
closed
with respect to a closure operator
푓
: 2
푋
→
2
푋
, if
퐴
=
푓
(
퐴
)
.
The set
푓
(
2
푋
)
of all closed sets with respect to the closure operator
푓
is the
topology
defined by
푓
,
and is denoted by
푆
(
푓
)
.
The terminology of closed sets and topology is justified by the following well-known result,
which we state as Lemma 1.
4
Lemma 1.
Let
푓
: 2
푋
→
2
푋
be a closure operator on
푋
, then the set of closed sets
푆
(
푓
)
is closed
under intersection and contains
∅
and
푋
. Indeed,
푆
(
푓
)
endowed with the meet and join operators
퐴
∧
퐵
=
퐴
∩
퐵
and
퐴
∨
퐵
=
푓
(
퐴
∪
퐵
)
is a lattice that has
∅
and
푋
as its (respectively) smallest and
largest elements.
Moreover, if
푆
is any subset of
2
푋
that is closed under intersection and contains
∅
and
푋
, then there
is a unique closure operator
푓
푆
: 2
푋
→
2
푋
such that
푆
(
푓
푆
)
=
푆
.
3.3 Application 1: A theory of classifiers
Interpret the elements of
푋
as data, and suppose given a finite set
퐿
of
labels
. A
labeling corre-
spondence
is a set-valued function
Φ
:
푋
⇒
퐿
that associates with each data point
푥
∈
푋
a subset
of labels
Φ
(
푥
)
.
Given a labeling correspondence
Φ
:
푋
⇒
퐿
, we define a
classifier
as a function
푓
: 2
푋
→
2
푋
with
푓
(
퐴
)
=
{
푥
|
푥
∈
푋,
Ñ
푦
∈
퐴
Φ
(
푦
) ⊆
Φ
(
푥
)}
for every
퐴
⊆
푋
.
The interpretation of a labeling correspondence is straightforward. It attaches a set of labels to
each data point. We interpret each label as a single feature or property attached to each data point.
Hence, attaching two different labels
푙
1
,푙
2
∈
퐿
to a data point
푥
∈
푋
,
Φ
(
푥
)
=
{
푙
1
,푙
2
}
, is interpreted
as if the data point
푥
has both of those properties.
To understand the definition of a classifier, assume that the classifier
푓
, associated with a labeling
correspondence
Φ
. Given a data point
푥
⊆
푋
,
Φ
(
푥
)
is the set of all labels associated with the point
푥
. To find the set of data points in the same class (or category) as
푥
, we need to consider all data
points with at least all the labels of the data point
푥
. This is precisely the definition of
푓
(
푥
)
.
More generally, for a given set of data points
퐴
⊆
푋
,
푓
(
퐴
)
is the set of all data points that at
least have all the labels in common with all points in
퐴
. The idea is that if a decision-maker wants
to find all data points that are in the same class as the observed data points in
퐴
(without any other
information), she should consider all points
푓
(
퐴
)
.
Remark.
A classifier derived from a labeling function is a closure operator: The extensivity and
monotonicity properties are simple to verify. To show idempotence, notice that by monotonicity
푓
(
퐴
) ⊆
푓
(
푓
(
퐴
))
. Hence, we only need to show that
푓
(
푓
(
퐴
)) ⊆
푓
(
퐴
)
. Assume that
푥
∈
푓
(
푓
(
퐴
))
.
By definition,
Ñ
푦
∈
푓
(
퐴
)
Φ
(
푦
) ⊆
Φ
(
푥
)
. We know that for every
푦
∈
푓
(
퐴
)
we have
Ñ
푧
∈
퐴
Φ
(
푧
) ⊆
Φ
(
푦
)
.
Hence,
Ñ
푧
∈
퐴
Φ
(
푧
) ⊆
Ñ
푦
∈
푓
(
퐴
)
Φ
(
푦
) ⊆
Φ
(
푥
)
. Thus,
푥
∈
푓
(
퐴
)
. As a result,
푓
satisfies the idempotence
property.
4
In the context of convex geometry, which is most relevant for our paper, the result has been noticed in Edelman and
Jamison [10]. But the result is well known; see, for example, Ward [22] and Kuratowski [17].
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
39
{
푎,푏,푐,푑
}
{
푎,푏,푑
}
{
푎
,푏
}
{
푎
,푐
}
{
푎
}
{
푏
}
{
푐
}
{
푑
}
∅
Fig. 1. The lattice associated with the labeling correspondence
Φ
in Example 1.
The ideas may be illustrated by means of an example.
Example 1.
Consider a set of four data points
푋
=
{
푎,푏,푐,푑
}
. The set of labels is defined as
퐿
=
{
dog
,
cat
,
black
,
white
,
female
,
male
,
car
}
. Assume that the labeling correspondence
Φ
:
푋
⇒
퐿
is as follows:
Φ
(
푎
)
=
{
dog
,
black
,
female
}
Φ
(
푏
)
=
{
dog
,
black
,
male
}
Φ
(
푐
)
=
{
cat
,
white
,
female
}
Φ
(
푑
)
=
{
car
,
black
}
The classifier associated with the above labeling correspondence has eight classes. Class1={a}
associated with the labels {
dog
,
black
,
female
}, Class2={b} associated with the labels {
dog
,
black
,
male
}, Class3={c} associated with the labels {
cat
,
white
,
female
}, Class4={d} associated with labels
{
car
,
black
}, Class5={a,b} associated with the labels {
dog
,
black
}, Class6={a,b,d} associated with the
labels {
black
}, Class7={a,c} associated with the labels {
female
}, and the last class is Class8={a,b,c,d}
associated with all data points in the set
푋
.
Figure 1 depicts the structure of the classifier and the associated lattice structure.
The topology
푆
(
푓
)
, represents all possible different
classes
of data points, and
푓
(
퐴
)
is the smallest
class that contains
퐴
. By Lemma 1, we know that the set of classes is closed under intersections.
Moreover, there is a lattice structure associated with the labeling correspondence. Indeed, we may
interpret a classifier through the topology it induces: Let
푥
∈
푋
be in two classes
퐴,퐵
∈
푆
, which
means that it has the properties of the classes
퐴
and
퐵
. Then, there is a class
퐶
∈
푆
, with the
properties of the classes
퐴
and
퐵
, such that
푥
∈
퐶
. The trivial class
푋
represents the set of all data
points, having every possible label.
These observations may be summed up in the following proposition.
Proposition 2.
Let
푋
be a set of data points. We have the followings:
(1)
Let
Φ
:
푋
⇒
퐿
be a labeling correspondence. The classifier
푓
: 2
푋
→
2
푋
associated with
Φ
is a
closure operator.
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
40
(2)
Let
푓
:
푋
→
푋
be a closure operator on
푋
. Then, there exists a set of labels
퐿
, and a labeling
correspondence
Φ
:
푋
⇒
퐿
such that the classifier associated with
Φ
is
푓
. Moreover, one choice
of
퐿
and
Φ
is achieved by defining
퐿
=
푆
(
푓
)
and
Φ
:
푋
⇒
퐿
with
Φ
(
푥
)
=
{
푠
|
푠
∈
푆
(
푓
)
,푥
∈
푠
}
.
The representation in the second part of the above proposition is not unique. However, section 5
provide the minimum number of labels needed to represent a given classifier.
3.4 Application 2: Decision theory
Consider a decision-maker who is going to ultimately choose an element
푥
∈
푋
, but who is first
presented with a choice among possible
menus
퐴
⊆
푋
. After selecting the menu
퐴
, the consumer
chooses an alternative from
퐴
.
We may think of a consumer, for example, who first decides between retail shops, or restaurants,
and then chooses an item from the shop, or a meal on the menu. But the situation is quite general:
Most problems in dynamic choice involve first selecting an alternative that will determine what
may be chosen in the future: think, for example, of choosing how much to consume and how much
to save, which will determine what is affordable in the future. Or making a career choice, which
may determine the set of geographical location one may ultimately be able to choose among to live
in. We capture the situation in the abstract as a problem of choosing a set in
푋
. In particular, we
shall focus on agents who have a
preference for flexibility.
Consider a decision maker, say Alice, who chooses according to a preference relation
⪰
on
푋
=
{
푥,푦,푧
}
. If Alice can perfectly predict her choice, she will only care about the best option
available in a menu. So if, for example,
푥
≻
푦
≻
푧
are Alice’s preferences, then she will be indifferent
between any menu that contains
푥
, and between any menu that does not contain
푥
but that contains
푦
. Alice’s situation may be described through a strategically rational operator, with
{
푥,푦,푧
}
=
푓
⪰
({
푥
})
=
푓
⪰
({
푥,푦
})
=
푓
⪰
({
푥,푧
})
=
푓
⪰
({
푥,푦,푧
})
.
Bob, in contrast, may be unsure about his ultimate choice from a menu. He might have the same
preference as Alice, or he might actually have the preference
푦
≻
′
푥
≻
′
푧
that ranks
푦
first. Observe
that, as a consequence, Bob will strictly prefer the menu
{
푥,푦,푧
}
to
{
푥
}
, or to
{
푥,푧
}
, as the larger
menu does not close any doors for Bob. If, in the end, Bob’s preference is
⪰
′
, then
{
푥,푦,푧
}
lets him
get his favorite choice. Indeed for Bob we need an operator with
{
푥,푦,푧
}
=
푓
({
푥,푦,푧
})
=
푓
({
푥,푦
})
≠
{
푥,푧
}
=
푓
({
푥
})
=
푓
({
푥,푧
})
.
Bob’s preferences cannot be captured through a single strategically rational operator. Actually
for him we have that
푓
=
푓
⪰
∩
푓
⪰
′
, and thus Bob’s operator
푓
is derived from
two
strategically
rational operators.
Now we see, as a preview of our results, that Bob’s behavior is
more complex
than Alice’s because
we need two basic strategically rational operators to capture Bob’s choice, while one suffices for
Alice.
In all, Bob has a “preference for flexibility,” a model that was first proposed by Kreps
[16]
.
5
In
Section 7 below we briefly recap Kreps’ model and show what our results have to say about the
resulting representation.
5
Kreps’ model motivated a sizable literature in decision theory; see, for example, Dekel, Lipman, and Rustichini
[7]
, Dekel,
Lipman, Rustichini, and Sarver
[8]
, Gul and Pesendorfer
[12]
, Nehring
[18]
, Nehring and Puppe
[19]
, Chateauneuf and
Jaffray [5], and Chambers, Miller, and Yenmez [4]
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
41
4 A GENERAL REPRESENTATION OF CLOSURE OPERATORS
A key motivation for the study in our paper is the next result, due to Chambers, Miller, and Yenmez
[4]
, which shows that a closure operator may be found as the intersection of supporting half-spaces.
6
Theorem 3.
A function
푓
: 2
푋
→
2
푋
is a closure operator iff there exist weak orders
⪰
1
, . . .,
⪰
푘
on
푋
, such that
푓
(
퐴
)
=
Ù
푖
∈{
1
,...,푘
}
퐻
(⪰
푖
,ℎ
퐴
)
.
(1)
Using the language introduced above, we may rephrase this result as follows:
Corollary 4.
A function
푓
: 2
푋
→
2
푋
is a closure operator iff there exist strategically rational
operators
푔
푢
푖
,
1
≤
푖
≤
푘
, so that
푓
(
퐴
)
=
Ù
푖
∈{
1
,...,푘
}
푔
푢
푖
(
퐴
)
.
(2)
Our first result is an elaboration on Theorem 3. It serves to introduce the notion that operators
generate more complex operators, and how the resulting topologies are connected.
Theorem 5.
Let
푔
1
, . . .,푔
푘
be closure operators on
푋
, then
푓
: 2
푋
→
2
푋
defined by
푓
(
퐴
)
=
Ù
푖
∈{
1
,...,푘
}
푔
푖
(
퐴
)
is a closure operator. We say that
푓
is
generated
from
푔
1
, . . .,푔
푘
.
Moreover, if
푓,푔
1
, . . .,푔
푘
are closure operators on
푋
then
푓
is generated from
푔
1
, . . .,푔
푘
iff
(1)
푆
(
푔
푖
) ⊆
푆
(
푓
)
for all
푖
∈ {
1
,
···
,푘
}
;
7
(2)
and if
퐴
∈
푆
(
푓
)
and
푥
∉
퐴
, then there exists a closure operator
푔
푖
∈ {
푔
1
, . . .,푔
푘
}
such that
푥
∉
푔
푖
(
퐴
)
.
Theorem 5 warrants some remarks. Assume that the classifier
푓
is generated by
푔
1
, . . .,푔
푘
. By
the first condition in the theorem, the topology
푆
(
푓
)
is finer than that of any constituent operator
푆
(
푔
푖
)
.
The second condition is similar to the Separating Hyper Plane Theorem in convex geometry.
It means that if
퐴
is a closed set of
푓
and
푥
∉
퐴
, then there should be a separating classifier
푔
푖
∈ {
푔
1
, . . .,푔
푘
}
that detect that
푥
is not in the closure of
퐴
with respect to
푔
푖
.
5 COMPLEXITY OF OPERATORS
In the Machine Learning literature, a neural network is built from a set of simple classifiers. Given
a data set, and a set of labels, a researcher can add many linear classifiers to build a large neural
network that can shatter data points to the correct classes. More generally, a researcher can combine
many different functions to form a complex function with lots of parameters to shatter the set of
data points to the correct classes.
We proceed with an analogous motivation: in Theorem 5, complex operators are built up from
simpler ones. In the abstract, discrete, setting of our paper, there is no useful notion of norm or
approximation, but the representation in Theorem 5 serves as a starting point. When
푓
=
∩
푔
푖
, we
may think of
푓
as being more complex than any of its building blocks
푔
푖
, just as a neural network is
more complex than its simpler constituents. In fact, using the theorem, we may associate complexity
to the topology defined from each operator:
6
Note also that Richter and Rubinstein [20] contains a similar result for linear orders.
7
This statement is Theorem 5.1 in Ward [22].
Session
1A:
Decision
Theory
∙
EC
’22,
July
11–15,
2022,
Boulder,
CO,
USA
42