Abdelkader Ouali

Albrecht Zimmermann

Samir Loudni

Yahia Lebbah

Bruno Cremilleux

Patrice Boizumault

Lakhdar Loukil

Integer Linear Programming for Pattern Set Mining; with an Application to Tiling

Pattern set mining is an important part of a number of data mining tasks such as classification, clustering, database tiling, or pattern summarization. Efficiently mining pattern sets is a highly challenging task and most approaches use heuristic strategies. In this paper, we formulate the pattern set mining problem as an optimization task, ensuring that the produced solution is the best one from the entire search space. We propose a method based on integer linear programming (ILP) that is exhaustive, declarative and optimal. ILP solvers can exploit different constraint types to restrict the search space, and can use any pattern set measure (or combination thereof) as an objective function, allowing the user to focus on the optimal result. We illustrate and show the efficiency of our method by applying it to the tiling problem.

Introduction

Pattern mining is one of the fundamental tasks in the process of knowledge discovery, and a range of techniques have been developed for producing extensive collections of patterns. However, resulting pattern collections are generally too large, difficult to exploit, and unstructured -without interpretable relations between patterns. This explains the interest of the community to pattern sets [START_REF] De Raedt | Constraint-based pattern set mining[END_REF]. Instead of evaluating and selecting patterns individually, pattern sets (i.e., sets of patterns) assemble local patterns to provide knowledge from a high-level viewpoint, using quality measures that evaluate, and constraints that constrain, the entire set. Examples of problems related to pattern sets include concept-learning, database tiling, data compression, or clustering, to cite a few. However, as the number of possible pattern sets is exponential in the size of the set of local patterns, which is itself huge, the computational efficiency of pattern set mining is a very challenging task. For specific quality measures, such as joint entropy, relatively tight upper bounds can be derived to prune candidate sets [START_REF] Knobbe | Maximally informative k-itemsets and their efficient discovery[END_REF]. Unfortunately, such pruning strategies are limited to very few cases. In practice, most approaches use a step-wise strategy in which first all local patterns are computed, then heuristically postprocessed according to an objective function to be optimized. Therefore only a single pattern set is returned; examples are [START_REF] Bringmann | One in a million: picking the right patterns[END_REF][START_REF] Cheng | Discriminative frequent pattern analysis for effective classification[END_REF][START_REF] Liu | Integrating classification and association rules mining[END_REF][START_REF] Vreeken | Krimp: mining itemsets that compress[END_REF]. Obviously this process does not ensure the optimality of the returned pattern set according to the objective function. To the best of our knowledge, only the algorithm proposed in [START_REF] De Raedt | Constraint-based pattern set mining[END_REF] proceeds by exhaustive search while pruning parts of the search space by using pattern set constraints. However, these pruning effects can be weak, and the number of patterns being very large, this method only works for small pattern collections.

In this paper, we formulate the pattern set mining problem as an optimization task, ensuring that the produced solution is the best from the entire search space. In a sense, we return to the spirit of the original idea of pattern set mining [START_REF] De Raedt | Constraint-based pattern set mining[END_REF] based on a complete method. However, we produce only the best solution, avoiding being drowned by patterns. What's more, we use constraint programming (CP) techniques since CP solvers can exploit a wider range of constraints than data mining approaches that are typically locked into a rather rigid search strategy. Modeling constraints independently from the search strategy also allows them to accomodate a variety of constraints, and therefore adapt the resulting pattern sets to the need of the user.

The key contribution of this paper is a method based on integer linear programming (ILP) that is (1) exhaustive, avoiding the loss of interesting solutions, (2) declarative, allowing us to make the most of provided constraints instead of being tied to a particular search strategy, (3) optimal, always returning the best solution according to an optimization criterion that satisfies the given constraints. Any measure that can be used as a constraint in an ILP model can also be chosen as an objective function to be optimized. This allows the user to prioritize particular aspects of the solution. Measures to be optimized can be combined, as long as they can be expressed as a linear term. This is once again an advantage over traditional mining, where a change would typically require the explicit redefinition of the search strategy. Our approach allows us to provide the first practically useful algorithm for addressing this problem setting. As an illustration, we experimentally address the tiling problem but our approach is broad enough to cover and leverage many pattern mining problems such as clustering [START_REF] Babaki | Constrained clustering using column generation[END_REF][START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], classification [START_REF] Liu | Integrating classification and association rules mining[END_REF], or pattern summarization [START_REF] Xin | Extracting redundancy-aware top-k patterns[END_REF].

The rest of the paper is structured as follows. Section 2 recalls preliminaries. Section 3 describes our approach. Section 4 introduces several complex queries, and Section 6 shows the results of solving queries for the k-tiling problem on different data sets. We discuss related work in Section 5.

Preliminaries

Local patterns

Let I be a set of n distinct items, an itemset (or pattern) is a non-null subset of I. The language of itemsets L corresponds to 2 I \∅. A transactional dataset D is a multi-set of m itemsets of L, with each t i , 1 ≤ i ≤ m called a transaction. We assume the database D is represented as a binary matrix of size n × m with

D ti = 1 ↔ (t, i) ∈ D.
Let D a database, ϕ ∈ L be a pattern, and match : L × L → {true, f alse} a matching operator. The cover of ϕ w.r. A pattern ϕ is said to be more general than a pattern ψ (ϕ ⪯ ψ) (resp., ψ is more specific than ϕ) iff ∀t ∈ L : match(ψ, t) ⇒ match(ϕ, t), i.e. if ψ matches any transaction t then ϕ matches it as well. A pattern ϕ is strictly more general than a pattern ψ (ϕ ≺ ψ), if ϕ ⪯ ψ and ¬(ψ ⪯ ϕ).

The local pattern mining problem consists of finding a theory T h(L, D, q) = {ϕ ∈ L | q(ϕ, D) is true}, where q(ϕ, D) a selection predicate that states the constraints under which the pattern ϕ is a solution w.r.t. the database D. A common example is the minimum support constraint sup(ϕ, D) ≥ θ, which is satisfied by all patterns ϕ whose support in the database D exceeds a given minimal threshold θ. Combined with L, this gives rise to the frequent itemset mining problem. An exact condensed representation of the frequent itemsets consists of the closed patterns [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF]. A closed pattern is one whose specializations have a smaller cover than the pattern itself: closed(ϕ) ⇔ ∀ψ, ϕ ⪯ ψ : cov(ψ) ⊂ cov(ϕ).

Pattern set mining

Pattern sets are simply sets of patterns. The task of pattern set mining entails discovering a set of patterns that satisfies a set of constraints involving not only individual patterns, as in the local pattern mining setting, but the whole set of patterns. Hereafter, we will denote by L the set of all the possible pattern sets that can be enumerated given a language L, i.e., L = 2 L . The individual/local patterns occurring in a pattern set will be denoted using lower case characters such as ϕ, . . . , ψ and for patterns sets, we will employ upper case characters such as Φ, . . . , Ψ .

More formally, the problem of pattern set mining can be formulated as the problem of computing the theory Th(L, D, p) = {Φ ∈ L | p(Φ, D) is true}, where p(Φ, D) a selection predicate that states the constraints under which the pattern set Φ is a solution w.r.t. the database D. In addition, as the number of pattern sets can become very large, we will study how to find the best pattern set with respect to an optimisation criterion f (Φ), i.e. argmax Φ∈Th(L,D,p) f (Φ). In classical pattern set mining, this is achieved by dynamically increasing the threshold of the constraint involving f . When using the ILP framework (see Section 3), this can be achieved by using f as an objective function to guide the search.

Categories of Constraints

This section discusses several categories of constraints that can be specified at the level of the pattern set as a whole. Coverage Constraints deal with defining and measuring how well a pattern set covers the data. Let Φ ∈ L be a pattern set and D a database, -Pattern set cover. The cover of Φ, denoted as cov(Φ, D), is the set of transactions in

D that Φ covers: cov(Φ, D) = ∪ ϕ∈Φ cov(ϕ, D). With
i . rep(Φ, D i , D) = sup(Φ, D i )/sup(Φ, D).
-Accuracy of a pattern set. Let a dataset D partitioned into subsets D 1 , . . . , D n , where each subset D i contains transactions from class i. The accuracy of a pattern ϕ is defined as acc(ϕ)

= maxD i ∈D sup(ϕ,Di) sup(ϕ,D)
. The accuracy of an entire pattern set is harder to quantify. We can however approximate it as acc(Φ) =

∑ ϕ∈Φ acc(ϕ)×sup(ϕ,D) ∑ ϕ∈Φ sup(ϕ,D)
Redundancy Constraints can be used to constrain or minimize the redundancy between different patterns. One way to measure this redundancy is to count the number of transactions covered by multiple patterns in the pattern set Φ: ψ,D) denotes the overlap between the two patterns ϕ, ψ [START_REF] De Raedt | Constraint-based pattern set mining[END_REF].

red(Φ, D) = |{t ∈ D | ∃(ϕ, ψ) ∈ Φ, t ∈ ovlp(ϕ, ψ, D)}|, where ovlp(ϕ, ψ, D) = cov(ϕ, D) ∩ cov(

Mining pattern sets using ILP

Throughout the remainder of this paper we employ the Integer Linear Programming (ILP) framework for representing and solving pattern set mining problems. ILP [START_REF] Andrzej | Integer and combinatorial optimization[END_REF] is one of the most widely used methods for handling optimization problems, due to its rigorousness, flexibility and extensive modeling capability. This framework has been shown 1) to allow for the use of a wide range of constraints, 2) to offer a higher level of problem formalization and modeling, and 3) to work for conceptual clustering [START_REF] Ouali | Efficiently finding conceptual clustering models with integer linear programming[END_REF]. Moreover, modern ILP solvers are very efficient with improved search heuristics.

Resolution approach

Finding a good pattern set is often a hard task; many pattern set mining tasks and their optimization versions, such as the k-tiling [START_REF] Geerts | Tiling databases[END_REF] or the concept learning [START_REF] Kearns | An introduction to computational learning theory[END_REF], are NP-hard. Hence, there are no straightforward algorithms for solving such tasks in general, giving rise to a wide ranges of approaches (Two-step vs one-step) and search strategies (Exact vs heuristic). In this paper, we adopt a two-step approach: (i) A local mining step mines the set of local patterns T h(L, D, q) that satisfy a set of constraints. (ii) An ILP mining step post-processes these patterns with the ILP exact solving technique to obtain the best pattern set in Th(L, D, p) under the given constraints.

Our motivation for adopting a two-step approach is two-fold: First, there exist efficient miners [START_REF] Xindong | The Top Ten Algorithms in Data Mining[END_REF] to find local patterns. Second, in the second step, the formulated ILP model (see Section 3.2) is very close to the well known partitioning (and covering) problems which are extensively studied within the integer programming community [START_REF] Jünger | 50 Years of Integer Programming 1958-2008 -From the Early Years to the State-of-the-Art[END_REF]. Modern ILP solvers, such as Cplex [START_REF]ILOG CPLEX: High-performance software for mathematical programming and optimization[END_REF], are efficient on such problems. Our ILP model is detailed in the next section.

Constraint name

Notation

ILP formulation

(C θ,≶ size ) size(Φ) ≶ θ ∑ p∈P xp ≶ θ (C θ,≶ cov ) (Cx,y) sup(Φ, D) ≶ θ ∑ t∈D yt ≶ θ yt ≤ ∑ p∈P at,p • xp ≤ |P| • yt, ∀t ∈ D (C θ,≶ area ) (Cx,q) area(Φ, D) ≶ θ ∑ i∈I,t∈D qt,i ≶ θ qt,i ≤ ∑ p∈P cq p t,i xp ≤ |P| . qt,i, ∀t ∈ D, ∀i ∈ I (C Φ0 gen ) Φ ⪯ Φ0 ∑ {p: ∀p∈P | p⪯ϕ} xp ≥ 1, ∀ϕ ∈ Φ0 (C Φ0 spe ) Φ0 ⪯ Φ ∑ {p: ∀p∈P | ∃ϕ∈Φ0, ϕ⪯p} xp ≥ ∑ p∈P xp (C θ,≶ redd ) (Cx,u) red(Φ, D) ≶ θ ∑ t∈D ut ≶ θ 2ut ≤ ∑ p∈P at,pxp ≤ yt + |P| . ut, ∀t ∈ D (C θ,≶,Di rep ) (Cx,y′ ) rep(Φ, Di, D) ≶ θ ∑ t∈Di y ′ t ≶ θ × ∑ t∈D yt y ′ t ≤ ∑ p∈P at,p • xp ≤ |P| • y ′ t , ∀t ∈ Di (C θ,≶ avg ) avg(sup(Φ, D)) ≶ θ ∑ p∈P fp • xp -θ ∑ p∈P xp ≶ 0 (C θ,≶ sum) sum(sup(Φ, D)) ≶ θ ∑ p∈P fp • xp ≶ 0
Table 1. ILP formulations of constraints discussed in Section 2.3.

ILP models

This section presents the ILP model of a pattern set, and the ILP formulations for constraints presented in Section 2.3.

Modeling a pattern set. Let P be the set of ℓ patterns. Hence, the pattern set mining problem can be modeled as an ILP using ℓ boolean variables x p (p ∈ P), where (x p = 1) iff the pattern p belongs to the unknown pattern set Φ that we are looking for.

Coverage Constraints. Let D be a database with m transactions. We introduce m boolean variables y t , (t ∈ D) such that (y t = 1) iff there exists at least one pattern ϕ ∈ Φ such that pattern ϕ matches t. So, we have sup(Φ, D) = ∑ t∈D y t . With some given threshold θ, the coverage constraint (C θ,≶ cov ) is defined on such boolean variables. Table 1 shows the formulation of the coverage constraints. Constraints C x,y establish the relationship between variables x and y, and state that each transaction t must belong to at most |P| patterns. Note that (y t = 0) iff there exists no pattern ϕ ∈ Φ such that the pattern ϕ matches t.

Let (a t,p ) be an m × ℓ binary matrix where (a t,p = 1) iff match(p, t) = true, i.e., the pattern p matches the transaction t. For the area constraint, we need to compute the number of ones in the binary matrix that are covered by the set of patterns. We can model this by introducing a temporary variable q t,i for every tuple (t, i), such that (q t,i = 1) iff there exists at least one tile (pattern) ϕ ∈ Φ such that t ∈ cover(ϕ, D) and i ∈ ϕ. Let cq p t,i be a binary matrix associated to each pattern p where (cq p t,i = 1) iff p covers both transaction t and item i. Constraints (C x,q ) establish the relationship between variables q and x. Let Φ 0 a given pattern set. We model the generality constraint (C Φ0 gen ) as follows: (Φ ⪯ Φ 0 ) iff for any pattern ϕ ∈ Φ 0 , there exists (at least) one pattern p ∈ Φ s.t. p ⪯ ϕ, i.e. x p = 1. For the specialisation constraint (C Φ0 spe ), (Φ 0 ⪯ Φ) iff for any pattern p ∈ Φ, there exists (at least) one pattern ϕ ∈ Φ 0 s.t. ϕ ⪯ p. "For any pattern p ∈ Φ" is modeled by stating that the number of patterns p ∈ Φ verifying the property must be greater or equal to size(Φ) = ∑ p∈P x p . Handling aggregates. Table 1 shows how constraints involving aggregates (e.g. sum, avg, min, max) can be modeled using ILP. For example, the constraint (C θ,≶ sum ) expresses that the sum of the supports over all patterns in Φ should be ≶ than θ. It can be modeled using a linear constraint, where f p is the support value of a local pattern p. Similarly, we can constraint the average taken over all patterns in Φ (C θ,≶ avg ). Redundancy constraints. To deal with redundancy, we need to know transactions that are multiply covered. Thus, we introduce boolean variables (u t ), (t ∈ D) s.t. (u t = 1) iff transaction t is matched by at least 2 patterns. The total number of such transactions is ∑ t∈D u t . Table 1 gives the modelisation of the redundancy constraint (C θ,≶ redd ), while constraints (C x,u ) establish the relationship between intermediate variables (u and y) and decision variables x.

Our definition of redundancy is similar to that proposed in [START_REF] Shima | Extraction of frequent few-overlapped monotone DNF formulas with depth-first pruning[END_REF] yet different from the (pairwise) redundancy proposed in [START_REF] De Raedt | Constraint-based pattern set mining[END_REF]. The latter was adopted mainly due to its effectiveness for pruning in a level-wise mining algorithm. The differences between the two formalizations of redundancy are briefly sketched here.

Consider the three cases of overlapping patterns shown in Figure 1. The numbers in overlapping areas denote the number of transactions in the overlap. All three cases would be considered the same by a constraint measuring the maximal pairwise overlap between patterns, such as used in [START_REF] De Raedt | Constraint-based pattern set mining[END_REF]. The global redundancy measure we employ evaluates to 6 for case (a), 9 for case (b), and 11 for case (c), capturing the actual situation much better. Notably, summing pairwise redundancies, another option proposed in that paper, will lead to a result of 15 for (c), overstating the redundancy. For this reason, we claim that our modelisation is more appropriate than the one chosen in [START_REF] De Raedt | Constraint-based pattern set mining[END_REF]. Representativeness constraints. Let D i ⊆ D be a partial data set. We introduce |D i | extra boolean variables y ′ t , (t ∈ D i ) such that (y ′ t = 1) iff there exists at least one pattern ϕ ∈ Φ such that pattern ϕ matches t. The modelisation of the representativeness constraint (C

θ,≶,Di rep

) is shown in Table 1. Constraints (C x,y ′ ) establish the relationship between variables (y ′ t ) and (x p ).

This section provides three examples of complex queries and shows how to model them as a combination of constraints presented in Section 2.3. As a first query (Q 1 ), we show the quintessential pattern set mining task: given the result of a local pattern mining operation, we aim to find a (relatively) small subset of patterns that is representative of the entire result. To this end, we want to select patterns that have very little overlap and together cover as much of the data as possible. There are two ways of modeling this query as an ILP problem :

         Maximize ∑ t∈D yt (C θ,≤ redd ) (Cx,y,u) xp ∈ {0, 1}, ∀p ∈ P yt ∈ {0, 1}, ut ∈ {0, 1}, ∀t ∈ D (1)          Minimize ∑ t∈D ut (C θ,≥ cov ) (Cx,y,u) xp ∈ {0, 1}, ∀p ∈ P yt ∈ {0, 1}, ut ∈ {0, 1}, ∀t ∈ D
(1) maximize support (z = ∑ t∈D y t ) subject to maximum redundancy constraints; (2) minimize redundancy (z = ∑ t∈D u t ) subject to minimum support constraints. Constraints (C x,y ) and (C x,u ) governing the new variables u and y can be merged and will be denoted as the following linear constraints (C x,y,u ):

y t + u t ≤ ∑ p∈P a t,p x p ≤ y t + |P| . u t , y t ≥ u t , ∀t ∈ D Our second query (Q 2
) is a refinement of the first one, by imposing a generality constraint. For instance, we aim to summarize a set of subgraphs mined from molecular data, so that a non-data miner, e.g. a chemist, has only a small set of fragments to evaluate. In that case, the practitioner might already have an idea what fragments she would like to see, and wants to see the rest fleshed out. This can be achieved by requiring that a pattern set include a particular pattern (or syntactically related patterns), i.e. that is more general than another one. In the ILP case as well, this just requires a generality constraint to be added.

Our last query (Q 3 ) concerns the k-tiling. The task consists of finding k tiles maximizing the area (z = ∑ t∈D,i∈I q t,i ). Equation (3) depicts our first ILP model M1. The number of tiles k can also be defined as a variable whose value will be determined by the ILP solver. This can be done by specifying a lower bound k min and/or an upper bound k max on the value of k. Note that tiles can be overlapping, but every tuple (t, i) covered is only counted once. This encoding requires (n × m + 2) constraints and ((n × m) + ℓ + 1) variables. This constitutes a major limitation when it comes to handling very large databases. Thus, we propose a second ILP model M2 that approximates the k-tiling by summing the areas v p (p ∈ P) of the individual tiles it contains. In this case, each tuple (t, i) covered may be counted more than once.

                         Maximize ∑ t∈D,i∈I qt,i (Cx,q) k = ∑ p∈P xp kmin ≤ k ≤ kmax k ∈ N, xp ∈ {0, 1}, p ∈ P qi,t ∈ {0, 1}, i ∈ I ∧ t ∈ D (3)                                  Maximize ∑ p∈P vp . xp (1) yt ≤ ∑ p∈P at,p . xp ≤ δo . yt, ∀t ∈ D (2) ∑ t∈D yt ≥ θt (3) zi ≤ ∑ p∈P wi,p . xp ≤ γo . zi, ∀i ∈ I (4) ∑ i∈I zi ≥ θi k = ∑ p∈P xp kmin ≤ k ≤ kmax k ∈ N, xc ∈ {0, 1}, c ∈ P yt ∈ {0, 1}, t ∈ D zi ∈ {0, 1}, i ∈ I (4)
Equation ( 4) depicts our second ILP model M2. It consists of finding a set of tiles covering both the set of transactions and the set of items, with small overlaps on transactions and on items. In this way, we allow to control the redundancy on tuples (t, i) that are multiply counted in the tiling. Constraint (2) states that at least θ t transactions must be covered, while Constraint (1) states that each transaction t cannot occur in more than δ o closed patterns. Let w i,p be an n × ℓ binary matrix where (w i,p = 1) iff the item i belongs to the tile or pattern p. Constraint (4) states that at least θ i items must be covered, while Constraint (3) states that each item i cannot occur in more than γ o tiles. In the experimental section, due to the space limitation, we focus on questions related to the k-tiling problem.

Related work

Pattern set mining is an important part of a number of data mining tasks such as classification [START_REF] Liu | Integrating classification and association rules mining[END_REF], clustering [START_REF] Babaki | Constrained clustering using column generation[END_REF][START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF], pattern summarization [START_REF] Xin | Extracting redundancy-aware top-k patterns[END_REF], or database tiling [START_REF] Geerts | Tiling databases[END_REF]. Due to the highly combinatorial nature of the problem, most methods proceed in two phases. First, an exhaustive algorithm generates the whole collection of local patterns satisfying given constraints and the second phase produces pattern sets by selecting smaller subsets of relevant patterns from the whole collection of local patterns, often by using heuristics to manage computational complexity. Unlike these works, our method does not use heuristics to provide a pattern set but relies on a solid formalization in the ILP paradigm, while the search is guided by the optimization of an objective function.

There are very few attempts on searching pattern sets according to complete approaches. The original idea of pattern set mining was proposed in [START_REF] De Raedt | Constraint-based pattern set mining[END_REF]. The authors formally introduce a variety of constraints at the level of the pattern sets. Unfortunately, the pruning techniques are weak and the algorithm remains limited to small collections of patterns. Specific settings have been proposed by [START_REF] Knobbe | Maximally informative k-itemsets and their efficient discovery[END_REF] (fixing the size of pattern sets and relying on the anti-monotonicity of a particular quality function) or [START_REF] Cagliero | Pattern set mining with schema-based constraint[END_REF] (using a dedicated global constraint on the attributes). The approach in [START_REF] Geerts | Tiling databases[END_REF] is heuristic but does not use post-processing, instead iteratively mining tiles, taking already found ones into account.

The constraint programming framework was investigated to accomplish the pattern set mining task by modeling pattern sets with constraints [START_REF] Guns | k-pattern set mining under constraints[END_REF][START_REF] Khiari | Constraint programming for mining n-ary patterns[END_REF]. However, these methods require to fix the number of local patterns included in a pattern set, a strong limitation in practice, and tend to have scaling problems. Recent contributions also employ more specialized systems such as satisfiability solvers [START_REF] Jabbour | The top-k frequent closed itemset mining using top-k SAT problem[END_REF] and integer linear programming techniques [START_REF] Babaki | Constrained clustering using column generation[END_REF][START_REF] Ouali | Efficiently finding conceptual clustering models with integer linear programming[END_REF]. These methods address particular problem settings whereas we propose a declarative and exhaustive method based on ILP returning the best solution according to an optimization criterion, and which is able to handle a wide variety of constraints and therefore various different pattern set mining tasks.

Experiments

For a better understanding of the suitability of the ILP approach, we focus our experiments on one prototypical task for pattern set mining: the k-tiling problem (NP-Hard).

The experimental evaluation is designed to address the following questions: 1. How do the running times of our approach (ILP) compare to the only existing CP approach, proposed by Guns et al. (KPatternSet), for the k-tiling problem? 2. Given the space requirements of the ILP model M1, how do the obtained k-tilings compare qualitatively with those resulting from the (approximating) ILP model M2? 3. In light of the exact nature of our approach, how do the resulting k-tilings compare qualitatively with those resulting from (k-LTM) [START_REF] Geerts | Tiling databases[END_REF]. 34. How do the k-tilings with overlapping tiles compare qualitatively with those having non-overlapping tiles ?

Experimental protocol. Experiments were carried out on the same datasets which were used in [START_REF] Guns | k-pattern set mining under constraints[END_REF] and available from the UCI repository. Table 2 shows the characteristics of these datasets. All experiments were conducted on AMD Opteron 6174 with 2.60 GHz of CPU and 256 GB of RAM. 4 We used closed patterns to represent tiles since they cover a larger area than their non-closed counterparts. We used LCM to extract the set of all closed patterns and CPLEX v.12.4 to solve the different ILP models. For all methods, a time limit of 24 hours has been used. As M2 requires setting the parameters for the coverage and non-overlap relations, we propose the following three settings : -M2a with settings allowing similar amounts of coverage and overlap as k-LTM; -M2b with settings allowing the coverage of all transactions (θ i = m) with the maximum overlap (δ 0 = |P|) and the coverage of at least one item (θ i = 1) without any overlap for items (γ 0 = 1); -M2c with settings allowing the coverage of all transactions (θ i = m) without any overlap (δ 0 = 1) and the coverage of at least one item (θ i = 1) with the maximum overlap for items (γ 0 = |P|).

To assess the quality of a k-tiling Φ, we define the recall of Φ, measured by the fraction of all ones in the binary matrix D belonging to area(Φ, D), which should be as large as possible: recall(Φ, D) = For the value of k for which an optimal k-tiling can be found, ILP-M1 is up to several orders of magnitude faster than KPatternSet.

∑ (t,i)∈area(Φ,D) D ti ∑ t ∑ i D ti . (
(b) Comparing M1 with M2a and M2b. ILP-M1 finds the optimal solution on most of the datasets, but ILP-M2a remains relatively close in terms of recall, particularly for (k ≤ 5). In addition, ILP-M2a is much faster, particularly on Lymph and Vote (speedup of up to 660). The main limitation of M1 remains its space requirement. For the three most difficult datasets -Mushroom, Hepatitis and Anneal -ILP-M1 fails to find a solution. Comparing ILP-M2a with ILP-M2b, the latter shows clearly higher recall ILP-M2b and k-LTM achieve higher recall than ILP-M2c. This is not surprising as the tilings found by ILP-M2b consist of large, transaction-overlapping tiles, contrary to those of ILP-M2c (see Col. 4). ILP-M2c makes up for this by covering more items than the other approaches, and mining item-overlapping tiles. This tuning of output characteristics is a strength of the declarative approach.

Conclusion

Pattern set mining has become an indispensable data mining task to control the overly large result sets of local pattern mining operations. In this work, we have for the first time presented a practically useful approach that retains the richness of the constraint language of the original pattern set mining approach [START_REF] De Raedt | Constraint-based pattern set mining[END_REF]. Our method is declarative, based on the techniques developed in ILP, allowing to choose particular (combinations of) pattern set measures as objective functions to be optimized. This permits the user to prioritize particular aspects of a pattern set, while constraining others. Existing ILP solver guarantee to return the best pattern set, according to the given optimization criterion, that satisfies a user-defined set of constraints. Experiments have illustrated and shown the efficiency of our approach through the example of the tiling problem but our approach is broad enough to cover and leverage many pattern mining problems such as clustering, classification, or pattern summarization. The flexibility of our approach is clearly a major step towards developing the interactive data mining systems that are requested in data science. Having defined this framework, further work will consist of properly specifying the models corresponding to different data mining tasks. It will be necessary to formulate new constraints and models, and fine-tune them to achieve best results. We also plan to exploit column generation techniques to enhance the scalability of our solving step.

  t D, denoted by cov(ϕ, D), is the set of transactions in D that ϕ matches: cov(ϕ, D) = {t ∈ D | match(ϕ, t) = true}. The support of ϕ is the size of its cover: sup(ϕ, D) = |cov(ϕ, D)|. The tile of a pattern ϕ contains all tuples that are covered by the pattern: tile(ϕ, D) = {(t, i) | t ∈ cover(ϕ, D), i ∈ ϕ}. These tuples form a tile or rectangle of 1's in the database D. The area of tile(ϕ, D) is equal to its cardinality: area(ϕ, D) = |tile(ϕ, D)| = |ϕ| . sup(ϕ, D).

  this definition, Φ is interpreted as the disjunction of the individual patterns ϕ it contains. -Support of pattern set. The support of Φ, denoted as sup(Φ, D), is calculated in the same way as for individual patterns: sup(Φ, D) = |cov(Φ, D)|. -Size of pattern set. The size of Φ, denoted as size(Φ), is the number of patterns that Φ contains: size(Φ) = |Φ|. -Area of pattern set. The area of a pattern set was studied in the context of large tile mining [6]. The area of Φ, denoted as area(Φ, D), is defined as the area of all the tiles of the individual patterns ϕ it contains: area(Φ, D) = | ∪ ϕ∈Φ tile(ϕ, D)|. -Generality of pattern set. A pattern set Φ is more general than a pattern set Ψ , denoted as Φ ⪯ Ψ , iff for all pattern ψ ∈ Ψ , there exists a pattern ϕ ∈ Φ s.t. ϕ ⪯ ψ. Discriminative Constraints. Given a database D organized into possibly overlapping subsets D 1 , . . . , D n ⊆ D, the discriminative constraints can be used to measure and optimize how well a pattern set discriminates between examples of subsets D i . Discriminative measures are typically defined by comparing the number of examples covered by the pattern set for a subset D i , to the total number of examples covered in D. -Representativeness of a pattern set. Representativeness indicates how characteristic the examples covered by the pattern set are for a subset D

3

 3

Fig. 1 .

 1 Fig. 1. Three patterns overlapping

  a) Comparing ILP-M1 with KPatternSet. Tab. 2 compares the performance compares of ILP-M1 and KPatternSet(in terms of CPU-times) for various values of k on different datasets. We also report the corresponding value of recall. The CPUtimes of ILP-M1 include those for the preprocessing step. ILP-M1 clearly outperforms KPatternSet on all datasets: KPatternSetgoes over the timeout for k ≥ 4.

Table 3 .

 3 Qualitative comparison. ( (3): ILP-M2b; (3'): ILP-M2c; (5): k-LTM).

	3	-0.36	-0.00	TO	-0.47	TO	-0.34	TO
	4	-0.46	-0.00	TO	-0.64	TO	-0.35	TO
	5	-0.52	-0.00	TO	-0.74	TO	-0.37	TO
	6	-0.57	-0.00	TO	-0.67	TO	-0.46	TO
	7	-0.59	-0.00	TO	-0.84	TO	-0.47	TO
	8	-0.62	-0.00	TO	-0.71	TO	-0.56	TO
	9	-0.64	-0.00	TO	-0.78	TO	-0.59	TO
	10	-0.65	-0.00	TO	-0.82	TO	-0.59	TO

We use the implementation available at https://people.mmci.uni-saarland.de/ ˜jilles/prj/tiling/.

The k-LTM implementation is Windows-only, and run times therefore only roughly indicate its behavior.

for Hepatitis, Primary Tumor and Vote. This is because ILP-M2b allows overlapping tiles with high redundancy (see Tab. 3). In addition ILP-M2b is faster than ILP-M2a on 51 instances (out of 64) with a speed-up between 1 and 4 for 27, and between 7 to 25 for 9 instances. Note that on Mushroom dataset, no k-tiling exists with M2b. These results show that ILP-M2a and ILP-M2b achieve good recall compared to ILP-M1 with less space requirement, hence the interestingness of using ILP-M2b as a faster alternative for approximating the optimal k-tiling.

(c) Comparing ILP with k-LTM. k-LTM differs from our approach in three points: 1) using a heuristic is faster but may lead to suboptimal solutions, 2) mining iteratively, k-LTM can take information about already found tiles into account, and 3) a k-LTM k + 1-tiling will always be a superset of a k-tiling -ILP can find different solutions. As Tab. 2 shows, ILP-M1 always achieves better recall than k-LTM, yet requires more time to find the optimum, (k-LTM running times are shown in the last column). For the most difficult dataset Anneal, neither method find a solution. Comparing ILP-M2b with k-LTM, k-LTM has a slight advantage (three data sets). While complete search beats iterative mining, it does help gaining an advantage over heuristic post-processing.

(d) Comparing M2c with M2b and k-LTM. In our last experiment, we mine k tiles without any overlap (i.e. M2c) and compare them to those resulting from M2b and k-LTM. Tab. 3 shows four distinct cases of recall and redundancy for the three approaches. Col.


Albrecht Zimmermann
email: albrecht.zimmermann@unicaen.fr

Guest editorial: Special issue on Sports Analytics

Ulf Brefeld • Albrecht Zimmermann the date of receipt and acceptance should be inserted later This special issue is dedicated to recent advances in sports analytics. The field got its start in the statistics community [START_REF]MathSport International[END_REF] and eventually attracted interest from sports management professionals (as immortalized by the book "Moneyball" [START_REF] Lewis | Moneyball: The art of winning an unfair game[END_REF]), culminating in the "MIT Sloan Sports Conference" [START_REF]MIT sloan sports analytics conference[END_REF].

As in most other areas of society, increasing amounts of data are being collected in all kinds of sports, and automated data analysis has become an important and rapidly developing field. Hence, more and more researchers from data mining (and machine learning) communities have joined the fray and specialised workshop series such as "Machine Learning and Data Mining for Sports Analytics" at ECML/PKDD [START_REF] Davis | Machine learning and data mining for sports analytics[END_REF] or "Large-Scale Sports Analytics" at KDD [START_REF] Lucey | KDD workshop on large-scale sports analytics[END_REF] attest the increasing popularity of intelligent data analysis for sports analytics.

Sports analytics resides at a very attractive intersection of concrete application problems (both in health care/medical/sports research and the various industries connected to professional sports), significant commercial interest, large data collections, and wide-spread interest by the general public. Similar to early artificial intelligence research on games, sports data offer themselves as an interesting test bed for data mining researchers. In contrast to games -most of which have by now been solved -the universe of sports data is not discrete, and the elements of human individuality and human error have more influence, increasing the challenge. Yet at the same time many sports are constrained by rules and the place (track, field, climbing wall etc.) where the action takes place, offering repeatability that other real-life settings lack. Finally, sports data are being systematically collected, without the gaps (or mis-assigned values) that occur in sensor or administrative data.

Today, many different strategies, methods, and techniques have been studied in the context of sports analytics, depending on the type of sports, the data, and the goals of the analysis. Consequently, despite sports analytics being a rather novel field, there already exists a very diverse set of research questions, approaches, and data sources in the literature. Hence, the collection of papers presented in this special issue is neither comprehensive nor anticipates all future trends, but we hope it will provide a starting point for entering this exciting area.

As we expected, the special issue received much interest, attracting twenty eight submissions, of which ten made the final cut. The material included in this collection covers sports as diverse as baseball (Bendtsen The reported analyses are performed both on an aggregated (match actions, referee bias etc) and on individual levels (player movements, player diets etc).

The contributions in this special issue challenge the standard computation model of learning from independently drawn instances by focusing on spatiotemporal player trajectories, regularly conducted physiological measurements, or player career data. Technically, the analyses are carried out using a variety of approaches, such as deep learning, Bayesian networks, or archetypal analysis. In contrast to typical data mining papers, in many cases the described work is not limited to the data analysis technique but involves the entire KDD pipeline from data preparation (or even data acquisition) via transformation, analysis, up to the interpretation of derived results. Some articles extend contributed papers of the afore-mentioned workshops, and the Sloan Sports Analytics Conference, but this special issue also contains novel contributions. We thus believe that it provides a timely snap-shot of the state-of-the-art in this exciting field, covering a wide range of methods and sports.

  et al.), basketball (van Bommel et al., Vinue et al.), beach volleyball (Kautz et al.), cricket (Salman et al.), ice hockey (Schulte et al.), rock climbing (Herault et al.), soccer (Andrienko et al., Kostakis et al.), and speed skating (Knobbe et al.).

We would like to thank everybody who contributed to the special issue, the authors for their valuable contributions, the guest editorial board for delivering high-quality reviews, Melissa Fearon and the Springer team for making it happen and, last but not least, Juffi Fürnkranz for pushing the idea of a special issue forward. Enjoy reading, Ulf Brefeld and Albrecht Zimmermann, 29/06/2017


Ajay Gopinathan
email: ajay.gopinathan@ucalgary.ca

Zongpeng Li
email: zongpeng@ucalgary.ca

Strategyproof Mechanisms for Content Delivery via Layered Multicast

Layered multicast exploits the heterogeneity of user capacities, making it ideal for delivering content such as media streams over the Internet. In order to maximize either its revenue or the total utility of users, content providers employing layered multicast need to carefully choose a routing, layer allocation and pricing scheme. We study algorithms and mechanisms for achieving either goal from a theoretical perspective. When the goal is maximizing social welfare, we prove that the problem is NP-hard, and provide a simple 3-approximation algorithm. We next tailor a payment scheme based on the idea of critical bids to derive a truthful mechanism that achieves a constant fraction of the optimal social welfare. When the goal is revenue maximization, we first design an algorithm that computes the revenue-maximizing layer pricing scheme, assuming truthful valuation reports. This algorithm, coupled with a new revenue extraction procedure for layered multicast, is used to design a randomized, strategyproof auction that elicits truthful reports. Employing discrete martingales to model the auction, we show that a constant fraction of the optimal revenue can be guaranteed with high probability. Finally, we study the efficacy of our algorithms via simulations.

Introduction

Data dissemination applications such as media streaming, file downloading and video conferencing represent an increasingly significant fraction of today's Internet traffic [START_REF] Kurose | Computer networking: a top-down approach featuring the Internet[END_REF]. A natural protocol for one-to-many content delivery is multicast [START_REF] Jain | Packing Steiner Trees[END_REF][START_REF] Thimm | On The Approximability Of The Steiner Tree Problem[END_REF], which reduces redundant transmissions and utilizes network bandwidth efficiently. The Internet is an inherently heterogeneous 'network of networks' with diverse connection types, and therefore disparate download capabilities among its users. As a result, single-rate multicast lacks the required flexibility to cater simultaneously to the needs of every user. Layered multicast [START_REF] Mccanne | Receiver-driven layered multicast[END_REF][START_REF] Zhao | Lion: Layered overlay multicast with network coding[END_REF][START_REF] Gopinathan | Optimal layered multicast[END_REF] offers an attractive solution by encoding the media content into layers with varying sizes: a base layer provides basic playback quality, and improvement is possible through further reception of a flexible number of enhancement layers. Users are then able to enjoy playback quality commensurate with their download capacities [START_REF] Mccanne | Receiver-driven layered multicast[END_REF][START_REF] Zhao | Lion: Layered overlay multicast with network coding[END_REF][START_REF] Gopinathan | Optimal layered multicast[END_REF].

The Internet contains private entities driven by selfish and often commercial interests. Content providers are thus compelled to include social and economic considerations when computing an appropriate multicast scheme. Previous studies on layered multicast have focused on optimizing metrics such as throughput [START_REF] Zhao | Lion: Layered overlay multicast with network coding[END_REF][START_REF] Gopinathan | Optimal layered multicast[END_REF], and do not consider the potential for strategic behaviour by users. Users subscribing to media content via layered multicast have different valuations for receiving the service [START_REF] Nisan | Algorithmic mechanism design (extended abstract)[END_REF][START_REF]Algorithmic Game Theory[END_REF], which is naturally proportional to the number of layers received. However, such valuation is private to the user itself, who may strategically misreport its value for potential economic benefit, e.g. in the hopes of receiving the multicast service with a lower payment. It is critical for content providers to take such strategic behaviour into consideration when routing and pricing the layers. An altruistic content provider aims to maximize social welfare, i.e., the sum of the user valuations for layers received. A commercially motivated content provider wishes to maximize its own revenue instead. The challenge for the content provider in either case is to determine simultaneously a layer allocation, routing and pricing scheme that approaches the stated goal, while ensuring users have no incentive to misreport their valuations.

In this paper, we provide a theoretical study on the classical economic problems of maximizing social welfare and revenue in the layered multicast setting. We adopt a network information flow approach to model layered multicast, and design algorithms and mechanisms for maximizing either social welfare or revenue, all the while treating multicast receivers as strategic agents. We focus on the common cumulative layering scheme, where decoding layer k requires the successful reception of layers 1 through k. Our solutions are both efficiently computable and provably strategyproof. A mechanism is strategyproof if users have no incentive to lie about their true valuations of the multicast service to the content provider.

We first show that the social welfare maximization problem for layered multicast is NP-Hard. Nevertheless, we design a 3-approximation algorithm for the problem. Our algorithm exploits network coding [START_REF] Ahlswede | Network Information Flow[END_REF] to find a layer allocation that simultaneously maximizes social welfare and guarantees a feasible routing scheme. We next focus on the problem of eliciting truthful valuation reports for maximizing social welfare. It turns out that the direct application of the well known VCG mechanism [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF][START_REF] Clarke | Multipart pricing of public goods[END_REF][START_REF] Groves | Incentives in teams[END_REF] is not strategyproof. We design a payment scheme built on the technique of finding the minimum critical bid capable of changing the outcome of the approximation algorithm, and proceed to prove that the resulting mechanism using this payment scheme is truthful.

We next focus on designing mechanisms that maximize revenue for content providers. The first challenge here is computing an appropriate layer pricing scheme for maximizing revenue. We show that a greedy algorithm that computes the best price for layer k, under the assumption that this same price will be used for all layers k ≥ k, is indeed optimal. The next challenge is to design a mechanism to elicit user valuations truthfully. We focus on the more realistic prior-free setting [START_REF] Goldberg | Competitive auctions[END_REF], when no information on the distribution of user valuations is known a priori. We first prepare a new revenue extraction procedure tailored to the layered multicast setting. This procedure, coupled with the revenue-maximization pricing algorithm, are used as ingredients in a strategyproof, randomized auction first proposed by Goldberg et al. [START_REF] Goldberg | Competitive auctions[END_REF]. We model the auction using discrete martingales [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF], and show that one can achieve a δ-fraction of the optimal revenue with probability at least 1 -2 exp(-

(1-2δ) 2 2α
), where α is the ratio of the maximum contribution by any agent to the optimal revenue.

Due to space constraints, we omit a number of technical results and their corresponding proofs from this paper. The interested reader is urged to examine the full paper [START_REF] Gopinathan | Strategyproof mechanisms for layered multicast[END_REF] for further details. The rest of this paper is organized as follows -we discuss related work in Sec. 2, and introduce our model and notations in Sec. 3. Sec. 4 and Sec. 5 study social welfare maximization, Sec. 6 studies revenue maximization. Simulations results are presented in Sec. 7 before we conclude the paper.

Previous Research

Traditionally, computing an optimal multicast routing scheme is modeled as optimal Steiner tree packing, a well-known NP-Hard problem [START_REF] Jain | Packing Steiner Trees[END_REF][START_REF] Thimm | On The Approximability Of The Steiner Tree Problem[END_REF]. The seminal work of Ahlswede et al. [START_REF] Ahlswede | Network Information Flow[END_REF] on network coding dramatically changed the landscape of multicast algorithm design. Exploiting the fact that information can be both replicated and encoded, network coding leads to efficient polynomial time algorithms for optimal multicast routing [START_REF] Li | On Achieving Optimal Throughput with Network Coding[END_REF][START_REF] Li | Efficient and Distributed Computation of Maximum Multicast Rates[END_REF].

The field of mechanism design originates from economic theory, where the goal is to implement a desired social choice in the presence of agents that behave strategically [START_REF]Algorithmic Game Theory[END_REF]. The seminal work of Vickrey in auction design [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF] and Clarke's pivot payment rule [START_REF] Clarke | Multipart pricing of public goods[END_REF] pioneered research on strategyproof mechanism design, which culminated in the general VCG mechanism as presented by Groves [START_REF] Groves | Incentives in teams[END_REF]. The VCG mechanism is the best known strategyproof method for maximizing social welfare, but in general fails to be truthful when the social welfare maximization problem is NP-Hard and approximate solutions are used [START_REF] Nisan | Algorithmic mechanism design (extended abstract)[END_REF].

Revenue maximizing mechanisms are known as optimal auctions in the parlance of economic theory [START_REF]Algorithmic Game Theory[END_REF]. Classic literature in such auction mechanism design assume that user valuations are drawn from a probability distribution known to the auctioneer [START_REF] Myerson | Optimal auction design[END_REF]. The seminal work of Myerson [START_REF] Myerson | Optimal auction design[END_REF] showed that applying the VCG [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF][START_REF] Clarke | Multipart pricing of public goods[END_REF][START_REF] Groves | Incentives in teams[END_REF] mechanism using virtual valuations of users yields a mechanism that is revenue-maximizing. From a computer science perspective however, the prior-free setting where such distribution information is not assumed is more realistic yet also more challenging. The work by Goldberg et al. [START_REF] Goldberg | Competitive auctions[END_REF] show that deterministic, revenue-maximizing auctions that are symmetric (i.e., independent of any ordering on agents) and strategyproof do not exist. Consequently, they design a randomized, strategyproof auction that guarantees a constant fraction of the optimal revenue. Borgs et al. [START_REF] Borgs | Multi-unit auctions with budget-constrained bidders[END_REF] further consider budget-constrained agents, and show that when budgets are private information, the VCG scheme is not truthful; they design a randomized revenue-maximizing auction instead.

Preliminaries

We model the network as a directed graph, G = (V, E). Each edge → uv ∈ E has a finite capacity C( → uv). A distinguished source node s ∈ V provides a multicast streaming service. The media is encoded into K layers, where the size of layer k ∈ [1..K] is l k . We will focus on the most commonly used layering techniquethe cumulative layering scheme [START_REF] Iso/Iec | Generic coding of moving pictures and association audio information[END_REF][START_REF] Itu | Video coding for low bit rate communication[END_REF], where decoding layer k requires the use of layers 1 through k -1 as well.

Let T denote the set of users or agents in the network potentially interested in this multicast service. We will take the network flow approach to modeling the multicast routing scheme. We employ network coding within each data layer, to enable polynomial time computability of the optimal flow for a given layer. Our model for computing multicast flows is based on a classic result on multicast network coding, which states that a multicast rate of d is feasible if and only if it is a feasible unicast rate to each receiver [START_REF] Ahlswede | Network Information Flow[END_REF]. This allows us to view the optimal flow within a network coded layer as the union of conceptual unicast flows [START_REF] Li | Efficient and Distributed Computation of Maximum Multicast Rates[END_REF][START_REF] Li | On Achieving Optimal Throughput with Network Coding[END_REF] to each receiver, where these flows do not compete for bandwidth.

For an agent i ∈ T , let t i ∈ V be the corresponding node in the network. We assume that an agent i is willing to pay v i ∈ Z + monetary units for receiving a multicast layer, where without loss of generality, v i is assumed to be of type integer. The value v i is private information known only to i. While we plan to consider more complex valuation functions in the future, the present work nonetheless provides valuable insight on the design of strategyproof mechanisms for layered multicast. An agent i may be charged a price p k for receiving a layer k. Let x be a 2D matrix with each entry x k i indicating whether agent i is allocated layer k or not. We will also use x i when referring to the layer allocation for agent i, while x k denotes the allocation of layer k for all agents. If an agent receives up to k layers and is charged p k for every layer received, then its overall utility function is given as

u i = v i k - k k=1 p k .
Each agent is assumed to be selfish and rational, and behaves strategically with the aim of maximizing its utility function. The utility of the content provider on the other hand is simply the sum of all payments received.

A mechanism is essentially a protocol that implements some desired social choice function. We will focus on revelation mechanisms [START_REF]Algorithmic Game Theory[END_REF], where the only strategy available to each agent in the network is to declare its valuation for receiving a data layer. In this case, the mechanism reduces to the well known auction problem, and hence we will also refer to the value declared by agent i as the bid b i . Let b denote the bid vector of all agents, and denote by b -i the bid vector of all agents but i. For a given bid vector, the utility of agent i when bidding b i will be denoted as u i (b i , b -i ). Our goal is to design mechanisms that either maximize social welfare or revenue. The social welfare of a mechanism is simply the sum of the utilities of all agents in the system, including the mechanism designer (this case, the content provider), which is equivalent to the sum of all user valuations since payments and revenue cancel each other. A revenue-maximizing mechanism or auction maximizes the payments collected from all agents in the system.

The seminal work of Myerson [START_REF] Myerson | Optimal auction design[END_REF] paved the way for strategyproof revenuemaximizing auctions, under the assumption that agent valuations were drawn from distributions known to the auctioneer. In contrast, recent work in the computer science community [START_REF] Goldberg | Competitive auctions[END_REF][START_REF] Borgs | Multi-unit auctions with budget-constrained bidders[END_REF][START_REF]Algorithmic Game Theory[END_REF] consider revenue-maximizing auctions when this information is unavailable. We will focus on this latter, prior-free setting as well in this paper.

A mechanism is said to be strategyproof if the dominant strategy of every agent is to bid its true valuation, regardless of the bids submitted by other agents, i.e.,

u i (v i , b -i ) ≥ u i (b i , b -i ), ∀b i = v i , ∀b -i .
The following characterization of truthfulness, due to Myerson [START_REF] Myerson | Optimal auction design[END_REF], will be particularly useful:

Lemma 1 [START_REF] Myerson | Optimal auction design[END_REF] Let x i (b i ) be the allocation function for bidder i with bid b i . A mechanism is strategyproof if and only if the following hold for a fixed b -i :

-x i (b i ) is monotonically non-decreasing in b i -Bidder i bidding b i is charged b i x i (b i ) - bi 0 x i (z)
dz Observe that the payment function is completely determined by the allocation function, and vice versa for a fixed b -i . This implies two equivalent methods of viewing a truthful mechanism: (i) there exists a critical bid b i that depends only on b -i , such that if i bids at least b i , then i is allocated the item, or (ii), the payment of every agent should not depend on its bid b i . We will use the first point of view to design strategyproof mechanisms that achieve efficiency in Sec. 5, while the second perspective will be useful when we design truthful revenue maximization mechanisms in Sec. 6.

The Social Welfare Maximization problem

In the social welfare maximization (SWM) problem, we seek a feasible multicast routing and layer allocation scheme that maximizes the sum of the utilities for all agents and the utility of the service provider. We can formulate SWM as the following linear integer program (IP):

Maximize k i vix k i (1)
Subject To:

v∈N (u) [f k i ( → uv) -f k i ( → vu)] = 0 ∀k, ∀i, ∀u f k i ( → uv) ≤ f k ( → uv) ∀k, ∀i, ∀ → uv k f k ( → uv) ≤ C( → uv) ∀ → uv x k+1 i ≤ x k i ≤ f k i ( → t i s) l k ∀k = 1..K -1, ∀i f k i ( → uv), f k ( → uv) ≥ 0; x k i ∈ {0, 1} ∀k, ∀i, ∀ → uv
Since the payment by the agents cancels the content provider's utility, both terms can be ignored in the objective function. We use the flow vector f to denote the multicast flow. The variable f k i ( the actual flow on edge → uv. For succinctness, the above formulation assumes a virtual, uncapacitied directed edge from each t i ∈ T to s. In the first constraint, N (u) denotes the set of u's neighbours in G. This constraint ensures the conceptual unicast flow is conserved at all nodes. The second constraint captures the notion that the true flow on an edge for a given layer k is the maximum of all conceptual flows on that edge carrying layer k. The third requirement ensures that capacity constraints are respected on all edges. The final constraint models: (i) the cumulative layering scheme requirement, a node is able to play layer k only if layers 1 through k -1 has been obtained as well, and (ii) a layer can be decoded only if all its l k bits have been received. However, even disregarding the routing dimension, the decision version of SWM is NP-Hard. The proof for this hardness result can be found in the full version of this paper [START_REF] Gopinathan | Strategyproof mechanisms for layered multicast[END_REF].

We are thus motivated to design an approximation scheme for SWM. Algorithm 1 shows our approximation algorithm for the SWM problem. We first compute the individual max flows for each agent, to decide the maximum number of layers it can receive. We then create k sets, where the set W(k) contains all agents that can receive up to at least layer k. If the set W(k ) yields the maximum social welfare, we set all agents in W(k ) to receive up to k cumulative layers. We are guaranteed that such a multicast scheme is feasible due to the classic result on multicast feasibility with network coding stated earlier. The next theorem shows that Algorithm 1 achieves a constant approximation ratio: Theorem 2 Alg. 1 is a 3-approximation algorithm for SWM.

A proof of the above theorem can be found in the full version of this paper [START_REF] Gopinathan | Strategyproof mechanisms for layered multicast[END_REF].

Strategyproof social welfare maximization

In this section, we design a strategyproof mechanism for content providers who wish to seek a layer allocation scheme that maximizes social welfare. Our goal is to ensure that the mechanism is both efficiently computable and strategyproof. A common approach here is to directly apply the celebrated Vickrey-Clarke-Groves (VCG) mechanism [START_REF] Vickrey | Counterspeculation, auctions, and competitive sealed tenders[END_REF][START_REF] Clarke | Multipart pricing of public goods[END_REF][START_REF] Groves | Incentives in teams[END_REF] in conjunction with Algorithm 1. We have shown that the latter is efficiently computable with at most a constant factor loss in the social welfare, while the former is a well known strategyproof mechanism. However, applying the VCG mechanism while using suboptimal algorithms can harm truthfulness [START_REF] Nisan | Algorithmic mechanism design (extended abstract)[END_REF], and we demonstrate that this is also the case with Algorithm 1. Please see the full paper for details [START_REF] Gopinathan | Strategyproof mechanisms for layered multicast[END_REF].

Next, we design a payment scheme that makes Algorithm 1 strategyproof. The key insight is to ensure that each agent is made to pay a critical bid for every outcome selected during each iteration of Algorithm 1. Recall that the outcome of every feasible iteration of Algorithm 1 is a chosen set W(k), where all agents in this set are allocated up to layer k. If the absence of an agent i causes some other outcome W(k ) to be selected by the algorithm, then this agent should made to pay the minimum bid required to ensure W(k) is selected ahead of W(k ). Let p i (r) be the payment charged to agent i in iteration r of Algorithm 1. The payment p i (r) can be computed using the procedure shown in Algorithm 2, which is called during every iteration of Algorithm 1, for every agent i. The total payment of each agent is then the sum of all payments incurred over all feasible iterations of Algorithm 1, p i = r p i (r). It can be shown that this payment scheme yields a truthful mechanism.

Theorem 3 Using the payment scheme in Algorithm 2, bidding truthfully is a dominant strategy for all agents when Algorithm 1 is used to solve SWM.

The proof for this theorem can be found in the full version of this paper [START_REF] Gopinathan | Strategyproof mechanisms for layered multicast[END_REF].

Strategyproof Revenue Maximization

It is known that mechanisms that achieve optimal social welfare have poor revenue generating properties [START_REF]Algorithmic Game Theory[END_REF]. In this section, we will design strategyproof mechanisms for optimizing the revenue for the content provider. To attain this goal, we need to first find a pricing scheme that maximizes the content provider's revenue, assuming truthful valuation reports are given. We will focus on the case when the content provider chooses a fixed price per layer, in the interest of fairness. Once we know how to compute the optimal layer prices, the next challenge is to design a mechanism that is strategyproof. We will focus on the prior-free setting, when no Bayesian information on the valuations of the agents are known. Such an assumption is both realistic, and without loss of generality. It implies that any guarantee our mechanisms make apply for all distributions of user valuations.

Algorithm 3: Computing Revenue-Maximizing Layer Prices

Input: Set of agents T , algorithm A for solving SWM, network G Output: Optimal layer price vector p, revenue R

1 Initialize k := 1, R := 0 ; 2 while k ≤ K do 3 Fixing x 1 . . . x k-1 , use A to compute allocation x k . . . x K on G; 4 Let v l i := vix l i ∀i, ∀l = k . . . K ; 5 p k := arg max v k j |{v l i |v l i ≥ v k j ∧ l ≥ k}| ; 6 ∀i such that v k i < p k , fix x k i := 0 ; 7 Set R := R + |{v k i |v k i ≥ p k }|

A Randomized Revenue-Maximizing Mechanism

We have shown that if user valuations are known, then the optimal prices can be computed using Algorithm 3. The next challenge is to elicit user valuations truthfully. In designing a strategyproof revenue-maximizing mechanism, the key obstacle in the prior-free setting is the lack of information on the distribution of user valuations. We require that the mechanism can somehow "guess" an optimal price to be charged to an agent i. We know from Lemma 1 that if the "guessing" process does not use i's valuation, then the dominant strategy for i is to declare its valuation truthfully. This intuition naturally suggests a sampling based approach. We can pick a random sampling of agents, whose valuations can be used to compute a good price. This price is then offered to the other agents not in the sample. To ensure truthfulness, we ignore the potential revenue from the sampled agents. This technique was originally used by Goldberg et al. in a random sampling auction [START_REF] Goldberg | Competitive auctions[END_REF] for digital goods, and we apply it as a platform to build our own revenue-maximizing auction for layered multicast.

We begin by introducing some key ingredients that will be required in the final mechanism. The first is a profit extraction algorithm [START_REF] Goldberg | Competitive auctions[END_REF], shown in Algorithm 4. The algorithm takes as input a target revenue R, and a set of agents with the 1-dimensional valuation vector w for some item. Algorithm 4 essentially runs the Moulin-Shenker tattonement process, which attempts to whittle down the initial set of agents in S until the remaining agents can adequately afford to share equally the target revenue R. Note that R, and therefore the price p offered to each agent, is independent of i's valuation w i , and the mechanism is therefore truthful. Let O be the optimal single price revenue that can be made agents who can receive layer k does not exceed the number of agents that can receive layer k < k. As a result, Algorithm 5 begins by distributing R among all layers, while favouring lower layers. Beginning at layer k = K, it attempts to extract the target revenue for each layer r(k) using Algorithm 4 with the valid bids in layer k. If this fails, it then reduces and redistributes r(k) by 1 -since valuations are integral, the revenue available from each layer is integral. Once again, since the prices offered at each layer to each agent is independent of its bid, Algorithm 5 is truthful. Further, if the revenue-maximizing pricing scheme for S generates a revenue of O and R ≤ O, Algorithm 5 will find a successful allocation of prices.

We have now developed all the necessary machinery to design a strategyproof, revenue-maximizing mechanism. The full mechanism is shown in Algorithm 6. The algorithm randomly splits agents into two sets, A and B, and computes the optimal revenue R A and R B from each set. It then attempts to extract R A from agents in B and vice versa. Since the target revenue for each set in Algorithm 5 is independent of the bids of agents in that set, this algorithm is strategyproof. We are guaranteed a revenue of R = min(R A , R B ). It remains now to analyze how R compares to the optimal revenue when all valuations are known exactly, which is at most

R A + R B .
Let p * (k) be the optimal layer price for layer k, and OP T be the optimal revenue when all agent valuations are known. In the optimal solution, let w(k) be the number of agents who contribute to OP T in each layer 1 . . . k. Therefore, we get OP T = k w(k) k l=1 p * (l) . After the random splitting process, let w A (k) and w B (k) be the number of agents who end up in sets A and B respectively, who contribute to OP T up to k layers. Denote by M = K k=1 p * (k) Then M represents the highest possible contribution to OP T by any one agent. The parameter α = M OP T , is a measure of the ratio of the maximum contribution of any one agent to the optimal revenue. We will show that the performance of our mechanism hinges on α.

Theorem 5 For 0 < δ < 0.5, Algorithm 6 achieves a revenue of δOP T with probability at least 1 -2 exp

-(1-2δ) 2 2α
Proof. First, observe that R A ≥ k w A (k) k l=1 p * (l) , while a similar revenue guarantee holds for B. Since the revenue of Algorithm 6 is min(R A , R B ), to achieve a revenue of at least δOP T , then we must have |R A -R B | ≤ (1-2δ)OP T . Now, let X i be the random variable which takes value 1 if agent i ends up in the set A during the random splitting process, and -1 if it ends up in B. Let t i be the revenue contributed by i to OP T , and so we have t i ≤ M , for all i. Impose some arbitrary ordering on the set of agents, and define the random variable Y j = i≤j X i t i , with Y 0 = 0. We then have that in expectation:

E[Yj+1|Y1 . . . Yj] = Yj + E[Xj+1tj+1] = Yj + 1 2 tj+1 + 1 2 (-tj+1) = Yj
That is, the random variable Y j forms a martingale sequence with respect to itself. If there are a total of n agents, then

|Y n -Y 0 | = |Y n | = |R A -R B |.
Further, we have |Y j+1 -Y j | ≤ M , for all j ≤ n. Hence we can bound the probability of the event |R A -R B | ≥ (1 -2δ)OP T using Azuma's inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] as the following:

P r(|Yn| ≥ (1 -2δ)OP T ) ≤ 2 exp - (1 -2δ) 2 OP T 2 2 n j=1 M 2 = 2 exp - (1 -2δ) 2 OP T 2 2nM 2 ≤ 2 exp - (1 -2δ) 2 OP T 2M = 2 exp - (1 -2δ) 2 2α
The first inequality is due to Azuma's concentration result on martingales with bounded differences [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF], while the second comes about since nM ≤ OP T .

We need to ensure strategyproofness is maintained at every stage of our mechanism. Hence, we use a strategyproof pricing scheme in conjunction with the algorithm A in Algorithm 3, and let q be the payment vector. We then run Algorithm 6 as described, and let r be the vector of revenue obtained from each agent. For each agent i in the winning set (either A or B), we charge max(q i , r i ).

It is easy to see that the entire mechanism is both strategyproof, and revenuemaximizing.

Simulations

We now present results from simulations performed to determine the effectiveness of our techniques in practical scenarios. We first studied the performance of Algorithm 1. We used BRITE [22] to generate random network topologies. Link capacities were distributed randomly to model the heterogeneous nature of the network. The multicast group was chosen randomly as well. For each topology, layer sizes were generated randomly between 1 and 5. Fig. 1a shows the social welfare achieved by Algorithm 1 and the optimal solution of Eq. ( 1) as computed by an integer linear program solver, for varying network sizes with 10 agents and 5 layers. In all cases, Algorithm 1 achieves at least 90% of the optimal social welfare. We next examined the effect of the number of layers on the performance of Algorithm 1. As can be seen in Fig. 1b, the greedy technique of Algorithm 1 starts to suffer when the number of layers increases beyond 3. The same effect is also observed in Fig. 1c, where Algorithm 1's approach becomes less effective when the number of agents increase. Nevertheless, in all cases observed, we obtain at least 90% of the optimal social welfare. We next implemented Algorithm 6, together with pricing scheme of Algorithm 3. We then performed simulations on randomly generated sets of agents, with randomly chosen allocations and valuations. Fig. 2a, shows the effect of the number of agents on the revenue gained by Algorithm 6. The revenue obtained by our mechanism improves significantly as the number of agents increase. This is due to the random splitting process. As the number of agents increase, the amount of revenue available from each set is more likely to be balanced. In Fig. 2b, we simulated the auction for different values of the maximum layer size an agent may receive. Here, we find that the auction performs well in all cases, and is not affected by the number of layers. We note that the auction performs well regardless, and tends to obtain at least 40% of the optimal revenue.

Conclusion

In summary, we provide tools for maximizing social welfare as well as revenue for content providers using layered multicast to disseminate information over the Internet. The algorithms and mechanisms developed are both efficiently computable, and strategyproof. We provide a constant factor approximation algorithm for maximizing social welfare in layered multicast, which we augment with a tailored payment scheme for strategyproofness. We also show how to compute optimal prices for maximizing revenue, and design a randomized strategyproof mechanism with provable revenue guarantees. Simulation results confirm the effectiveness of the proposed solutions in practical settings.

→ 1 : 6 if ki = 0 for all i then 7 feasible:= False ; 8 else 9 foreach k ∈ 1 . . . K do 10 W(k) := ∅ ; 11 foreach ti ∈ T do 12 if ki ≤ k then 13 W 16 W

 1678911011121316 uv) indicates the conceptual flow[START_REF] Li | Efficient and Distributed Computation of Maximum Multicast Rates[END_REF][START_REF] Li | On Achieving Optimal Throughput with Network Coding[END_REF] to agent t i carrying layer k, on edge → uv. Similarly, the variable f k ( → uv) indicates Algorithm Approximation algorithm for SWM Input: Set of agents T , network G Output: A 3-approximate multicast routing and layer allocation scheme, x 1 Initialize x k i := 0, s(i) := 0 ∀i, ∀k ; 2 feasible := True ; 3 while feasible do 4 Compute max-flow values mi for each agent i ;5ki := max k | k k=s(i) l k ≤ mi ∀i ; (k) := W(k) ∪ i ; 14 foreach k ∈ 1 . . . K do 15 S(k) := i∈W(k) vik ; (k ) := max k S(k) ; 17 foreach i ∈ W (k ) do 18 x k i := 1 ∀k = 1 . . . k ; s(i) := k + 1 ;19Solve LP degradation of Eq. (1) on G with x ; 20 Set G :=Residual network of G ;

and let k := k + 1 ; 4 :

 14 Algorithm ProfitExtract(R, S, w) Input: Target revenue R, bidder set S with valuation w Output: Winner vector y 1 price p := R |S| 2 For each bidder i ∈ S with wi < p, remove i from S 3 If S = ∅, return failure 4 If no bidder i is removed in Step 2, set yi := 1 for all i ∈ S. Return price p and winner vector y 5 Otherwise repeat from step 1

Fig. 1 .

 1 Fig. 1. The performance of Algorithm 1 is compared to the optimal social welfare for varying network sizes in (a), number of layers in (b) and number of multicast receivers in (c).

Fig. 2 .

 2 Fig. 2. The revenue obtained by Algorithm 6 is compared to the optimal revenue for varying number of agents in (a) and number of layers in (b).

Algorithm 2: Strategyproof Payment Scheme for Algorithm 1

Input: A chosen allocation W(k) in iteration r of Algorithm 1, set of agents T , an agent i Output: Payment charged to agent i for iteration r, pi(r) 1 T := T \ i ; 2 Use Algorithm 1 to find allocation W(k ) in round r for T ; 3 if k < k then

Revenue-Maximizing Layer Prices

Let us first consider how to compute the optimal layer prices when agent valuations have been disclosed truthfully. First, observe that when there is only a single layer (K = 1), the optimal revenue maximizing layer price p is given as p = arg max vi |{v l |v l x l ≥ v i }|. That is, the optimal price is given as the valuation v i that maximizes the size of the set of agents whose valuations are at least v i . One may be tempted to use this equation to find the best prices beginning from layer 1 through K. However, doing so ignores the cumulative layering requirement, and results in a revenue that has an unbounded gap from the optimal. For example, consider three agents with v 1 = 3 and v 2 = v 3 = 1, and x 1 = (1, 0), x 2 = x 3 = (1, 1). Then the previously mentioned greedy scheme charges p 1 = 3 for layer 1, resulting in overall revenue of 3. The optimal pricing scheme is p 1 = p 2 = 1, resulting in a revenue of 5. It is easy to make this example arbitrarily bad. Instead, one needs to recursively optimize the layer prices greedily beginning at each layer, while considering the potential revenue from higher layers. This is precisely the idea behind Algorithm 3. The algorithm takes as input an algorithm A for computing the social welfare maximizing layer allocation. Hence, A can either be Algorithm 1, or an integer program solver used in conjunction with Eq. ( 1). Algorithm 3 computes the best price for layer k, under the assumption that this price will be used for all layers k and above. Once this price is set, we fix the allocation for layer k by assigning it only to agents whose valuation is at least the current price. This may result in some agents being "deallocated" layer k, which in turn leads to excess capacity in the network. Hence, we re-solve the welfare maximizing layer allocation for layer k + 1. Algorithm 3 is optimal, the proof of which can be found in the full version of the paper [START_REF] Gopinathan | Strategyproof mechanisms for layered multicast[END_REF]. Theorem 4 Algorithm 3 computes revenue-maximizing prices with respect to the social welfare computed by A.

Algorithm 5: Profit Extraction with Layers

Input: Set of agents S, allocation x, target revenue R Output: Layer price vector p, winner vector z 1 Initialize r(k) := 0 ∀k = 1 . . . K ; 2 Set k := 0 ; 3 while R > 0 do Algorithm 6: Competitive Auction Input: Set of agents, S Output: Total revenue R 1 Randomly assign bidders in S to one of two sets, A or B 2 Use Algorithm 3 to compute optimal price and revenue for sets A and B 3 Let RA and RB denote the revenue from sets A and B respectively 4 Run Algorithm 5 on A (resp. B) using target revenue RB (resp. RA) 5 Return revenue gained from running Algorithm 5 successfully from S. Then observe that the mechanism is able to successfully find a set of agents to share the revenue R if and only if R ≤ O.

We wish to generalize the design to a truthful profit extraction mechanism when valuations are multi-valued instead of single-valued, as is the case in Algorithm 4. Further, due to the cumulative layering scheme, we must ensure that if an agent is priced out of layer k, no revenue can be extracted from it for all layers k > k. Our profit extraction scheme for agents with valuations for layers is shown in Algorithm 5. The algorithm again takes a target revenue R, and attempts to share them among agents in the set S. The allocation vector x is provided by a social welfare maximizing algorithm, and ensures that agents are only considered for layers which they can receive in the network. The algorithm utilizes the fact that the revenue extracted from any layer k cannot exceed the revenue from any layer k < k. This follows from (a) agents have the same valuations for all layers, and (b) cumulative layering implies that the number of