The system used in Germany to translate votes into mandates is complicated; it significantly grew in complexity in the last decade. I believe that a brief overview of former systems is helpful to understand how we ended up here.
Historical systems
A long-term Federal Election Law was not promulgated until 1956. In the first two elections, single-use Election Laws were promulgated.
In 1949, voters only had a single vote. Each state was allocated a certain number of MdBs (e.g. the state of Hesse was allocated 36). States were divided into districts such that the number of districts represented about 60 % of the total seats (e.g. Hesse would have somewhere around 22 districts; 22 were designated). With their single vote, voters would elect a district MdB using the first past the post (FPTP) system. All votes in a state were also aggregated and used to determine each party's share of MdB's from that state using a proportional system (d'Hondt); parties that received less than 5 % of the vote in that state did not receive seats unless if they won at least one district representative. Any seat a party was entitled to in excess of the directly elected members would be filled from a party state list; any directly elected member elected in excess of the party's proportional vote share would remain with the party (Überhangmandat). This happened twice: once in Baden (CDU) and once in Bremen (SPD), meaning the Bundestag hat 402 instead of the intended 400 members.
In 1953, voters had two votes. With the first vote they would vote for a district representative by FPTP. The second vote was used to determine the vote shares of the parties. As had been the case in 1949, each state received a fixed allocation of MdB's from the total of now 484 (e.g. Hesse received 44). Unlike before, exactly half of the seats were reserved for districts and the states were divided into districts by a Federal minister (not the states themselves). In addition, the 5 % threshold now applied federally, not on a per-state basis; as previously, winning at least one district exempted a party from the threshold. As had been the case, any seats a party was entitled to based on proportional representation at a state level in excess of their directly elected district members were filled from a party's state list; any districts a party won in excess of what they were entitled to based on proportional representation remained with the parties. There were three excess seats: 2 for the CDU in Schleswig-Holstein and one for the Deutsche Partei (German Party) in Hamburg.
The 1956 system
When crafting a long-term Election Law, the following features were seen as desirable and kept:
- local districts representing half of the MdBs should remain
- the seats allocated to each state should remain approximately the same across elections (except for adjusting due to shifting populations)
- parties should contest the election with state-based lists
- a federal threshold of 5 % of the vote share should apply
- proportional represenation should be the basis of seats in parliament
So, obviously, the first feature was keeping local FPTP districts; the number of local districts has always been half of the norm size the Bundestag should have. Party vote totals (the second vote, Zweitstimme) were now, however, aggregated at a federal level and total seats allocated to parties based on their federal vote share (if they exceeded 5 % or won at least 3 districts – more than the 1 district required in the previous elections). A party's federal seat allocation was then broken down into state shares based on the fraction of a party's total vote that came from that state. From this state seat share, the directly elected district candidates were subtracted and what was left filled from the state list. If a party won more districts in a state than their state seat share would allow, they kept the extra seats (Überhangmandate).
In the first two elections, a number of different parties had gained district victories but by 1957 this had consolidated to essentially only CSU (in Bavaria), CDU (in all other states) and SPD (in all of Germany) winning districts. At the same time, their share of the federal vote (CDU and CSU combined) was typically in excess of 30, often even 40 % each with larger shares coming from states where they won more districts. This meant that in the elections from 1965 to 1976 (inclusive) there were no Überhangmandate at all and the next three elections only featuring 1, 2 and 1, respectively. Of course, the fact that from 1961 to 1980 only four parties were represented in the Bundestag (CDU in all states but Bavaria, CSU in Bavaria, the two forming a single parliamentary group; in addition SPD and FDP) made things very simple. In 1983 the Greens crossed the 5 % threshold as the first additional party since the 1950's making Überhangmandate ever so slightly more likely but still an overall rare occurrance.
The old voting system tl;dr
With their first vote (Erststimme), voters elect a district representative by FPTP.
With their second vote (Zweitstimme), voters determine which parties are represented in the Bundestag by proportional representation. Parties need to gain 5 % federal vote share or with 3 districts to be considered. Party seats were broken down into state party seats. Any state party seats not filled by district representatives were filled by a state list; any excess district representatives kept their seat anyway.
Problems with the historical systems
With only three (1983–1990: 4; 1990–2005: 5) blocks in parliament of which three were only around 5 to 10 % and mostly unlikely to win a district, this system worked quite well. However, it contained paradoxes, the most important of which was the negative weight of votes.
Since district seats won in excess of a party's state allocation remained with a party (and no compensation existed), this could mean that winning less votes could be beneficial to a party's representation in parliament and, in extreme cases, could change the outcome of an election. One example which I will briefly reproduce here can be found in the actual election results of 1998 as outlined by Wahlrecht.de in German:
Of the SPD's 20,181,269 votes, the party gained 445,276 in Hamburg and 1,028,886 in Rhineland-Palatinate. This corresponds to 6 seats for Hamburg and 15 seats in Rhineland-Palatinate according to the Hare-Niemeyer method (also known as Hamilton's method) in use at the time. The SPD also won 7 districts in Hamburg and 10 in Rhineland-Palatinate. All was fine in the latter (five candidates from the list were elected) but in the former the 7 districts exceeded the 6 seats so one Überhangmandat was awarded.
Now imagine if the SPD had won 20,000 additional votes in Hamburg. This would not have affected the overall seat-by-party allocation at a federal level. However, using a total of 20,201,269 votes for the SPD, Hamburg's 465,276 votes correspond to 7 seats using the Hare-Niemeyer method while Rhineland-Palatinate's unchanged 1,028,886 votes now correspond to only 14 seats. The SPD does not receive the Überhangmandat in Hamburg but loses one in Rhineland-Palatinate leading to one seat less in parliament. By gaining votes, the party lost a seat.
This issue was brought to the Constitutional Court in the late 2000's which ruled in no uncertain terms that negative weight of votes was definitively unconstitutional and had to be fixed.
All changes that have been introduced since 2009 were intended, in some way, to fix the problem of negative weight of votes while keeping as many characteristics of the former system as possible.
In addition, the Constitutional Court was concerned about the effect too many Überhangmandate might have on the proportionality of the results. While historically no such additional seat had resulted in a change in majority, it worried that the distorting effect would become too large if more than 15 extra mandates were awarded (this corresponds to 2.5 % of the indended seats).
Attempts at fixing the system
In 2011 a reform was introduced that switched the order of allocations: instead of doing parties first, states second seats should be allocated to states first and then broken down to parties at a per-state level. However, this reform did not address the issue of Überhangmandate at all. It was brought before the Federal Constitutional Court which declared it unconstitutional within a year. It was never applied to any federal election. The way the court struck down the law meant that Germany was left without an election law altogether.
In 2013, just in time for the 2013 election, a new reform was agreed upon. To combat the phenomenon of negative weight of votes, it was decided that Überhangmandate should be balanced out by the Ausgleichsmandate that the question asks about. In the 2013 reform, all Überhangmandate were to be balanced out. Balancing out the extra seats meant that their absolute number no longer had to be restricted as they would not change the relative strength of parties in parliament.
Negative weight of votes can, in some sense, still occur; however, it will now either affect all parties simultaneously (i.e. more votes leads to less Überhangmandate which in turn will lead to fewer Ausgleichsmandate, not affecting proportionality) or it will only affect the allocation of seats to states within a party but not their overall seat count (i.e. more votes for a party in Hamburg might lead to Hamburg winning a seat at the expense of Rhineland-Palatinate but the party's total will remain the same).
There was another feeble fixing attempt in 2020 which said that up to three Überhangmandate will not be balanced. The wording was unclear but the Federal Returning Officer decided that this will mean three Überhangmandate in total across all parties in all states. These three were won by the CSU in Bavaria in 2021.
The balancing problem
As we can see from the excursion into history, the Bundestag has always had an intended size (598 since 2002). However, it has always been possible to win excess seats and this has happened in most elections. In 1994 and 2005, 16 additional seats were won by CDU and SPD (each time both sides profited). In 2009, this increased to 24, all favouring the CDU and CSU. One reason for this discrepancy was the SPD losing 10 % of the vote share, dropping below 25 %. While this mainly affected the second votes, the SPD also won significantly first votes, meaning significantly fewer districts. Conversely, the CDU and CSU won over 2/3 of the districts (218 of 299) with only 34 % of the vote share.
In 2013, Germany got a bit lucky in a certain sense. While the SPD remained relatively weak at only 25 % and while the CDU and CSU now won 236 of the 299 districts, the FDP failing to clear the 5 % threshold meant that the 41 % of federal vote share CDU and CSU received came close to 50 % of the vote share of threshold-clearing parties. This in turn meant there were less additional district seats that had to be balanced out and the final size of the Bundestag was only 631 seats.
2013, however, proved to be an outlier. In 2017, the CDU and CSU only received a combined 33 % despite winning 231 of 299 districts, the SPD remained weak at 20 %, the FDP returned to parliament winning almost 11 % and the AfD became the second new party to make it in after the Greens in 1983, also winning double-digits. Furthermore, as CDU and CSU are separate parties separately contesting seats, the fact that the CSU's vote share in Bavaria plummeted to 38.8 % – even though they still won almost all districts there – meant that there were now a lot of extra seats to be balanced out, leading to a total size of the Bundestag of 709 seats.
In the vote last Sunday, the CDU and CSU lost a great number of districts retaining only 143. Many of the lost districts were picked up by the SPD. This meant that the extra seats now affect both CDU and SPD to a certain extent and the overall effect is balanced out. This was not a given: had the CDU despite its poorer performance maintained a district landslide (e.g. due to the left-wing vote splitting between Greens and SPD as happened in a number of districts in Bavaria), we could have been looking at an overall size of up to around 900. This number remains a rough projection and is dependent on too many factors – in fact, estimates varied greatly – but the fact that it is approximately 150 % of the intended size and thus corresponds approximately to the 299 districts plus 598 intended seats should be considered a coincidence.
A tl;dr on how Ausgleichsmandate work
As mentioned, Germany is divided into (currently) 299 districts. In each of these districts, a member is elected by FPTP. The people elected in the districts get a seat in parliament, no matter what.
However, the Bundestag should be elected according to proportional representation. It is becoming increasingly likely that one party sweeps a supermajority of districts with only a tight plurality of votes in each district. To maintain proportionality of the overall seats, the size of the Bundestag is increased from its intended 598 until all district representatives can receive a seat with no party exceeding its proportional representation.
The actual calculation is very complicated, involves multiple steps and in addition to the aforementioned goal also attempts to ensure that the states are represented in parliament (by any party) according to their relative populations and within each party approximately according to the relative success of the party within the states.
Minor addendums
Certain second votes are not included in the total vote count; namely, if the voter successfully elected a district representative whose party did not clear the threshold or who ran as an independent.
Parties representing national recognised minorities need not clear any threshold to be considered for seats. So far, this has only applied to the SSW, the party of the Danish minority, which won a seat thanks to this exception in 2021.
If a party single-handedly wins a majority of votes but not a majority of seats they receive additional seats to ensure a majority.
The first and second vote of a voter are cast using a single ballot paper (see linked image). A ballot is fully valid if there is one cross in the left-hand column and one in the right-hand column. If only half of the ballot is marked correctly, then that half is valid unless the entire ballot becomes invalid due to technicalities (such as personally identifyable information added onto it).