Numerous signature schemes have been proposed in the literature. One of the major applications of digital signature is the notion of multi-signature, that enables many co-signers to authorize a document on their behalf. Nevertheless, the major impediment in this notion relies on the need to have all signers to behave in accordance to the protocol correctly. If one of the signers does not release his signature, then all of the other signers will be disadvantaged while the malicious signer can obtain a valid multi-signature on behalf of the others with his own knowledge on his partial signature. In this paper, we aim to bridge this gap by proposing the notion of fair multi-signatures. In our notion, when there is any dishonest signer in the group, then the honest signers will not be disadvantaged. Furthermore, if the signing protocol is incomplete, nobody will be able to produce a valid signature on behalf of the group. However, if the protocol completes, then each signer can output a signature on the agreed message. Our notion provides one step ahead in terms of the adoption of multi-signature in practice.