The way that negative interest groups are implemented today is through the additional bids mechanism.
We see several problems with that for Native advertising around the order of ads that are returned.
For example, say our placement displays 3 ads:
ad1, ad2, ad3

They are displayed in this order since ecpm(ad1)>ecpm(ad2)>ecpm(ad3)

Now let's say that ad1 has a suppression rule (negative targeting). Now in the current flow, our ad server will filter ad1 and bring ad4 so the new order is ad2, ad3, ad4. Let's say that this is the optimal order.
If we want to use Protected Audience for suppression, will have to return an additional bid of ad1 with the negative targeting and a fallback item ad4 for that auction. So the new order is now ad4, ad2, ad3 which is not the optimal order.

We were thinking that to solve this, there might be a way to pass the negative interest groups to the ad server, in the contextual ad request, without compromising the users' privacy by using a Bloom-filter (or something similar) that represents the Negative Interest groups for the ad server to query. This can even be very noisy and contain data that are not real negative interest groups, it doesn't matter, as long as the negative interest groups are there. It's even ok that in some low probability it would remove some of the negative interest groups to further enhance privacy.