Q:

How to properly design a VS match table in PostgreSQL? 

I've put some thought into this, and I haven't been able to come up with anything better.  So let me describe my problem, my current solution, and what I'd like to improve.  I've also got a few concerns, like whether or not my design is actually normalized or not. 
I'm making a database where I'd like to store VS Match information for tournaments.  For simplicity, lets just pretend they are chess matches.  1v1.  My current design is as follows:
CREATE TABLE matches(
  match_id bigserial PRIMARY KEY,
  tournament_id int NOT NULL,
  step int NOT NULL,
  winner match_winner,
  (etc.  etc.) 
  UNIQUE(match_id, tournament_id, step), -- Actual primary key
  FOREIGN KEY (tournament_id) references tournaments(tournament_id)
    ON DELETE RESTRICT
    ON UPDATE CASCADE
);

CREATE TABLE match_players(
  match_id bigint NOT NULL,
  tournament_id int NOT NULL,
  step int NOT NULL,
  player_id int NOT NULL,
  first boolean NOT NULL,
  PRIMARY KEY (match_id, tournament_id, step, player_id),
  UNIQUE (tournament_id, step, player_id),
  foreign key (match_id, tournament_id, step) -- keep em together
        references matches(match_id, tournament_id, step)
    ON DELETE RESTRICT
    ON UPDATE CASCADE,
  foreign key (player_id) references accounts(player_id)
    ON DELETE RESTRICT
    ON UPDATE CASCADE
);

-- Partial index, ensure no more than one "first" player exists per match
CREATE UNIQUE INDEX idx_match_players_primary
    ON match_players
    USING btree
    (match_id, tournament_id, step)
    WHERE first=true;

-- Also ensure that no more than one "not-first" player exists per match
CREATE UNIQUE INDEX idx_match_players_not_primary
    ON match_players
    USING btree
    (match_id, tournament_id, step)
    WHERE first=false;

To get the actual vs matches, I can simply join match_players to itself (on mp1.match_id = mp2.match_id, and mp1.first = true and mp2.first = false, where mp1 and mp2 are the two instances of matches).  The partial unique indexes ensure that a maximum of two players can be added. 
The database has been normalized this way because players are unordered.  As in, A vs B is the same as B vs A. I've added the "first" boolean to matches so that A vs B can be consistently displayed. ( I guess I could simplify it so that mp1.player_id < mp2.player_id... but the "first" boolean seems to work). 
The tournament_id and step are repeated in the 2nd table because they are needed on the Unique index of that table... to ensure that players only have one match per step of the tournament.  
Here's my primary question:

It is currently possible to have orphaned rows in the first table
(matches).  A match should have exactly two players in it.  In
particular, if a match exists in the matches table, it is possible
to have no rows matching it in the match_players table.  Is there a
way to ensure that matches ALWAYS has two associated rows in
matches_players ?  With the "first" method, I've definitely limited
the number of players per match to be less than 2... so figuring out
a way to ensure the minimum of 2 players would solve the problem. 

Here is one of my concerns:

As orphaned rows can exist still, are there any other data anomalies
that can crop up in this design?  I'm a bit uncomfortable with the
compound (triple) primary key in match_players, but I think the
compound foreign_key requirement covers me for that table. 

Thanks to anyone who can help me.  This is the best I could do so far.  I think if I solve the orphaned rows issue, then this design would be perfect.  I guess I can set up a cron job to clear out the orphaned rows, but I'd like to know if a cleaner design exists before settling on this one. 
I do think that a subquery in a check constraint would solve the issue, but alas, I don't think PostgreSQL actually supports that feature yet. 

A:

This is what I call the "forward looking problem" namely that you can have issues regarding data constraints that rely on rows not yet inserted.   The transaction as a whole has requirements that the individual rows do not.   Most databases offer few if any tools for addressing this problem.   Fortunately PostgreSQL offers you a few options. 
Denormalized "input buffer" using TOAST
The first approach would be to add a column to matches called match of type match_player[].  Then you'd store an array of players on the match here.  This would be materialized to the match_player table using a trigger.   This has significant penalties though in terms of development and foreseeing corner cases.   I do see it as a viable option but it is not an ideal one.   This avoids forward-looking constraints by flattening the table.   However it could only store step 0 records.   Once folks are making moves... that must be done by inserting only into match_players. 
Constraint Triggers
The second approach would be to create a trigger function which runs once per statement as an INITIALLY DEFERRED DEFERRABLE CONSTRAINT TRIGGER executing at the end of the transaction.   This would pull system columns from the table to look for rows inserted, and then would check to make sure that matches occur in the other table.   This is probably the best, general approach to solving the forward-looking constraint problem.