Why not:
CREATE TABLE Connections (
connectionsid PRIMARY KEY AUTOINCREMENT INT NOT NULL,
village INT NOT NULL,
army INT NOT NULL,
);
(and if table is expected to have more reads than writes maybe INDEXes for village and army too)
What you need FOREIGN KEYs for (I never used it, maybe because I use MyISAM which is quite primitive)? Is it for cascade delete or something?
I'm definitely no expert on SQL, so you're probably right.

I had just assumed that using village/army as a primary key would be more efficient, since there are fewer variables. I was assuming that the connections are two-way, so there would be no need to duplicate a certain village/army combination. Are single integers a better choice for primary keys?
Now that you mention it, I have no idea what foreign keys are for.

I always assumed they auto-indexed or something. From what I see online this does not usually appear to be the case. Apparently it throws an error if you try to delete or alter the primary key of a row being referenced elsewhere, and there are some commands that affect all children of a given record. I should really learn this stuff.

So yeah, what I said up there was probably not the best way to do it, and I wouldn't know what the best way is, but it should work, I think.