J Christian Schön

C Oligschleger
email: christina.oligschleger@h-brs.de

J Cortes
email: juan.cortes@laas.fr

Prediction and clarification of structures of (bio)molecules on surfaces -a review

Prediction and clarification of structures of (bio)molecules on surfaces-a review

C. Schön" C. Oligschleger, Juan Cortés

Introduction

Throughout its history, the field of synthetic chemistry has been divided into several subfields, depending on the way chemistry has been perceived by its practitioners. One of the first divisions, according to classes of compounds, was into organic and inorganic chemistry. Subsequently the latter was subdivided into solid state and molecular chemistry, while the formed spawned fields like polymer chemistry, biochemistry, or metal-organic chemistry. Other divisions took their lead from the actual physical size of the material at hand, leading to a distinction between molecular, cluster, surface, or (bulk) crystal chemistry.

More recently, the field of nanochemistry with its focus on the synthesis of, and with, nanosized objects [START_REF] Ozin | Nanochemistry: A Chemical Approach to Nanomaterials[END_REF][START_REF] Philp | [END_REF][3][START_REF] Steed | Core Concepts in Supramolecular Chemistry and Nanochemistry[END_REF] has produced hybrid-like compounds, where e.g. complex molecules, clusters, or nano-size (mono)-layer flakes, are arranged in layered or three-dimensional patterns. Usually, one still employs classical chemical synthesis techniques to reach such nano-patterned compounds. But the development of advanced deposition techniques [START_REF] Räder | [END_REF][6][7] has allowed us to conceive the generation of compounds, or materials in general, by adding one building block, i.e. molecule, cluster, etc., at a time [8]. A precondition for such a way to produce new compounds is the ability to predict and control the formation of molecular arrangements on well-defined surfaces.

The past couple of decades have seen a plethora of experimental studies of the deposition of molecules of various sizes, ranging from simple gases like N 2 [9], CO [10],

Xe [START_REF] Jänsch | Proc. Nat. Acad. Sci[END_REF], etc., to highly complex biomolecules such as proteins [START_REF] Ouyang | [END_REF], spurred at least partly by new measurement probes such as scanning tunneling microscopy (STM) [13] or atomic force microscopy (AFM) [14]. But just as it had originally been the case in other fields of synthetic chemistry, such as molecular or solid state chemistry, the outcome of such a deposition with respect to the structure of the individual molecule or the structural arrangement of many molecules is very hard to predict without prior experimental input.

Empirical rules and heuristics can be used to "explain" the structures observed after deposition. But we are still far away from an unbiased structure prediction of thermodynamically and/or kinetically stable structures of molecules on surfaces.

Similarly, the a priori design of optimal deposition routes leading to desired specific patterns of molecules on surfaces is still farther in the future.

Or are we? At least with regard to the prediction of (meta)stable structures, we know from our experience with the analogous problem in the fields of molecular [15,[START_REF] Wales | Energy Landscapes with Applications to Clusters, Biomolecules and Glasses[END_REF] and solid state [START_REF] Schön | [END_REF][18][19] chemistry, how to solve this problem, in principle: we need to globally study the energy landscape of molecules on surfaces, and identify kinetically and thermodynamically stable regions on this landscape. These so-called locally ergodic regions [18][19][START_REF] Schön | Proc. RIGI workshop 1998[END_REF][START_REF] Schön | [END_REF] correspond in many cases to local minima on the landscape plus their surrounding basins. Similarly, the powerful global search techniques that have been applied to, and sometimes specifically developed for, the structure prediction of crystals and single molecules in vacuum or solvent can also be employed for the prediction of the structure(s) of molecules on surfaces.

One curious difference between molecules on surfaces and e.g. in crystals is the amount of firm atom-level structure information available from experiment. While in crystalline compounds one usually knows the positions of all atoms involved from X-ray and/or neutron scattering -unless the crystal is disordered -, only in rare cases one knows more than the rough shape of the molecule on the surface with resolution down to about 1/2 nanometer. Even worse, in many instances the chemical identity of the atoms observed with e.g. a scanning tunneling microscope cannot be determined through this measurement. As a consequence, most of the theoretical work about structures of molecules on surfaces has been aimed at structure clarification, and to a much lesser degree at structure prediction, although the computational tools employed could equally well be used for the latter endeavor, in principle.

In this mini-review, we present an overview over the current state of the field regarding the use of theoretical methods for the clarification and prediction of structures of medium-sized and large organic molecules and biomolecules on surfaces. This is of great interest for basic research and technological applications. Indeed, such hybrid bio-inorganic molecular systems [START_REF]Bio-inorganic hybrid materials[END_REF] might serve as ingredients of electronic or sensor devices [START_REF] Sanchez | [END_REF], allow for design of nano-drugs [24], tissue engineering and efficient drug delivery [25], improve our understanding of catalysis [26], lead to efficient sequencing procedures [27], and constitute controllable model systems for the dynamics of complex processes such as protein folding [28]. After a quick summary of the range of experimental studies, we shortly describe some of the most popular computational methods employed. This is followed by an overview over the types of systems studied so far using computational approaches, together with an attempt to draw some preliminary conclusions based on these theoretical investigations with respect to their applicability and general understanding of molecules on surfaces.

Experiment

On the experimental side, (bio)molecules on surfaces have been studied for a long time.

The motivation have been questions like the origin of life [29,30], neurology [31,32], understanding self-assembled monolayers (SAM) [25,[33][34][35][36][37], surface engineering [8,[38][39][40], nanobiotechnological applications [41][42][43], or catalysis [26]. Proteins and peptides have been deposited on metal surfaces of various orientations, such as the (100), (110) and (111) surfaces of Cu, Ag, Au, Ni, etc. [44][45][46][47], on inorganic (oxide) surfaces [29,30] such as SiO 2 [44,48], TiO 2 [49], etc., on self-assembled monolayers [50,51], membranes [52], semiconductors such as Si [53], graphite [44] and graphene [54], just to name a few. These investigations have been performed both in vacuum and in solution [55]. Of great interest has been the formation of ordered structures at low deposition densities (less than one monolayer) ranging from dimers [56] to islands of periodic 2D-structures [57], and the generation of complete self-assembled monolayers [33]. Figure 1 shows three typical experimental results for large flexible molecules (cytochrome C [45], angiotensin II [58], crown-ether [59]) on metal surfaces obtained via scanning tunneling microscopy.

The main tools for the study of the structures the biomolecules exhibit on surfaces have been local probes such as scanning tunneling microscopy (STM) [60,61] or atomic force microscopy (AFM) [62,63], STM-vibrational spectroscopy [64], probes that address single molecules, in principle, but without very high spatial resolution such as IR or Raman scattering [65][66][67], ADXPS [68], NMR [69,70], LEED [71], X-ray spectroscopy [60], and (small angle) X-ray or neutron scattering that in the context of biomolecules should be suitable for the identification of periodic features of the structures. These methods yield information about structural, electronic and vibrational properties of individual molecules, in principle, and possible structural arrangement patterns of small and large groups of molecules. However, the in-principle atomic resolution these methods could provide is usually only possible to achieve in special instances such as for pentacene on Cu [72]; more representative are spatial resolutions of ca. 1/2 nanometer (c.f. figure 1). Furthermore, the chemical identities of the atoms observed, or even the identities of the molecules themselves, are often not directly available through experimental measurements, although dynamic force microscopy appears to be a potential way to address this issue [73].

Typical deposition processes [74,75] are deposition from solution [76], physical and chemical vapor deposition [71,77], and ion soft landing with matrix assisted laser desorption/ionization (MALDI) [START_REF] Räder | [END_REF], or electrospray ionization (ESI) [6,7,[START_REF] Ouyang | [END_REF]48,78] sources. While the deposition from solution has been theoretically analyzed in depth (as we will see below), only few theoretical investigations of the processes involved in ion soft landing have been performed [7].

Theoretical methods

Energy landscape concepts

In the realm of theory, modeling and prediction of the structure of biomolecules has been taking place for about forty years, starting with the so-called secondary structure prediction and the investigation of the protein folding problem (for a review of the early work, c.f. [18,19] and references therein). The theoretical study of biomolecules on surfaces is a more recent field. Nevertheless, in the last years, theoretical and computational methods have largely paralleled the experiments mentioned above (e.g. [44,46,47,53]), with respect to the large variety of systems investigated, and are often guided by experimental information [79].

As is the case with all chemical systems, the (meta)stable compounds or the kinetically stable conformations of individual molecules or clusters, correspond to so-called locally ergodic regions on the energy landscape of the system [START_REF] Schön | Proc. RIGI workshop 1998[END_REF][START_REF] Schön | [END_REF]. The energy landscape is the hypersurface of the potential energy or enthalpy for all arrangements of the N atoms belonging to the chemical system. Each arrangement corresponds to the vector X = (x 1 ,...,x N ) in R 3N where x i is the position vector for the i'th atom in the usual three-dimensional space. As discussed in more detail elsewhere [START_REF] Schön | [END_REF], subregions R of the state space in which the trajectory of the N-atom system X(t) resides long enough to equilibrate on a given observation times scale t obs , t eq (R) << t obs , while at the same time being confined to this region for a sufficiently long time before escaping, t esc (R) >> t obs , are called locally ergodic. This implies that we can compute measurements of observables O, <O> t = (1/t obs )∫ 0 tobs O(X(t))dt, by using the standard ensemble average formula restricted to the region R,

<O> ens = ∑ Xi in R O(X i )exp(-E(X i )/k B T)/Z(R), with Z(R) = ∑ Xi in R exp(-E(X i )/k B T).
In particular, we can define a local free energy

F(R) = -k B T lnZ(R)
for each such locally ergodic region (for a given time scale t obs ).

Clearly, if we want to predict the stable phases or conformations of a chemical system by determining its locally ergodic regions, we need to first identify such candidates and subsequently verify their stability and equilibration on the observational time scale of interest, and finally compute their local free energy. In practice, in most cases, locally ergodic regions are associated with basins of the energy landscape around local minima, and thus various global optimization techniques (for an overview see e.g [START_REF]Modern Methods of Crystal Structure Prediction[END_REF], and references therein) are used to find candidate regions. This is followed by an analysis of the probability flows between these regions, using barrier exploration methods [START_REF] Neelamraju | [END_REF]. In many instances, the stability can be characterized by the generalized barriers surrounding the regions, which include energetic, entropic and kinetic contributions [82,83], or by rate constants [START_REF] Wales | Energy Landscapes with Applications to Clusters, Biomolecules and Glasses[END_REF]84] that can be translated into time-scale dependent free energy barriers [85]. However, this comprehensive approach already employed in the structure prediction of molecules, clusters and crystals, has not been realized for molecules on surfaces so far.

Energy functions

Several types of energy functions can be applied to the study of biomolecules on surfaces, allowing us to deal with a plethora of systems on many time scales and levels of accuracy. We may classify them based on their resolution or degree of accuracy, where the most accurate ones are typically also the computationally most expensive ones.

The most accurate energy functions are those computed via so-called ab initio methods based on quantum mechanics (QM). Among the different types of ab initio methods, density functional theory (DFT) is most commonly used (e.g. [86]). DFT energies are often combined with empirical fitted 1/r n interaction terms that are used to model the van der Waals (vdW) interactions among molecules and between molecules and surfaces, which are difficult to describe with basic QM methods [87][88][89][90]. DFT approaches enable us to treat larger systems compared to classical wave-function based ab initio methods such as the Hartree-Fock method. Nevertheless, using current computational resources, QM methods can only be applied in practice to analyze one or a few small-sized biomolecules on a reduced surface model.

For larger systems, energy functions based on classical mechanics, usually called empirical energy functions or interaction potentials, have to be applied. A plethora of such functions can be found in the literature. The empirical energy functions employed for the modeling of biomolecules on surfaces are predominantly force fields (see e.g. ref.

[ 91,92]), many of which have been implemented in molecular dynamics codes such as GROMACS [93,94], AMBER [28,95,96], NAMD [97] or DL-POLY [98,99]. For the atom-level interactions among molecules and between molecule and surface, Coulomb potentials [100,101] and Lennard-Jones-type potentials -the latter for the description of van der Waals forces -are frequently employed [102,103]. In the case of metallic surfaces, the induced polarization is incorporated via explicit image charges or polarization dipoles [104][105][106]. In addition, some potentials are specially designed or adapted to efficiently reproduce the peptide-peptide or peptide-metal (surface) interactions [107].

In many cases, the empirical force fields are parameterized using QM calculations.

Very popular has been the recently developed GoIP force field [108] used to describe the interaction between organic molecules and gold surfaces. Here, the potentials are usually fitted to results of DFT calculations since reliable atom-level experimental (structure) data are mostly lacking. Furthermore, empirical potentials are used to describe the interactions between the molecule and the surrounding medium, if a solvent is assumed to be present [109,110].

A possible intermediary approach is the combination of different types of energy functions, somewhat reminiscent of the QM/MM methods [111]: While the properties of the molecules can be modeled with MM-type force-fields, an embedded atom model [112,113] can be applied for the underlying surface. For the interaction between the metallic surface and the molecules, a van der Waals and Coulomb-type potential is often assumed to work well. However, the quality of the potential is decisive for the reproducibility of known results [53,114]. Therefore, it is necessary -due to a frequent lack of atom-level resolution experimental data -to compare the results with ab-initio calculations in order to improve the empirical potential parameters.

In order to perform simulations of very large systems, or to reduce computing time, coarse-grained energy models have also been proposed that model interactions between rigid (sub)-groups of atoms inside large molecules [62,115] or even between whole molecules (described e.g. as a single ellipsoid). For instance, a simple Gō-like model can be used to represent intra-molecular interactions in peptides or proteins at the amino-acid residue level, together with a specific residue-based energy function for the interactions with the surface [116].

In addition to the aforementioned physics-based energy functions, statistics-based approaches can also be applied to model hybrid biomolecule-surface systems [117].

Finally, we mention that terms in physical and statistical energy functions can be combined, as is done in ROSETTA's all-atom score function used for protein structure prediction, which has been extended to consider biomolecule-surface interactions [118].

Exploration and simulation methods

Concerning the methods used to explore the configuration space of the molecules on the surface, these fall into several general categories: molecular dynamics (e.g. [119][120][121][122][123][124][125][126][127][128][129]) and Monte Carlo simulations [127,130], global optimization methods [131,132], and steered MD (e.g. [27]) and metadynamics (e.g. [53]) for barrier investigation methods. Perusing the theoretical studies of molecules on surfaces available up to now, it quickly becomes clear that 90 % or more of the investigations employ molecular dynamics. The reason for this lies both in the intuitively high degree of "realism" of the method regarding the reproduction of the kinetic processes involved in structure formation, and in the wide availability of large and well-developed MD-codes suitable, and often specifically designed for efficiently simulating large molecules in solutions or at the interfaces between solid, liquid, and vacuum.

Since the first simulations performed by Alder and Wainwright in the 1950s [133], the method of (classical) molecular dynamics has become an appropriate instrument to investigate structures, conformations, dynamics, and thermodynamics of atomic systems. In the last decades the growth in the field of applications is coupled with the development of both computer power (hardware and architecture) and fast energy functions (see above).

While the first enables the investigation of large systems (up to several millions of atoms [134]) via parallel computing, which can be performed by the linked cell algorithm or the replica data method, the latter enables the modeling of realistic systems.

The systems investigated range from inorganic materials, e.g. crystalline phases or amorphous substances, over organic (polymers) up to complex biomolecules. Using different computational set-ups (external pressures can be applied and the system temperature can be controlled by Nose-thermostats) and environments (for example surface effects / gradients / solutions) will generate appropriate ensembles. These can be applied in order to compare the results of molecular dynamics simulations to those of experiments. In order to determine structural, dynamic and thermodynamic quantities, one typically explores time averages and correlation functions, e.g. determination of the van Hove correlation gives insight into the radial distribution of atomic distances, and the calculation of the velocity autocorrelation [135] or displacement autocorrelation [136] reveals the vibrational spectrum of configurations. This is often combined with periodic local minimizations, in order to gain an overview of possible candidates for kinetically stable structures in the system; this method was first used to identify so-called inherent structures in amorphous solids and liquids.

However, due to internal high frequency vibrations, the time steps used in MD simulations are typically about 1 fs, limiting the simulation time to nano-seconds. Applications of multiple time steps [137] can elongate the simulation time by a factor five. Efforts to reach long simulation times are necessary to address the long-time processes which play a crucial role in biomolecular systems, e.g. protein folding [138]. Furthermore, in the context of many biomolecular simulations a computational set-up which should resemble an experimental one has to include lipids, water molecules or carbohydrates in addition to the biomolecule under investigation. As a consequence, the simulation of such complex systems has led to the development of sophisticated and very specialized interaction potentials, and also to the construction of a number of dedicated MD codes such as AMBER, GROMACS or NAMD.

By now, MD simulations, often incorporating new sampling methods [132,[139][140][141],

have become an established method to reproduce and predict the structures of biomolecules under physiological conditions to elucidate their interactions and to mimic the local dynamics on a time scale of several hundreds ns. Various groups have simulated carbohydrates on metals using DFT [142], the folding of macromolecules on metal surfaces [143], or the adsorption of molecules on various surfaces [144][145][146][147][148][149].

Concerning the global exploration and optimization methods, we find that most of the other (i.e. not-MD-based) standard procedures have been employed in the context of structure prediction of (bio)molecules or clusters in vacuum [START_REF] Wales | Energy Landscapes with Applications to Clusters, Biomolecules and Glasses[END_REF], but much more rarely or not at all for molecules on surfaces. Firstly, there are various types of simulated annealing, i.e. Monte Carlo or MD simulations with slowly decreasing temperature [150],

multiple local optimizations such as stochastic quenches or gradient minimizations, or basin hopping [151] that is analogous to stochastic simulated annealing but with large changes in configurations followed by local minimizations [152]. Other methods suitable for biomolecules, in vacuum or on surfaces, are e.g. the recently proposed so-called threshold-minimization algorithm for the investigation of flexible molecules [153], and a variety of genetic or evolutionary algorithms [154][START_REF] Neelamraju | [END_REF][156], and numerous hybrid approaches combining elements of several methods.

For the exploration of the connectivity and barrier structure of the energy landscape of molecules, various search methods such as standard saddle-point search procedures [START_REF] Wales | Energy Landscapes with Applications to Clusters, Biomolecules and Glasses[END_REF], the threshold algorithm [157] where random walkers explore the landscape below a given set of energy lids [START_REF] Neelamraju | [END_REF]158], and metadynamics [140] where MD or MC simulations are combined with elements of taboo-searches [159] that prevent a return to previously explored parts of the energy landscape [53], are available and have been employed to study molecular systems. Besides these global search methods, there are procedures for detailed studies of the local barrier structure, such as the nudged elastic band methods [160], the string method [161], transition path sampling [84],

discrete path sampling [START_REF] Wales | Energy Landscapes with Applications to Clusters, Biomolecules and Glasses[END_REF], the prescribed path method [162], and the pathopt algorithm [163].

Most of the methods listed above are well known, and they have been employed for many global optimization problems and landscape explorations within and without chemistry (for more details we refer to [18,19,[START_REF] Schön | [END_REF][START_REF]Modern Methods of Crystal Structure Prediction[END_REF] and references cited therein). However, the limited speed of these very general exploration methods -that can be easily employed for all types of optimization problems, however, -is still a central issue. Thus, of special interest in recent years has been a new class of search methods originating from robotics. Relying on the analogy between problems in robotics and structural biology [START_REF] Parsons | Proc. Int. Conf. Intel. Sys. Mol. Biol[END_REF], methods originally developed to compute robot motions have been extended and applied to the simulation of molecular systems. In particular, computationally efficient methods have been developed for sampling and exploring the conformational space of biological macromolecules (see [START_REF] Al-Bluwi | [END_REF] for a survey). Algorithms have been proposed to generate conformational ensembles of flexible segments in proteins (i.e. protein loops) [166][167][168][169] and to simulate their motions [170][171][172].

Combined with methods in computational physics such as normal mode analysis [173], or using appropriate multi-scale molecular models [174], robot path-planning algorithms are able to compute large-amplitude conformational transitions in proteins several orders of magnitude faster than standard simulation methods such as molecular dynamics. In tandem with other optimization methods, robotics-inspired algorithms have also been proposed for the global exploration of the energy landscapes of highly flexible biomolecules [175][176][177].

Comparison with experiment

Most often, no precise atom-level structure information is available to easily verify the predicted structures. Therefore, one usually tries to reproduce the actual experimental measurements, at least approximately. For such a direct comparison with experiment, primarily STM images have been calculated [59], using e.g. the Tersoff-Hamann approach [178], where in many instances just the charge distribution of the molecule on the surface (or even without the surface) has been computed. Computations of STM images taking the shape of the tip of the STM-probe explicitly into account have been performed [179,180], but can be highly problematic since the tip-shape is usually not known with sufficient accuracy.

Another quantity that is, in principle, suitable for a comparison with experiment is the vibrational density of states of molecules on surfaces. This can be calculated either directly from the Hessian for empirical potentials and from approximations to the Hessian via the frozen phonon approximation, or via the Fourier transformation of the velocity-velocity autocorrelation obtained during molecular dynamics simulations [136,181,182]. In particular, the combination of both methods might be suitable for studying the vibrational density of states of biomolecules on a surface, since this combination also allows the computation of decay times of the eigenmodes of the molecule on the surface, and a comparison between the modes of the molecule in vacuum or solution and the ones on the surface. Of course, the modes will contain contributions from both the molecule and the surface. But in many instances one can expect that the molecule and the surface are rather weakly coupled, and thus the individual modes will be dominated by either the molecule or the surface. Figure 2 is a snapshot taken from such a MD-simulation, and shows the deformation of a C 240 bucky-ball right after hitting a graphene monolayer [183].

Procedures and examples

Nearly all theoretical studies of structures of molecules on surfaces have taken place in close association with experiments. Important classes of molecules investigated have been e.g. amino acids, peptides, proteins, and large organic and organometallic molecules [47,93,143,144]. In the appendix, we present a summary of many such examples in form of a table; we note that this list is far from exhaustive, however.

Optimal conformations of individual biomolecules and their multi-molecule patterns [46,184] on many types of surfaces have been proposed, either taken directly from experiment, from short or moderately long MD simulations, or, more rarely, from global optimizations. Subsequent verification of their stabilities is usually restricted to a local optimization or relatively short molecular dynamics simulations starting from the proposed structure. In most instances, experimental data, within the resolution limits mentioned above, had already been available to guide the theoretical investigations by suggesting e.g. the overall shape of the molecule or the approximate arrangements of groups of molecules. The majority of these studies constitute "structure clarifications", where the goal is to show that the experimental measurements are consistent with a proposed structure and / or that the suggested structure is a likely outcome of the deposition route employed in the experiment. In fact, by now, it has become almost routine to add some kind of structure calculation to interpret experimental data;

summaries of such instances going beyond those listed in the appendix can be found in a number of reviews [30,39,60,130,[185][186][187]. In a number of studies, these kinds of calculations have been expanded to study in-depth the details of the interactions between the molecule and the surface, with the goal to explain the molecule-surface binding mechanism. The third stage consists of the global search for optimal conformations of the molecule on the surface, and for optimal patterns of many interacting molecules on the surface. The final step is the computation of the physical properties of these optimal configurations, in order to be able to compare them with experimental data and to analyze the physical and chemical reasons underlying the existence and particular features of the observed structures. Essentially all the studies discussed in this review follow at least some partial route of this flow diagram, but only very few are comprehensive enough to merit being classed as unbiased structure predictions.

At the two extremes lie the straightforward minimization of a single proposed structure candidate and the careful long MD simulation of the deposition process (often modeled in a multistage fashion following the flow diagram outlined in figure 3). In some instances, the latter procedure is general and comprehensive enough to be roughly equivalent to a true global optimization that would have predictive power regarding the outcome of the experiment without any prior experimental measurement available.

Between these two extremes, we find MD simulations of varying lengths with empirical potentials, resulting in a number of (meta)stable structure candidates that could be re-optimized on ab initio level and compared with experimental data. However, the true prediction -in contrast to the verification of experimental data -of the feasible conformations and patterns of biomolecules on metal surfaces requires exhaustive global searches on highly complex landscapes, as discussed above. In the following, we will discuss some important features of the procedures commonly used for structure clarification and prediction, and mention some exemplary studies.

Structure clarification

The starting point, either directly or indirectly, of all the structure clarification studies is some experimental information about the structure of the molecule on the surface.

Typically, this data is available with a resolution down to one, perhaps one half, An extension of this approach, called type B, uses the minimized candidates as starting points of additional relatively short MD-simulations, usually with an empirical potential, in order to verify the stability of the proposed structure. Examples of this type are more rare. For instance, there is the study of the surface immobilized peptide cecropin P1 (cCP1) on a self-assembled monolayer [124]. Here, two very different conformations in aqueous solution were used as starting points of MD-simulations, demonstrating the different behavior and stability of the deposited or tethered, respectively, protein, compared to its behavior in solution far away from the surface.

If the molecule exhibits a noticeable degree of flexibility, then systematically using approach A would force us to test an extremely large number of candidates. To avoid this, multistage procedures have been developed, with all the advantages and disadvantages associated with such methods: on the one hand, multistage methods constitute efficient divide-and-conquer approaches to sampling the configuration space of interest, but the price we often pay is a lack of proof that all relevant configurations have been considered. The most basic of these procedures, called type C in this review, consists of a pre-optimization of the shape of the individual molecule in vacuum or solution before placing the most promising pre-optimized polymorph of the molecule onto the surface at the location suggested by experiment, for the final optimization. An example using this type of procedure is the investigation of the role of van der Waals forces in the adsorption of PTCDA (3,4,9,10-perylene-tetracarboxylic-dianhydride) molecules on KBr [88]. Here, the authors used DFT and DFT+vdW energy minimizations to first pre-test a variety of adsorption sites, upon which careful high-accuracy minimizations followed, demonstrating the importance of the van der Waals term for the energy ranking of the binding sites and the diffusion barriers along selected displacement paths.

Closely related but more complex is procedure D, where the ab initio / high quality empirical potential (local) optimization of a random or e.g. protein-database based starting structure in vacuum (or implicit solvent) is followed by a second local optimization / equilibration in solution via a short MD simulation using an empirical potential. Finally, the solution-equilibrated molecule is placed on top of the surface, usually together with the solution molecules, for the third minimization or local equilibration step. An example of this quite frequently applied procedure is the study of the adsorption orientation and conformation of myoglobin on rutile surfaces [127]. As a first step, the rutile surface was constructed, followed by the construction of the protonated state of the protein in solution.

Keeping the protein rigid, parallel tempering Monte Carlo simulations were performed to determine a starting orientation of the protein on the surface. The configuration with the lowest energy was then used as starting point of the MD-simulations of the protein on the surface, where in addition the protein was immersed in a box of water molecules. It was found that depending on the type of rutile surface (001 or 110), the heme group of the protein was close or far away from the surface, respectively, demonstrating the importance of surface features in the adsorption of proteins.

Structure prediction

The performed in the past for relatively small (< 50 atoms) isolated molecules in vacuum or in solution [152,[START_REF] Neelamraju | [END_REF]184], where the latter one was often modeled as an effective medium [188]. For small systems like e.g. inorganic [START_REF] Neelamraju | [END_REF] or intermetallic [158] clusters in vacuum, such searches could be performed on the ab initio energy level [156], but for larger ones, empirical potentials were employed, often combined with ab initio local optimizations [189]. In contrast, no single-step global optimization studies of individual biomolecules or groups of such molecules on surfaces have been performed so far; the closest to this ideal case are studies where multi-stage procedures of types F or G have been employed. One problem is that the computational effort needed to perform a global optimization even of a small molecule on a surface on ab initio level (for both molecule and surface!) is prohibitively high. Thus the situation for molecule + surface systems is comparable to the one in crystal structure prediction twenty years ago when empirical potentials were used for the global search followed by a local ab initio minimization of all candidate structures found.

Nevertheless, there are some studies following the procedure type F, which could be considered global searches. Such a case is the exploration of the statherin-hydroxyapatite system [190]. The procedure used in this study takes its inspiration from the prediction of protein docking and folding in solvent or vacuum, i.e. it is an analogous algorithm for docking and folding of proteins on surfaces. This algorithm folds a peptide from a fully extended conformation to a solution-and an adsorbed-state structure, and repeats this procedure ca. 10 5 times, yielding an ensemble of protein + substrate structure candidates, from which the ones with the lowest energies are selected for a further analysis and comparison with experiment. One finds that large scale features of the molecule in solution and on the surface are predicted reasonably well.

We will close this section with an example of a recent global optimization following procedure G, where no molecular dynamics simulations have been involved, addressing the structure prediction of small sugar molecules on a variety of noble metal surfaces [191]. First, the most representative energy minimum conformations of a single molecule on the surface were determined using a new robotics-inspired stochastic method for global optimization [192]. An empirical potential was used at this level for the energy computations. Figure 4 shows some low-lying minimum configurations representing major basins on the energy landscape of an individual sucrose molecule on a Cu (111) surface. Then, ab initio local optimizations of the molecule on the surface were performed to improve the quality of the identified conformations. Finally, the self-organization of groups of these molecules on the surface was analyzed using a certain variant of basin hopping simulated annealing (implemented in G42+ [193]). These global optimizations identified stable low-energy structures (such as the one shown in Figure 5) that qualitatively agree with experimentally observed STM images [START_REF] Abb | Poster at Eur. Conf. Surf. Sci[END_REF].

Structure explanation

Structure clarification to assist the experiment and structure prediction to guide future experiments are important goals in the theoretical investigation of the structure of molecules on surfaces. Going beyond the issue of correctly assigning a structure model to a given molecule on a specific surface, we would like to also explain the mechanism underlying the structure formation in the molecule+surface system. Obtaining such an explanation would allow us to understand details of the observed structures and of the experimental measurements, and thus guide us in the choice of interesting new systems to explore.

However, a major concern regarding the explanatory power of calculations clarifying and predicting such structures is the choice and quality of the energy function employed. The empirical potentials usually used for the MD-simulations are inherently limited in this respect, even though specially fitted interaction potentials can often generate structures that agree with experiment quite well. But in particular when trying to identify the dominating interactions among molecules, between molecule and solvent, and between molecule and surface, we must employ ab initio energy calculations. In this subsection, we summarize a couple of examples, where such an analysis has been performed.

A system frequently studied is benzene on metal surfaces. For instance, let us consider a density functional theory study [START_REF] Morin | [END_REF] using the generalized gradient approximation (GGA) and the Perdew-Wang exchange-correlation functional to investigate benzene on a Pt (111) surface. The authors concluded that the most favorable arrangement places the aromatic ring on bridge sites parallel to the surface. In this conformation, the molecule is slightly distorted such that it can form six C-Pt bonds with four Pt-atoms at the surface. This contrasts with the alternative, a placement on a hollow site, where six C-Pt bonds are formed but only with three Pt atoms.

Decomposing the adsorption energy into the most important contributions leads to three terms. Two of these must be paid for, i.e. they raise the overall energy of the system: the distortion energy of the molecule relative to the conformation in the gas phase, and similarly the distortion energy of the surface compared to the unperturbed surface. These terms are balanced by the interaction energy of the distorted molecule with the distorted surface, which stabilizes the adsorbed molecule on the surface. The distortion energy is considerably larger on the bridge site (1.51 eV) than on the hollow site (0.87 eV), and the distortion energy of the surface is approximately the same (0.33 eV vs. 0.35 eV). We note that this surface distortion contribution is more important for larger aromatic molecules, such as naphthalene and anthracene, than for benzene. But this energy price is worth paying: the gain in interaction energy equals 2.74 eV for the bridge site, in contrast to only 1.90 eV for the hollow site. The distortion of the molecule also affects its HOMO-LUMO gap, which changes from 5.06 eV in the gas phase to 3.94 eV on the surface, and, of course, leads to a redistribution of the electron density depleting the π and π* molecular orbitals.

We can contrast this with another study of benzene on a Cu(110) surface [196],

where the authors include explicit van der Waals interaction terms in addition to their DFT energy (GGA and PBE exchange-correlation functional). These calculations show again a planar arrangement of the benzene molecule on the metal surface for the optimal configuration. The effect of the van der Waals term barely reduces the distance between the chemisorbed benzene and the surface from 2.43 Å to 2.35 Å, indicating that the partly metallic character of the benzene-metal interaction is not strongly affected by the introduction of the van der Waals interaction. A quantitative analysis shows that the chemical interaction between molecule and surface increases. This effect is not large for benzene, but it becomes quite significant for N-substituted ring molecules such as pyridine and pyrazine. For these molecules, the molecule-surface distance also changes considerably from 2.98 Å to 2.43 Å for pyridine, and from 2.99 Å to 2.59 Å for pyrazine, respectively. This leads to an increase of the metallic character of the molecule-surface bond and thus changes the character of the adsorption from physisorption to chemisorption in the case of pyridine and pyrazine.

A second popular system is fullerene on metal surfaces. In a study of C 60 located on top of a surface atom for a Au (111) and Ag(100) surface [197], DFT calculations with the LDA exchange-correlation functional were performed, in order to investigate the C 60 -surface bonding and the charge transfer involved. It is found that the charge transferred from Au (111) to C 60 is very small, while it amounts to about 0.2 electrons for C 60 on Ag (100). While in both cases one would speak of physisorption, it is clear that on Au (111) the bonding mechanism is a charge-neutral polarization, similar to what is usually modelled via e.g. van der Waals interactions, and the mechanism on Ag( 100) is a combination of polarization and ionization.

Additional information has been gained from another DFT study [198] using GGA and a Becke-Perdew exchange-correlation functional, this time for C 60 on a Cu (111) surface. Here, several positions of the fullerene molecule on the surface were compared,

showing that several kinetically stable local minimum configurations exist. Regarding the bonding, the authors find a considerable charge transfer of about 0.5 electrons indicating that we are facing chemisorption in the case of C 60 on copper, in contrast to the gold and silver substrates. However, we note that neither of these two investigations included energy terms that can model the charge localization or electron correlation effects with sufficient accuracy to decide which of the sites is the energetically preferred one.

Furthermore, inclusion of such net-attractive terms might change the classification of the C 60 -Au-and the C 60 -Ag-surface interactions to chemisorption.

As a final example, we consider a study of the formation of a gadolinium -(4,1',4',1''-terphenyl-1,4''-dicarbolic acid) network on Cu(111) [199]. The ab initio DFT calculations were performed in the generalized gradient approximation for the PBE exchange-correlation functional. It was found that the presence of the surface increased the binding energy of the network by about 1.7 eV per molecule. The molecules are slightly tilted by about 5° with respect to a completely planar arrangement on the surface, and the carboxylic groups are rotated by about 45° to increase the amount of bonding between the Gd-and O-atoms. Furthermore, there is a large charge transfer between gadolinium atoms, terminal oxygen atoms and the surface. Using a Bader analysis, one finds that there is a positive charge of about +2.1 electrons associated with the Gd-atom, one of -1.1 electrons with each of the oxygen atoms, and a net value of about +0.9

electrons transferred from the surface to the metal-organic assembly unit, respectively.

Thus, the authors of the study conclude that there are strong ionic features controlling the optimal structure of the metal-organic network.

Other interesting non-standard studies

One type of theoretical structure investigations that is very common in the case of solid state chemistry is the so-called structure determination. Here, important structural information is available, such as the unit cell parameters and the unit cell content, and perhaps even a powder diffractogram of the sample, but the positions of the atoms inside the cell are unknown. Combining this experimental information and global optimizations that minimize the energy or a combination of energy and similarity between measured and computed structure factors, one can determine the unknown structure with high probability. Such a type of study is very rare in the molecule-on-surface system, but might occur more often in the future with improvements of e.g. computed and measured STM-images that could be combined to deduce the atom positions in the molecule directly with high confidence.

An example is the study of conformational changes of Cu-tetra-3,5-di-terbutylphenyl porphyrin molecules on Cu(211) [200]. Using the elastic scattering quantum chemistry technique for the energy calculation and the sum of the energy and the "difference between computed and experimentally observed STM-images" as the cost function of the global optimization (a so-called Pareto-optimization), the authors could show that two slightly different STM-images could be associated with an ON and OFF state of the molecule, which were characterized by the orientation of one of the legs in the porphyrin molecule.

While many of the studies mentioned in this review have modeled the adsorption process from solution, at least to some degree, only few theoretical studies of some aspects of the deposition/adsorption process during ion-soft landing have been performed [201]. These include the collision of cytochrome C with a Cu(100) substrate [143], the adsorption and self-assembly of pyrene-polyethylene on graphene [144],

deposition of tripetide on rutile surfaces [145], and the adsorption and patterning of DNA-bases on Au(111) [146,147]. Other interesting studies deal with the dynamics of cytochrome C on Au [148], and the RNA adsorption on SAMs [149].

Finally, we present an example where steered MD is used to show that different DNA-bases can be identified by moving a DNA-fragment through a graphene nanopore, essentially associating each base-nanopore interaction with a kind of energy barrier [27].

To do so, the molecule was placed close to the nanopore and solvated in a box of water.

Next, a harmonic spring force was applied to one of the ends of the molecule, forcing it to move through the nanopore. Measuring the resistance force acting on the spring during the steered MD-simulation yielded characteristic force profiles that could be associated with the passage of specific bases (A, T, C, G, and 5-methylcytosine).

Conclusion and outlook

While most of the work on (bio)molecules on surfaces in the literature is concerned with experimental investigations, by now also a considerable oeuvre of theoretical studies exists. We can classify these studies according to the degree to which the simulation is guided by available experimental data. The vast majority of these studies deal with the clarification and interpretation of experimental measurements, thus complementing the experimental observations.

In principle, those computational procedures that go beyond local minimizations by employing MD-simulations would be capable of actually predicting the structures of molecules on surfaces without relying on experimental data, in analogy to the by now well-established prediction of crystal structures and molecular / cluster conformations in vacuum or in a solvent. But the computational efficiency of straightforward deterministic MD-simulations is usually not sufficient for this purpose.

Thus, it is encouraging that new fast global optimization techniques and energy landscape exploration methods are being developed that are dedicated to the unbiased structure prediction of molecules on surfaces. Similarly, established stochastic optimization algorithms are being adapted to address this exciting problem. Considering the state of the field described above, it appears that we are fast approaching a break-through point in the prediction of molecules on surfaces. Thus, we expect that within another five to ten years we will have reached the ability to predict the structures of molecules on surfaces with comparable success to that of crystal structure prediction today.

Appendix:

Table 1: List of structure simulation studies of (bio)molecules on surfaces. "Molecule", "Solvent" and "Surface" characterize the system that is investigated in paper no. "Ref.".

In a number of studies, the effects of different solvents and surfaces are compared, thus several solvents and surfaces are listed. "S/P" refer to whether the structure of single individual molecules (S) or whole structure patterns of many molecules (P), respectively, are investigated in the paper (for example, Y/N is short for Yes/No, with the first entry referring to single molecules and the second to whole patterns). "Type" denotes the simulation strategy according to the classification described in section four in the main text, and "Energy" indicates the kind of energy function(s) employed in the study; here, "emp." refers to any empirical potential. Finally, "Focus" informs about the main focus of the study, as far as the theoretical aspects are concerned. This list aims to give an overview over many typical studies in the field ordered by the name of the molecule involved, but it is far from exhaustive, of course. 2"nm" 10"nm" a" b" c" 0.5"nm" 0.5"nm"

Molecule

Cs"24,crown,8"

Na"24,crown,8"

Figure 3

 3 Figure3shows a generic flow diagram that contains all the elements of a multi-stage set-up that would allow us to derive the structures of molecules on surfaces a priori, based only on the information which type of molecules are to be adsorbed on

  nanometer, if at all. Combined with chemical information and intuition about the molecule -is the molecule rigid or flexible?, would we expect the formation of covalent bonds between (parts of) the molecule and the surface?, can the molecule form metal-organic complexes with individual metal atoms usually expected to be present on the surface?, etc. -, this is often sufficient to propose a candidate structure for the molecule or whole patterns of molecules on the surface. In this situation, the theoretical contribution commonly addresses the following issues: a) If the molecule is flexible, what is its actual shape, and does it differ from the shape in vacuum / solution / crystal? b) How is the molecule aligned / positioned / oriented with respect to the underlying surface? c) Does the surface reorganize due to the presence of the molecule? d) Is the proposed shape / positioning / arrangement pattern of the molecule(s) on the surface a stable configuration?In the literature, we find a number of procedures, of increasing complexity, that are applied to answer these questions. Very frequently, one or a few positions and/or shapes of the molecule are constructed by hand and locally minimized with respect to energy, often on ab initio level. This is particularly common for rigid molecules where only one or two different shapes are feasible and only minor changes are expected upon placing the molecule onto the surface. An example of this very common procedure, called type A in the table in the appendix, is the formation of supramolecular islands of deprotonated 1,3,5-tris(4-ethynylphenyl) benzene (ext-TEB) on Cu(111) [184]. Here, careful DFT-minimizations of individual molecules and multi-molecule arrangements in agreement with experimental observations were used to analyze and interpret the experimental data and to understand the types of bonding among the molecules and between the molecules and the surface.

  multistage procedure type D presented in the previous subsection has already the potential to evolve into an unbiased global search procedure if the final minimization is replaced by very long MD simulation that can explore a representative sample of the full configuration space of the molecule-surface system. Of course, up to now such simulations cannot be performed on ab initio level, and thus one is often forced to add a further local optimization on ab initio level afterwards. Furthermore, one would want to also employ global optimization techniques during the first stages of the procedure, and use as many of the outcomes of the early stages as possible for starting points of the long MD simulations. Computational schedules that follow this route at least to some degree are denoted type E procedures in the table, while those that are fully global and unbiased would be a type F procedure when they are based on MD-simulations and type G if they do not involve MD simulations as part of the global optimization. Finally, there are investigations employing essentially one moderately long MD-simulation stage; these studies are summarized in the table as type H procedures. An example of type E studies which only weakly rely on experimental structure information but are not yet fully global is the modeling of a 2D-molecular self-assembly of 1,3,5-tris(4'-X-Y-phenyl) benzene molecules (X = H, Br; Y = mono, bi) on a Si:B surface[53]. In this study, the first step consists of a DFT-investigation of the individual molecules. Next, metadynamics simulations with empirical force fields are performed for single molecules on the surface, yielding elementary building blocks. From these, one constructs by hand two-dimensional lattices (presumably roughly in agreement with experimental images), which serve as starting points of long MD-simulations. Finally, the outcomes of the simulations are compared with the experiment, where one finds that the results of the simulations are in good agreement with what chemical intuition would suggest for the experimentally observed patterns. We note that procedures F or G (and possibly already C, D or E) usually include a global optimization of the individual molecule in vacuum or solution. Such global structural optimizations of individual molecules without a surface have been frequently

Figure captions:Figure 1 :

 1 Figure captions:

Figure 2 :

 2 Figure 2: C 240 -buckyball hitting a graphene surface, Note the deformation of the C 240 molecule and the dip on the graphene surface. Figure based on ref. [183].

Figure 3 :

 3 Figure 3: Generic flow diagram of the computational elements of a multi-stage procedure to predict the structures of molecules on surfaces, i.e. conformations of individual molecules and arrangement patterns of assemblies of molecules. The arrows indicate that the calculations in the next stage are assumed to be able to start from configurations derived in the previous stage. The theoretical studies discussed in this review usually include only some stages of the flow diagram, e.g. the investigation might start with a global optimization of the molecule in the solvent, followed by a deposition by hand on the surface, and finishes with a local optimization of the molecule's conformation on the surface. Alternatively, one might perform a local optimization of the single molecule in vacuum, which is then placed at random on the surface in vacuum, and globally optimized on the surface, followed by a local optimization of a chemically intuitive pattern of many molecules created by hand. Of course, the original starting point of all studies(not shown explicitly in the diagram) is the choice of the organic molecule or biomolecule that can usually be assumed to preserve its topology (the pattern of bonds) throughout the process, where its structure is taken from some database. Note that while most empirical potentials force the molecule's topology to remain unchanged during the simulations, global optimizations on ab initio level can lead to the break-up (or even merger) of molecules, in principle, although such a massive reconstruction of the molecule will only rarely occur.

Figure 4 :

 4 Figure 4: Four low-energy minima conformations belonging to different major basins on the energy landscape of an individual sucrose molecule on a Cu(111) surface. Colors: White = H-atom, red = O-atom, blue = C-atom, golden = Cu-atom. Starting point of thesearch was a sucrose molecule that had been optimized in vacuum (following the procedure described in ref.[153]) and then placed on the copper surface. The global optimization of the molecule on the surface allowed the variation of all dihedral angles and of the position and orientation of the molecule with respect to the Cu-surface. Figure based on ref.[191].

Figure 5 :

 5 Figure 5: Low-energy minimum structure pattern of many sucrose molecules on a Cu(111) surface, observed during global optimization using a basin-hopping simulated annealing type algorithm. Starting point of the global search were several molecules with the conformation shown in Figure 4a), which had been placed at random on the substrate inside a variable simulation box with periodic boundary conditions in the two dimensions parallel to the substrate surface. During the search, simulation cell parameters, and position and orientation of the sucrose molecules were allowed to vary. Note that the aim of this figure is to show the overall pattern observed as a result of the global optimization, not the atom-level structural details of how the sucrose molecules individually are positioned on the surface. Figure based on ref.[191].

Figure 1 :

 1 Figure 1:

Figure 2 :

 2 Figure 2:

Figure 3 :

 3 Figure 3:

Figure 4

 4 Figure 4:

Acknowledgements:

We would like to thank S. Rauschenbach and M. Ternes for helpful comments and suggestions, and S. Rauschenbach for kindly providing figure 1.


Preventing "Monkey Business". Fettered Apes in the Middle Ages

The practice of keeping monkeys and apes in captivity during the Middle Ages, mainly as pets, is well known. Janson, in his classical study, Apes and Ape lore in the Middle

hauz homes font chiertez") even though this animal is unpleasant and ugly. Alexander Neckam, at he beginning of the 13 th Century, writes that one could find domestic apes at the court of the rich (De naturis rerum, 208, cap. 128).

Mâcon, Bibliothèque municipale, Ms 1, f. 211, 15th Century

In a sermon attributed to Hughes of Saint-Victor (Paris, BnF, Ms. Latin 14934, f. 82), it is written that even clerics like to keep them in their house: "even though the ape is a most vile, filthy, and detestable animal, the clerics like to keep it in their house and to display it in their windows so as to impress the passing rabble with the glory of their possessions" (Janson 1952, 30 and 57, note 4). In the thirteenth century, canons of Notre-Dame of Paris still kept monkeys in the cloister (Cartulaire de Notre-Dame de Paris, t. II, p. 406). Thus, kings, nobles and higher clergy loved to have them at court, as a diverting pet and also as a demonstrable sign of wealth.

Monkey business, or pets going ape

Petrarch criticizes the possession and the search for exotic animals; about monkeys he adds that they are ugly animals and create a mess at home by destroying and scattering whatever they find (Petrarch,Remedies for Fortune I.61: 180). Some mediaeval documents show us more precisely the damage that apes could do. Alexander Neckam relates that a monkey destroyed and tore pieces of leather with a knife he stole from a cobbler, after gaining entry to his empty house through an open window (De naturis rerum, 209, cap. 129).

A monkey destroyed a charter at the court of Robert, Duke of Burgundy in the year 1288. The chancery of the Duke had to copy some original letters of his ancestor Eudes, dated from the beginning of the 12th century, because Robert's monkey had torn the documents. And even worse, the copy charter relates that the animal completed his crime by separating the seal from the letter (Guyotjeannin 2001, 211-219). Apes therefore had to be prevented from carrying out their "monkey business" of tearing charters or leather into pieces.

Collars and leashes

You can keep apes and monkeys in cages, but medieval texts and images report that monkeys actually lived rather freely in houses and castles. proprietatibus rerum, XVIII, cap. 94, cf. Janson 1952, 82). Pierre Bersuire mentions this information and adds a Christian moralization: linking the monkey to the wooden block symbolises the self-enslavement of the rich to their own avarice -his description may really be an attack against that strange pleasure of wealthy people to keep such awful and devilish beasts like monkeys! (Reductiorum morale, lib. X, cap 90, 9, p. 413 § 13)

Instead of keeping monkeys all day on leashes or chaining them to walls, people used to restrain their movements using an heavy block or bowl, like human prisoners. We have a few testimonies about these blocks, in documentary sources and in iconography.

In the accounts of Jean de Berry, in the year 1376, it is said that Jehan d'Estampes was paid for making a rounded wood bowl and an iron chain for the duke's monkey. The same year, John of Berry paid Henry, a locksmith from Paris for another iron chain for securing his monkey (Guiffrey 1899, 75). Queen Isabeau of Bavaria had a monkey that was chained to a wooden bowl that turned within an iron circle (Chartier,Chronique,III,283).

Detail of the Tapestry of the Lady and the unicorn, Musée de Cluny, Paris, circa 1500

In

Concluding remarks

We always need to keep in mind that some of the animals found in art may also reflect real animals in courtly life. If symbolic patterns are often obvious, we have to remember that monkeys were REALLY chained, fettered and linked to blocks, to prevent "monkey business". Keeping apes and monkeys at home was part of everyday courtly life, and the chains, bowls and leashes used to restrain them, were part of the material culture of living with exotic pets. While all these objects used to constrain the monkey's mobility was, on the one hand, part of the animal's life it could sometimes also be hurtful and cruel. Not only did the heavy block represent a symbol of evil pleasures, complacency, habit and the heavy burdensome affairs of the human condition for Christian scholars (Janson

  The monkeys were also attached to leashes like dogs as you can see in this painting by Lorenzetti.Den Haag, Koniklijke Bibliotek, Ms. 135 K40, f. 14, 15th century Two apes with red collars, chains and belts. Detail from Gentile da Fabriano, Adoration of the Magi, 1423. Tempera on wood. 173 × 200 cm. Florence, Offices, Inv. 1890 n. 8364. Bowls, blocks and chains The 13 th Century encyclopaedist Bartholomew of England says that the ape, which is a fierce and malicious beast, may be tamed thoroughly by violence using whips and chains. He adds that wooden blocks (trunco sive blocco) are attached to monkeys to prevent them from going anywhere they want to and to suppress their insolence (De

  the Palace of Jacques-Coeur, in the city of Bourges, capital of the Dukes of Berry at the end of the Middle Ages, one can find a curious monkey ballet sculpted in the stone of a chimney and dating to the end of the 15th and the beginning of the 16 th century. Monkeys are attached to wooden blocks by ropes. Palais Jacques-Coeur, Bourges, 15th-16th Century.

Preventing "Monkey Business". Fettered Apes in the Middl... https://mad.hypotheses.org/37 2 sur 11 30/03/2016 18:32

Preventing "Monkey Business". Fettered Apes in the Middl... https://mad.hypotheses.org/37


Mathew Goonewardena
email: mathew-pradeep.goonewardena.1@ens.etsmtl.ca

Samir M Perlaza
email: samir.perlaza@inria.fr

Animesh Yadav
email: dav.animesh@uqam.ca

Wessam Ajib
email: ajib.wessam@uqam.ca

Generalized Satisfaction Equilibrium: A Model for Service-Level Provisioning in Networks

This paper presents a generalization of the existing notion of satisfaction equilibrium (SE) for games in satisfaction form. The new equilibrium, which is referred to as the generalized SE (GSE), is particularly adapted for modeling problems such as service-level provisioning in decentralized selfconfiguring networks. Existence theorems for GSEs are provided for particular classes of games in satisfaction form and the problem of finding a pure strategy GSEs with a given number of satisfied players is shown to be NP-hard. Interestingly, for certain games there exist a dynamic, analogous to the best response of games in normal form, that is shown to efficiently converge to a pure strategy GSE under the given sufficient conditions. These contributions form a more flexible framework for studying selfconfiguring networks than the existing SE framework. This paper is concluded by a set of examples in wireless communications in which classical equilibrium concepts are shown to be not sufficiently adapted to model service-level provisioning. This reveals the relevance of the new solution concept of GSE.

I. INTRODUCTION

Game theory has played a fundamental role in the analysis of decentralized self-configuring networks (DSCNs), e.g., sensor networks, body area networks, small cells, lawenforcement networks. See for instance [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF]- [START_REF] Alpcan | Mechanisms and Games for Dynamic Spectrum Allocation[END_REF] and references therein. A DSCN is an infrastructure-less network in which transmitters communicate with their respective receivers without the control of a central authority, for instance, a base station. Therefore, radio devices must autonomously tune their own transmit-receive configuration to meet a required quality-of-service (QoS) or quality-of-experience (QoE), as well as efficiently exploit the available radio resources. The underlying difficulty of this individual task is that meeting a given QoS/QoE depends also on the transmit-receive configuration adopted by all other counterparts. This suggests that communications networks can be modeled by games as first suggested in [START_REF] Blachman | Communication as game[END_REF], which justifies the central role of game theory.

An object of central attention within this context is the notion of equilibrium. In particular, the notion of Nash equilibrium (NE) [START_REF] Nash | Equilibrium points in n-person games[END_REF], [START_REF] Nisan | Algorithmic game theory[END_REF] is probably the most popular solution to games arising from DSCNs. An NE is reminiscent to notions used in mechanics, for instance, a small perturbation to a system at a stable (mechanical) equilibrium induces the system to spontaneously go back to the equilibrium point. Similarly, within a communication network operating at an NE, any transmitter unilaterally deviating from the equilibrium point degrades its own individual performance and thus, backs down to the initial equilibrium configuration. The relevance of the notion of equilibrium is that it sets up the rules under which a DSCN can be considered stable, and thus exploitable. In any other state, the network cannot be fruitfully exploited as there always exists at least one radio device aiming to change its individual transmit-receive configuration. Aside from NE, there are other notions of equilibria particularly adapted to DSCN. Each solution concept has advantages and disadvantages, as described in [START_REF] Perlaza | Game-Theoretic Solution Concepts and Learning Algorithms[END_REF].

A major disadvantage that is common to most of equilibrium concepts is that stability depends on whether or not each radio device achieves the highest performance possible. This does not necessarily meet the original problem in which radio devices must only ensure a QoS or QoE condition [START_REF] Meshkati | Energy-efficient resource allocation in wireless networks with quality-of-service constraints[END_REF]. To overcome this constraint, a new solution concept known as satisfaction equilibrium (SE) was suggested in [START_REF] Ross | Satisfaction equilibrium: Achieving cooperation in incomplete information games[END_REF] and formally introduced in the realm of wireless communications in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], [START_REF]Satisfaction equilibrium: A general framework for QoS provisioning in self-configuring networks[END_REF]. The SE notion relaxes the condition of individual optimality and defines an equilibrium in which all radio devices satisfy the QoS or QoE constraints. From this perspective, radio devices are not anymore modeled by players that maximize their individual benefit but by players that aim at satisfying some individual constraints. This new approach was adopted to model the problem of dynamic spectrum access in [START_REF] Ren | User demand-centric distributed wirless resource sharing in dynamic environment: A QoE game perspective[END_REF]- [START_REF] Ellingsaeter | Frequency allocation game in satisfaction form[END_REF] and small cells in [START_REF] Perlaza | On the decentralized management of scrambling codes in small cell networks[END_REF]. Other applications of SE are reported for instance in the case of collaborative filtering in [START_REF] Xu | User participation game in collaborative filtering[END_REF]. In [START_REF] Goonewardena | Existence of equilibria in joint admission and power control for inelastic traffic[END_REF], it is shown that the games in normal form discussed in [START_REF] Andrews | Maximizing capacity in arbitrary wireless networks in the sinr model: Complexity and game theory[END_REF], [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF] have satisfaction form representations, such that their pure strategy NEs coincide with the SEs. However, the notion of SE as introduced in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] presents several limitations. As pointed out in [START_REF] Southwell | Quality of service games for spectrum sharing[END_REF] and [START_REF] Mérriaux | On the achievability of efficient satisfaction equilibrium in self-configuring networks[END_REF], the notion of SE is too restrictive. Simultaneously satisfying the QoS/QoE constraints of all radio devices might not always be feasible, and thus an SE cannot be achieved, even if some of the radio devices can be satisfied. Hence, existence of an SE is highly constrained, which limits its application to wireless communications. These limitations are more evident in the case of mixed-strategies. In mixed-strategies, an SE corresponds to a probability distribution that assigns positive probability to actions that satisfy the individual constraints for any action profile that might be adopted by all the other players.

A. Contributions

In this paper, the notion of SE presented in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] is generalized to embrace the case in which only a subset of the radio devices can satisfy their QoS/QoE individual constraints. This new notion of equilibrium is referred to as generalized satisfaction equilibrium (GSE). At a GSE, there are two groups of players: satisfied and unsatisfied player set. The former is the set of players that meet their own QoS/QoE conditions. The latter is the set of players that are unable to meet their own QoS/QoE, given the actions adopted by all the other players. The key point is that at a GSE, none of the actions of a given unsatisfied player allows meeting the individual QoS/QoE constraints and thus, none of the players unilaterally deviates from an equilibrium point. Note that if all players can be satisfied, then the notion of SE and GSE are identical.

The existence of GSEs in games in satisfaction form is studied and general existence results are presented for some classes of games. Interestingly, these existence conditions are less restrictive than those observed for the case of SE in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF]. Nonetheless, the existence of a GSE is shown to be not ensured even in the case of mixed-strategies. This contrasts with other game formulations, such as the normal-form, for which there always exists an NE in mixed-strategies. Finally, the relevance of SF games in the realm of wireless communications is highlighted by several examples.

The rest of the paper is organized as follows. Sec. II introduces games in satisfaction form and presents the definition of GSE. The complexity of the problem of finding a pure strategy GSEs of a finite game in satisfaction form is also studied in this section. In particular, it is shown that this problem is NP-hard. This section concludes by presenting a satisfaction-response dynamic and identifies sufficient conditions under which this dynamic converges to a pure strategy GSE. Finally, Sec. IV concludes this paper.

II. SATISFACTION FORM AND GENERALIZED SATISFACTION EQUILIBRIUM

This section introduces games in satisfaction form and generalizes the notion of equilibrium presented in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF].

A. Games in Satisfaction Form

A game G in satisfaction form is defined by the triplet

G N , {A i } i∈N , {g i } i∈N , (1)
where N = {1, . . . , N } is a finite set containing the indices of all players. The set A i is finite and contains all the pure strategies (actions) of player i ∈ N . Let (A i ) denote the set of all probability distributions over A i . The correspondence ) determines the set of strategies that satisfy the individual constraints of player i. The notation 2 (Ai) denotes the power-set of the set (A i ). More specifically, given a strategy profile π

g i : (A 1 ) × . . . × (A i-1 ) × (A i+1 ) × . . . × (A N ) → 2 (Ai
= (π 1 , . . . , π N ) ∈ (A 1 ) × . . . × (A N ), player i is said to be satisfied if π i ∈ g i (π -i ), with π -i = (π 1 , . . . , π i-1 , π i+1 , . . . , π N ).
The correspondence g i should not be confused with a constraint on feasible strategies, as in the case of games with coupled actions [START_REF] Scutari | Monotone games for cognitive radio systems[END_REF]. Player i can choose any π i ∈ (A i ) as a response to a given π -i , however, only the strategies in g i (π -i ) satisfy its individual constraints. When only pure strategies are considered, with a slight abuse of notation, the correspondence in pure strategies is denoted by

g i : A 1 × . . . × A i-1 × A i+1 × . . . × A N → 2 Ai .
Then, given a -i = (a 1 , . . . , a i-1 , a i+1 , . . . , a N ), the set g i (a -i ) denotes the set of pure strategies that satisfies the individual constraints of player i.

B. Generalized Satisfaction Equilibrium

Each strategy profile π of the game (1) induces a partition over the set N of players formed by the sets N s and N u . Players in the set N s are said to be satisfied, that is, ∀i ∈ N s , π i ∈ g i (π -i ). Alternatively, players in the set N u are said to be unsatisfied, that is, ∀i ∈ N u , π i ∈ g i (π -i ) . The players in N s are satisfied and thus, they do not possess any interest in changing their own strategy. Conversely, players in N u are unsatisfied and thus, to guarantee an equilibrium, it must hold that none of their strategies can be used to satisfy their individual constraints. This notion of equilibrium, namely generalized satisfaction equilibrium, is introduced by the following definition. Definition 1. Generalized Satisfaction Equilibrium (GSE): A strategy profile π is a GSE of the game in (1) if there exists a partition of N , e.g., N s and N u , such that ∀i ∈ N s , it holds that π i ∈ g i (π -i ) and ∀j ∈ N u , it holds that g j (π -j ) = ∅.

At a GSE strategy profile π, either a player i satisfies its individual constraints or it is unable to satisfy its individual constraints since g i (π -i ) = ∅. From Def. 1 it follows that a pure strategy GSE of ( 1) is a profile a ∈ A, where ∀i ∈ N s , a i ∈ g i (a -i ) and ∀j ∈ N u , g j (a -j ) = ∅. This equilibrium notion generalizes previously proposed solution concepts to games in satisfaction form. An SE, as introduced in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], is a special case of a pure strategy GSE of Def. 1. Specifically, every GSE in which all players are satisfied in pure strategies is an SE, as suggested in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF]. An -SE, as defined in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], is a GSE in which

N u = ∅ and ∀i ∈ N , g i (π -i ) = {π ∈ (A i ) : E 1 gi(a-i) (a i ) = 1 -},
where the expectation is taken over the mixed strategy profile. Finally when = 0, the SE in mixed strategies as introduced in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF], also follows as a special case of the GSE in Def. 1.

The set of all GSEs of a game can be categorized by the number of players that are satisfied. An N s -GSE denotes a GSE in which N s ≤ N players are satisfied. An N -GSE satisfies all players and thus, it is referred to as an SE in this paper. The qualifiers mixed-and pure-for the set of strategies may be omitted when the meaning is clear from the context.

C. Existence of Generalized Satisfaction Equilibria

The existence of a GSE in (1) depends on the properties of the correspondences g 1 , . . . , g N . Let g : (A 1 ) × . . . × (A N ) → 2 (A1)×...× (A N ) be such that for a given strategy profile π, it follows that

g(π) (π 1 , . . . , π N ), (2)
with π i ∈ g i (π -i ), for all i ∈ N . Then, an SE is a fixed point of g, i.e., π ∈ g (π) ,

and thus, the tools of fixed-point equations [START_REF] Border | Fixed Point Theorems with Applications to Economics and Game Theory[END_REF] can be used to state existence theorems of SEs. This is not the case for GSEs. Note that at a GSE action profile π, where N s < N there exists an i ∈ N for which g i (π -i ) = ∅ and thus, a fixed point is not properly defined. This observation highlights the difficulty of providing a general existence result for a GSE. It also emphasizes the key difference between GSE and NE. By definition, an NE is a fixed point of the special case when the correspondences of ( 1) are best response mappings with respect to individual utility functions and therefore, for finite games there always exists at least one NE [START_REF] Nash | Equilibrium points in n-person games[END_REF], [START_REF] Nisan | Algorithmic game theory[END_REF]. Thus, the satisfaction form in ( 1) is a more general formulation that the normal form [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF].

Existence results can be given for very particular classes of correspondences g 1 , . . . , g N . Consider for instance a game in which player i obtains an expected reward given by the function u i : (A 1 ) × . . . × (A N ) → R and it is satisfied only if the expected reward is higher than a given threshold τ i (the expectation is over the mixed strategies). That is, the set of mixed strategies that satisfies the individual constraints of player i is given by:

g i (π -i ) = {π i ∈ (A i ) : u i (π) ≥ τ i } . (4)
Examples of games in satisfaction form following this construction are used in [START_REF] Perlaza | Quality-of-service provisioning in decentralized networks: A satisfaction equilibrium approach[END_REF] to describe several dynamic spectrum access problems. In this case, the game in satisfaction form possesses at least one GSE. This observation is formalized by the following proposition.

Proposition 1. The finite game in satisfaction form in [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF] for which ∀i ∈ N , g i (π -i ) = {π i ∈ (A i ) : u i (π) ≥ τ i } , possesses at least one GSE.

Proof: The proof of Prop. 1 is presented in [START_REF] Goonewardena | Generalized satisfaction equilibrium: A model for service-level provisioning in networks[END_REF]. The statement of Prop. 1 is only for games with the specified correspondences. Prop. 1 does not hold if the correspondence is modified for instance to g i (π -i ) = {π i ∈ (A i ) : τ i ≤ u i (π) ≤ τ i }, with τ i and τ i , any two reals. In general, the existence of an GSE in games in SF is not guaranteed.

An interesting example of a game in satisfaction form that does not possess a GSE in mixed strategies is presented hereunder. Define a two player game in which each player i has two actions a 1 i , a 2 i , i ∈ {1, 2} . The probability that the strategy of player i assigns to action a j i is π i (a j i ), j ∈ {1, 2} . The correspondence of player 1 is

g1 (π2) =      π1 ∈ (A1) : π1 a 1 1 < π1 a 2 1 if π2 a 1 2 ≥ π2 a 2 2 π1 ∈ (A1) : π1 a 1 1 ≥ π1 a 2 1 othewise . ( 5
)
and the correspondence of player 2 is

g2 (π1) =      π2 ∈ (Ai)2 : π2 a 1 2 < π2 a 2 2 if π1 a 1 1 < π1 a 2 1 π2 ∈ (Ai)2 : π2 a 1 2 ≥ π2 a 2 2 othewise . (6)
Let π ∈ Π be an arbitrary strategy profile. Then, one of the following cases holds π 2 a 1 2 ≥ π 2 a 2 2 or π 2 a 1 2 < π 2 a 2 2 . Consider the case π 2 a 1 2 ≥ π 2 a 2 2 . Then, player 1 is either in the case in which π 1 a 1 1 < π 1 a 2 1 or else it is in the case π 1 a 1 1 ≥ π 1 a 2 1 . In the former, i.e., π 1 a 1 1 < π 1 a 2 1 , player 1 is satisfied. In the latter, i.e., π 1 a

1 1 ≥ π 1 a 2 1 , player 1 deviates to π 1 , with π 1 a 1 1 < π 1 a 2 1 .
Either way when player 2 has π 2 a 1 2 ≥ π 2 a 2 2 , player 1 converges to a strategy in which π 1 a 1 1 < π 1 a 2 1 . However, when player 1 is in this case, player 2 is unsatisfied and it deviates to a strategy π 2 a 1 2 < π 2 a 2 2 . This causes player 1 to be unsatisfied in its current strategy π 1 a 1 1 < π 1 a 2 1 and it deviates to a strategy π 1 a 1 1 ≥ π 1 a 2 1 . Since the above cases cover the entire mixed-strategy space, this game does not possess a GSE.

D. Complexity of Generalized Satisfaction Equilibria in Pure Strategies

This section establishes the complexity of the GSE search problem in pure strategies. The problem is stated as follows: given the game in satisfaction form in [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF], if there is a pure strategy SE find it, otherwise indicate that it does not exist. The following proposition asserts its complexity. The method to establish the time complexity of a problem is the polynomialtime Karp reduction [START_REF] Arora | Computational Complexity: A Modern Approach[END_REF]. Proposition 2. Pure strategy SE search problem is NP-hard.

Proof: The proof of Prop. 1 is presented in [START_REF] Goonewardena | Generalized satisfaction equilibrium: A model for service-level provisioning in networks[END_REF]. The pure strategy N s -GSE search problem is: given the game in satisfaction form in [START_REF] Lasaulce | Game Theory and Learning for Wireless Networks: Fundamentals and Applications[END_REF] and a natural number N s , with 1 ≤ N s ≤ N , if there is an N s -GSE, in pure strategies find it, with the highest possible N , otherwise, indicate that it does not exist.

Corollary 1. Pure strategy N s -GSE problem is NP-hard.
Proof: The proof of Prop. 1 is presented in [START_REF] Goonewardena | Generalized satisfaction equilibrium: A model for service-level provisioning in networks[END_REF]. Finding the complexity of the mixed strategy GSE search problem is left as an open problem.

E. Satisfaction Response Algorithm

Solving for a pure strategy GSE of the game in ( 1) is a hard problem in general, see [START_REF] Goonewardena | Generalized satisfaction equilibrium: A model for service-level provisioning in networks[END_REF]. However, it is possible to identify games in satisfaction form that have a special structure and thus, a pure strategy equilibrium can be efficiently found. Suppose Y is an ordered set so that ∀(y, y ) ∈ Y 2 , either y ≤ y or y > y holds. Define finite action spaces A i ⊂ Y, ∀i ∈ N , so that A i is totally ordered as well. For all pairs (a, a ) ∈ A 2 , the relation a ≤ a holds if ∀i ∈ N , a i ≤ a i . Alternatively, the relation a < a holds if ∀i ∈ N a i ≤ a i and for at least one j ∈ N , it holds that a j < a j . The smallest and largest elements of A i are denoted by a i and a i respectively. Define the following vectors, a (a 1 , . . . , a N ) and ( 7) a (ā 1 , . . . , āN ) .

Consider the following mappings:

φ i :A -i → Y and (9)
φ i :A -i → Y. (10)
Given the condition a -i ≤ a -i , the mapping φ i is called order-preserving if

φ i (a -i ) ≤ φ i a -i (11)
and is called order-reversing if

φ i (a -i ) ≥ φ i a -i . (12)
Then consider the game in satisfaction form in (1) and let the correspondence g i , ∀i ∈ N , be defined by

g i (a -i ) = {a i : φ i (a -i ) ≤ a i ≤ φi (a -i ) (13)
in which both φ i and φ i are order-preserving. For a ∈ A, if a i / ∈ g i (a -i ) and if g i (a -i ) = ∅, then there always exists an a i ∈ g i (a -i ) that player i can use to satisfy its individual constraints. This deviation a i is called a satisfaction response and is denoted by

SR i (a -i ) ∈ g i (a -i ).
Let N u ⊆ N be the subset of unsatisfied players with nonempty correspondence, i.e., i ∈ N u , if a i / ∈ g i (a -i ) and g i (a -i ) = ∅. Then, consider the discrete time asynchronous update sequence in which at each instance a subset N ⊆ N u , performs satisfaction response. This update process is called asynchronous, as opposed to synchronous, in which all players in N u simultaneously perform the response and as opposed to sequential, in which only one of those players at a time performs the response. Algorithm 1 provides the pseudo code for asynchronous satisfaction response and Prop. 3 states its convergence properties.

Algorithm 1 Asynchronous Satisfaction Response

Initialize a = a While a is not a GSE: Select N ⊆ N u a := (SR j (a -j )) j∈N , (a i ) i∈N \N Proposition 3. Consider a game in satisfaction form (1) with g i given by (13), ∀i ∈ N . Then, starting at a ∈ A the asynchronous satisfaction response algorithm converges to a pure strategy GSE.

Proof: The proof of Prop. 1 is presented in [START_REF] Goonewardena | Generalized satisfaction equilibrium: A model for service-level provisioning in networks[END_REF]. Note that in Prop. 3, there exists an implicit assumption that every player that finds itself in N u with a nonempty correspondence performs satisfaction response within a finite number of future steps. If ∀i ∈ N and ∀a -i ∈ A -i , φ i , φ i are order-reversing, then Algorithm 1 converges initialized at a ∈ A. Worst case iterations for sequential satisfaction response is O (N max {|A i | : i ∈ N }) which occurs when all players are initially in N u and each player advances to N s with SR i (a -i ) = φ i (a -i ) only to be found back in N u at the beginning of its next chance to respond. Simultaneous satisfaction response is bounded by O (max {|A i | : i ∈ N }) . Convergence time of the more general asynchronous cases can be bounded between the sequential and simultaneous limits, with the minor condition that every player in N u has to perform a response at least once in a predetermined time interval lower than N .

Algorithm 1 applies to infinite action spaces that are closed intervals in the real line. However in that case convergence time may depend on the minimum step size. Power control in continuous domain to achieve a required rate is an example and is discussed later. Sequential satisfaction response up to a predefined fixed number of iterations is discussed in [START_REF] Ross | Satisfaction equilibrium: Achieving cooperation in incomplete information games[END_REF] as a possible learning algorithm however, conditions for convergence are not identified.

III. APPLICATIONS OF GSES

This section presents a particular application of games in satisfaction form in wireless networks. The objective is to demonstrate the applicability of GSE into simple but relevant problems. Power control and channel allocation are the main focus.

A. Uplink Power Control Game

Power control under per user rate requirements has been well studied for its feasible region and Pareto optimal solutions [START_REF] Hande | Distributed uplink power control for optimal SIR assignment in cellular data networks[END_REF]. The possibly infeasible case in which a subset of the transmitters may not be satisfied has received less attention. In [START_REF] Monemi | Distributed multiple target-SINRs tracking power control in wireless multirate data networks[END_REF], the over constrained SINR targets are handled by introducing multiple SINR targets such that the infeasible users switch to lower targets.

The single-input-single-output (SISO) power control game in the interference channel is presented in [START_REF] Scutari | Potential games: A framework for vector power control problems with coupled constraints[END_REF] as a generalized Nash equilibrium problem. The following development considers single-input-multiple-output (SIMO) case as a game in satisfaction form. The baseband equivalent signal at the destination of transmitter i is

y i = √ p i h ii s i + j∈N {i} √ p j h ji s j + z i , (14)
where y i ∈ C ni is the received symbol vector at the receiver of i th transmitter, n i is the number of receiver antennas, s i ∈ C is the transmitted symbol of i, h ji ∈ C ni is the channel between transmitter j and destination of i, and z i ∼ CN (0, σI) is the circular symmetric complex additive white Gaussian noise. The payoff of transmitter i is the achievable rate u i p i , p -i = log(1 + p i h H ii R -1 -i h ii ) bits/sec/Hz, where R -i = j∈N \{i} p j h ji h H ji +σI is the interference plus noise covariance matrix. The transmit power is p i ∈ P i , where P i = [p i , p i ], p i , p i ∈ R ≥0 . The game in satisfaction form played by the transmitters is

G PC N , {P i } i∈N , {g i } i∈N , (15)
in which ∀i ∈ N ,

g i p -i = {p i ∈ P i : τ i ≤ u i (p) ≤ τi } , where 0 ≤ τ i ≤ τi . The
i : φ i p -i ≤ p i ≤ φ i p -i .
From the properties of positive (semi-)definite matrices [START_REF] Horn | Matrix Analysis[END_REF], p -i ≤ p -i implies R -1 -i p -i R -1 -i p -i which in turn implies u i p i , p -i ≤ u i p i , p -i and therefore concludes that φ i p -i ≤ φ i p -i and φi p -i ≤ φi p -i . The inequalities hold strictly if p -i < p -i . Thus by extension of Prop. 3 to action spaces that are closed intervals in the real line Algorithm 1 converges to a GSE in the game [START_REF] Perlaza | On the decentralized management of scrambling codes in small cell networks[END_REF]. If the upper threshold is removed, by setting τi = +∞, the stronger condition p -i < p -i implies g i p -i ⊂ g i p -i .

The standard power control game is to minimize the transmit power with per-user rate constraints and one solution can be a generalized NE. However, a generalized NE might not always exist when the problem is over constrained. Interestingly, when this problem is modeled as a game in satisfaction form, there always exists a GSE.

B. Efficient-GSEs and Admission Control

At a pure strategy GSE p ∈ P of (15), an unsatisfied player i ∈ N u obtains u i (p) < τ i , but may have p i > p i . If a player in N u lowers its power, then it is possible that another in N u can deviate to satisfaction and thus disrupt the equilibrium. In some applications it is desirable that at a GSE ∀i ∈ N u p i = p i . Such profiles are called efficient-GSEs as the N u poses the least interference to N s . Efficient-GSEs do not necessarily exist.

IV. CONCLUSION

This paper presents a generalization of the notion of satisfaction equilibrium, namely the generalized satisfaction equilibrium, (GSE) for games in satisfaction form. When players attempt to satisfy a required service level, rather than maximize their utility, the GSE is a more appealing solution. At a GSE, unsatisfied players are unable to unilaterally deviate to meet their individual constraints. GSE bridges constraint satisfaction problems and games in satisfaction form as the two problems can be transformed into each other.

  upper bound τ i is considered for the sake of generality. For instance the transmitter or receiver may have a maximum operational rate. This model is valid for τi = +∞, which corresponds to rate unbounded from above.Define ∀i ∈ N φ i p -i = inf : u i p i , p -i ≤ τ i . Then restate the correspondence g i p -i ≡ {p i ∈ P

pi∈R p i : u i p i , p -i ≥ τ i and φi p -i = sup pi∈R p i

This work was supported in part by the European Commission under Individual Fellowship Marie Skłodowska-Curie Action (CYBERNETS) through Grant 659316.