Elvis Bernard

Thomas Rolain

Pascal Courtin

Pascal Hols

Marie-Pierre Chapot-Chartier

Identification of the Amidotransferase AsnB1 as Being Responsible for meso-Diaminopimelic Acid Amidation in Lactobacillus plantarum Peptidoglycan ᰔ †

The peptidoglycan (PG) of Lactobacillus plantarum contains amidated meso-diaminopimelic acid (mDAP). The functional role of this PG modification has never been characterized in any bacterial species, except for its impact on PG recognition by receptors of the innate immune system. In silico analysis of loci carrying PG biosynthesis genes in the L. plantarum genome revealed the colocalization of the murE gene, which encodes the ligase catalyzing the addition of mDAP to UDP-N-muramoyl-D-glutamate PG precursors, with asnB1, which encodes a putative asparagine synthase with an N-terminal amidotransferase domain. By gene disruption and complementation experiments, we showed that asnB1 is the amidotransferase involved in mDAP amidation. PG structural analysis revealed that mDAP amidation plays a key role in the control of the L,D-carboxypeptidase DacB activity. In addition, a mutant strain with a defect in mDAP amidation is strongly affected in growth and cell morphology, with filamentation and cell chaining, while a DacB-negative strain displays a phenotype very similar to that of a wild-type strain. These results suggest that mDAP amidation may play a critical role in the control of the septation process.

Peptidoglycan (PG) is a heteropolymer of glycan strands cross-linked by peptidic stems most often between the fourth and the third amino acids of the donor and the acceptor stem, respectively. The composition of this peptidic stem can vary from one bacterial species to another and, in Lactobacillus plantarum, is composed of L-Ala, D-Glu, meso-diaminopimelic acid (mDAP), and D-Ala. D-Lactic acid is found as the last moiety of the peptidic stem in PG precursors [START_REF] Bernard | Characterization of O-acetylation of N-acetylglucosamine: a novel structural variation of bacterial peptidoglycan[END_REF].

Different amino acids found in PG have been reported as amidated in various species: D-Glu into D-iso-Gln [START_REF] Bernard | Characterization of O-acetylation of N-acetylglucosamine: a novel structural variation of bacterial peptidoglycan[END_REF][START_REF] Courtin | Peptidoglycan structure analysis of Lactococcus lactis reveals the presence of an L,D-carboxypeptidase involved in peptidoglycan maturation[END_REF][START_REF] Kraus | Muropeptide modification-amidation of peptidoglycan D-glutamate does not affect the proinflammatory activity of Staphylococcus aureus[END_REF][START_REF] Schleifer | Peptidoglycan types of bacterial cell walls and their taxonomic implications[END_REF], mDAP into amidated mDAP [START_REF] Atrih | Analysis of peptidoglycan structure from vegetative cells of Bacillus subtilis 168 and role of PBP 5 in peptidoglycan maturation[END_REF][START_REF] Bernard | Characterization of O-acetylation of N-acetylglucosamine: a novel structural variation of bacterial peptidoglycan[END_REF][START_REF] Schleifer | Peptidoglycan types of bacterial cell walls and their taxonomic implications[END_REF], and D-Asp into D-Asn in species possessing a D-Asp as a cross bridge. Among these PG modifications, only the D-Asp amidation was characterized in Lactococcus lactis [START_REF] Veiga | Identification of the asparagine synthase responsible for D-Asp amidation in the Lactococcus lactis peptidoglycan interpeptide crossbridge[END_REF]. D-Asp amidation is catalyzed by an asparagine synthase, AsnH, which is involved in autolysis control and resistance to cationic peptides [START_REF] Veiga | Identification of the asparagine synthase responsible for D-Asp amidation in the Lactococcus lactis peptidoglycan interpeptide crossbridge[END_REF].

We have recently shown that both D-Glu and mDAP are highly amidated (100% and 94%, respectively) in L. plantarum [START_REF] Bernard | Characterization of O-acetylation of N-acetylglucosamine: a novel structural variation of bacterial peptidoglycan[END_REF]. The functional role of these amidations remains poorly understood, except for their impact on PG recognition by the mammalian host innate immune system [START_REF] Asong | Binding and cellular activation studies reveal that Toll-like receptor 2 can differentially recognize peptidoglycan from Gram-positive and Gram-negative bacteria[END_REF][START_REF] Girardin | Nod1 detects a unique muropeptide from Gramnegative bacterial peptidoglycan[END_REF][START_REF] Kraus | Muropeptide modification-amidation of peptidoglycan D-glutamate does not affect the proinflammatory activity of Staphylococcus aureus[END_REF]. As a typical prokaryotic structure, PG is sensed by pattern recognition receptors involved in bacterial detection (e.g., Nod1, Nod2, and Toll-like receptor 2[TLR2]), and PG modifications were shown to affect this process [START_REF] Asong | Binding and cellular activation studies reveal that Toll-like receptor 2 can differentially recognize peptidoglycan from Gram-positive and Gram-negative bacteria[END_REF][START_REF] Boneca | A critical role for peptidoglycan N-deacetylation in Listeria evasion from the host innate immune system[END_REF][START_REF] Girardin | Nod1 detects a unique muropeptide from Gramnegative bacterial peptidoglycan[END_REF][START_REF] Girardin | Peptidoglycan molecular requirements allowing detection by Nod1 and Nod2[END_REF]. Unamidated mDAP is essential for Nod1 detection [START_REF] Asong | Binding and cellular activation studies reveal that Toll-like receptor 2 can differentially recognize peptidoglycan from Gram-positive and Gram-negative bacteria[END_REF], whereas amidated mDAP was reported to modulate the recognition by TLR2 [START_REF] Girardin | Nod1 detects a unique muropeptide from Gramnegative bacterial peptidoglycan[END_REF]. Despite these important immunomodulatory properties, the genetic determinants of mDAP amidation have never been described, and the functional role of mDAP amidation in bacterial physiology remains completely unexplored.

In this study, we identify the first mDAP amidotransferase and reveal its importance for growth and cell morphology in L. plantarum.

MATERIALS AND METHODS

Bacterial strains, plasmids, and growth conditions. The bacterial strains and plasmids used in the present study are listed in Table 1. Plasmids were constructed in Escherichia coli MC1061. E. coli was grown in LB medium with shaking at 37°C. L. plantarum was grown in MRS broth (Difco Laboratories Inc., Detroit, MI) at 30°C. When required, erythromycin (250 g/ml for E. coli, 5 g/ml for L. plantarum) or chloramphenicol (10 g/ml for E. coli and L. plantarum) was added to the medium. Solid agar plates were prepared by adding 2% (wt/vol) agar to the medium. Nisin A (Sigma, Bornem, Belgium) was routinely used at a concentration of 20 ng/ml for the induction of genes under the control of the nisA expression signals as previously described [START_REF] Pavan | Adaptation of the nisin-controlled expression system in Lactobacillus plantarum: a tool to study in vivo biological effects[END_REF]. For growth rate determinations, cell cultures were inoculated at an initial optical density at 600 nm (OD 600 ) of 0.1, and growth was monitored in MRS medium by measuring the OD 600 of cell cultures every 20 min with a Varioskan Flash multimode reader (ThermoFisher Scientific, Zellic, Belgium). The growth rate was calculated from the exponential growth phase.

DNA techniques and electrotransformation. General molecular biology techniques were performed according to the instructions given by Sambrook and Russell [START_REF] Sambrook | Molecular cloning: a laboratory manual[END_REF]. Electrotransformation of E. coli was performed as described by Dower et al. [START_REF] Dower | High-efficiency transformation of Escherichia coli by high-voltage electroporation[END_REF]. Electrocompetent L. plantarum cells were prepared as previously described [START_REF] Aukrust | Transformation of Lactobacillus by electroporation[END_REF]. PCR was performed with the Phusion high-fidelity DNA polymerase (Finnzymes, Espoo, Finland) in a 2400 GeneAmp PCR system (Applied Biosystems, Foster City, CA). The primers used in this study were pur-chased from Eurogentec (Seraing, Belgium) and are listed in Table S1 in the supplemental material. Construction of mutants by single crossover (SCO) recombination. Internal fragments of asnB1 (lp_0980) and thrA1 (lp_0979) were amplified by PCR using primer pairs intAsnB1pstI/intAsnB1SpeI and intthrA1pstI/intthrA1SpeI, respectively (see Table S1 in the supplemental material). Both PCR products were restricted by PstI and SpeI and then cloned between NsiI and XbaI restriction sites of the pGIZ907 suicide vector, resulting in the disruption plasmids pGIEB13 and pGIEB14, respectively. An internal fragment of dacB (lp_1010) was amplified by PCR using primers intdacB_1/intdacB_2 (see Table S1) and then cloned into the SmaI restriction site of the suicide vector pRV300, resulting in the disruption plasmid pGIEB17. The thrA1 and dacB disruptions by chromosomal integration of pGIEB14 and pGIEB17, respectively, were successfully achieved. The genotypes of the resulting mutant strains EB043 (thrA1::pGIEB14) and EB047 (dacB::pGIEB17) were validated by PCR using primers flanking the sites of recombination (see Table S1).

Construction of a stable thrA1 mutant. Construction of the thrA1 deletion mutant was performed as previously described [START_REF] Lambert | Cre-lox-based system for multiple gene deletions and selectable-marker removal in Lactobacillus plantarum[END_REF]. A double crossover (DCO) gene replacement strategy was used to replace the open reading frame (ORF) of the thrA1 gene by a chloramphenicol resistance cassette lacking a transcriptional terminator (P32-cat). Briefly, the upstream and downstream flanking regions of thrA1 were amplified by PCR using primer pairs Uthra1/Uthra2 and Dthra1/ Dthra2, respectively (see Table S1 in the supplemental material). Subsequently, amplicons were, respectively, cloned in the SwaI and SmaI restriction sites of the suicide vector pNZ5319 [START_REF] Lambert | Cre-lox-based system for multiple gene deletions and selectable-marker removal in Lactobacillus plantarum[END_REF]. The mutagenesis plasmids were transformed in L. plantarum WCFS1, and colonies displaying a chloramphenicol-resistant and erythromycin-sensitive phenotype represent candidate double crossover gene replacements. The genotype of the resulting EB042 mutant strain (thrA1::P32-cat) was confirmed by PCR by using primers flanking the site of recombination (see Table S1).

Construction of complementation vectors. The asnB1 and thrA1 ORFs and their associated ribosomal binding sites (RBSs) were amplified by PCR using primer pairs 5ЈAsnB1lp-SDpstI/3ЈAsnB1lpXbaI and 5ЈThra1lp-SDpstI/ 3ЈThra1lpXbaI, respectively (see Table S1 in the supplemental material). Both PCR amplicons were restricted by PstI and XbaI and then cloned between PstI and SpeI of vector pNZ8048 [START_REF] Kuipers | Quorum sensing-controlled gene expression in lactic acid bacteria[END_REF], leading to expression plasmids pGIEB15 and pGIEB16, respectively. The integrity of the asnB1 and thrA1 genes was verified by DNA sequencing (see primers in Table S1). The two generated transcriptional fusions are under the control of P nisA , which allows their induction in the pres-ence of nisin [START_REF] Pavan | Adaptation of the nisin-controlled expression system in Lactobacillus plantarum: a tool to study in vivo biological effects[END_REF]. These two vectors were electroporated in the EB043 strain for complementation trials.

Purification and structural analysis of PG. PG from L. plantarum strains was prepared as described previously [START_REF] Courtin | Peptidoglycan structure analysis of Lactococcus lactis reveals the presence of an L,D-carboxypeptidase involved in peptidoglycan maturation[END_REF], with some modifications. DNase (50 g/ml) and RNase (50 g/ml) treatments were applied before hydrofluoric acid treatment. PG was digested with mutanolysin from Streptomyces globisporus (Sigma), and the resulting muropeptides were analyzed by reversed-phase high-performance liquid chromatography (RP-HPLC) and matrix-assisted laser desorption ionization-time of flight mass spectrometry (MALDI-TOF MS) as previously reported [START_REF] Courtin | Peptidoglycan structure analysis of Lactococcus lactis reveals the presence of an L,D-carboxypeptidase involved in peptidoglycan maturation[END_REF]. For tandem mass spectrometry (MS-MS) structural analysis, muropeptides were desalted on a Betasil C 18 column (4.6 by 250 mm; Thermo Electron Corporation) with the acetonitrile/formic acid buffer system and dried with a speed vacuum. Samples were solubilized in 2% acetonitrile and 0.1% formic acid in Milli-Q water (1 l for 1 mAU [10 Ϫ3 absorbance unit] detected at 214 nm in the previous HPLC system). Each purified muropeptide was injected and analyzed at a flow rate of 0.2 l/min on the mass spectrometer (LTQ-Orbitrap; Thermo Fisher) located on the PAPPSO platform (INRA, UMR1319 Micalis, France; http://PAPPSO.inra.fr). The injected muropeptide was first fragmented by source-induced dissociation (SID), leading to the loss of GlcNAc. The resulting ion was selected and fragmented in the LTQ ion trap; fragments were analyzed in the Orbitrap analyzer (accuracy of 10 ppm with external calibration).

Microscopy observations. Microscopy analyses were performed using an Axio observer Z1 inverted microscope (Carl Zeiss). FM4-64 (Molecular Probes, Leiden, The Netherlands) and DAPI (4Ј,6-diamidino-2-phenylindole) (Sigma, Bornem, Belgium) staining was performed as previously reported [START_REF] Andre | Fluorescence and atomic force microscopy imaging of wall teichoic acids in Lactobacillus plantarum[END_REF]. Analyses of micrographies were performed using the AxioVision 4.8. software (Carl Zeiss).

RESULTS AND DISCUSSION

The asnB1-thrA1-murE operon contains putative gene candidates for mDAP amidation. Based on the hypothesis that genes involved in the same biosynthetic pathway are often colocalized in a genome sequence, we examined all possible loci carrying PG biosynthetic genes in the genome of L. plantarum WCFS1 in order to identify a candidate amidotransferase that could be involved in mDAP amidation. Among these loci, the putative asnB1-thrA1-murE (accession numbers and locus tags are NP_784689 and lp_0980, NP_784688 and lp_0979, and NP_784687 and lp_0977, respectively) operon was especially relevant, since the murE gene codes for the well-conserved MurE ligase catalyzing the addition of mDAP to the UDP-N-muramoylalanyl-D-glutamate PG precursor (Fig. 1A). The asnB1 and thrA1 genes are predicted to code for a potential asparagine synthase with an N-terminal amidotransferase domain and a putative diaminopimelate-sensitive aspartokinase, respectively. Intriguingly, Cahyanto et al. [START_REF] Cahyanto | Regulation of aspartokinase, aspartate semialdehyde dehydrogenase, dihydrodipicolinate synthase and dihydrodipicolinate reductase in Lactobacillus plantarum[END_REF] have shown that ThrA1 was unable to phosphorylate L-Asp and that this enzymatic reaction is performed by ThrA2 in L. plantarum. By analogy to AsnH, which is the amidotransferase responsible for D-Asp amidation in L. lactis [START_REF] Veiga | Identification of the asparagine synthase responsible for D-Asp amidation in the Lactococcus lactis peptidoglycan interpeptide crossbridge[END_REF], we hypothesized that AsnB1 could be responsible for mDAP amidation in L. plantarum. Peptidoglycan from a thrA1 mutant obtained by single crossover recombination shows a defect in mDAP amidation. In order to assign a role to asnB1 and thrA1, we attempted to disrupt each of them by SCO homologous recombination using derivatives of the pGIZ907 suicide vector. This vector was chosen since it contains a P ldhL promoter that allows the constitutive expression of the essential murE gene after chromosomal integration (Fig. 1). thrA1 was successfully disrupted (Fig. 1B), while despite several attempts, asnB1 inactivation was never obtained, suggesting that asnB1 plays an essential role in L. plantarum. The PG of wild-type NZ7100 and EB043 (SCO thrA1 mutant) strains was purified and digested by mutanolysin, and the resulting muropeptides were separated by RP-HPLC. Notably, muropeptides lacking amidation on mDAP in the control strain NZ7100 dramatically increased in the SCO thrA1 mutant (ϳ20-fold in monomers) (Fig. 2A and 2; see also Table S2 in the supplemental material). Tandem mass spectrometry (MS-MS) on the muropeptides present in peaks 4 and 13 showed the presence of unamidated mDAP in the molecules, as illustrated for peak 4 in Fig. 3A. The mass fragmentation of the muramoyl tetrapeptide derived from the disaccharide tetrapeptide yielded a fragment of 262.17 Da corresponding to unamidated mDAP linked to D-Ala. Other fragments of interest showed the loss of the unamidated mDAP (172.08 Da) between the muramoyl tripeptide (649.33 Da) and its derived dipeptidic form (477.25 Da). Similar fragments were obtained from the molecule of peak 7, corresponding to an amidated disaccharide tetrapeptide used as a control (Fig. 3B). In this case, the ending dipeptide has a mass of 261.17 Da, and the difference between the muramoyl tripeptide and dipeptide displayed a mass of 171.08 Da, which corresponds to an amidated mDAP. Intriguingly, the ratio between disaccharide tripeptides and disaccharide tetrapeptides in the pool of monomers is affected by the level of mDAP amidation (Table 2). While the disaccharide tripeptide (e.g., peak 2) is the major monomer among the fully amidated muropeptides in wild-type NZ7100 (Fig. 2A), the disaccharide tetrapeptide (e.g., peak 4) dominates in monomers lacking mDAP amidation in the SCO thrA1 mutant (Fig. 2B). The global quantification of monomers confirmed that tripeptidic forms were almost 4-fold more represented than the tetrapeptidic forms in the wild type, while this ratio was slightly below 1 in the SCO thrA1 mutant (Table 2).

Importantly, these data demonstrate that the asnB1-thrA1-murE locus is involved in mDAP amidation and suggest that mDAP amidation plays an important role in the control of the L,D-carboxypeptidase activity in this species.

ThrA1 is not involved in mDAP amidation. In order to confirm a direct role of ThrA1 in the amidation of mDAP, a stable thrA1 mutant was constructed by double crossover (DCO) recombination, resulting in the allelic exchange of thrA1 by a P32-cat cassette (Fig. 1C). Surprisingly, comparative PG analysis between NZ7100 and EB042 (thrA1::P32-cat) strains revealed a very similar muropeptide profile (Fig. 2A andC). This observation shows that the presence of muropeptides lacking mDAP amidation in the PG of the SCO thrA1 mutant (thrA1::pGIEB14) was not due to thrA1 inactivation as such but was more likely due to a polar effect resulting from plasmid integration. One possible explanation is the antisense orientation of the erm resistance marker after pGIEB14 integration (Fig. 1B), which could decrease the expression of the upstream asnB1 gene due to the leaky transcriptional terminator of the erm gene (P. Hols, unpublished data).

The asnB1 gene is able to complement the mDAP amidation defect of the SCO thrA1 mutant strain. In order to clarify the phenotype of the SCO thrA1 mutant (EB043), two complementation vectors carrying asnB1 and thrA1 were constructed. Both genes are under the control of P nisA , which allows their induction in the presence of nisin. Notably, the complementation with asnB1 (EB045) was able to partially restore the muropeptide profile observed in the control strain NZ7100 (Fig. 2E; Table 2), while the complementation with thrA1 (EB046) has only a minor impact on peptidoglycan composition (Fig. 2D; Table 2). These data confirm that the phenotype observed a Peak numbers and structures were previously assigned ( 5) and refer to those listed in Fig. c Calculated masses are those of sodiated molecular ions that were the most abundant ions on MALDI-TOF mass spectra for all muropeptides.

d The percentage of each peak was calculated as the ratio of the peak area over the sum of areas of all the peaks identified on the corresponding chromatogram.

in the SCO thrA1 mutant (EB043) was due to a polar effect on asnB1 expression and that asnB1 encodes the amidotransferase responsible for mDAP amidation in L. plantarum. Defect in mDAP amidation has a negative impact on growth. In order to evaluate the impact of mDAP amidation on the growth rate of the different mutant strains, the OD 600 of cell cultures performed in MRS medium was monitored. The stable thrA1 mutation (strain EB042) had no significant effect on growth compared to that of the NZ7100 control strain, while thrA1 inactivation by SCO (EB043) negatively affects the growth rate (Fig. 4A andC). We then monitored growth of the EB045 and EB046 complemented strains for comparison with that of the EB043 control strain harboring the empty expression vector (EB044) in the presence of antibiotics and nisin. The additional presence of nisin and chloramphenicol is responsible for a decrease in growth rate of the EB044 control strain compared to that of EB043. However, the complementation of strain EB043 with asnB1 (EB045) was able to significantly increase the growth rate compared to that of the EB044 control strain, while the complementation with thrA1 has no effect (EB046) (Fig. 4B andC). The growth rates observed above corroborate the levels of defect in mDAP amidation of the different mutant strains. Proper cell septation in L. plantarum requires amidated mDAP. Since the defect in mDAP amidation of PG could result in altered cell morphology, microscopy analyses were performed on thrA1 mutant cells (EB042 and EB043) for their comparison to wild-type cells (NZ7100). The cell morphology of the DCO thrA1 mutant (EB042) is very similar to that of the wild-type strain at all growth stages (data not shown), while the SCO thrA1 mutant (EB043) shows multiple morphological alterations (Fig. 5). In the early exponential phase, curved cells and some short filaments are observed (Fig. 5B andC). The morphological defects are more pronounced in the late exponential phase, with an increased filamentation and cell chaining (Fig. 5E to M). At this growth stage, ϳ21% (n ϭ 197) of cells from the SCO thrA1 mutant harbored these morphotypes, while only one filamentous cell (n ϭ 304) was found in the wild type and none (n ϭ 661) in the DCO thrA1 mutant. Remarkably, DAPI staining showed that up to 39 separated nucleoids could be found in one filament (Fig. 5G andK), while only four distinct cells were observed by membrane staining with FM4-64 (Fig. 5F andJ). LIVE/DEAD assays with Syto9/propidium iodide staining (LIVE/DEAD BacLight kit; Invitrogen) showed that more than 99% of the bacterial cell population was alive, including the cell subpopulation with a strongly altered morphology (data not shown).

Since PG analysis of the SCO thrA1 mutant revealed that the lack of mDAP amidation also results in a higher proportion of muropeptides carrying a tetrapeptide, the observed morphological alterations could be due to a modification of the L,D- carboxypeptidase activity. In order to test this hypothesis, the dacB gene (lp_1010), coding for the unique L,D-carboxypepti- dase (9) identified in the genome of L. plantarum WCFS1, was inactivated by SCO as described in Materials and Methods. PG analysis of the SCO dacB mutant showed that the tetrapeptide/ tripeptide ratio was dramatically changed (see Fig. S1 and Table S3 in the supplemental material), with a small amount of muropeptides with a tripeptide acceptor chain and a much higher proportion of muropeptides with a tetrapeptide acceptor chain than in the wild type (see Table S3 in the supplemental material). Interestingly, the morphology of dacB mutant cells is very similar to that of the wild type, without filamentation aberrations (see Fig. S2 in the supplemental material). All together, these results suggest that the morphological alterations observed in the SCO thrA1 mutant could be linked to the decrease of mDAP amidation levels and that mDAP amidation may play a key role in the septation process of L. plantarum.

Concluding remarks. In this study, we show that the asnB1-thrA1-murE locus encodes the determinants of mDAP amidation in L. plantarum. Our genetic analysis by gene disruption and complementation revealed the key contribution of the asnB1 gene to this modification, which indicates that it encodes the first-described mDAP amidotransferase. In contrast, we were not able to assign any functional role to the thrA1 gene in our growth conditions. Its colocalization with asnB1 and murE suggests that it may play a role in mDAP amidation in unknown conditions, possibly through the biosynthesis of the substrate that acts as the amino group donor. This work also revealed the important role played by mDAP amidation of PG for the survival of L. plantarum. Despite several attempts, we were not able to either disrupt or delete the asnB1 gene. The attenuated mutant (SCO thrA1 mutant) strongly deficient in mDAP amidation displayed a major growth defect, suggesting that this PG modification could be essential in this species. Nevertheless, the expression of the downstream murE gene in the SCO thrA1 mutant is under the control of the constitutive P ldhL promoter, which could also contribute to a certain extent to the growth defect of the mutant. A detailed genetic analysis using the construction of conditional mutants will be required to definitively conclude on the essentiality of mDAP amidation in this species. PG structural analysis revealed that PG with lowered mDAP amidation levels displays a higher tetrapeptide/tripeptide ratio than the highly amidated wild-type PG, which suggests that the unamidated mDAP-containing tetra-peptide is a poor substrate compared to its amidated counterpart for the L. plantarum L,D-carboxypeptidase DacB. The septation defect leading to filamentation observed for the mutant deficient in mDAP amidation (SCO thrA1 mutant) is reminiscent of the filamentation phenotype of L. lactis grown in the presence of methicillin that inhibits the septal penicillin-binding protein Pbp2X [START_REF] Perez-Nunez | A new morphogenesis pathway in bacteria: unbalanced activity of cell wall synthesis machineries leads to coccus-to-rod transition and filamentation in ovococci[END_REF]. Thus, mDAP amidation could be critical for septal PG biosynthesis in L. plantarum. Future work will be dedicated to better understand the contribution of mDAP amidation to the control of septation in time and space in this species as well as its importance in live cells for its recognition by the innate immune system.

FIG. 1 .

 1 FIG.1. Genetic organization of the asnB1-thrA1-murE operon in the L. plantarum wild type (A), SCO thrA1 mutant (B), and DCO thrA1 mutant (C). The putative operon is composed of three genes (white arrows), encoding AsnB1, a putative amidotransferase; ThrA1, a putative aspartokinase; and MurE, a muramoyl-tripeptide synthetase. The dotted line represents a pGIEB14 insertion in the SCO thrA1 mutant. P erm and P ldhL represent promoters carried by pGIEB14 allowing expression of the erythromycin resistance gene and genes located downstream of the insertion, respectively. The insertion of the P32-cat cassette in the DCO thrA1 mutant results from the allelic exchange of thrA1 with P32-cat. The murE gene is under the transcriptional control of P32 due to the absence of a transcriptional terminator at the 3Ј end of cat.

  2. b Tri, disaccharide tripeptide ͓L-Ala-D-iGln-mDAP(NH 2 )͔; tetra, disaccharide tetrapeptide ͓L-Ala-D-iGln-mDAP(NH2)-D-Ala͔; penta, disaccharide pentapeptide ͓L-Ala-D-iGln-mDAP(NH 2 )-D-Ala-D-Lac͔; disaccharide, GlcNAc-MurNAc; (NH 2 ), amidation; Ac, acetylation on MurNAc or GlcNAc; OAcM, O-acetyl MurNAc; OAcG, O-acetyl GlcNAc. Muropeptides missing one amidation are indicated in bold.

FIG. 3 .

 3 FIG.3. MS-MS analysis of disaccharide tetrapeptides contained in peak 4 (Fig.2and Table2) (A) and peak 7 (Fig.2and Table 2) (B).Fragmentation was performed on the [MϩH] ϩ ions at m/z 738.3 (A) and 737.3 (B), which result from the loss of GlcNAc by source-induced dissociation (SID). Indicated m/z values correspond to ions obtained by cleavage of peptide bonds, as represented on the chemical structures.

FIG. 4 .

 4 FIG. 4. Effect of mDAP amidation on growth in MRS medium. (A and B) Growth curves of NZ7100 (wild type [WT]; open circles), DCO thrA1 mutant (EB042; black squares), SCO thrA1 mutant (EB043; black triangles), SCO thrA1 mutant carrying the empty plasmid pNZ8048 (SCO thrA1/ctl mutant, EB044; open diamonds), and SCO thrA1 mutant complemented with asnB1 (SCO thrA1/asnB1, EB045; black diamonds), and SCO thrA1 mutant complemented with thrA1 (SCO thrA1/thrA1 mutant, EB046; crosses). (C) Effect of mDAP amidation on growth rate of all constructed mutants. Mean values of one of two independent experiments (with 6 repetitions for each). Significance based on Student's t test; ,ءءء P value of Ͻ0.001.

FIG. 5 .

 5 FIG. 5. Micrographs of L. plantarum wild type and SCO thrA1 mutant cells grown in MRS medium. WT NZ7100 (A) and SCO thrA1 mutant (EB043) (B and C) cells from early exponential phase; WT NZ7100 (D) and SCO thrA1 mutant (E) cells from late exponential phase; FM4-64 staining (F and J), DAPI staining (G and K), merge of FM4-64 and DAPI staining (H and L), and phase-contrast (I and M) of SCO thrA1 cells from late exponential phase.

TABLE 1 .

 1 Bacterial strains and plasmids

	Strain or plasmid	Characteristic(s) a	Source or reference
	Lactobacillus plantarum strains
	NZ7100	WCFS1 lp_0076::nisRK	22
	EB042	NZ7100 thrA1::P32-cat	This work
	EB043	NZ7100 thrA1::pGIEB14	This work
	EB044	EB043 containing pNZ8048	This work
	EB045	EB043 containing pGIEB15	This work
	EB046	EB043 containing pGIEB16	This work
	EB047	NZ7100 dacB::pGIEB17	This work
	Escherichia coli strain MC1061	rpsL150 (strR) spoT1 mcrB1 hsdR2(r Ϫ m ϩ ) F Ϫ ⌬(ara-leu)7697 ͓araD139͔ B/r ⌬(codB-lacI)3 galK16 galE15 Ϫ e14 Ϫ mcrA0 relA1	8
	Plasmids
	pNZ5319	Cm r Em r ; pACYC184 derivative containing the cat gene under the control of the P32	16
		constitutive promoter of Lactococcus lactis (lox66-P32-cat-lox71 cassette)
	pNZ8048 pGIZ907	Cm r ; shuttle vector containing P nisA promoter and start codon in NcoI site Em r Ap r ; pUC18Ery with a 0.352-kb insert containing the ldhL expression signals of	15 13
		L. plantarum NCIMB8826
	pRV300	Em r Ap r ; pBluescript derivative	17
	pGIEB13	Em r Ap r ; pGIZ907 derivative containing a 759-bp fragment from asnB1	This work
	pGIEB14	Em r Ap r ; pGIZ907 derivative containing a 501-bp fragment from thrA1	This work
	pGIEB15	Cm r ; pNZ8048 derivative expressing asnB1 in transcriptional fusion	This work
	pGIEB16	Cm r ; pNZ8048 derivative expressing thrA1 in transcriptional fusion	This work
	pGIEB17	Em r Ap r ; pRV300 derivative containing a 425-bp fragment from dacB	This work

a Cm r , Ap r , and Em r indicate resistance to chloramphenicol, ampicillin, and erythromycin, respectively.

TABLE 2 .

 2 Monomer composition of PG from L. plantarum wild-type NZ7100, SCO thrA1 (EB043) mutant, EB043 complemented by asnB1 (SCO thrA1/asnB1 mutant; EB045), and EB043 complemented by thrA1 (SCO thrA1/thrA1 mutant; EB046)

			Calculated			% of all peaks d
	Peak a	Proposed structure b	mass ͓MϩNa͔ ϩc	NZ7100 (wild type)	EB043 (SCO thrA1 mutant)	EB045 (SCO thrA1/asnB1 mutant)	EB046 (SCO thrA1/thrA1 mutant)
	1	Tri missing NH 2	892.37	0.36	1.52	0.45	0.84
	2	Tri	891.39	10.38	6.41	9.86	8.91
	4	Tetra missing NH 2	963.41	0.47	10.12	3.20	8.47
	5	Di	720.29	1.06	0.51	0.95	1.08
	7	Tetra	962.42	3.30	3.39	5.87	5.18
		Tri missing NH 2 (Ac)	934.39	0	0.66	1.04	0.76
	10	Tri (OAc-M)	933.40	0.96	0.39	0.31	0.225
	12	Tri (OAc-M)	933.40	6.75	3.04	5.10	3.69
	13	Tetra missing NH 2 (Ac)	1,005.42	0.11	3.77	1.12	2.78
	14	Tri (OAc-G)	933.40	1.09	0.46	0.94	0.85
	15	Di (Ac)	762.30	0.51	0.46	0.40	0.40
	17	Tetra (Ac)	1,004.44	1.33	0.83	1.68	1.36
	19	Tetra (Ac)	1,004.44	0.22	0.25	0.135	0.105
	23	Tri (2Ac)	975.41	1.19	1.53	1.19	1.72
		Monomers		27.7	33.4	32.3	36.4
		Monomers with amidated mDAP		25.2	16.1	25.1	22.0
		Monomers with nonamidated mDAP		0.9	16.3	5.8	12.8
		Ratio amidated/nonamidated		28.0	1.0	4.3	1.7
		Tripeptide chain		20.7	14.0	18.9	17.0
		Tetrapeptide chain		5.4	18.4	12.0	17.9
		Ratio of tripeptide/tetrapeptide		3.8	0.8	1.6	0.95

on March 11, 2013 by INRA-MME CORNIC http://jb.asm.org/ Downloaded from

J. BACTERIOL. on March 11, 2013 by INRA-MME CORNIC http://jb.asm.org/ Downloaded from

BERNARD ET AL. J. BACTERIOL. on March 11, 2013 by INRA-MME CORNIC http://jb.asm.org/ Downloaded from

VOL. 193, 2011 mDAP AMIDATION IN L. PLANTARUM 6329 on March 11, 2013 by INRA-MME CORNIC http://jb.asm.org/ Downloaded from

ACKNOWLEDGMENTS

We thank A. Guillot (PAPPSO platform, UMR1319 Micalis, INRA, France) for helpful advice for MS-MS.

The work of M.-P.C.-C. was supported by INRA (Jeune Equipe grant). The work of P.H. was supported by the National Foundation for Scientific Research (FNRS), the Universite ´Catholique de Louvain (Fonds Spe ´ciaux de Recherche), and the Research Department of the Communaute ´Franc ¸aise de Belgique (Concerted Research Action). E.B. was the recipient of a Marie Curie fellowship for Early Stage Research Training (EST) of the FP6 LabHealth project (MEST-CT-2004-514428). T.R. held a doctoral fellowship from FRIA. P.H. is a research associate of the FNRS.


Érik Martin-Dorel
email: erik.martin-dorel@irit.fr

Sergei Soloviev
email: sergei.soloviev@irit.fr

A Formal Study of Boolean Games with Random Formulas as Payoff Functions

Keywords: 2012 ACM Subject Classification Theory of computation → Higher order logic, Theory of computation → Algorithmic Boolean games, Random process, Coq formal proofs Digital Object Identifier 10.4230/LIPIcs.TYPES.2016.14

In this paper, we present a probabilistic analysis of Boolean games. We consider the class of Boolean games where payoff functions are given by random Boolean formulas. This permits to study certain properties of this class in its totality, such as the probability of existence of a winning strategy, including its asymptotic behaviour. With the help of the Coq proof assistant, we develop a Coq library of Boolean games, to provide a formal proof of our results, and a basis for further developments.

Introduction

One of the main motivations to consider the classes of games with random parameters is that it is a good method to explore these classes in their totality and to understand the relative importance of various properties of games (such as simultaneous or alternating moves, different assumptions concerning the access to information, etc.)

The situation when, for a given game, only its type can be known in advance but its parameters cannot, is common when the game-theoretic approach is used to study the behaviour of embedded systems, i.e., when at least some of the players are programs and the parameters are not fully controlled. The augmented frequency of interaction that usually surpasses any conceivable capacity of human players, and rapid evolution of parameters of interaction makes the use of probabilistic methods quite natural.

In this paper we present the first r esults o btained v ia t his a pproach a pplied t o Boolean Games [START_REF] Harrenstein | Boolean Games[END_REF][START_REF] Harrenstein | Logic in Conflict. Logical Explorations in Strategic Equilibrium[END_REF][START_REF] Dunne | Representation and complexity in boolean games[END_REF][START_REF] Bonzon | Modélisation des interactions entre agents rationnels : les jeux booléens[END_REF]. More precisely, we limit our study to Boolean Games with random formulas that represent payoff functions. This model is naturally related to the situation when games between automated systems (e.g., embedded systems in computer networks) are considered. Indeed, assuming that the players are finite n on-deterministic m achines, they can be simulated by a family of Boolean formulas.

Before the exploration may start, several choices have to be made concerning the probabilistic model.

Regarding elementary events: we have chosen Boolean functions as elementary events. Another possible choice would be to consider formulas as syntactic objects, but the former choice makes it easier to define p robability d istributions t hat a re n aturally r elated t o the properties on the associated Boolean games (while the latter choice would require to cope with the complex behaviour of the logical equivalence of formulas).

It seems natural also to consider a probability space for each n, where n is the number of variables. Indeed, n is one of the key parameters involved when considering the complexity of Boolean functions, and if we shall need to consider different values of n, it is possible to combine in some way the spaces built for each n.

Let us recall some basic properties of Boolean functions.

(i) The domain of these functions is 2 n = {false, true} n , the set of all Boolean vectors of length n (which contains 2 n elements).

(ii) Each Boolean function can be identified with a characteristic function of a subset of 2 n and thus with the subset itself, so the set of all elementary events is Ω = 22 n .

(iii) A subset of 2 n may be identified with a formula of n variables in the full disjunctive normal form 2 that is satisfied by exactly these vectors (to each vector corresponds the conjunction of variables and their negations: to true at the i-th place corresponds v i and to false corresponds ¬v i ).

(iv) The set Ω is a complete Boolean algebra, and logical operators on elements of Ω correspond to the set-theoretic operators on 2 n . The top element of this algebra is the set 2 n ∈ Ω (it represents the Boolean function true) and the bottom element of this algebra is the set ∅ ∈ Ω (it represents the Boolean function false). How these logical operators "interact" with probability on Ω is a separate question, for example, P(true) needs not of course be equal to 1.

(v) There is a natural partial order on the elements of Ω, that is defined by the inclusion of subsets of 2 n and at the same time by Boolean implication (see Definition 1 below).

Since the elements of Ω may be seen at the same time as Boolean functions and as sets of Boolean vectors, we pose the following definition: Definition 1. Let ω 1 , ω 2 be two Boolean functions (ω 1 , ω 2 ∈ Ω := 2 2 n ). We shall write ω 1 ⇒ 0 ω 2 and say that "ω 2 is true on ω 1 " if for each vector v ∈ 2 n , ω 1 (v) = true implies ω 2 (v) = true. Also, this is equivalent to the inclusion of ω 1 in ω 2 , seen as subsets of 2 n :

∀ω 1 , ω 2 ∈ 2 2 n . (ω 1 ⇒ 0 ω 2 ) ⇐⇒ (ω 1 ⊆ ω 2 ) .
Remark. We may see random Boolean functions as (not necessarily independent) vectors of 2 n random variables with values in 2 = {false, true}.

Regarding the sigma-algebra of events: as usual for finite p robability s paces, we consider the sigma-algebra S of all subsets ofΩ :

S = 2 2 2 n .
Regarding the probability distributions on the spaces of Boolean formulas: as it is noticed in [START_REF] Gardy | Random Boolean expressions[END_REF], it is often assumed that all Boolean functions on a given number of variables have the same probability (see also [START_REF] Riordan | The number of two-terminal series-parallel networks[END_REF]). In this paper where we start our study, we decided to consider a slightly more general class of probability distributions, where Boolean functions are generated by a Bernoulli scheme on Boolean vectors, with any probability p as parameter. Some more sophisticated ways to define probability distributions on Boolean expressions are discussed in [START_REF] Gardy | Random Boolean expressions[END_REF] and we plan to explore them in a near future.

In Section 2, we prove several general results on the probability of winning strategies assuming an arbitrary probability distribution. Then in Section 3, we study the case of Boolean functions constructed through a finite Bernoulli process, specialise our results in this simpler setting, then discuss the relevance of these results. In Section 4, we further study the probability that a winning strategy exists for player A, with the new assumption that player A knows s bits of the opponent player. Then in Section 5, we study the growth rate of the aforementioned probability, with respect to the knowledge of the second player's choices. Section 6 is devoted to technical remarks about the formalisation of our results within the Coq [START_REF]The Coq Proof Assistant: Reference Manual: version 8.8[END_REF] formal proof assistant. Finally, a discussion on the notion of "non-guaranteed win" and its relationship with the order of moves is presented in Appendix A.

All the results of the paper have been formally verified within Coq. 3The Coq code is available online at https://github.com/erikmd/coq-bool-games and it also has been archived, see [START_REF] Martin | erikmd/coq-bool-games[END_REF].

Beyond the fact that formal certification is interesting in itself to the types community, it is nowadays common in the development and characterisation of the behaviour of autonomous programs, which is one of the subjects of this study.

Probability of Winning Strategies

Building upon the material of the previous section, we can consider any probability P defined on the sigma-algebra S = 2 2 2 n , and thus obtain a probability space (Ω, S, P). We shall show in this section that several results can be derived in this setting, however general as it may sound.

Example 2 (using Definition 1). The probability of the event "ω is true on ω 0 ", with fixed ω 0 ∈ Ω, is

P(ω 0 ⇒ 0 ω) = ω ω0⇒0ω P({ω}).
Below we shall consider the Boolean Games of two players A and B with a random Boolean function F of n variables as the payoff function of A, and its negation as the payoff function for B. We shall assume that A controls the first k variables, a nd B t he remaining n -k variables.

The strategy of A is any vector that belongs to 2 k (valuation of the first k variables) and the strategy of B any valuation of the remaining n -k variables (a vector of 2 n-k ).

The outcome of the game is given by player A's payoff function F : 2 n → 2, which can thereby be viewed as a function F : 2 k × 2 n-k → 2 (mapping a profile strategy to a Boolean outcome). In the sequel of the paper, we shall identify these two possible types for the function F -while in the formal development they will be encoded respectively as (bool_fun n) and (bool_game n k). Definition 3 ( winA). F or a ny g ame F :

2 k × 2 n-k → 2 , a s trategy a = (a 1 , . . . , a k ) of player A is winning if it wins against any strategy b ∈ 2 n-k of B: win A [F ](a) := ∀b ∈ 2 n-k . F (a, b) = true.
If there is no ambiguity, we shall omit the name of the game and simply write win A (a).

In other words, a is winning if the payoff function is equal to true on all vectors of length n that "extend" a. This led us to introduce the following Definition 4 ( w_, W _). F or a ny a ∈ 2 k , l et ω a b e t he s et o f vectors i n 2 n t hat e xtend a:

ω a := {v ∈ 2 n | v 1 = a 1 ∧ • • • ∧ v k = a k } ∈ Ω
and W a be the set of all Boolean functions that are true on ω a :

W a := {ω ∈ Ω | ω a ⇒ 0 ω} ∈ S.
These definitions straightforwardly imply the following lemma: Lemma 5 (winA_eq). For any Boolean function F : 2 n → 2 and any strategy a ∈ 2 k of player A in the associated Boolean game, we have:

win A (a) ⇐⇒ F ∈ W a .
Lemma 5 implies that the probability that a winning strategy exists satisfies:

P(∃a : 2 k . win A (a)) = P   a∈2 k W a   .
(

Then we shall rely on the inclusion-exclusion formula, which we proved in full generality as follows:

Theorem 6 (Pr_bigcup_incl_excl). For any finite probability space (Ω, S, P) and any sequence of events (S i ) 0≤i<n , we have:

P   0≤i<n S i   = n m=1 (-1) m-1 J⊆N∩[0,n) Card J=m P   j∈J S j   .
(

) 2
Proof. For proving this theorem in Coq we formalise a small theory of indicator functions Ind S : Ω → {0, 1} for any finite set S ⊆ Ω, including the fact that the expectation satisfies E(Ind S ) = P(S), then formalise an algebraic proof of the inclusion-exclusion formula. 4These proofs strongly rely on the bigop theory of the MathComp library, as well as on the tactic "under" that we developed in Ltac to easily "rewrite under lambdas" (e.g., under the symbol). These tactics facilities will be further detailed in Section 6.

Hence the following result:

Theorem 7 (Pr_ex_winA). For any finite probability space (Ω, S, P), the probability that there exists some strategy a = (a 1 , . . . , a k ) of A that is winning satisfies:

P(∃a : 2 k . win A (a)) = a∈2 k P(W a ) - a,a ∈2 k a =a P(W a ∩ W a ) + • • • = 2 k m=1 (-1) m-1 J⊆2 k Card J=m P a∈J W a .
Proof. The result follows from (1) and ( 2), after reindexing all big-operators , , by natural numbers instead of Boolean vectors a ∈ 2 k , or conversely. Theorem 7 is applicable with any probability P , but it is not easy to handle. In the upcoming section, we shall investigate in more detail the case when P is relatively simple.

Before refining Theorem 7 with specific definitions of P, we formally study the dual case (i.e., the existence of a winning strategy from the point of view of player B). Definition 8 (winB). For any game F :

2 k × 2 n-k → 2, a strategy b = (b 1 , . . . , b n-k ) of player B is winning if it wins against any strategy a ∈ 2 k of A: win B [F ](b) := ∀a ∈ 2 k . F (a, b) = false.
If there is no ambiguity, we shall omit the name of the game and simply write win B (b).

A first result consists in showing that player B wins in a given game if and only if player A wins in the "dual game". Lemma 9 (winB_eq). Any Boolean game F : 2 k × 2 n-k → 2 (with n variables, k of which are controlled by player A) can be associated with a dual Boolean game F :

2 n-k × 2 k → 2 such that win B [F ](b) ⇐⇒ win A [F ](b)
Proof. First, we define the dual game F := bool_game_sym(F ) associated with F as:

F := (b, a) → ¬F (a, b).
Then, we define bool_game_sym' (the inverse of function bool_game_sym) and show that both functions are bijections. In the formal development, the related lemmas are named bool_game_sym_bij and bool_game_sym'_bij.

We then deduce the following result, which relates the probability of existence of a winning strategy for player B with respect to that of player A.

Theorem 10 (Pr_ex_winB). For any finite p robability s pace (Ω, S, P ), t he p robability that there exists some strategy b = (b 1 , . . . , b n-k ) of B that is winning satisfies:

P ∃b : 2 n-k . win B [F ](b) = P ∃a : 2 n-k . win A [F ](a) ,
where F := bool_game_sym(F ).

Proof. The proof straightforwardly derives from Lemma 9.

Finally, we prove the intuitive fact that the events "∃a. win A (a)" and "∃b. win B (b)" are disjoint, and thereby their probability adds up: Lemma 11 (Pr_ex_winA_winB_disj). For any finite probability space (Ω, S, P), we have:

P (∃a. win A (a) ∨ ∃b. win B (b)) = P (∃a. win A (a)) + P (∃b. win B (b)) .
Proof. Given the definitions of win A and win B , for a given game F and any strategies a and b, the events "win A (a)" and "win B (b)" are disjoint. So the proof path just amounts to lift this fact (considering existence) and use the additivity of P.

Bernoulli Process and Winning Strategies

In this section we still consider the space Ω = 2 2 n of random Boolean formulas of n variables endowed with the discrete σ-algebra S = 2 2 2 n , and the associated Boolean games with parameter 0 ≤ k ≤ n. But now, we assume that the Boolean formulas (in DNF) are determined by a random choice of the Boolean vectors that satisfy the formulas.

To be more precise, we assume the probability that each vector v ∈ 2 n belongs to the truth-set of the formula F is equal to p, (0 ≤ p ≤ 1). As usual, we write q = 1 -p.

In the sequel, we shall often identify Boolean functions F : 2 n → 2 and their truth-set F -1 ({true}) ∈ 2 2 n . In the Coq formalisation, the distinction between the two is always made explicit, and the function that gives the truth-set of a Boolean function is implemented by a function finset_of_bool_fun : ∀ n : nat, bool_fun n -> {set bool_vec n} and the inverse of this function is formalised as a function DNF_of (disjunctive normal form).

Our setup amounts to constructing a Bernoulli process, that is a series of independent Bernoulli trials, to decide whether each vector v ∈ 2 n belongs to the truth-set of F or not. We obtain the following result: Lemma 12 (dist_BernoulliE). For any F ∈ Ω, the probability of an elementary event {F } with respect to the considered probability P n; p (modelling a series of 2 n independent Bernoulli trials of parameter p) is:

P n; p ({F }) = p m (1 -p) 2 n -m
where m denotes the number of vectors in the truth-set of F , and 2 n -m denotes the number of vectors in the truth-set of the negation of F .

Proof. The proof (and its formal counterpart in Coq) straightforwardly derives from the definitions.

For now, we assume that the choices of player A and B are done simultaneously. A wins if the value of F is true, otherwise B wins. What is the probability that A has a winning strategy?

First, suppose that the strategy a of A is fixed, a nd l et u s c ompute t he p robability that it is winning. We first p rove t he following Lemma 13 (Pr_implies0_Bern). Let S ⊆ 2 n , and let us write m := Card S. Then the probability that F is true on S satisfies:

P n; p (S ⇒ 0 F ) = p m .
Proof. We follow the following proof path:

P n; p (S ⇒ 0 F ) = F S⊆F P n; p ({F }) = S ⊆2 n \S F =S∪S P n; p ({F }) = S ⊆2 n \S p Card(S∪S ) q 2 n -Card(S∪S ) by Lemma 12 = 2 n -m m =0 2 n -m m p m+m q 2 n -m-m = p m 2 n -m m =0 2 n -m m p m q (2 n -m)-m = p m (p + q) 2 n -m = p m .

Lemma 14 (card_w_a_Bern). For any strategy a of player A, we have

Card w a = 2 n-k .

Proof. This lemma easily follows from the fact that w a is the image of the strategy space 2 n-k of B by an injective function.

Hence the following theorem, which gives the probability that a fixed strategy of A is winning:

Theorem 15 (Pr_winA_Bern). For any strategy a of player A, we have

P n; p (win A (a)) = p 2 n-k .
Proof. This result is an immediate consequence of Lemmas 13 and 14.

Now, let us determine what is the probability that

A has at least one winning strategy. One may first notice the following Lemma 16 (w_trivIset). The truth-sets of w a (for a ∈ J ⊂ 2 k ) are pairwise disjoint.

Proof. By contradiction: if we had a, a ∈ 2 k such that w a = w a and w a ∩ w a = ∅, then let us pose x ∈ w a ∩ w a . By unfolding Definition 4, this means that the first k bits of x coincides with all bits of a, and likewise for a . This implies that a = a and thereby w a = w a , which contradicts the initial hypothesis.

Lemma 16 implies that we have Card

a∈J w a = a∈J Card w a = Card J • 2 n-k . ( 3
)
We can now prove the following Theorem 17 (Pr_ex_winA_Bern). For any n and k, if P n; p follows the Bernoulli scheme that we previously constructed, the probability that player A has a winning strategy is:

P n; p (∃a. win A (a)) = 1 -1 -p 2 n-k 2 k .
Proof. Thanks to Theorem 7, we can write:

P n; p (∃a : 2 k . win A (a)) = 2 k m=1 (-1) m-1 J⊆2 k Card J=m P n; p a∈J W a = 2 k m=1 (-1) m-1 J⊆2 k Card J=m P n; p a∈J [w a ⇒ 0 F ] = 2 k m=1 (-1) m-1 J⊆2 k Card J=m P n; p a∈J w a ⇒ 0 F = 2 k m=1 (-1) m-1 J⊆2 k Card J=m p Card a∈J wa by Lemma 13 = 2 k m=1 (-1) m-1 J⊆2 k Card J=m p m•2 n-k
by using (3) and Lemma 14 =

2 k m=1 (-1) m-1 2 k m p m•2 n-k = 1 - 2 k m=0 2 k m (-p 2 n-k ) m 1 2 k -m = 1 -1 -p 2 n-k 2 k .
By duality, one can derive the existence of a winning strategy for player B:

Corollary 18 (Pr_ex_winB_Bern). For any p, n, k, if P n; p denotes the considered Bernoulli scheme (with parameters 0 ≤ p ≤ 1 and n ∈ N) and if k denotes the number of variables controlled by player A, then the probability that player B has a winning strategy is:

P n; p (∃b : 2 n-k . win B (b)) = 1 -1 -(1 -p) 2 k 2 n-k .
Proof. The result follows from Theorems 10 and 17. Also, the proof makes use of our under tactic for rewriting under lambdas (it will be presented in Section 6). Corollary 19 (Pr_nex_winA_winB_Bern). For any p, n, k, if P n; p denotes the considered Bernoulli scheme (with parameters 0 ≤ p ≤ 1 and n ∈ N) and if k denotes the number of variables controlled by player A, then the probability that no player has a winning strategy is:

P n; p ¬ (∃a. win A (a)) ∨ (∃b. win B (b)) = 1 -p 2 n-k 2 k + 1 -(1 -p) 2 k 2 n-k -1. ( 4
)
Proof. The result follows from Lemma 11, Theorem 17 and Corollary 18.

Discussion

The computations above may seem elementary, but lead to some observations that are less trivial. As we may see, there is a considerable probability that there is no winning strategy at all. For example, if p ∈ { 1 4 , 1 2 , 3 4 }, n ∈ {10, 20}, 0 < k < n, the probability that a winning strategy exists neither for A nor for B (cf. Equation ( 4)) is given in Tables 1 and2 (the values were computed using Sollya 5 with 3-digit decimal output). In both tables, it should be noted that 1 actually means a value extremely close to 1, not 1 exactly. Also, one may notice that when p ∈ (0, 1) is fixed, k = c • n for a given constant 0 < c < 1, and n tending towards +∞, the probability that a winning strategy exists neither for player A, nor for player B, tends to 1.

If (for some game F ) a winning strategy exists neither for A nor for B, then the order of moves becomes important. Indeed, let a be an arbitrary strategy of A. Since it is not winning, there exists at least one b of B such that F (a, b) = false. If B makes his choice after A, he may always win. Similarly, if A makes his choice after B, he may always win.

We shall elaborate on this observation and give a motivating example in Appendix A. Bradfield, Gutierrez and Wooldridge notice [START_REF] Bradfield | Partial-order Boolean games: informational independence in a logic-based model of strategic interaction[END_REF] (as do some other authors): "As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players -they are games of simultaneous moves.

For many settings, this is clearly unrealistic." Our simple probabilistic analysis provides a direct quantitative argument to support this general observation. In other words, we are interested in the probability of guaranteed win by A when s choices by B among n -k are known (assuming 0 ≤ s ≤ n -k). We thus introduce the following predicate:

Definition 20 (winA_knowing). For any game F : 2 k × 2 n-k → 2 and any b 1:s ∈ 2 s , we say that a strategy a ∈ 2 k is winning under the knowledge of b 1:s if it is winning against all strategy profile (a, b)

∈ 2 k × 2 n-k that is compatible with b 1:s : win A (a | b 1:s ) := ∀b ∈ 2 n-k . compat_knowing(b 1:s , b) =⇒ F (a, b) = 1, where compat_knowing(b 1:s , b) := ∀i ∈ 2 s . (b 1:s ) i = b i .
For relating this predicate with that of Definition 3, the proof of the following lemma is immediate:

Lemma 21 (winA_knowingE). For any game F : 2 k × 2 n-k → 2 and any bit-vectors b 1:s ∈ 2 s and a ∈ 2 k , we have:

win A [F ](a | b 1:s ) = win A [bgk(F, b 1:s )](a)
where bgk(F, b 1:s ) : 2 k × 2 n-s-k is the Boolean game defined by: bgk

(F, b 1:s )(a, b ) = F (a, (b 1:s , b )).
Now, to compute the probability P n; p ∀b 1:s ∈ 2 s . ∃a ∈ 2 k . win A (a | b 1:s ) in the space (Ω, S, P n; p ) introduced in Section 3, we shall first construct a probability space (Ω , S , P ) that is provably isomorphic to (Ω, S, P n; p ), but which is simpler to handle.

First, we note that there are 2 s possible Boolean vectors b 1:s = (b 1 , ..., b s ) and for all b 1:s , we pose

B b1:s = {v ∈ 2 n | v k+1 = b 1 ∧ • • • ∧ v k+s = b s }.
The family (B b1:s ) b1:s∈2 s constitutes a partition of 2 n (we have 2 n = b1:s∈2 s B b1:s , intersections of B b1:s for different b 1:s are empty, and no set B b1:s is empty).

Second, we define Ω b1:s := 2 B b 1:s as the powerset of B b1:s and show that there is a one-to-one correspondence between Ω b1:s and 2 2 n-s . We shall denote the corresponding bijections by g : Ω b1:s → 2 2 n-s and h : 2 2 n-s → Ω b1:s . In the formal development, the related lemmas are named bool_fun_of_OmegaB_bij and OmegaB_of_bool_fun_bij.

Next, we consider the probability P b1:s := P n-s; p • h -1 defined a s t he pushforward distribution (with respect to function h) of the Bernoulli process P n-s; p with parameters n -s and p.

We then consider the product space (Ω , S , P ) defined by:

         Ω = b1:s∈2 s Ω b1:s S = 2 Ω P = b1:s∈2 s P b1:s
Relying on functions g and h, we finally show that there is a one-to-one correspondence between Ω and Ω = 2 2 n . We shall denote the corresponding bijections by g : Ω → Ω and h : Ω → Ω . In the formal development, the related lemmas are named bool_fun_of_Omega'_bij and Omega'_of_bool_fun_bij.

We now prove that the spaces (Ω, S, P n; p ) and (Ω , S , P ) are isomorphic:

Lemma 22 (isom_dist_Omega'). The probability distribution P n; p (defined in Section 3 as the Bernoulli process with parameters n and p) is extensionally equal to the pushforward distribution of P with respect to function g .

Proof.

In the Coq formal proof, this lemma amounts to splitting a big-operator expression with respect to the partition of 2 n , reindexing big-operator expressions half-a-dozen times, and rewriting "cancellation lemmas" for simplifying the composition of a bijection and its inverse function. Also, the use of our under tactic (see Section 6) contributed to simplify the mechanisation of this proof.

A key ingredient for the sequel will be the following Lemma 23 (ProductDist.indep). Given a finite type I and a family of finite probability spaces (Ω i , S i =2 Ωi , P i ) i∈I , the product space defined by

         Ω Π = i∈I Ω i S Π = 2 Ω Π P Π = i∈I P i
is such that the projections (π i : Ω Π → Ω i ) i∈I are independent random variables. In other words, for any family of events (Q i ) i∈I ∈ i∈I S i , we have:

P Π i∈I π -1 i (Q i ) = i∈I P i (Q i ).
We can now prove the following Theorem 24 (Pr_ex_winA_knowing_Bern). For all p ∈ [0, 1] and for all integers n, k, s satisfying 0 ≤ s ≤ n -k ≤ n, if P n; p is the Bernoulli process with parameters n and p defined in Section 3, the probability of guaranteed win for player A knowing s choices of player B among his n -k variables is:

P n; p ∀b 1:s ∈ 2 s . ∃a ∈ 2 k . win A (a | b 1:s ) = 1 -1 -p 2 n-k-s 2 k 2 s . ( 5
)
Proof. We follow the following proof path:

P n; p ∀b 1:s ∈ 2 s . ∃a ∈ 2 k . win A (a | b 1:s ) = P n; p F ∈ Ω ∀b 1:s ∈ 2 s . ∃a ∈ 2 k . win A [F ](a | b 1:s )
hence by using Lemma 21

= P n; p F ∈ Ω ∀b 1:s ∈ 2 s . ∃a ∈ 2 k . win A [bgk(F, b 1:s )](a)
hence by using Lemma 22

= (P • g -1 ) F ∈ Ω ∀b 1:s ∈ 2 s . ∃a ∈ 2 k . win A [bgk(F, b 1:s )](a)
hence by using elementary facts on g, g and the bgk function defined in Lemma 21

= P f ∈ Ω ∀b 1:s ∈ 2 s . f (b 1:s ) ∈ S ∈ Ω b1:s ∃a ∈ 2 k . win A [g(S)](a)
hence by using Lemma 23

= b1:s∈2 s P b1:s S ∈ Ω b1:s ∃a ∈ 2 k . win A [g(S)](a)
hence by definition of P b1:s

= b1:s∈2 s P n-s; p • h -1 S ∈ Ω b1:s ∃a ∈ 2 k . win A [g(S)](a)
hence by definition of g and h

= b1:s∈2 s P n-s; p F ∈ 2 2 n-s ∃a ∈ 2 k . win A [F ](a)
hence by using Theorem 17 in the case of random Boolean functions with n -s variables

= b1:s∈2 s 1 -1 -p 2 n-s-k 2 k = 1 -1 -p 2 n-k-s 2 k 2 s .
We may compare this probability with the probability of existence of unconditionally winning strategy studied in Section 3 (Theorem 17). The upcoming section will focus on this question.

Remark. In Theorems 17 and 24, we formally studied the probability of guaranteed win (knowing partial information on the opponent), that is, the probability that for every value taken by the first s variables of B, 6 there exists a strategy for A that wins against all strategies of B given this fixed value of the first s variables of B. This problem is purely combinatorial and does not depend on the "preferences" of B (regarding the variables that he controls). So this probability will typically be different from the probability of non-guaranteed win for player A, as this latter probability could be influenced by the preferences of B for some choices, the dependency of these choices on F , and so on.

Probability of Guaranteed Win: Growth Rate

Using the result given by Theorem 24, we would like to study how the probability of guaranteed win grows with each bit of information concerning the choice of B.

For fixed values of p ∈ (0, 1), n, k ∈ N such that 0 < k < n, and for 0 ≤ s ≤ n -k, let us write g(s) the quantity given in Equation [START_REF]The Coq Proof Assistant: Reference Manual: version 8.8[END_REF].

First, we note that when s tends to n -k, the probability of guaranteed win for A tends to:

g(n-k) = 1 -1 -p 2 0 2 k 2 n-k = 1 -(1 -p) 2 k 2 n-k = 1-1 -1 -(1 -p) 2 k 2 n-k
proba. of guaranteed win for B

Then, an interesting question may be: what is the order of growth of the difference

φ(s) := g(s) -g(0) (∈ [0, 1])
with respect to s? The following result is a first answer to this question:

Theorem 25 (phi_ineq). For any p ∈ (0, 1), n, k ∈ N * such that 0 ≤ s ≤ n -k, if the following condition holds:

2 k p 2 n-k-s < 1, (6)
then we have

φ(s) > 2 (k-1)2 s -2 k p 2 n-k , ( 7
)
where

φ(s) = g(s) -g(0) = 1 -1 -p 2 n-k-s 2 k 2 s -1 -1 -p 2 n-k 2 k .
In particular, condition (6) is satisfied as soon as the following, stronger condition is satisfied:

s ≤ (n -k) -log 2 (k + 1) + log 2 (| log 2 p|). ( 8
)
Proof. Let us write t = p 2 n-k-s . By the binomial formula, we have:

1 -(1 -t) 2 k = 2 k t -(2 k t) 2 2 k i=2 (-1) i 2 -2k 2 k i t i-2 . ( 9
)
We notice that if (6) holds, that is if 2 k t < 1, then the absolute value of the (i + 1)th member of the sum in ( 9) is less than that of the i-th member because it is obtained by multiplication by ((2 k -i)/(i + 1))t < 2 k t. So, if (6) holds, then the sum (positive) is less than or equal to its first term. Moreover, the first term of the sum in ( 9) is 2 6) is satisfied for some n, k, s, then from ( 9) we obtain

-2k 2 k (2 k -1) 2 < 1 2 . So, if (
1 -(1 -t) 2 k ≥ 2 k t - 1 2 (2 k t) 2 = 2 k t 1 - 1 2 2 k t > 2 k-1 t. ( 10
)
Thus, under these conditions

g(s) = 1 -1 -p 2 n-k-s 2 k 2 s > 2 (k-1)2 s p 2 n-k . ( 11
)
Next, a similar analysis applied to 1 -1 -p 2 n-k 2 k gives an estimation

g(0) = 1 -1 -p 2 n-k 2 k = 2 k p 2 n-k - 2 k i=1 2 k i -p 2 n-k i ≤ 2 k p 2 n-k (12)
Combining ( 11) and ( 12) yields the following inequality:

g(s) -g(0) > 2 (k-1)2 s p 2 n-k -2 k p 2 n-k = 2 (k-1)2 s -2 k p 2 n-k . ( 13
)
Finally, the following condition is obviously stronger than (6):

2 k p 2 n-k-s ≤ 1 2 ,
which is equivalent to

2 n-k-s log 2 p ≤ -(k + 1).
Since 0 < p < 1 we may write instead

2 n-k-s | log 2 p| ≥ (k + 1).
Applying the log a second time, we obtain

s ≤ (n -k) -log 2 (k + 1) + log 2 (| log 2 p|),
which is thereby a sufficient condition for [START_REF] Dantsin | Algorithms in Games Evolving in Time: Winning Strategies Based on Testing[END_REF].

For example, if p = 2 , condition (8) becomes

s ≤ (n -k) -log 2 (k + 1). ( 14
)
1 2
And if 0 < p < , log 2 (| log 2 p|) > 0 so we havelog 2 (k + 1) < -log 2 (k + 1) + log 2 (| log 2 p|), and thereby we can also rely on condition [START_REF] Martin | erikmd/coq-bool-games[END_REF].

It can be noted that inequality [START_REF] Dunne | Representation and complexity in boolean games[END_REF] essentially gives an order of growth of 2 (k-1)2 s with respect to the quantity of information s (number of extra bits known by player A), which is much faster than usual orders of growth of s or 2 s .

Still, a more refined s tudy o f t he b ehaviour o f t he f unction t hat d escribes t he g rowth of g(s) (the probability of a guaranteed win depending on s) requires much more effort and space that we could give to it in this exploratory paper. For example, it is intuitively clear that the graph of this function is a typical "S-form" curve (see Figure 1), but it is not easy to determine where the critical points are placed; and for small values of the parameter s, the inequality we get in ( 7) may be too rude to place with sufficient precision. However the behaviour of this function g may be of interest for strategic planning concerning both players. This remains subject of future work.

6

Remarks on the Formal Setup in the Coq Proof Assistant

Related Works on Formal Libraries of Probability

There have been several works focusing on the formalisation of measure theory or probability using interactive theorem proving. Some of these works only deal with discrete probability, or focus on the analysis of randomised algorithms; others formalise large fragments of measure theory up to Lebesgue's integration theory. Using the HOL proof assistant, Hurd [START_REF] Hurd | Formal verification of probabilistic algorithms[END_REF] developed a framework for proving properties of randomised programs, relying on a formalisation of measure theory, and following a "monadic transformation" approach that provides the user with an infinite sequence of independent, identically distributed Bernoulli( 12 ) random variables. Still using the HOL proof assistant and building upon Hurd's work, Mhamdi, Hasan and Tahar [START_REF] Hasan | Using theorem proving to verify expectation and variance for discrete random variables[END_REF][START_REF] Mhamdi | On the formalization of the Lebesgue integration theory in HOL[END_REF] developed a comprehensive formalisation of measure theory, including Lebesgue's integration theory.

Using the Coq proof assistant, Audebaud and Paulin-Mohring [START_REF] Audebaud | Proofs of randomized algorithms in Coq[END_REF] developed the ALEA library 7 that provides a framework to reason about randomised functional programs. Unlike Hurd's approach, it does not require a complete formalisation of measure theory: it is built upon a Coq axiomatisation of the interval [0, 1] and it interprets randomised programs as (discrete) probability distributions.

Still using the Coq formal proof assistant, Affeldt, Hagiwara and Sénizergues [START_REF] Affeldt | Formalization of Shannon's theorems[END_REF] developed the Infotheo library 8 that provides a formalisation of information theory. This library comes with a formalisation of finite probability theory and strongly relies on the theories of the MathComp library 9 .

For developing our library on random Boolean games, we have chosen to rely on the Infotheo library. Even though it only deals with finite probability, this setting was sufficient for formalising our results and, further, it allowed us to benefit from the facilities of the SSReflect/MathComp library. In the rest of this section, we shall summarise the main notions that we used from the MathComp library and present our related contributions (in Section 6.2), then describe the overall setup of the Infotheo probability theory and present our related contributions (in Section 6.3).

MathComp and Our Related Contributions

The MathComp library was born in the Mathematical Components project, which aimed at formalising the Odd Order Theorem in the Coq proof assistant [START_REF] Gonthier | A Machine-Checked Proof of the Odd Order Theorem[END_REF], while organising formal proofs into components to get a reusable library of mathematical facts. It is built upon SSReflect, an extension of Coq's proof language that has a native support for the so-called small scale reflection (and in particular Boolean reflection) and often leads to concise proof scripts.

For our library of random Boolean games, we have been especially using the following libraries: (i) fintype for finite types with decidable equality, (ii) finfun for functions over finite domains, (iii) finset for finite sets, (iv) bigop for properties on "big-operators".

Big-operators and rewriting under lambdas

Regarding big-operators such as , , or , they are formalised in MathComp as a higher-order function bigop that takes several arguments, including a function that specifies the "domain predicate" and the "general term". For example, the sum

4 i=1 i odd i 2
can be formally written as \sum_(1 <= i < 5 | odd i) i^2, which amounts to the following term if we get rid of the \sum notation: bigop 0 ( index_iota 1 5) ( fun i : nat = > BigBody i addn ( odd i ) ( i ^2))

If we want to transform such a big-operator expression by rewriting its domain predicate or general term, the following two MathComp lemmas on big-operators can be used.

eq_bigr :

forall ( R : Type ) ( idx : R ) ( op : R -> R -> R ) ( I : Type ) ( r : seq I ) ( P : pred I ) ( F1 F2 : I -> R ) , ( forall i :

I , P i -> F1 i = F2 i ) -> \ big [ op / idx ] _ ( i <-r | P i ) F1 i = \ big [ op / idx ] _ ( i <-r | P i ) F2 i eq_bigl : forall ( R : Type ) ( idx : R ) ( op : R -> R -> R ) ( I : Type ) ( r : seq I ) ( P1 P2 : pred I ) ( F : I -> R ) , P1 =1 P2 -> \ big [ op / idx ] _ ( i <-r | P1 i ) F i = \ big [ op / idx ] _ ( i <-r | P2 i ) F i
Still, applying them directly would require to provide the entire term corresponding to the function we want to obtain. We thus developed a Coq tactic "under" for rewriting under the lambdas of big-operators.

A generalised version of our tactic, also applicable for MathComp notions such as matrices, polynomials, and so on, is available online at https://github.com/erikmd/ssr-under-tac and we plan to submit it for possible inclusion in MathComp. Below is a typical example of use for that generalised implementation of the under tactic.

For a goal that looks like

= = = = 0 <= \ sum_ (0 <= k < n ) \ sum_ ( J in { set A } | #| J | == k ) \ sum_ ( j in J ) F j

Dependent product of finTypes

MathComp has built-in support for finite functions: for any (A:finType) and (T:Type), the notation {ffun A -> T} stands for the type of finite functions from A to T. If n denotes the cardinal of A, these functions are represented by a n-tuple of elements of T, which allows one to obtain convenient properties such as the extensionality of finite functions, which wouldn't hold otherwise in the constructive, intensional logic of Coq.

If T is also a finite type, then the MathComp library allows one to automatically retrieve (thanks to type inference and so-called canonical structures) a finite type structure for the type {ffun A -> T} itself. Thus, this construct amounts to the non-dependent product of a finType.

However, for formalising our results and in particularly to construct the type Ω that appears in Section 4, we have been led to formalise the dependent product of a finite family of finite types. This material is gathered in a file fprod.v which provides a type fprod, some notations in MathComp style and several support results such as lemmas fprodP and fprodE, whose signature is as follows: This theory involves proofs with dependent types, and to facilitate the formalisation process we tried to follow a MathComp formalisation style as much as possible, by using finite functions, records with Boolean conditions, and so on. This enabled us to rely on extensionality of functions, the Altenkirch-Streicher K axiom and proof irrelevance, which can be used "axiom-free" in the decidable fragment of MathComp finTypes.

Infotheo and Our Related Contributions

The Infotheo library relies on MathComp as well as the Reals theory from Coq's standard library. Among the Infotheo theories, the proba theory was the starting point of our formalisation. It first defines distributions as a dependent record dist, gathering a function pmf that gives the probability of each elementary event, and a proof that the sum of these probabilities is equal to 1:

Record dist ( A : finType ) := mkDist { pmf : > A -> R + ; pmf1 : \ rsum_ ( a in A ) pmf a = 1 }.

Then, it defines the probability of a subset of A as the sum of the probabilities of all elementary events in A:

Definition Pr ( A : finType ) ( P : dist A ) ( E : { set A }) := \ rsum_ ( a in E ) P a .

Then, basic properties of probability and expectation are provided in this setting. On top of the Infotheo theories, we have developed the following contributions: (i) a formalisation of the pushforward distribution dist_img with the associated lemma Lemma Pr_dist_img :

forall { A B : finType } ( X : A -> B ) ( PA : dist A ) ( E : { set B }) , Pr ( dist_img X PA ) E = Pr PA ( X @ ^-1: E ).

(ii) a formal proof of a general version of the inclusion-exclusion theorem that we presented above in Theorem 6; (iii) the product distribution of a family of distributions, whose signature is as follows:

ProductDist . d : forall ( I : finType ) ( T_ : I -> finType ) , ( forall i : I , dist ( T_ i )) -> dist ( fprod I T_ )

The associated independence result was presented above as Lemma 23.

Conclusion

In this work, we used the basics of the theory of Boolean games. In this sense, our work is obviously related to this area. But to the best of our knowledge, the idea of using probability theory applied to a certain class of Boolean games as a whole (in difference from merely random strategies) is new. The analysis of the whole class of games permits to discover some quantitative properties of these games that would be difficult to discover in the study of an individual game. Furthermore, we used type theory and interactive theorem proving to formalise our results in order to give strong guarantees on their correctness as well as to extend existing formal libraries with new items.

In particular, we have proved a closed formula for the probability of existence of winning strategies in those random Boolean games. We specialised this result with a probability distribution on Boolean functions that are generated by a Bernoulli scheme on Boolean vectors with any probability p as parameter (it can be noted that this setting subsumes the simpler case where all Boolean functions have the same probability: this latter case corresponds to choosing p = 1 2 in our setting).

In this paper our methods remained elementary, but they permitted to estimate the relative importance of the cases where the players use simultaneous and alternative moves. Another interesting phenomenon seems to us to be the growth of probability of the win as function of the information about the choices of the opponent. Essentially, it is much faster than usual 2 s where s is the quantity of information (number of extra bits) known by the player. This phenomenon emphasises the difference between the information that is required for winning and the "measure of knowledge" of the opponent and its strategies.

We already mentioned the interest of machine checked verification f or t he g ames between autonomous programs (embedded systems).

As a future work, we plan to consider more general classes of probability distributions and explore the "weight" of information with respect to winning in this more general setting.

We plan also to consider more closely the connection with algorithmic games [START_REF] Dantsin | Algorithms in Games Evolving in Time: Winning Strategies Based on Testing[END_REF].

A Non-Guaranteed Win: When the Order of Choices Matters

Let us consider an example of three variables a, b, c and two players, Alice who controls a and Bob who controls b, c. Let us consider all possible Boolean functions as payoff functions.

There are 256 that may be identified with the subsets of the nodes of the cube below. Each subset is interpreted as the disjunction of the conjunctions in the nodes.

abc abc abc abc abc abc abc abc

It makes sense to analyse this situation in a purely combinatorial way before we consider randomly generated payoff functions. We notice the following facts: Alice has an unconditionally winning strategy in 31 cases (these cases correspond to all subsets that contain all nodes of either the face with a or the face with a; the number of subsets is easily counted by the formula of inclusions-exclusions).

Bob has an unconditionally winning strategy in 175 cases (the cases correspond to the subsets that do not intersect with one of the four edges defined by the choice of two literals among b, c, b, c; the number is counted as above).

There are 50 cases when neither Alice nor Bob has an unconditionally winning strategy. In these cases the order of choice matters: If Alice chooses the value of a first, then Bob has a winning strategy (he may win in all these cases). Similarly, if Bob chooses the values of b, c first then Alice may win in all these cases. Now let us consider in more detail the case where the order of choices is B -A -B. In fact, here we need to distinguish three subcases: 1. Bob may give a value to any of b, c at his first step.

2.

At his first step, Bob gives a value to b, and at his second to c. 3. At his first step, Bob gives a value to c, and at his second to b.

It can be noted that these three variants may correspond to preferences or to obligations (extra constraints) concerning Bob, in line with the remark at the end of Section 4 (page 12). We elaborate on these three subcases below. This gives Alice more possibilities to win. Indeed, she may win if the subset of nodes includes either abc, abc, abc, abc or abc, abc, abc, abc. We may add one or more nodes to each subset of four, but if we exclude the previously considered cases, we shall have 12 more cases when Alice may win.

3.

Similar analysis shows that it will be 12 cases (not considered previously) where Alice may win if Bob must choose the value of c first.

It is important to notice that the choices of Alice and Bob are not necessarily interpreted as the choices of logical values of a, b, c. This model may be used to model any binary choice. Indeed, let a = true mean the choice of some value v a and a = false mean the choice of v a by Alice. Similarly, Bob may choose one of v b , v b and one of v c , v c . Instead of conjunction of literals (e.g., abc) let us take for each such conjunction a predicate 10 P abc (x, y, z) which is true if and only if x = v a , y = v b , z = v c . Instead of considering the disjunction of these conjunctions, let us take the disjunction of corresponding predicates. It appears that the logical value of the result will exactly be the logical value of the payoff function represented by the DNF (or Boolean function).

The roles of Alice and Bob may be seen as the roles of "coaches" who choose the players for a series of matches. Alice wins if her "champion" wins at least one match. Also, to come back to the situation with random payoff functions, it makes perfect sense that in a real tournament the coach cannot know in advance which matches will be necessary to play.

The same idea may be used to model markets (the choice a = true may mean that Alice orders to buy a certain product a, a = false that she orders to sell, and the presence of abc that she makes profit when she buys at the same time when Bob sells his two products).

This analysis also clearly shows what may be the role of introduction of random choice of payoff functions. It takes into account certain amount of unpredictability in a real situation. Notice that it does not eliminate some "geometric flavour" displayed in the above example.

However, as we emphasised before, we intend to use probability mostly for the analysis of the totality of games with all possible Boolean functions as payoff, rather than for considering one game with a randomly-chosen payoff function (though this may sometimes make sense).

The choice of probability distribution will influence the relative "weight" of the cases that we considered above in a purely combinatorial way, and has to be taken into account when additional conditions are considered, such as the order of moves or access to the information.

For example, if the probability parameter p takes a value of 1 2 (i.e., if we focus on the instance P 3; 1 2 of the Bernoulli process presented in Section 3), this will give the uniform distribution on the 256 cases considered in the appendix.

4

  Partial Information on the Opponent's ChoicesNow, let us consider the case when A may have partial information about the choices of B before making his own choice. Without loss of generality, we may assume that he knows the values of the first s variables among the variables v k+1 , ..., v n controlled by B. We shall consider the probability of existence of strategies of A such that for every vector b 1:s = (b 1 , ..., b s ) ∈ 2 s there exists a strategy a ∈ 2 k that wins against any strategy b ∈ 2 n-k where first s values coincide with b 1:s .

Figure 1

 1 Figure 1 Graph of g(s), for the parameters p = 1 2 , n = 10, and k = 6. The vertical line at s 1.19 indicates the largest s ∈ R that satisfies (8).

  = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 0 <= \ sum_ (0 <= k < n ) \ sum_ ( J in { set A } | #| J :&: [ set : A ]| == k ) \ sum_ ( j in J ) F j the proof script under eq_bigr [ k Hk ] under eq_bigl [ J ] rewrite setIT . will yield the following goal: A : finType n : nat F : A -> nat = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =

  fprod : forall I : finType , ( I -> finType ) -> finType fprodP : forall ( I : finType ) ( T_ : I -> finType ) ( f1 f2 : fprod I T_ ) , ( forall x : I , f1 x = f2 x ) <-> f1 = f2 fprodE : forall ( I : finType ) ( T_ : I -> finType ) ( g : forall i : I , T_ i ) ( x : I ) , [ fprod i = > g i ] x = g x

1 . 2 .

 12 The choice of Bob may be interpreted as the selection of one of the four faces of the cube that corresponds to b, b, c, c respectively. There are four cases when Alice may win if she knows the first choice of Bob. One subset is shown below in bold, other are obtained by rotation. (We exclude the cases of unconditional win that were counted before.)In the case displayed above, if Bob has chosen b = true then Alice has to choose a = true and wins because the remaining formula will be c ∨ c. If at the first step Bob must choose the value of b, then it may be seen as the choice of one of the two faces of the cube that correspond to b or b.

Table 1

 1 The probability that a winning strategy exists neither for A nor for B (n = 10).

	p\k	1	2	3	4	5	6	7	8	9
	0.25 1.52e-184 5.11e-43 1.37e-6 0.525 0.997 1	0.998	0.367	4.46e-15
	0.5	1.07e-64	6.68e-8	0.606	0.999 1	0.999 0.606	6.68e-8	1.07e-64
	0.75 4.46e-15	0.367	0.998	1	0.997 0.525 1.37e-6 5.11e-43 1.52e-184

Table 2

 2 The probability that a winning strategy exists neither for A nor for B (n = 20).

	p\k	1			2		3	4	5	6 7 8 9 10
	0.25 1.27e-188231 2.04e-43307 2.15e-6005 1.99e-287 3.72e-2 1 1 1 1 1
	0.5	1.32e-65504	2.74e-7348	1.61e-223	0.368	1	1 1 1 1 1
	0.75 7.53e-14696	2.58e-446	0.135	1	1	1 1 1 1 1
	p\k	11 12 13 14 15	16	17	18		19
	0.25 1	1	1	1	1	1	0.135	2.58e-446	7.53e-14696
	0.5	1	1	1	1	1	0.368	1.61e-223	2.74e-7348	1.32e-65504
	0.75 1	1	1	1	3.72e-2 1.99e-287 2.15e-6005 2.04e-43307 1.27e-188231

In particular, the empty subset may be identified with the empty DNF, that is the constant false (the neutral element of the disjunction).

In the sequel of the paper, all definitions and theorems will be stated in mathematical syntax, and the corresponding Coq identifier will be given between brackets.

taking inspiration from the proof path presented at https://en.wikipedia.org/wiki/ Inclusion-exclusion_principle#Algebraic_proof

This work was partly supported by the FAGames project of LabEx CIMI. wishes to thank Cyril Cohen and Enrico Tassi for advice and enhancement suggestions for our under tactic.

1 S. Soloviev was partly supported by the Government of Russian Federation Grant 08-08 at ITMO University, Saint-Petersburg, Russia (associated researcher).