How to learn (arbitrary) constraints for selecting the best candidate from a group?

In my classification problem, each instance is a group of possibly hundreds of candidates, from which only one should receive the label $True$ and the remainder the label $False$. For example, in simple unmarked matrix clauses in English, there is only a single subject (ignoring things like coordination, etc.). The candidates could be every 'word' in the sentence, and one of them (and only one) has to be assigned the label $subject$, while the remaining words get the label $not-subject$.

Suppose there are thousands of training pairs of the following form:

$y_0, \{f_1, f_2, f_3, ..., f_n\}$

...

$y_n, \{f_1, f_2, f_3, ..., f_n\}$

where $y_i$ denotes the label ($True$ or $False$) of the $i$th training instance and each feature function $f_j$ is categorical in that it returns values from a closed set, usually binary.

The input for unknown instances would simply be their associated values for their feature functions, but each 'instance' is actually hundreds of possible candidates, from which the algorithm must select only one, versus a typical classifier can assign each instance a label, irregardless of the global label assignment.

One solution I thought of was to learn the constraints somehow, and then build an OT grammar with those learned constraints. I'd then just learn whatever candidate evaluation metric optimizes the F-measure of k-folds cross-validation within the training set, and use the learned constraints and learned candidate evaluation metric given these learned constraints to create an algorithm for unknown instances.

So my solution would be:

Pick the constraints (and their weights) and pick the candidate evaluation metric (which is based on the constraints) which maximize the F-measure of k-folds cross-validation within the training set.

(note that the evaluation metric is in some sense arbitrary--e.g. there could be constraints whose violation by themselves is OK, but if they are both violated by the same candidate, it constitutes a fatal violation, even if the score is 'lowest.')

As I'm not an expert in ML or statistics, I am not sure if this approach is valid/worth the effort exploring (time is money so to speak), and if anyone would suggest different approaches, I would be happy to hear them.