A couple of people have already pointed out similarities to mtg/hearthstone so I thought it might be a good way to think explicitly about the rules/specific cards (some reasoning behind it, but these aren't predictions, just a way to solidify my intuitions):

- Hearthstone-like mana system since no lands (Lotus works like innervate?)
- Creatures regenerate like in mtg, otherwise bigger creatures could just be traded off with 2 or 3 smaller ones and it wouldn't be so big a deal to lotus one of them out
- Starting life total is balanced in a way that good aggro decks and good control (that is lotus ramp) decks have approximately even odds against each other

- Archetypes:
   - Good guy tribal: Battalion is some sort of lord for guards , knights, vigilantes and copies of itself (making it one of the inexpensive cards that doesn't do too badly with lotuses, because it makes sense to ramp out things that lord each other)
       - (intuition stats: guard: 1 mana 1/4, knight: 3 mana 3/3, vigilante: 3 mana 4/2, battalion: 2 mana 2/2 and buff all others by +1/+1. something like this would explain why battalion/guard > battalion/knight > battalion/vigilante)

   - Lotus ramp: Lotus out a big thing, big thing clears the board and wins the game. Dragons seem worse at this than Angels, emperors are slower than both 
       - (intuition stats: Angel: 5 mana 4/6, Dragon: 6 mana 5/6, Emperor: 7 mana 7/7, Lotus: gain 2-3 mana this turn only)

   - Evil equip: Sword of shadows is presumably some kind of equipment you put on Pirates, Hooligans or Minotaurs to give them stats and it can be reused when the creature has died (or maybe it's an anthem sort of thing, but that would go against its name). Pirates have a high winrate in general, and work well with both Swords and Angels, so I would expect Pirate to be overstatted for its cost and slightly defensive-leaning. Minotaurs don't have a great winrate and are not great with Swords, but are the other "low-cost" thing that works reasonably well with lotuses, and game nr. 185896 gives a hint of what minotaur does (mainly, having a minotaur unopposed gives you a short clock, 2-3 turns maybe?). 
       - (intuition stats: Pirate: 1 mana 2/3, Hooligan: 2 mana 3/2, Minotaur: 4 mana 7/1, Sword: 0 or 1 mana +2/+1 equip for 0)

- presumably, Swords technically also work with Dragons and Emperors, but those are big enough that it doesn't make much of a difference, same with Angels and battalions.

Strategy:

- diverse decks do well because it's important to curve out. Yugi's gonna be hitting the perfect curve, which means we have to defend early and outvalue late. With my completely made-up stats Yugi's curve would look something like: Pirate/Sword into Hooligan into Lotus Angel into Minotaur into Knight/Battalion into Dragon into Emperor.

- one way to do the "outvalue late" part of the plan is going with angels and at least 1 emperor. Which means we'll need lotuses. For the "defend early" part, this strongly depends on how exactly lotuses work. It might be that if we have, say, 5 Lotuses and 5 Angels, we can double Lotus into Angel turn 1 which already stops the aggro cold. But if you can only play one Lotus a turn or something, we're gonna need some smaller creatures.

- especially for smaller creatures, exact stats and things like whether double-blocking is a thing are hugely important. The first idea would be to just take a bunch of pirates, but then a pirate with a sword probably just eats those and it's not clear whether the saved life total makes up for the lost value.

- another way is stacking swords on things and hoping that that suffices to at least trade with Yugi's big creatures in the later turns or, depending on the cost of swords, to out-aggro him (seems unlikely against a perfect curve)

- starting Hand size is really hard to speculate on, but we can try anyway: Main observation is that lotuses don't work with aggro cards. If the starting hand size was something like 7, there would be no reason for that. It seems like, unless they have a sword/battalion or some good high-cost cards, aggro decks quickly run out of steam. Aggro can stay aggressive for about as many turns as it can double-spell to keep board control and it would seem that that limit is reached pretty early on, if a lotus decreasing that number by 1 is more relevant than a big boost in turn 1-2 board control. So my guess would be something like 2-3 cards in opening hand, with one drawn every turn. Yugi loves a small hand size, so this is something we'll need to keep in mind.

2x Angel, 3x Minotaur Hooligan, 3x Pirate, 4x Sword.

Absolutely no reasoning was applied in reaching this conclusion; all my attempts to solve this one analytically met dead ends. Instead, I copied the ML-based approach gjm won Defenders of the Storm with - except using gradient descent to search deckspace instead of trying all possible options - and got an answer I have no way to explain or evaluate. I'm very curious to see if this works!

• As a general rule, a more diverse deck leads to a better outcome. (Our opponent has the most diverse deck; this is worrying.)
• Victory seems to be more down to synergies within a player's own deck than counters to their opponent's cards.
• Apparent synergies: Angels like Lotuses, Emperors like Dragons, Pirates like Swords.
• Having too many of the same card is always bad, but the diminishing-return point and the level of damage caused by homogenity both depend on the card. You need >4 Angels for it to start hurting you, but having eight of them sends your odds of victory to <20%; meanwhile, Vigilantes aren't that great, but you can have a deck that's two-thirds composed of them without your win chance going below 40%.
• The four obviously and inarguably evil cards are bizarrely middle-of-the-road in terms of average effectiveness. Banality of Evil?
• A GBM with treedepth=2 beats one with treedepth=1 and one with treedepth=3. This (weakly) suggests there are two-way interactions between cards, but no three-way interactions.

I had a transcription error in the original draft of this post: it should have been 3x Hooligan, not 3x Minotaur.

1. Filter decks that fought against a similar to the rivals deck, using a simple measure of distance (sum of absolute differences between the deck components)
2. Compute a 'score' of the decks. The score is defined as the sum of 1/deck_distance(deck) * (1 or -1 depending on whether the deck won or lost against the challenger) 
3. Report the deck with the maximum score

So my submission would be: [0,1,0,1,0,0,9,0,0,1,0,0]

Code

There doesn't seem to be a killer card that dominates one or more of the others.

Having a balanced deck seems to be important, as the probability of winning  consistently declines as the number of distinct cards falls, and the maximum number of a single card rises.

The cards clearly aren't equivelant as some groups of cards do consistently better than others. 

I haven't been able to get a grip on what the rules might be, but peering through the fog suggests that the following combination won't be too bad:

 2 Alessin, Adamant Angel
 0 Bold Battalion
 1 Dreadwing, Darkfire Dragon
 2 Evil Emperor Eschanous, Empyreal envoy of entropic dead
 0 Gentle Guard
 1 Horrible Hooligan
 0 Kindly Knight
 2 Lilac Lotus
 1 Murderous Minotaur
 1 Patchy Pirate
 0 Swords of the Shadow
 2 Virtuous Vigilante

This is my provisional entry for both the main and PVP objectives.

Seems like you want to include A, L, P, V, E in your decks, and avoid B, S, K. Here is the correlation between the quantity of each card and whether the deck won. The ordering is ~similar when computing the inclusion winrate for each card.

Alessin_Adamant_Angel_Deck_A_Count: 3 

Murderous_Minotaur_Deck_A_Count: 1 

Patchy_Pirate_Deck_A_Count: 6 

Sword_of_Shadows_Deck_A_Count: 2 

This deck has around a 70% probability of beating the rival. I used a LightGBM booster trained on all the data. The out-of-sample accuracy before dumping all the data in was an AUC of 0.66, but the model is well-calibrated, so I'm confident in the ~70% probability.