Marco Conti

Matteo Mordacchini

Andrea Passarella

Liudmila Rozanova

A Semantic-Based Algorithm for Data Dissemination in Opportunistic Networks

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The increasing, pervasive presence of devices interacting among themselves and their users is leading to a complex and vast information environment, where information flows from the physical world to the cyber one, and vice-versa. Users mobile devices, sensor networks, and all the devices spread in the environment with data generation capabilities (e.g., in Internet of Things applications) will constantly generate huge amounts of data thus generating a very rich information landscape. This scenario is known as the Cyber-Physical World (CPW) convergence [START_REF] Conti | Looking ahead in pervasive computing: Challenges and opportunities in the era of cyberphysical convergence[END_REF]. Mobile devices will act in the CPW convergence scenario as proxies of their human users. They will be in charge of discovering and evaluating the relevance for their human users of the huge amount of information available in the cyber world. This has to be done quickly and using limited resources, as devices will be constantly face large amounts of data items. This situation resemble what the human brain does when it has to assess the relevance of the information coming from the surrounding environment. Since devices will act as the avatars of their owners, considering the way the human brain deals with huge amounts of data in a short time is a sensible point for designing effective and efficient information dissemination schemes in the CPW convergence scenario .

Opportunistic networking [START_REF] Pelusi | Opportunistic networking: data forwarding in disconnected mobile ad hoc networks[END_REF] is one of the key paradigms to support direct communication between devices in scenarios like the CPW convergence. In this paradigm, nodes are mobile, and forwarding of messages occurs based on the store, carry and forward concept. In this paper we present a data dissemination algorithm for opportunistic networks inspired by real human communication schemes. It exploits the semantic representation of data (e.g., tags and other metadata associated to data items) in order to assess the relevance of information to be exchanged among mobile nodes upon contact. A dissemination scheme for spreading the actual content associated with semantic data can be built on top of such an algorithm, as we point out later in Sec. [START_REF] Lenders | Wireless ad hoc podcasting[END_REF]. The focus of this paper is to define and give an initial performance evaluation of a semantic data dissemination mechanism, in order to study the viability of this approach before exploiting it to design effective and efficient content dissemination schemes in opportunistic networks. In this proposal, the data stored in a device is semantically represented using an approach based on semantic networks. A semantic network is a graph, where vertices are the semantic concepts (e.g., the tags associated to data items) and edges represent the connections that exist among them (e.g., the logical link between two tags). We describe how semantic networks can be used to determine the relevance of information to be exchanged upon physical contact among nodes. Essentially, similar to a real human communication, the selection of information starts from a set of semantic concepts in common between the two nodes. The relevance for one node of the rest of the information available in the other node's semantic network can then be assessed based on the links between the semantic concepts in the semantic network. Similarly to a human dialogue, information logically closer to a set of common concepts is exchanged first, and the longer the discussion (i.e. the duration of the physical contact among nodes), the greater the amount of information exchanged. Once an encounter finishes, new semantic concepts are passed from one node to the another, and new connections among new and old concepts can be established, thus increasing the knowledge of each node.

The rest of this paper is organized as follows. In Sec. 2 we review the relevant literature for the opportunistic data dissemination problem. In Sec. 3 we give a general overview of the concepts behind the solution we propose, while in Sec. 3.1, Sec. 3.2 and Sec. 3.3 we describe how semantic networks can be constructed and interact. Sec. 4 presents some preliminary simulation results obtained with this solution. Finally, Sec. 5 concludes the paper.

Related Work

The data dissemination problem in opportunistic networks has been faced by many solutions in literature. PodNet [START_REF] Lenders | Wireless ad hoc podcasting[END_REF] is one of the first works on this subject. The authors of PodNet propose four different strategies to weight the relevance of data to be exchanged on the basis of the estimated popularity of the general topic (channel) the data belongs to. More refined approaches try to take advantage of the information about users' social relationships to drive the dissemination process. For instance, in [START_REF] Yoneki | A socio-aware overlay for publish/subscribe communication in delay tolerant networks[END_REF], the authors propose to build a pub/sub overlay in an opportunistic network. The most "socially-connected" nodes, i.e., those nodes that are expected to be most available and easily reachable in the network, take the role of brokers, as in more traditional pub/sub systems. They are in charge to collect information from their social groups, spread this data among them, and eventually deliver it toward interested peers. Also the authors of ContentPlace [START_REF] Boldrini | Design and performance evaluation of contentplace, a social-aware data dissemination system for opportunistic networks[END_REF] propose to drive the data dissemination process using the social structure of the network of users. Specifically, each node tries to fetch from other encountered peers those data items that are likely of interest to other users it has social relationships with (and which, therefore, are expected to be in touch with them in the near future). In [START_REF] Conti | Data dissemination in opportunistic networks using cognitive heuristics[END_REF][START_REF] Bruno | An analytical model for content dissemination in opportunistic networks using cognitive heuristics[END_REF], the authors define a data dissemination scheme that directly embodies and exploits the very same cognitive rules (cognitive heuristics) used by the human brain to assert the relevance of information. This solution proves to be as effective as another scheme like ContentPlace in disseminating the information, while requiring much less overhead.

With respect to all these approaches, in this paper we take a different direction. None of the approaches above take into consideration the semantic dimension of data. In the following we define how a semantic representation of information can be used to determine the relevance of information to be exchange in an opportunistic network scenario, and we validate this proposal with preliminary simulation results.

Data Dissemination using Semantic Networks

In order to semantically represent the information carried by each user, we exploit an approach based on semantic networks. A semantic network is a graph where vertices are semantic concepts and edges connect semantically related concepts. In order to derive this representation, we consider that each user has a collection of data elements, like pictures, blog posts, status updates, geospatial data, etc. Some of these data items could be difficult to analyze semantically. Anyway, we could take advantage of the fact that many of these data items are usually associated with tags, as happens in many real-world social networks like Twitter, Flickr, Instagram, etc. Thus, a simple and, at the same time, effective way of creating a semantic network is to use data tagging, as depicted in Fig. 1. Tags can then become the nodes of a user semantic network, while edges can be derived from the associations the user has done when tagging their own data. Note that not all the information belonging to a user may by represented in the user's semantic network. It seems reasonable that only information that is assumed to be relevant for the user at a given time is mapped in her semantic network. In order to select this information, we can act in a similar way like the human brain does, exploting an approach built on models of the human forgetting process. Thus, we can assume that information that has not been used for a long time is forgotten, while information that is frequently accessed is harder to forget. Rather than a limit, forgetting is a mechanism that could aid some human cognitive processes (e.g. [START_REF] Schooler | How forgetting aids heuristic inference[END_REF]) by letting them keep and consider only the most relevant data. To model a forgetting process into our system, we propose to introduce a special "forgetting" function similar to an experimental curve that has been first obtained by H. Ebbinghaus in 1885 [START_REF] Ebbinghaus | Memory: A contribution to experimental psychology[END_REF] and then confirmed and refined by numerous subsequent studies (Fig. 2). This curve reflects the exponential decline of individual human memory retention with time. The rate of forgetting depends on the repetition rate of incoming information.

! !! ! ! ! ! !!!!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!!()*%! +')(,!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! +')(,!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"(#-%$!
To model this process, we propose to introduce a special "forgetting" function similar to an experimental curve that has been obtained first by H. Ebbinghaus at 1885 and then confirmed and refined by numerous subsequent studies (Figure 3).

This curve reflects the exponential decline of individual human memory retention with time. The rate of forgetting depends on repetition rate of incoming information.

An algorithm of forgetting is presented at Figure 4.

Using such mechanism in the semantic model looks reasonable, because transferring only the actual and potentially interesting information will save limited network resources.

The example 1 is an illustration of the mechanisms described above.

Thus, the semantic network of each user is dynamic; it is constructed from the individual information by tagging, taking into account the relationships between data elements, and frequency and/or duration of accessing them.!! Example 1.

Each user has a collection of data elements (e.g pictures, blog posts, status updates etc.) associated with tags. These elements have been created and/or modified at different points in time. When a data element is created or requested, links between associated tags are set to the maximum weight. If the user did not access this content for a long time, the weight of links between associated tags decreases, up to their complete disappearance (we can vary the time threshold before it happens).

In that case the actual user's content does not disappear, but it no longer reflected in the semantic network -therefore, transfer of this content to other users does not occur. When a data element is accessed again, the associated tags reappear in the semantic network with the maximum weight.

Picture 1 is not being accessed for some time, so weight of the respective link in the semantic network decreases and eventually the link disappears.

A request for this picture leads to link reappearance.

!

Interaction between users and reconstruction of the semantic networks

Data is transmitted from one person to another by merging of semantic networks when they are interacting; thus the data transfer can be done through chain of users temporarily storing data for each other.

Consider how the semantic network is changing in interaction with another network. This process in our model is similar to real human communication, where people meet, connect, exchange ideas and conceptions, and as a result of such interaction their own systems of knowledge are being restructured.

Any user is able to communicate with all users within the reach. However, in real world people usually talk with those who share at least some common interests. Similar to that, in opportunistic networks information might be transmitted only to those users who have any intersection in their individual semantic networks.

We can organize this process as follows. During the initial connection between users (devices) in the opportunistic network, we ask for a set of tags of all available users. After exchanging the tag sets, we find out which users have the same tags and only the associated data elements will participate in subsequent data transfer (Figure 5).

Specific algorithms of data transfer will be discussed later at the p.3.4.

./012! ./013 Given the description above, the semantic network of each user is dynamic; it is constructed from the individual information by tagging, taking into account the relationships between tags defined by the user herself, and frequency and/or duration of accessing them.

! "#$%&'! ()*%! ! ! ()*%! "(#-%$! +')(,! ! "#$%&'! !!!!!!!!!!!!()*%! !!!!!!!!!!!!!!!!()*%! ! +')(,!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! ! !!!!!!!!!+')(,!!!!!!!"(#-%$!
Using this description, in the following sections we first describe how each device can build its own semantic network from the data it owns. Next, we exploit the semantic network associated to data items in order to define a data dissemination scheme in an opportunistic network scenario, where information is exchanged only upon physical contact between nodes. The algorithm we describe deals with semantic data only. Anyway, it can be easily used as the basis for designing the dissemination of the actual content the semantic data is related to, as we stated in the Introduction. The semantic data exchanged with another node can be used to sort the content items in order to select which of them can be transferred to the encountered peer. For istance, a simple way to do this can be to give precedence to those items with the largest intersection between the semantic concepts associated to them and the set of semantic concepts that are going to be exchanged with the other peer. In this paper, we describe how semantic data can be spread in an opportunistc network scenario, leaving the design of an effective and efficient content dissemination mechanism based on this scheme as a future research direction.

Semantic Network Creation

We define the semantic network of each user as a dynamic weighted graph G = {V, E, f (e, t)} : t ∈ T , where t is the time, V is the set of vertices in the graph, E is the set of edges and f (e, t) is a weighting function for each e ∈ E that reproduces the human forgetting process in our system. In addition, each edge e ij between two vertices i and j has an associated "popularity" p t ij that measures the number of times e ij was present in exchanges with other nodes' semantic networks in the encounters happened till time t.

In the context of an active user participation to the creation of content, we assume that each data item owned by a user is associated with a set of tags, defined by the user herself. In the graph G that represents the user's semantic network, tags are the vertices, while edges connecting tags are created using the following strategy. Firstly, for each data item, its tags are linked together in order to form a completely connected component. Then, each set of vertices carrying the same label (i.e. they where created from tags having the same name) is considered. These are vertices belonging to different components and they are merged together, forming a single vertex with their same label. This single vertex inherits all the edges pointing to the original vertices in their respective components.

As an example of this process, consider the example given in Fig. 3. The user has two different pictures and their associated tags. For the two pictures, two completely connected components are created. Then, the components are merged using the common vertex "lake" as the pivot of this process. An algorithm of forgetting is presented at Figure 4.

Using such mechanism in the semantic model looks reasonable, because transferring only the actual and potentially interesting information will save limited network resources.

The example 1 is an illustration of the mechanisms described above.

Thus, the semantic network of each user is dynamic; it is constructed from the individual information by tagging, taking into account the relationships between data elements, and frequency and/or duration of accessing them.!! Example 1.

Each user has a collection of data elements (e.g pictures, blog posts, status updates etc.) associated with tags. These elements have been created and/or modified at different points in time. When a data element is created or requested, links between associated tags are set to the maximum weight. If the user did not access this content for a long time, the weight of links between associated tags decreases, up to their complete disappearance (we can vary the time threshold before it happens). In that case the actual user's content does not disappear, but it no longer reflected in the semantic network -therefore, transfer of this content to other users does not occur. When a data element is accessed again, the associated tags reappear in the semantic network with the maximum weight.

Consider how the semantic network is changing in interaction with another network. This process in our model is similar to real human communication, where people meet, connect, exchange ideas and conceptions, and as a result of such interaction their own systems of knowledge are being restructured.

Any user is able to communicate with all users within the reach. However, in real world people usually talk with those who share at least some common interests. Similar to that, in opportunistic networks information might be transmitted only to those users who have any intersection in their individual semantic networks.

We can organize this process as follows. During the initial connection between users (devices) in the opportunistic network, we ask for a set of tags of all available users. After exchanging the tag sets, we find out which users have the same tags and only the associated data elements will participate in subsequent data transfer (Figure 5). Specific algorithms of data transfer will be discussed later at the p.3.4.

./012! ./013 ! "#$%&'! ()*%! ! ! ()*%! "(#-%$! +')(,! ! "#$%&'! !!!!!!!!!!!!()*%! !!!!!!!!!!!!!!!!()*%! ! +')(,!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! ! !!!!!!!!!+')(,!!!!!!!"(#-%$!

Forgetting Mechanism

Let us now define the forgetting function f (e, t) as a function that is able to assign a weight to any edge e at a time t. If f (e, t) ≤ f min , where f min is a limiting threshold value, then the edge e does not exist in the semantic network at time t. Initially, at time t 0 = 0, for any e ∈ E, we have that: f (e, t 0 ) = 1. Subsequently, for any edge e ij and time t > t 0 , in each interval (t * , t) , where t * is the last time this edge was used in exchanges with other peers (i.e. its last "activation"):

f (e ij , t) = αe -βij (t-t * )
where α is a normalizing coefficient and β ij is the "speed of forgetting", i.e. the weakening of the connection (taken in accordance with the experimental curve obtained by H. Ebbinghaus [START_REF] Ebbinghaus | Memory: A contribution to experimental psychology[END_REF]). Obviously, β ij depends on the total number of previous connections. Then the "popular" connections are "being forgotten" more slowly in the situation when there are no subsequent connections. So, we can define this parameter as follows:

β ij = β p t ij
, where β is a speed coefficient and p t ij is the "popularity" of e ij at time t, i.e. the number of times e ij has been used in the encounters happened before t. Fig. 4 shows one of the side effects of the forgetting process. Not only edges, but even vertices can be forgotten. In fact, if the deletion of an edge e implies that a vertex v at one of e's endpoints is no longer connected to any other vertex in the network, then v is also deleted from the semantic network. After that, in order for it to reappear in the semantic network, it should be received during successive encounters with other nodes, using the data exchange scheme detailed in the following section.

! !! !!!!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!!()*%! +')(,!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! +')(,!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"(#-%$!
e propose to introduce a special ilar to an experimental curve that H. Ebbinghaus at 1885 and then y numerous subsequent studies xponential decline of individual with time. The rate of forgetting e of incoming information.

g is presented at Figure 4.

n the semantic model looks rearring only the actual and potenation will save limited network ustration of the mechanisms deork of each user is dynamic; it is ividual information by tagging, relationships between data ele-/or duration of accessing them.!! data elements (e.g pictures, blog posts, with tags. These elements have been rent points in time. When a data element between associated tags are set to the id not access this content for a long time, sociated tags decreases, up to their comry the time threshold before it happens). ntent does not disappear, but it no longer rk -therefore, transfer of this content to en a data element is accessed again, the e semantic network with the maximum Picture 1 is not being accessed for some time, so weight of the respective link in the semantic network decreases and eventually the link disappears.

A request for this picture leads to link reappearance. !

Interaction between users and reconstruction of the semantic networks

Data is transmitted from one person to another by merging of semantic networks when they are interacting; thus the data transfer can be done through chain of users temporarily storing data for each other.

Consider how the semantic network is changing in interaction with another network. This process in our model is similar to real human communication, where people meet, connect, exchange ideas and conceptions, and as a result of such interaction their own systems of knowledge are being restructured.

Any user is able to communicate with all users within the reach. However, in real world people usually talk with those who share at least some common interests. Similar to that, in opportunistic networks information might be transmitted only to those users who have any intersection in their individual semantic networks.

We can organize this process as follows. During the initial connection between users (devices) in the opportunistic network, we ask for a set of tags of all available users. After exchanging the tag sets, we find out which users have the same tags and only the associated data elements will participate in subsequent data transfer (Figure 5). Specific algorithms of data transfer will be discussed later at the p.3.4.

"#$%&'! !!!!!!!!!!!!()*%! !!!!!!!!!!!!!!!!()*%! ! +')(,!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! ! !!!!!!!!!+')(,!!!!!!!"(#-%$! sentation of the forgetting curve ! !! ! ! ! ! !!!!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!!()*%! +')(,!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! +')(,!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"(#-%$!
To model this process, we propose to introduce a special "forgetting" function similar to an experimental curve that has been obtained first by H. Ebbinghaus at 1885 and then confirmed and refined by numerous subsequent studies (Figure 3). This curve reflects the exponential decline of individual human memory retention with time. The rate of forgetting depends on repetition rate of incoming information.

An algorithm of forgetting is presented at Figure 4.

Using such mechanism in the semantic model looks reasonable, because transferring only the actual and potentially interesting information will save limited network resources.

The example 1 is an illustration of the mechanisms described above.

Thus, the semantic network of each user is dynamic; it is constructed from the individual information by tagging, taking into account the relationships between data elements, and frequency and/or duration of accessing them.!!

Example 1.

Each user has a collection of data elements (e.g pictures, blog posts, status updates etc.) associated with tags. These elements have been created and/or modified at different points in time. When a data element is created or requested, links between associated tags are set to the maximum weight. If the user did not access this content for a long time, the weight of links between associated tags decreases, up to their complete disappearance (we can vary the time threshold before it happens). In that case the actual user's content does not disappear, but it no longer reflected in the semantic network -therefore, transfer of this content to other users does not occur. When a data element is accessed again, the associated tags reappear in the semantic network with the maximum weight.

Picture 1 is not being accessed for some time, so weight of the respective link in the semantic network decreases and eventually the link disappears.

A request for this picture leads to link reappearance. !

Interaction between users and reconstruction of the semantic networks

Data is transmitted from one person to another by merging of semantic networks when they are interacting; thus the data transfer can be done through chain of users temporarily storing data for each other.

Consider how the semantic network is changing in interaction with another network. This process in our model is similar to real human communication, where people meet, connect, exchange ideas and conceptions, and as a result of such interaction their own systems of knowledge are being restructured.

Any user is able to communicate with all users within the reach. However, in real world people usually talk with those who share at least some common interests. Similar to that, in opportunistic networks information might be transmitted only to those users who have any intersection in their individual semantic networks.

We can organize this process as follows. During the initial connection between users (devices) in the opportunistic network, we ask for a set of tags of all available users. After exchanging the tag sets, we find out which users have the same tags and only the associated data elements will participate in subsequent data transfer (Figure 5). Specific algorithms of data transfer will be discussed later at the p.3.4.

./012! ./013 ! "#$%&'! ()*%! ! ! ()*%! "(#-%$! +')(,! ! "#$%&'! !!!!!!!!!!!!()*%! !!!!!!!!!!!!!!!!()*%! ! +')(,!!!!!!!"(#-%$! !!!!!!!!!!!!!!!!!!!!!!!!"#$%&'! !!!!!!!!!!!!!!!!!!!!!!!!!()*%! ! !!!!!!!!!+')(,!!!!!!!"(#-%$!

Interaction Between Semantic Networks

In a real human communication, a dialogue begins with some concepts that are in common between both parties. Similarly to this behaviour, we let the interaction between two semantic networks start with one or few key concepts (vertices) that belong to both semantic networks. Starting from these key vertices, each device is able to compute which are the vertices and edges from its own semantic network that are to be communicated and transferred to the other party. Precisely, looking from the viewpoint of a device, let its semantic network G = (V, E, f (e, t)) be the donor network, while the other party semantic network G = (V , E , f (e , t)) is termed the recipient network. During the interaction between these two networks, concepts of the donor network are included in the recipient network and new connections between concepts are formed. In order to determine which vertices and edges from the donor network are exchanged during a communication, a node computes a contributed network C = ( V , Ē, f (ē, t)), which will contain the data that will be transmitted. Once the contributed network is received, it is merged with the recipient network in order to create the updated recipient network. In the following, we describe how a node computes the contributed network and how this is finally merged with the recipient network. Hereafter, when we say that an edge is included in the contributed network, we imply that the vertices at both the endpoints of that edge are also included, in case the contributed network does not already contain them.

Supposing that the interaction starts at time t, the pseudo-code used for initializing the contributed network is presented in Alg.1. As already stated, we assume that a data exchange between two nodes starts from a set of shared semantic concepts, i.e. a set of vertices K = {v k : v k ∈ V ∩ V } (lines 1-6 of the pseudo-code). Note that in case K = ∅, nothing is passed from one node to the other. Vertices and the corresponding edges that connect them directly (one-hop distance) with key nodes are included instantly in the contributed network (lines 7-12). This process is analogue to the idea of "gestalt", when the understanding is not limited to a single concept, but brings a system of linked concepts i.e. a part of the semantic network. Note that the weights of edges included in the contributed network are set to the maximum in both the donor and contributed networks (lines 10-11), as the exchange of this data leads to a sort of "activation" of the corresponding edge in memory, thus inducing the forgetting process to "restart". In order to compute which of the remaining vertices and edges of the donor network should be included in the contributed network, we proceed as detailed in Alg. 2. Edges will be subject to a "warming" process, that will mainly depend on the duration of the contact and the proximity of an edge's endpoints to a key vertex. Thus, vertices and edges will be included in the con-Algorithm 1 Contributed Network Creation at time t 1: Let G = (V, E, f (e, t)) be the donor network; 2: Let C = ( V , Ē, f (ē, t)) be the contributed network; 3: Let K be the set of key vertices, K ⊆ V 4: for each k ∈ K do 5:

V ∪ = k 6: end for 7: for each v ∈ V and each k ∈ K such that ∃e kv ∈ E do 8:

V ∪ = v 9:

Ē∪ = e kv 10:

Set f (e kv , t) = 1 in G 11:

Set f (e kv , t) = 1 in C 12: end for tributed network by levels, as shown in Fig. 5. The proximity value is computed Fig. 5. Selection of vertices from the donor network using proximity levels as the minimum number of hops needed to the reach any of the key vertices in the donor network. Edges that connect vertices that are closer to a key node will be "warmed up" faster than those linking vertices located far away. Moreover, the longer will last an interaction between two nodes, the easier an edge will be "warmed". This process mimics what happens in a human communication process, where, starting from a set of common concepts, other semantically connected notions could be included in the dialogue. The longer the discussion takes, the more concepts are exchanged. When the interaction is terminated, the contributed network has only those edges (and related vertices) that exceed a "warm" activation threshold. Thus, only that information is transferred to the recipient network.

In detail, supposing that a connection starts at time t and ends at time t * , edge warming is computed using the following formula:

w(e ij , ∆ t ) = γ step 1 + e -p t * ij (1 -e -τ ∆t )
where e ij ∈ E is an edge of the donor network, ∆ t is the duration of the connection, i.e. ∆ t = t * -t, p t * ij is the popularity of e ij at time t * and τ is a normalizing factor. The coefficient γ step is used to weight the proximity of e ij to any key vertex. We can define this value as γ step = γ n , where n is the the number of hops in the shortest path to the nearest key vertex and γ is a normalizing factor.

Being w min the minimum warm threshold, the contributed network will contain an edge e ij iff w(e ij , ∆ t ) ≥ w min (lines 10-17). Moreover, in order to limit the amount of information exchanged during an encounter, we consider that, apart from its warm weight, an edge e ij is included in the contributed network iff it is within h hops from any key vertex in the donor network (line 8). At the end of Algorithm 2 Contributed Network computation at the end of an encounter E,f (e,t)) be the donor network; 2: Let C = ( V , Ē, f (ē, t)) be the already initialized contributed network; 3: Let K be the set of key vertices, K ⊆ V 4: Let A = (V ∩ V ) -K 5: Let h be the depth limit 6: Let wmin be the weight threshold 7: Let depth = 2 8: while depth ≤ h do 9:

1: Let G = (V,
Let B = ∅ 10:

for each v ∈ (V -V ) such that ∃eav ∈ E, a ∈ A do 11:

if w(eav, t * ) ≥ wmin then 12:

V ∪ = v 13: Ē∪ = ea,v 14:

Set

f (eav, t) = 1 in G 15: Set f (eav, t) = w(eav, ∆t) in C 16: B∪ = v 17: end if 18:
end for 19:

A = B 20: depth = depth + 1 21: end while the interaction, the contributed network is transferred from the donor node to the recipient one. The contributed network is merged with the recipient network using Alg. 3. Edges and vertices that do not exist in the recipient network are added (lines 5-14). In case an edge of the contributed network already exists in the recipient one (line 16), its weight is set to the maximum between the weigth already assigned to it in the recipient network and the weight passed by the contributed network.

Simulation Results

In order to evaluate the proposed algorithm, we simulated its behaviour in the following scenario. We consider 99 mobile nodes that move in a 1000mx1000m area. In order to simulate real user movement patterns, nodes move according to the HCMM model [START_REF] Boldrini | Hcmm: Modelling spatial and temporal properties of human mobility driven by users' social relationships[END_REF]. This is a mobility model that integrates temporal, social and spatial notions in order to obtain an accurate representation of real user movements. Specifically, in HCMM the simulation space is divided in cells representing different social communities. Nodes move between social communities, and nodes movements are driven by social links between them. In this preliminary study, we consider that there exists only one social community, i.e. the simulation space consists of one cell that covers all the simulation area.

Algorithm 3 Merging of contributed and recipient networks

1: Let G = (V , E , f (e , t) be the recipient network; 2: Let C = ( V , Ē, f (ē, t)) be the contributed network; 3: Let G * = (V * , E * , f * (e * , t)) be the updated recipient network; 4: G * = G ; 5: for each ēij ∈ Ē do 6:

if ēij / ∈ E * then 7:

if vi / ∈ V * then 8:

V * ∪ = vi 9:

end if 10:

if vj / ∈ V * then 11:

V * ∪ = vj 12:

end if 13:

E * ∪ = ēij 14: Set f * (ēij, t) = f (ēij, t) 15: else 16: Set f * (ēij, t) = max(f * (ēij, t), f (ēij, t)); 17:
end if 18: end for Data assigned to these nodes is selected from the CoPhIR dataset [START_REF] Bolettieri | CoPhIR: a test collection for content-based image retrieval[END_REF]. This is a dataset containing more than 100 million images taken from Flickr. Along with other data, for each image it is possible to know the user that generated it and the associated tags. In order to create a useful dataset to test our solution, we selected images with at least 5 tags each. This number was chosen considering that the overall mean number of tags per image in the dataset is 5.02. Then, we extracted those users that have at least 10 such images in their collections. Finally, from this set of users, we randomly chose the 99 users that we used in the simulation. For each of these users, a corresponding semantic network is created, according to the description given in Sec. 3.1. We then study the transient state of the interaction between these users, by repeating 10 different tests obtained by producing 10 different mobility traces using the HCMM model. Results reported in the following simulations are the average of all the performed tests. Each simulation experiment runs for 5000 sec.

Fig. 6(a) (log-scale on the x axis) shows the evolution over time of the tags Hit Ratio for three different settings of the forget function. The overall Hit Ratio is defined as the mean of the per tag hit ratio. This latter quantity is computed as the mean number of nodes having a given tag in their semantic networks at a given time. We set the parameters of the forget function in order to have the less popular edges be deleted after 50, 100 and 250 sec of inactivity, respectively. In this scenario, vertices at more than 3 hops from a key vertex are not exchanged during contacts. The first thing to note is that tags are not spread to any node in all the cases we present. This is consistent with the view that each user is probably not interested in every semantic concept available. Rather, she is more interested in fetching the concepts more pertinent with her own knowledge. Anyway, as one could expect, the forget function plays a key role in the data dissemination process. The longer we let the edges (and related vertices) stay in their semantic networks before being forgotten, the higher will be the final diffusion of the corresponding tags in the network. Since there are great variations in the Hit Ratio values, a proper tuning of the forget function parameters implies a trade-off between the willingness to let the concepts permeate the network and the need to limit the associated resource consumption (storage, bandwidth, etc.). In all the reported results, the Hit Ratio reaches a stabilization value. This is due to the fact that (i) useful information has been already shared among potentially interested nodes; (ii) the meeting rate of this data is faster than the forget process, i.e. data is seen again before the associated forget function value falls below the forgetting threshold. In Fig. 6(b) we report the impact on the Hit Ratio of the proximity level limit h for the exchange of vertices and related edges. In this case we fixed the forget function parameters in order to let the least popular edges disappear after 100 sec. of inactivity. Results are obtained for h = 2, 3 and 5. We can see that allowing to include in the contributed networks a larger (i.e. more distant from key vertices) portion of the donor networks result in a larger diffusion of semantic concepts (i.e. an higher Hit Ratio). Anyway, the Hit Ratio is less sensitive to changing in the h value rather than to changes in the forget function parameters. Thus, although different values of h lead to different Hit Ratios, tuning of this parameter is less critical than that of the forget function, since it leads to relatively small differences in the final Hit Ratio values.

In the next sets of results, we study some of the general properties of the semantic networks as they result at the end of the simulation. Main parameters are: h = 3; the forget function deletes the least popular edges after 100 sec. The left side of Fig. 7 shows the evolution over time of the mean number of different connected components that form each semantic network. Each semantic network is not a complete graph. Rather it is a set of different weakly connected components. On one hand, these different sets of semantic concepts (i.e. vertices) may be thought to represent different, semantically uncorrelated groups of topics the user is interested in. Anyway, these sets could also be disconnected one from the others since the user lacks the knowledge needed to put them together. We can see that, as time passes, the mean number of different connected components rapidly falls down, as an effect of the data dissemination process. Since new vertices and new connections between old and new vertices are created, some sets of previously disconnected nodes start to merge, until the process stabilizes. Moreover, from the right side of Fig. 7, we can deduce that, on average, the biggest connected component of each semantic network acts as an attractor of other previously disconnected components. In fact, in parallel with the reduction of the number of disconnected components, the average relative size of the biggest connected component rapidly increase. Once the number of disconnected components stabilizes, the size of the biggest connected component comprises almost all the vertices of a semantic network. Indeed, less then 1% of all the vertices are in the other components. Finally, Fig. 8 plots the degree dis- tribution at the beginning and end of the simulation. The figures uses a log-scale on the y axis only, in order to let the differences between the two distributions be more visible. It is possible to note that, at the end of the simulation, the algorithm preserves the same slope of the nodes degree distribution that was present before the simulation starts. Anyway, there is an increased probability to find nodes with high degree, as shown by the CCDF of the final degree distribution. Node with an intial higher degree have more chances to be involved in an exchange than nodes with lower degrees. Moreover, the forget process cuts less popular edges, thus further reducing the degree of less spread vertices. Edges attached to high-degree nodes take advantage of the nodes' probability to be exchanged in order to avoid to be forgotten. Eventually, this mechanism favours the increase of the degree of already well-connected nodes. The semantic information associated with data items could be a powerful tool in a data dissemination scheme in order to assert the relevance and relationship of already owned information and newly discovered knowledge. Exploiting the data semantic tagging done by the users themselves, we defined a semantic-based data dissemination algorithm for opportunistic networks. We show how each device is able to give a semantic network representation of its own data and how this representation can be used to select the information to be exchanged by users upon physical contact. In a first set of preliminary simulation results based on this approach, we studied the impact of various parameters on both the data dissemination process and the evolution and final properties of the users' semantic networks. Future research directions encompass the definition of a content dissemination scheme based on this solution, an even more formal mathematical description of this proposal, a more comprehensive study via simulation of the performances and properties of the algorithm and its application to different scenarios, where other factors, like social relationships among users, should be taken into account.

Fig. 1 .

 1 Fig. 1. Creation of a Semantic Network by data tagging.

Figure 3 .Fig. 2 .

 32 Figure 3. A typical representation of the forgetting curveFig. 2. Example of a forgetting curve

  repetition rate of incoming information.

Fig. 3 .

 3 Fig. 3. Creation process of a user Semantic Network.

Figure 3 .

 3 Figure 3. A typical representation of the forgetting curve

Fig. 4 .

 4 Fig. 4. Effects of the forgetting process

  As a result we obtain a new (updated) recipient semantic network G * = (V * , E * , f * (e * , t)). Being |V | = n and |V | = m, we have that |V * | = l ≤ n + m.

Fig. 6 .

 6 Fig. 6. Hit Ratios for different settings of (a) the forget function and (b) parameter h

Fig. 7 .

 7 Fig. 7. Evolution of (a) the number of distinct connected components and (b) the size of the biggest connected component

Fig. 8 .

 8 Fig. 8. Nodes' degree distribution before and at the end of the simulation

This work is funded by the EC under the RECOGNITION (FP7-IST 257756) and EINS (FP7-FIRE 288021) projects. This work was carried out during the tenure of L. Rozanova's ERCIM "Alain Bensoussan" Fellowship Programme. This Programme is supported by the Marie Curie Co-funding of Regional, National and International Programmes (COFUND) of the European Commission.


E Kokolaki

M Karaliopoulos

I Stavrakakis

On the efficiency of information-assisted search for parking space: a game-theoretic approach *

This paper seeks to systematically explore the efficiency of the uncoordinated information-assisted parking search in urban environments with two types of parking resource facilities: inexpensive but limited facilities (public) and expensive yet unlimited ones (private); an additional cruising cost is incurred when deciding for a public facility but failing to actually utilize one. Drivers decide whether to go for the public or directly for the private facilities, assuming perfect knowledge of prices and costs, total parking capacities and demand; the latter information can be broadcast by an ideal centralized information dissemination mechanism, assisting the otherwise uncoordinated parking search process. Drivers are viewed as strategic decision-makers that aim at minimizing the cost of the acquired parking spot. We formulate the resulting game as an instance of resource selection games and derive its Nash equilibria and their dependence on the environmental parameters such as the parking demand and supply as well as the pricing policy. The cost at the equilibria states is compared to that under the optimal resource assignment (dictated to the drivers directly by an ideal centralized scheme) and conditions are derived for minimizing the related price of anarchy. Finally, the numerical results and the presented discussion provide hints for the practical management and pricing of public and private parking resources.

Introduction

The tremendous increase of urbanization necessitates the efficient and environmentally sustainable management of urban processes and operations. The (pilot) implementation of solutions and pioneering ideas from the area of information and communication technologies presents a response to this need paving the way for the so-called "smart cities". The search for available parking space is among the daily routine processes that can benefit from this new kind of city environments. In particular, transportation engineers have developed parking assistance systems, realized through information dissemination mechanisms to alleviate not only the traffic congestion problems that stem from the blind parking search but also the resulting environmental burden. Common to these systems is the exploitation of wireless communications and information sensing technologies to collect and broadcast (in centralized mechanisms, i.e., in [START_REF] Mathur | Parknet: Drive-by sensing of road-side parking statistics[END_REF], [START_REF] Wang | A reservation-based smart parking system[END_REF]) or share (in distributed systems, i.e., in [START_REF] Caliskan | Decentralized discovery of free parking places[END_REF], [START_REF] Delot | A cooperative reservation protocol for parking spaces in vehicular ad hoc networks[END_REF]) information about the availability of parking space and the demand for it within the search area. This information is then used to steer the parking choices of drivers in order to reduce the effective competition over the parking space and make the overall search process efficient. Additionally, the implementation of smart demand-responsive pricing policies on the parking facilities intends to improve parking availability in overused parking zones and reduce double-parking and cruising phenomena (i.e., in [1]).

This paper seeks to systematically explore the fundamental limits on the efficiency of these parking assistance systems. To this end, it ideally assumes that drivers become completely aware of the competition intensity, parking capacity and applied pricing policies on the parking facilities. Thus, the particular questions that become relevant for this exploration are: How do these three parameters modulate drivers' parking choices? How do they affect the cost that drivers incur and the revenue accruing for the parking service operator?

We formulate the parking spot selection problem as an instance of resource selection games in Section 2. We view the drivers as rational selfish agents that try to minimize the cost they pay for acquired parking space. The drivers choose to either compete for the cheaper but scarce on-street parking spots or head for the more expensive private parking lot(s)1 . In the first case, they run the risk of failing to get a spot and having to a posteriori take the more expensive alternative, this time suffering the additional cruising cost in terms of time, fuel consumption (and stress) of the failured attempt. Drivers make their decisions drawing on perfect information about the number of drivers, the availability of parking spots and the pricing policy, which is broadcast from the parking service operator. In Section 3, we derive the equilibrium behaviors of the drivers and compare the induced social cost against the optimal one via the Price of Anarchy metric. Most importantly, in Section 4, we show that the optimization of the equilibrium social cost is feasible by properly choosing the pricing and location of the private parking facilities. We outline related research in Section 5 and we close the discussion in Section 6 iterating on the model assumptions.

The parking spot selection game

In the parking spot selection game, the set of players consists of drivers who circulate within the center area of a big city in search of parking space. Typically, in these regions, parking is completely forbidden or constrained in whole areas of road blocks so that the real effective curbside is significantly limited (see Fig. 1). The drivers have to decide whether to drive towards the scarce low-cost (controlled) public parking spots or the over-dimensioned and more expensive private parking lot (we see all local lots collectively as one). All parking spots that lie in the same public or private area are assumed to be of the same value for the players. Especially the on-street parking spots are considered quite close to eachother, resulting in practically similar driving times to them and walking times from them to the drivers' ultimate destinations. Thus, the decisions are made on the two sets of parking spots rather than individual set items.

We observe drivers' behavior within a particular time window over which they reach this parking area. In general, these synchronization phenomena in drivers' flow occur at specific time zones during the day [2]. Herein, we account for morning hours or driving in the area for business purposes coupled with long parking duration. Thus, the collective decision making on parking space selection can be formulated as an instance of the strategic resource selection games, whereby N players (i.e., drivers) compete against each other for a finite number of common resources (i.e., public parking spots) [START_REF] Ashlagi | Resource selection games with unknown number of players[END_REF]. More formally, the one-shot2 parking spot selection game is defined as follows:

Definition 1. A Parking Spot Selection Game is a tuple Γ = (N , R, (A i ) i∈N , (w j ) j∈(pub,priv) ), where:

-N = {1, ..., N }, N > 1 is the set of drivers who seek for parking space, -R = R pub ∪ R priv is the set of parking spots; R pub is the set of public spots, with R = |R pub | ≥ 1; R priv the set of private spots, with |R priv | ≥ N , -A i = {public, private}, is the action set for each driver i ∈ N , w pub (•) and w priv (•) are the cost functions of the two actions, respectively.

The parking spot selection game comes under the broader family of congestion games. The players' payoffs (here: costs) are non-decreasing functions of the number of players competing for the parking capacity rather than their identities and common to all players. More specifically, drivers who decide to compete for the public parking space undergo the risk of not being among the R winner-drivers to get a spot. In this case, they have to eventually resort to private parking space, only after wasting extra time and fuel (plus patience supply) on the failed attempt. The expected cost of the action public, w pub : A 1 × ... × A N → R, is therefore a function of the number of drivers k taking it, and is given by

w pub (k) = min(1, R/k)c pub,s + (1 -min(1, R/k))c pub,f (1)
where c pub,s is the cost of successfully competing for public parking space, whereas c pub,f = γ • c pub,s , γ > 1, is the cost of competing, failing, and eventually paying for private parking space.

On the other hand, the cost of private parking space is fixed

wpriv(k) = cpriv = β • c pub,s (2)
where 1 < β < γ, so that the excess cost δ • c pub,s , with δ = γ -β > 0, reflects the actual cost of cruising and the "virtual" cost of wasted time till eventually heading to the private parking space.

We denote an action profile by the vector a = (a i , a -i ) ∈ × N k=1 A k , where a -i denotes the actions of all other drivers but player i in the profile a. Besides the two pure strategies reflecting the pursuit of public and private parking space, the drivers may also randomize over them. In particular, if ∆(A i ) is the set of probability distributions over the action set of player i, a player's mixed action corresponds to a vector p = (p pub , p priv ) ∈ ∆(A i ), where p pub and p priv are the probabilities of the pure actions, with p pub + p priv = 1, while its cost is a weighted sum of the cost functions w pub (•) and w priv (•) of the pure actions.

In the following section, we derive the game-theoretic analysis of the particular game formulation looking into both the stable and optimal operational conditions as well as the respective costs incurred by the players.

Game analysis

Ideally, the players determine their strategy under complete knowledge of those parameters that shape their cost. Given the symmetry of the game, the additional piece of information that is considered available to the players, besides the number of vacant parking spots and the employed pricing policy, is the level of parking demand, i.e., the number of drivers searching for parking space. We draw on concepts from [START_REF] Koutsoupias | Worst-case equilibria[END_REF] and theoretical results from [START_REF] Ashlagi | Resource selection games with unknown number of players[END_REF][START_REF] Cheng | Notes on the equilibria in symmetric games[END_REF] to derive the equilibrium strategies for the game Γ and assess their (in)efficiency.

Pure equilibria strategies

Existence: The parking spot selection game constitutes a symmetric game, where the action set is common to all players and consists of two possible actions, public and private. Cheng et al. have shown in ([9], Theorem 1) that every symmetric game with two strategies has an equilibrium in pure strategies.

Derivation: Due to the game's symmetry, the full set of 2 N different action profiles maps into N + 1 different action meta-profiles. Each meta-profile a(m), m ∈ [0, N ] encompasses all N m different action profiles that result in the same number of drivers competing for on-street parking space. The expected costs for these m drivers and for the N -m ones choosing directly the private parking lot alternative are functions of a(m) rather than the exact action profile.

In general, the cost c N i (a i , a -i ) for driver i under the action profile a = (a i , a -i ) is

c N i (ai, a-i) = w pub (N pub (a)), for ai = public wpriv(N -N pub (a)), for ai = private (3)
where N pub (a) is the number of competing drivers for on-street parking under action profile a. Equilibria action profiles combine the players' best-responses to their opponents' actions. Formally, an action profile a = (a i , a -i ) is a pure Nash equilibrium if for all i ∈ N : ai ∈ arg min

a i ∈A i (c N i (a i , a-i)) (4)
so that no player has anything to gain by changing her decision unilaterally. Therefore, to derive the equilibria states, we determine the conditions on N pub that break the equilibrium definition and reverse them. More specifically, given an action profile a with N pub (a) competing drivers, a player gains by changing her decision to play action a i in two circumstances: when a i = private and w pub (N pub (a) + 1) < c priv (5) when a i = public and w pub (N pub (a)) > c priv [START_REF] Ashlagi | Resource selection games with unknown number of players[END_REF] Taking into account the relation between the number of drivers and the available on-street parking spots, R, we can postulate the following Lemma: Lemma 1. In the parking spot selection game Γ , a driver is motivated to change his action a i in the following circumstances:

• ai = private and N pub (a) < R ≤ N or (7) R ≤ N pub (a) < N0 -1 ≤ N or (8) N pub (a) < N ≤ R (9)
• ai = public and R < N0 < N pub (a) ≤ N [START_REF] Delot | A cooperative reservation protocol for parking spaces in vehicular ad hoc networks[END_REF] where

N 0 = R(γ-1) δ ∈ R.
Proof. Conditions ( 7) and ( 9) are trivial. Since the current number of competing vehicles is less than the on-street parking capacity, every driver having originally chosen the private parking option has the incentive to change her decision due to the price differential between c pub,s and c priv .

When N pub (a) exceeds the public parking supply, a driver who has decided to avoid competition, profits from switching her action when (5) holds, which combined with (1), yields [START_REF] Caliskan | Decentralized discovery of free parking places[END_REF]. Similarly, a driver that first decides to compete, profits by switching her action if (6) holds, which combined with (1), yields [START_REF] Delot | A cooperative reservation protocol for parking spaces in vehicular ad hoc networks[END_REF].

The following Theorem for the pure Nash equilibria of the parking spot selection game may now be stated.

= N 0 -1, if N > N 0 and N 0 ∈ [R + 1, N ] ∩ N * .
Proof. Theorem 1 follows directly from ( 4) and Lemma 1. The game has two equilibrium conditions on N pub for N > N 0 with integer N 0 (case c), or a unique equilibrium condition, otherwise (cases a, b).

Efficiency: The efficiency of the equilibria action profiles resulting from the strategically selfish decisions of the drivers is assessed through the broadly used metric of the Price of Anarchy [START_REF] Koutsoupias | Worst-case equilibria[END_REF]. It expresses the ratio of the social cost in the worst-case equilibria over the optimal social cost under ideal coordination of the drivers' strategies.

Proposition 1. In the parking spot selection game, the pure Price of Anarchy equals:

PoA =      γN -(γ-1) min(N,R) min(N,R)+β max(0,N -R) , if N 0 ≥ N N0 δ-R(γ-1)+βN R+β(N -R) , if N 0 < N Proof.
The social cost under action profile a equals:

C(N pub (a)) = N i=1 c N i (a) = c pub,s (N β -N pub (a)(β -1)), if N pub (a) ≤ R and (11)
c pub,s (N pub (a)δ -R(γ -1) + βN ), if R < N pub (a) ≤ N
The numerators of the two ratios are obtained directly by replacing the first two N N E pub values (a) and (b) (worst-cases) computed in Theorem 1. On the other hand, under the socially optimal action profile a opt , exactly R drivers pursue on-street parking, whereas the remaining N -R go directly for the private parking. Therefore, under a opt , no drivers find themselves in the unfortunate situation to have to pay the additional cost of cruising in terms of time and fuel after having unsuccessfully competed for an onstreet parking spot. The optimal social cost, C opt is given by:

Copt = N i=1 c N i (aopt) = c pub,s [min(N, R) + β • max(0, N -R)]
Proposition 2. In the parking spot selection game, the pure Price of Anarchy is upperbounded by

1 1-R/N with N > R.
Proof. The condition is obtained directly from Proposition 1, when N > R.

Mixed-action equilibria strategies

We mainly draw our attention on symmetric mixed-action equilibria since these can be more helpful in dictating practical strategies in real systems. Asymmetric mixed-action equilibria are discussed in [START_REF] Kokolaki | Leveraging information in vehicular parking games[END_REF].

Existence: Ashlagi, Monderer, and Tennenholtz proved in ([6], Theorem 1) that a unique symmetric mixed equilibrium exists for the broader family of resource selection games with more than two players and increasing cost functions. It is trivial to repeat their proof and confirm this result for our parking spot selection game Γ , with N > R and cost functions w pub (•) and w priv (•) that are non-decreasing functions of the number of players (increasing and constant, respectively).

Derivation: Let p = (p pub , p priv ) denote a mixed-action. Then, the expected costs of choosing the on-street (resp. private) parking space option, when all other drivers play the mixed-action p, are given by

c N i (public, p) = N -1 N pub =0 w pub (N pub + 1)B(N pub ; N -1, p pub ) (12)
c N i (private, p) = cpriv (13)
where B(N pub ; N -1, p pub ) is the Binomial probability distribution with parameters N -1 and p pub , for N pub drivers choosing on-street parking. The cost of the symmetric profile where everyone plays the mixed-action p is given by

c N i (p, p) = p pub • c N i (public, p) + ppriv • c N i (private, p) (14)
With these at hand, we can now postulate the following Theorem.

Theorem 2. The parking spot selection game Γ has a unique symmetric mixed-action Nash equilibrium p N E = (p N E pub , p N E priv ), where:

-p N E pub = 1, if N ≤ N0 and -p N E pub = N 0 N , if N > N0,
where p N E pub = 1 -p N E priv and N 0 ∈ R. Proof. The symmetric equilibrium for N ≤ N 0 corresponds to the pure NE we derived in Theorem 1. To compute the equilibrium for N > N 0 we invoke the condition that equilibrium profiles must fulfil

c N i (public, p N E ) = c N i (private, p N E ) (15)
namely, the costs of each pure action belonging to the support of the equilibrium mixed-action strategy are equal. Hence, from ( 12), ( 13) and ( 15) the symmetric mixedaction equilibrium p N E = (p N E pub , p N E priv ) solves the equation

f (p) = -β + N -1 k=0 (γ -min(1, R k + 1 ) • (γ -1))B(k; N -1, p) = 0 (16)
A closed-form expression for the equilibrium p N E pub is not straightforward. However, it holds that: and f (p) is a continuous and strictly increasing function in p since

lim p→0 f (p) = -β + 1 < 0 and lim p→1 f (p) = δ(1 - N0 N ) > 0 (
f (p) = N -1 k=0 (γ -min(1, R k + 1 )(γ -1))B (k; N -1, p) > N -1 k=0 B (k; N -1, p) = 0
Hence, f (p) has a single solution. It may be checked with replacement that f (N 0 /N ) = 0.

Numerical results

The analysis in Section 3 suggests that the charging policy for on-street and private parking space and their relative location, which determines the overhead parameter δ of failed attempts for on-street parking space, affect to a large extent the (in)efficiency of the game equilibrium profiles. In the following, we illustrate their impact on the game outcome and discuss their implications for real systems.

For the numerical results we adopt per-time unit normalized values used in the typical municipal parking systems in big European cities [2]. The parking fee for public space is set to c pub,s = 1 unit whereas the cost of private parking space β ranges in (1, 16] units and the excess cost δ in [1, 5] units. We consider various parking demand levels assuming that private parking facilities in the area suffice to fulfil all parking requests.

Figure 2 plots the social costs C(N pub ) under pure (Eq. 11) and C(p pub ) under mixed-action strategies as a function of the number of competing drivers N pub and competition probability p pub , respectively, where

C(p pub ) = c pub,s N n=0 N n p n pub (1 -p pub ) N -n • [min(n, R) + max(0, n -R)γ + (N -n)β] (18)
Figure 2 motivates two remarks. First, the social cost curves for pure and mixed-action profiles have the same shape. This comes as no surprise since for given N , any value for the expected number of competing players 0 ≤ N pub ≤ N can be realized through appropriate choice of the symmetric mixed-action profile p. Second, the cost is minimized when the number of competing drivers is equal to the number of on-street parking spots. The cost rises when either competition exceeds the available on-street parking capacity or drivers are overconservative in competing for on-street parking. In both cases, the drivers pay the penalty of the lack of coordination in their decisions. The deviation from optimal grows faster with increasing price differential between the on-street and private parking space.

Whereas an optimal centralized mechanism would assign exactly min(N, R) public parking spots to min(N, R) drivers, if N > R, in the worst-case equilibrium the size of drivers' population that actually competes for on-street parking spots exceeds the real parking capacity by a factor N 0 which is a function of R, β and γ (equivalently, δ) (see Lemma 1). This inefficiency is captured in the PoA plots in Figure 3 for β and δ ranging in [1.1, 16] and [1, 5], respectively. The plots illustrate the following trends: Fixed δ -varying β: For N ≤ N 0 or, equivalently, for β ≥ δ(N -R)+R R , it holds that ϑP oA ϑβ < 0 and therefore, the PoA is strictly decreasing in β. On the contrary, for

β < δ(N -R)+R

R

, the PoA is strictly increasing in β, since ϑP oA ϑβ > 0.

Fixed β -varying δ: For N ≤ N 0 or, equivalently, for δ ≤ R(β-1) N -R we get ϑP oA ϑδ > 0. Therefore, the PoA is strictly increasing in δ. For δ > R(β-1) N -R , we get ϑP oA ϑδ = 0.

Hence, if δ exceeds R(β-1) N -R , PoA is insensitive to changes of the excess cost δ. Practically, the equilibrium strategy emerging from this kind of assisted parking search behavior, approximates the optimal coordinated mechanism when the operation of private parking facilities accounts for drivers' preferences as well as estimates of the typical parking demand and supply. More specifically, if, as part of the pricing policy, the cost of private parking is less than δ(N -R)+R R times the cost of on-street parking, then the social cost in the equilibrium profile approximates the optimal social cost as the price differential between public and private parking decreases. This result is inline with the statement in [START_REF] Larson | Congestion pricing: A parking queue model[END_REF], arguing that "price differentials between on-street and offstreet parking should be reduced in order to reduce traffic congestion". Note that the PoA metric also decreases monotonically for high values of the private parking cost, specifically when the private parking operator desires to gain more than δ(N -R)+R R times the cost of on-street parking, towards a bound that depends on the excess cost δ. Nevertheless, these operating points correspond to high absolute social cost, i.e., the minimum achievable social cost is already unfavorable due to the high fee paid by N -R drivers that use the private parking space (see Fig. 2, large β). On the other hand, there are instances, as in case of R = 50 (see Fig. 3), where the value δ(N -R)+R R corresponds to a non-realistic option for the cost of private parking space, already for δ > 1. Thus, contrary to the previous case, PoA only improves as the cost for private parking decreases. Finally, for given cost of the private parking space, the social cost can be optimized by locating the private facility in the proximity of the on-street parking spots so that the additional travel distance is reduced to the point of bringing the excess cost below R(β-1) N -R .

Related work

Various aspects of the broader parking space search problem have been addressed in the literature. Probably the first formulation of the problem appeared in [START_REF] Macqueen | Optimal persistence policies[END_REF] in the context of the broader family of stopping problems. Parking spots are spread randomly, with density λ over equal-size blocks that are adjacent to a destination, and drivers circle through them crossing the destination every time such a circle is over. Ferguson in [START_REF] Ferguson | Optimal stopping and applications[END_REF] considers a simpler variant of the problem, whereby the drivers' destination lies in the middle of an infinite-length straight line with parking spots that are occupied with probability p. In either case, the optimal policy for the drivers is shown to be of the threshold type: they should occupy an available vacant parking spot whenever this lies within some distance r = f (λ), resp. f (p), from their destination and continue searching otherwise. Pricing and more general economic dimensions of the parking allocation problem are analyzed in [START_REF] Larson | Congestion pricing: A parking queue model[END_REF] and [START_REF] Anderson | The economics of pricing parking[END_REF]. A queueing model for drivers who circulate in search for on-street parking is introduced in [START_REF] Larson | Congestion pricing: A parking queue model[END_REF] in order to analyze economic effects of congestion pricing. From a microeconomical point of view, Anderson and de Palma in [START_REF] Anderson | The economics of pricing parking[END_REF] treat the parking spots as common property resource and question whether free access or some pricing structure result in more efficient use of the parking capacity. Working on a simple model of city and parking spot distribution, they show that this use is more efficient (in fact, optimal) when the spots are charged with the fee chosen in the monopolistically competitive equilibrium with private ownership. The situation is reversed, i.e., drivers are better off when access to the parking spots is free of charge.

Subsequent research contributions in [START_REF] Arnott | Spatial competition between parking garages and downtown parking policy[END_REF], [START_REF] Arbatskaya | The parking lot problem[END_REF] and [START_REF] Ayala | Parking slot assignment games[END_REF] have explicitly catered for strategic behavior and the related game-theoretic dimensions of general parking applications. In [START_REF] Arnott | Spatial competition between parking garages and downtown parking policy[END_REF], the games are played among parking facility providers and concern the location and capacity of their parking facility as well as which pricing structure to adopt. Whereas, in the other two works, the strategic players are the drivers. In [START_REF] Arbatskaya | The parking lot problem[END_REF], which seeks to provide cues for optimal parking lot size dimensioning, the drivers decide on the arriving time at the lot, accounting for their preferred time as well as their desire to secure a space. In a work more relevant to ours, the authors in [START_REF] Ayala | Parking slot assignment games[END_REF] define a game setting where drivers exploit (or not) information on the location of others to occupy an available parking spot at the minimum possible travelled distance, irrespective of the distance between the spot and driver's actual travel destination. The authors present distributed parking spot assignment algorithms to realize or approximate the Nash equilibrium states. In our work, the game-theoretic analysis highlights the cost effects of the parking operators' pricing policies on drivers' decisions, drawing on closed-form expressions of the stable operational points in the different game settings.

Conclusions -Discussion

In this paper, we draw our attention on fundamental determinants of parking assistance systems' efficiency rather than particular realizations. We have, thus, formulated the information-assisted parking search process as an instance of resource selection games to assess the ultimate impact that an ideal mechanism broadcasting accurate information on parking demand, supply and pricing policies, can have on drivers' decisions. Our model dictates plausible conditions under which different pricing policies steer the equilibrium strategies, reduce the inefficiency of the parking search process, and favor the social welfare.

We conclude by iterating on the strong and long-debatable assumption that drivers do behave as fully rational utility-maximizing decision-makers; namely, they can exhaustively analyze the possible strategies available to themselves and the other drivers, identify the equilibrium profile(s), and act accordingly to realize it. Simon in [START_REF] Simon | A behavioral model of rational choice[END_REF], challenged both the normative and descriptive capacity of the fully rational decision-maker, arguing that human decisions are most often made under knowledge, time and computational constraints. One way to accommodate the first constraints is through (pre-) Bayesian games of incomplete information. In [START_REF] Kokolaki | Leveraging information in vehicular parking games[END_REF], we formulate (pre-)Bayesian variants of the parking spot selection game to assess the impact of information accuracy on drivers' behavior and, ultimately, the service cost. However, models that depart from the utility-maximization norm and draw on fairly simple cognitive heuristics, e.g., [START_REF] Goldstein | Models of ecological rationality: The recognition heuristic[END_REF], reflect better Simon's argument that humans are satisficers rather than maximizers. For example, the authors in [START_REF] Hutchinson | Ecological rationality: intelligence in the world[END_REF] explore the impact of the fixed-distance heuristic on a simpler version of the unassisted parking search problem. The comparison of norma-

Fig. 1 .

 1 Fig. 1. Parking map of the centre area of Athens, Greece. Dashed lines show metered controlled (public) parking spots, whereas "P" denotes private parking facilities. The map illustrates, as well, the capacity of both parking options.

Theorem 1 .

 1 A parking spot selection game has:(a) one Nash equilibrium a * with N pub (a * ) = N N E,1 pub = N , if N ≤ N 0 and N 0 ∈ R (b) N N0 Nash equilibrium profiles a with N pub (a ) = N N E,2 pub = N 0 , if N > N 0 and N 0 ∈ (R, N )\N * (c) N N0 Nash equilibrium profiles a with N pub (a ) = N N ENash equilibrium profiles a with N pub (a ) = N N E,3 pub

Fig. 2 .

 2 Fig. 2. Social cost for N = 500 drivers when exactly N pub drivers compete (a) or when all drivers decide to compete with probability p pub (b), for R = 50 public parking spots, under different charging policies.

Fig. 3 .

 3 Fig. 3. Price of Anarchy for N = 500 and varying R, under different charging policies.

Hereafter in the paper, the terms public parking spots and private parking facilities denote onstreet parking spots and parking lots, respectively. Their context in this paper should not be confused with that of public/private goods in economics.

The study of the dynamic variant of the game is a natural direction for future work.

tive and more descriptive decision-making modeling approaches both in the context of the parking spot selection problem and more general decision-making contexts, is an interesting area worth of further exploration.

* This work has been supported in part by the European Commission IST-FET project RECOG-NITION (FP7-IST-257756), the European Commission under the Network of Excellence in Internet Science project EINS (FP7-ICT-288021) and the University of Athens Special Account of Research Grants no 10812.