The hard part of Pseudonym Pairs is how to mix the "tokens" from month to month. Here is an idea for a "roulette" mixer where you have no idea who you are paired with or the amount they deposited. Mixed with pairs. Fixes the problem of how to keep track of all different deposit preferences people could have, by just not keeping track of it. Mixers filled incrementally. Attackers are deterred from attacking random pairing because they pay equal transaction fees to join mixers. Lowest common deposit is used. Once paired, if deposit of peer is not acceptable, person calls "joinMixer()" again. Once either peer transfers their NYM to their mixer, the deposits are locked. If both transfer it, the mixing is complete. If just one transfers, the deposit is sent to them after a period of time has passed (even if they back out and join new mixer. )

To get more anonymity, mix multiple times, group-size becomes 2^sessions, sort of.

Sketch,

contract Mixer is NYM {

mapping(address => uint) deposits;

mapping(address => uint) index;
mapping(uint => uint) mixer;
mapping(uint => uint) transfers;

uint counter = 1;

function deposit() payable {
    deposits[msg.sender] += msg.value;
}
function joinMixer() {
    uint id = index[msg.sender];
    if(id != 0) {
        isLocked = transfers[id]^uint(msg.sender);
        require(isLocked == 0 || isLocked  = uint(msg.sender));
        mixer[id]^uint(msg.sender);
    }
    counter++;
    mixer[counter/2]^uint(msg.sender);
    index[msg.sender] = counter/2;
}
function readDeposit() returns(uint) {
    uint id = index[msg.sender];
    address peer = address(mixer[id]^uint(msg.sender));
    require(peer != 0 || peer != msg.sender);
    return deposits[peer];
}
function withdraw(uint _amount) {
    uint id = index[msg.sender];
    if(id != 0) {
        isLocked = transfers[id]^uint(msg.sender);
        require(isLocked == 0 || isLocked  = uint(msg.sender));
    }
    require(deposits[msg.sender] > uint _amount);
    msg.sender.send[_amount];
}

}

Summary

Honest actors (people wanting to mix their NYM) have an incentive to put in a deposit that would deter an attacker. Since people are probabilistically paired with a random other person, the deposit preference of their peer should average a good judgement. The reason a “roulette” mixer could work is because in Pseudonym Pairs, every person mixes exactly the same quantity of something (their proof-of-person “token”).

A "roulette" mixer for Pseudonym Pairs NYM tokens

Summary