Great problem! The solution below is extremely wordy, so any suggestions to improve it would be appreciated!

arkobanerjee wrote: Great problem! The solution below is extremely wordy, so any suggestions to improve it would be appreciated!

This problem ends up being complicated to phrase a solution to, with every solution either being imprecise, wordy, or requiring extra ideas beyond what's necessary to solve the problem. With that said, here's my solution, which falls into the third category:

The answer is no, and the construction is where all the mafia are lined up. Consider the general claim that if it is Tony's turn with \(m\) mafia and \(2m\) town, he doesn't have a strategy. Induct on \(m\). Note that the only information Tony can obtain is that if a counter is removed, at least 1 of its neighbors is a mafia counter. Thus, pretend that Madeline can exchange the counters at any time as long as the new construction is compatible with the information that has been produced. For the sake of simplicity, assume Tony removes one counter at a time and can choose to end his turn whenever. The base case is \(m=1\). On the first turn, one can easily verify that Tony may not move, using the fact that Madeline can switch the mafia counter with either of the town counters depending on Tony's move. Then, Tony is left with \(MT\) on the next turn with no information (except that at most one of them is mafia), which means that he loses (also easy to verify). Now, I claim that Madeline can begin with the configuration \(M_1M_2\ldots M_kT_1T_2\ldots T_{2k}\) such that \(T_{2k}\) and \(M_{1}\) are adjacent. We employ the following algorithm. If Tony tries to remove any mafia counter on his first turn, swap the mafia counter with the town counter adjacent to \(M_k\), so that he removes only town counters. If he moves any town counter, Madeline can use \(M_k\) to steal the adjacent town counter if there are an odd number of town counters remaining (so that there are now \(2i<2k\) town counters). Madeline can then declare \(k-i\) of the mafia counters to effectively be deleted (because the mafia counters lie in one contiguous strip, this is okay even if Tony chooses not to believe her), and induction finishes, as Tony has no other information. Thus, Tony does not remove any mafia counters, and Madeline uses \(M_k\) to removes \(T_1\). Then, Tony knows that at least one of \(T_2\) and \(M_k\) are mafia counters. Assume he doesn't try to remove any other counters that are not \(T_2\) or \(M_k\), as Madeline can proceed as before. If he does nothing, \(M_k\) removes \(T_2\) so that \(M_k\) is revealed as mafia and effectively deleted. If he only removes one of the two, we can switch the two to force him to remove \(T_2\). Then, Madeline can declare \(M_k\) as a mafia counter. If he removes both, Madeline allows the move. In each of the 3 cases, the three counters \(T_1, T_2, M_k\) are removed. It can remain Tony's turn, and he knows no information about the rest of the counters, so the induction finishes. This resolves every possible scenario, so we're done.

The answer is no. In fact, we prove the following generalization: if the game starts with $n$ unknown mafia, $m \leq 2n$ unknown town, $p$ known mafia, and $q$ adjacent pairs of counters such that it is known exactly one of these is town and one is mafia (but not which is which), then Tony cannot win. Call the aforementioned pairs sus. The problem is specifically for $(m,n,p,q)=(673,1346,0,0)$. This is by induction on the number of counters $m+n+p+2q$, with the base case of zero counters being obvious. Call a check a Tony move where he selects the empty set. First, suppose Tony does not check on the first turn. Suppose he removes $a$ unknown players, $b$ known mafia, $c$ sus pairs completely, and $d$ sus pairs partially (i.e. one in each pair). It could be the case that all of the removed counters were town and as many unknown town as possible were removed. In this case, the bad news is publicly announced to Tony (in particular, the $d$ mafia part of partially-removed sus pairs become known). It is clear that this is equivalent to some case with a smaller number of players where Tony checked on the first move, so by hypothesis Tony loses. Now suppose Tony checks the first turn. If there are any sus pairs, Madeline picks one arbitrarily and removes its town member; otherwise, Madeline arbitrarily removes a town member. Call the removed counter $c$. If $c$ was part of a sus pair, then Tony loses a sus pair and gains a known mafia, then the resulting game state has less players and still has $m \leq 2n$, since in fact neither of these quantities change (clearly Tony gains no additional information). Otherwise, there are no sus pairs. If there was a known mafia adjacent to $c$, then Tony in fact gains no information whatsoever, and the number of town decreases by $1$, so inductive hypothesis handles this as well. Therefore, suppose that both counters adjacent to $c$ were unknown. If Tony didn't remove either counter adjacent to $c$, then Madeleine could reveal that there was exactly one town and one mafia adjacent to $c$, thus forming a sus pair, and then it could also be the case that as many of the unknown counters that Tony removed were town (and this information would be revealed to). This game state is equivalent to some with $m \leq 2n$ (either we end up with $m=0$, or the number of unknown town removed across Madeleine and Tony's moves is at least $2$ while exactly one unknown mafia is removed), and has less counters that Tony started by checking in, so Tony loses by hypothesis. If Tony removed both counters, then it could also be the case that there was exactly one town and one mafia adjacent to $c$, and as many of the removed unknown counters as possible were town. If this information is revealed, then the game state is still equivalent to some state with $m \leq 2n$, less counters, that Tony started by checking in, so Tony still loses. If Tony removed exactly one counter adjacent to $c$, then Madeleine could reveal that this removed counter was town, thus making the other counter known Mafia. It could also be the case that as many of the removed unknown counters as possible were Town, and this would be announced to Tony, so this is still equivalent to a game state with $m \leq 2n$ and less counters that Tony started by checking in, so Tony still loses! These cases finish the induction, so we are done. $\blacksquare$

Here's an alternate solution with expected value; I hope this is right but someone please check it, nice problem though. We proceed by induction to show that at least n mafia and at most 2n town people is a losing position for Tony, with base case n=1 immediate (and suffices to consider only equality, since less town is obviously worse). Define a \textit{switch} as a different position that doesn't change the information known. We claim that the config T_1T_2...T_{2n}M_1M_2...M_n is losing. Note that on the first move, if Tony tries to remove any subset, by shifting/switching the position by some cyclic number of places, we can get him to remove at least double of town than mafia (this is possible by expected value); assume henceforth he uses empty set first move. Madeline now removes T_{2n}. If Tony removes the counter to the right (WLOG) of T_{2n}, by \textit{switching} the position s.t. T_{2n} is T_1, no info is changed, but Tony removes a town, which reduces into inductive hypothesis; ergo, the first move does not actually guarantee Tony anything, so he either removes a random nonempty subset or does not remove anything, from which the former by expected value the position can be shifted s.t. he removes at least twice-1 towns than of mafia, which is inductive hypothesis, or in the latter, Madeline removes T_{2n-1}, and it's inductive hypothesis again (in this case, it's at least n-1 mafia and 2(n-1) town).

Never posted this shrug emoji $\boxed{\text{Tony cannot}}$. Assume Tony can assure a ``victory" of ending with at least one town counter. Consider the following initial arrangement of counters (where the left and the right are adjacent on the circle): \[ TTMTTMTTMTTM\cdots TTM \]where $T$ stands for town and $M$ stands for mafia. We will call the counter in the leftmost position as counter $1$, the second to the left as counter $2$, and so on until the $2019$-th counter. Tony's first move cannot be significant, since Tony must guarantee a victory, so WLOG assume that Tony removes no counters on his first move. Now Madeline removes counter $2$. Tony now knows that either counter $1$ or counter $3$ is a mafia counter, but not which one. Therefore, in order for Tony be able to guarantee victory, he must remove either both $1$ and $3$ or neither. He cannot remove any other counters, because he has no information about them, and cannot guarantee anything. Now, Madeline will remove counter $5$. As before, Tony knows that either counter $4$ or counter $6$ is a mafia counter, but not which one. Notice that Madeline removing counter $5$ does not give Tony any more information about counters $1$ and $3$. As before, on Tony's move, he will remove only counters $4$ and $6$, or remove none at all (he could still remove both $1$ and $3$ if he hadn't done so earlier, though). Madeline then continues this process, continuing to remove counters $3n-1$ for $1 \leq n \leq 673$. None of these moves gives information about the same counter twice, and Tony cannot guarantee to remove any Mafia counters without removing the same number of town counters. If Tony had removed counters $1$ and $3$, then $4$ and $6$, then $7$ and $9$, and so on until $2014$ and $2016$, then Madeline can remove $2018$, and Tony cannot guarantee victory. Therefore, Tony must \textit{not} have removed some pairs of counters. Therefore, after all of Madeline's $673$ turns removing $2$, $5$, \dots $2018$, the circle becomes \[ TMTMTMTM\cdots TM \]where there are $x$ $T$'s and $x$ $M$'s now. Notice the above operation by Madeline guarantees the $TM$'s are $2$ indices apart (in the original circle). We will now re-index this circle, with the leftmost counter as counter $1$, and the rightmost counter as the $2x$-th counter. Now it's Madeline's turn. She removes counter $1$. This immediately tells Tony that counter $2$ must be a mafia counter, and he removes it, along with any $TM$ (but not $MT$) pairs he wishes (these don't matter at all). Madeline now removes counter $3$, and similarly, Tony may remove counter $4$ safely, along with any $TM$ pairs he wishes. Madeline continues in this way, removing all the $T$'s in order from left-to-right. Tony can guarantee one mafia counter each turn, but this is not enough to stop Madeline. She will remove all the $T$ counters before Tony can remove all the $M$ counters. The game is now over, and Madeline wins.

No. Since Tony does not know the positions of the counters, Madeline can freely permute the counters as long as all removed counters still have an adjacent mafia counter. Divide the counters into adjacent groups of three, and suppose there is one mafia counter in each group. Madeline's strategy is to pick a group with $\geq 2$ counters remaining. If the group has $3$ counters left, she removes the middle counter. If the group has $2$ counters remaining, she removes one of the counters and sets the other one as mafia. If she cannot find a group with $\geq 2$ counters, then there are no town counters left. This guarantees that as long as there are still counters left, at least one of them will be a mafia counter.

Tony won't always be able to win. Consider the arrangement $TTMTTM\dots$, and separate the counters into groups $TTM$, $TTM$, $\dots$. Say that Madeline removes the middle town counter in a group, so the group is left with $T$ and $M$. Now Tony knows that at least one of the two adjacent counter is mafia. On the next move, Madeline can remove the remaining $T$ in the group, so we are only left with $M$. Then, Tony knows for sure that the $M$ is mafia, so he removes it(as he must eventually) and we are left with $672$ groups, so we can induct down with our base cases of groups $= 1$ being true(as Tony is not sure which counter is mafia until all town are gone).

This problem is sus