You can have a single transaction that does both fees.  That way either neither pays the fee or both do.

The protocol would be

Step 1) Commit to hashes

Alice and Bob create 1000 key pairs.

Alice sends hash(alice_public_key_array) and hash(alice_fee_unlock)
Bob sends hash(bob_public_key_array) and hash(bob_fee_unlock)

TTP is the trusted third party.

The fee transaction has 3 output (plus any change outputs)

A) pays fee to Alice but requires , otherwise it goes to TTP after 7 days
B) pays fee to Bob but requires , otherwise it goes to TTP after 7 days
C) pays to TTP after 7 days

Output C is a 1 of 2 multisig to commit to hash(hash(bob_public_key_array) | hash(alice_public_key_array))

Note:  Both parties could exchange a list of TTPs and then pick one of the intersection.  The default software could assign the author as one and allow -add_ttp_key as an option (and probably -author_ttp_disable)

Step 2) Choose

Once the fee transaction is broadcast/confirmed, the choose step can happen.

Alice and Bob pick M and N.

Alice sends Bob and the private keys except key N.
Bob sends Alice and the private keys except key M.

Both parties verify the key pairs and then assume the one they didn't pick is probably ok.

As long as the key pairs were valid and the TTP is honest, then an attacker can reclaim his fees (less the TTP's fee).

Step 3) Deposit

Bob pays to an output which gives the money to Alice, unless he releases his private key within 2 days.

He can re-claim his deposit immediately, but that means he ends up bailing out of the protocol.

Step 4) Alice bail in

Alice pays her bail-in to a multisig.  If Bob reclaims his deposit, then she can reclaim her bail-in.

Step 5) Bob bails in

Bob pays his output.  He can reclaim his output after 1 day.  Alice can claim it immediately but then she has to release the fee unlock code and also give Bob her private key, so he can claim his output.

At the end of this step, Bob is stuck.  If he reclaims his deposit, then he lets Alice get her bail-in back and she can also claim his bail-in.

Step 6) Alice spends her output (and provides alice_priv_m).

For this step, Alice would also have to provide alice_fee_unlock, and alice_priv_m.  Bob can reclaim his fee and also claim his output (and his deposit).

Step 7) Bob can spend the altcoin output

For this step, Bob would also have to provide bob_fee_unlock, so Alice can reclaim his fee.

Step Bob reclaims his deposit

Bob can reclaim his deposit, since the info released is stale at this point.

So, by the time Bob's deposit is locked, Alice has paid a fee transaction and has also locked her bail-in.  I think that is reasonable.