Definitional question: difference between a correspondence and a function

Question

Is there a difference between a correspondence and a function? For example, in game theory I am told that for a given strategy set, $\Sigma_i$, the best response given by $BR_i(\sigma_{-i})=\text{argmax}u_i(\sigma_i,\sigma_{-i})$ is a correspondence, not a function. But what is the difference?

Answer 1

It is called a correspondence here because there may be multiple best responses. That is, letting $|A|$ denote the cardinality of set $A$, it is not necessarily true that $|BR_i(\sigma_{-i})|=1$ for all $\sigma_{-i}$, i.e., that there is a unique best response to every profile of opponent play.

Consider a trivial game where all of your actions, $a_i \in A_i$, give you one util regardless of the opponents play. Then $BR_i(\sigma_{-i})=A_i$ for all $\sigma_{-i}$. It is a correspondence because $|A_i|>1$.

The term correspondence has a number of related meanings in mathematics. In economics, or at least game theory, we typically use it to mean a multivalued function. Actually, even that is a little misleading, because a function is only multivalued if at least one input is associated with at least two outputs. We say correspondence simply whenever it's not obvious that each input has a unique output -- a correspondence is a function that may or may not be multivalued.

Answer 2

The set-theory def'n of a function $f$ from $A$ into $B$ is that $f$ is a subset of $A\times B$ such that for each $x\in A$ there is a unique $y\in B$ with $(x,y)\in f.$ Any subset $S$ of $A\times B$ is called a binary relation. When $A=B$ it is called a binary relation on $A,$ and $xSy$ means that $(x,y)\in S.$ For a particular $x,y$ it is not logical to write $y=f(x)$ (for a relation $f$) unless $[(x,y)\land (x,z)\in f] \implies y=z.$ Better to write $(x,y)\in f.$ Sometimes it is convenient to write $f(x,y)$ to mean $(x,y)\in f.$