(I'm taking my definition of a cardinal characteristic from Blass' excellent article http://www.math.lsa.umich.edu/~ablass/need.pdf, which cites Vojtas/Fremlin/Miller; theirs is more general, but I'm already interested in this more restrictive context.)

Fix a binary relation $S$ on $\omega^\omega$. A set $X\subseteq \omega^\omega$ is *$S$-adequate* if for any $x\in \omega^\omega$ there is a $y\in X$ such that $xSy$. Assuming the reals are well-ordered, the cardinal characteristic associated to $S$ is then the minimum cardinality of any $S$-adequate set. For example, taking $S$ to be domination, $\le^*$, yields the dominating number $\mathfrak{d}$.

My question, roughly, is: to what extent is there a meaningful theory of cardinal characteristics in contexts where choice fails, perhaps very badly?

One approach that seems interesting to me is via "theta-like" cardinals. Recall that $\Theta$ is defined to be the smallest ordinal onto which $\mathbb{R}$ does not surject; see value of Theta in ZF+AD for some facts about $\Theta$ in the context of $AD$, which is where it is usually studied. We can define analogues of $\Theta$ for cardinal characterstics, as follows: for $S$ a binary relation on $\omega^\omega$ (or similar) we define $\Theta_S$ as the supremum of the cardinals onto which every $S$-adequate set surjects. Assuming $\mathbb{R}$ is well-orderable this is of course equal to the standard cardinal associated with $S$; in the absence of such a fact, this is still a meaningful definition.

(Note that we could also define $\Theta_S$ as the supremum of the cardinalities which inject into every $S$-adequate set, but this seems less natural. For one thing, it is consistent that $\Theta_=\not=\Theta$, which is probably a bad sign.)

On to the questions:

(Q1) Is there work done on cardinal characteristics in the absence of choice, at all?

Note that there is work done - such as Blass' article, as well as Nicholas Rupprecht's thesis http://deepblue.lib.umich.edu/bitstream/handle/2027.42/77915/furikuri_1.pdf?sequence=1 - on computability-theoretic aspects of cardinal characteristics. This is really interesting stuff, but I'm looking for something more on the set theory side, ideally actually assigning specific ordinals to relations in a nice way.

In particular,

(Q2) What can be said about the various $\Theta_S$s as defined above?

canonicallyproduce witnesses to the pullback of $U$ failing to be an ultrafilter! This is neat: given a (non-principal) countably complete ultrafilter $U$ on $\aleph_1$ and a surjection $f: [0, 1]\rightarrow\aleph_1$, let $F$ be the pullback of $U$ along $f$ as above. Now define $L=\{r: \{x: x<r\}\in F\}$ and $R=\{r: \{x: x>r\}\in F\}$. Clearly $1\in L$, $0\in R$, and $L$ is closed upwards and $R$ is closed downwards: I claim $L\cup R\not=[0, 1]$. If so, then pick $a\in [0, 1]-(L\cup R)$; neither $\{x<a\}$ nor $\{x>a\}$ are in $F$. $\endgroup$ – Noah Schweber Jan 5 '15 at 22:25