Sidi Ould

Saad Hamady

Solis: a modular, portable and high performance 1D semiconductor device simulator

Keywords: modular, portable, and high-performance 1D semi-conductor device simulator Solis, Simulation, Semiconductor devices, Scripting, Design, Portable, Solar cell, Heterostructure

may come

I. INTRODUCTION

Numerical simulation is an important step in the design and elaboration of novel photovoltaic solar cells. Over the years, several noncommercial one-dimensional device simulators have been developed [START_REF] Basore | PC1D version 4 for Windows: from analysis to design Photovoltaic Specialists Conference[END_REF][START_REF] Zhu | Applications of AMPS-1D for solar cell simulation[END_REF][3], contributing to the development of the photovoltaic industry. These tools are not portable and can hardly be upgraded or extended; For example, PC1D [START_REF] Basore | PC1D version 4 for Windows: from analysis to design Photovoltaic Specialists Conference[END_REF], the main one-dimensional simulator, was developed in the 1990s for the Windows operating system and uses the nonportable Microsoft Foundation Class (MFC) library with a code basis mixing calculation algorithms and user interface routines. It has been widely used in the photovoltaic community, with the last official version released in June 2003 and updated in 2008 with the release of its source code. 1 SCAPS [3], another popular one-dimensional simulator with a large number of features and regular updates, uses the proprietary National Instruments LabWindows CVI development framework used in virtual instrumentation and running only on Windows. The last official version of AMPS-1D [START_REF] Zhu | Applications of AMPS-1D for solar cell simulation[END_REF], one of the three main noncommercial device simulators, dates from 1997, and runs natively only on Windows 95 up to XP (requiring a Windows 95 up to XP virtual machine to run on Windows 7/8/10). 2 1 An unofficial release of PC1D named PC1D-mod was developed with minor changes but unfortunately removing the ability to handle heterostructures. 2 As for PC1D, there is an unofficial release of AMPS-1D named wxAMPS with changes mainly related to the user interface.

Secondly, the existing tools, mainly the three most widely used ones presented above, do not use some paradigms in computer science related, for instance, to modularity, portability, interoperability, and versatility. None of these free simulators includes a scripting language like in commercial simulators. 3 SCAPS uses a mechanism tightly linked to the user interface to automate user actions, without being a scripting language. Including a scripting language is nowadays necessary to extend possibilities of the simulator for the development of, for example, specific physical models, graded devices, complex nonhomogeneous structures, or optimization of material parameters. On the other hand, these tools do not separate the user interface from the simulation engine; they are mixed by design. The nonmodularity, lack of separation between the user interface and backend simulation engine, and the wide use of nonportable proprietary formats and frameworks automatically imply the features underlined here and highlight the limitations now faced by these existing tools.

Thirdly, Solis includes features that are not included in the mentioned 1D simulators. It can handle the spontaneous and piezoelectric polarizations, an important feature for wurtzite semiconductor materials such as gallium nitride and related alloys. In addition, it handles Schottky contacts and heterostructures in a more comprehensive way and has the capability to simulate graded semiconductor devices easily.

These facts justify the need for a new simulator that takes into account, at each step, the criteria of portability, modularity, versatility, and performance which are now becoming crucial considering the development of heterogeneous computing platforms and the central role of simulation in the development of novel devices. I therefore developed Solis, a new 1D device simulator particularly adapted for solar cell simulation. Solis runs natively on Windows (from XP to 10) or Linux (Debian, CentOS, Ubuntu, etc.) and is easily portable to other platforms including, but not limited to, Android and macOS. It is freely available to download from the author's website4 [START_REF] Saad Hamady | Software for Photovoltaics[END_REF]. Its standard C++ coded simulation engine, optimized at each step of its development process, ensures high performance while retaining complete portability. The embedded fast just in time Lua scripting engine gives the user control over every aspect of the simulation. Solis implements the drift-diffusion model by solving the Poisson-continuity equations, using both the coupled Newton method and the iterative Gummel decoupled method. It can also calculate the band diagram of any heterostructure (using the given database parameters or adding new material parameters), the potential, field and carrier concentration distributions, the currentvoltage characteristic in the dark and under illumination (with a monochromatic, AM1.5 or any user defined spectrum), the capacitance-voltage characteristic, the external quantum efficiency, etc. It takes into account various recombination processes and can handle both nonideal ohmic and Schottky contacts, and can also include spontaneous and piezoelectric polarizations in wurtzite III-N materials. Solis is complementary to some very new tools such as Simudo [START_REF] Dumitrescu | [END_REF] and Solcore [6]. Since Solis is fully implemented in C++ and offers high performance while being fully extensible through the integrated scripting language, it is more suitable for 1D simulation and numerical optimization while these Python tools are suitable for specific simulations including, e.g., quantum effects or intermediate-band materials.

II. MODELING, NUMERICAL METHODS AND IMPLEMENTATION

The Solis simulation engine uses the drift-diffusion model, which is the de facto standard physical model used to describe and calculate the electrical properties of semiconductor devices [START_REF] Selberherr | Analysis and simulation of semiconductor devices[END_REF]. Solis implements both the coupled Newton method and the decoupled Gummel method to solve the model equations.

A. Drift-diffusion model

The drift-diffusion model is composed of the Poisson equation and the two current continuity equations, as shown in onedimensional z and normalized form in Eq. 1. The normalization factor in the Poisson equation is taken to be equal to unity, using the Debye length as the position normalization parameter.

d dz ε(z) dV (z) dz + P(z) = n(z) -p(z) + N - A (z) -N + D (z) + ∑ t N - tA (z) -∑ t N + tD (z) dJ n dz = -GR(z)/γ 2 dJ p dz = +GR(z)/γ 2 J n (z) = -n(z)µ n dφ n (z) dz J p (z) = +p(z)µ p dφ p (z) dz (1)
with the electrostatic potential V, the spontaneous and piezoelectric polarization P (if any), the permittivity ε, the free electron concentration n, the free hole concentration p, the ionized donor N + D and ionized acceptor N - A concentration, and the ionized donor-N + tD and acceptor-like trap N - tA concentration. The concentrations can vary with the position coordinate z. J n and J p are the electron and hole currents, and GR the net generation term. γ 2 is a normalization parameter (the continuity factor shown in Table I). µ n and µ p are the electron and hole mobilities, φ n and φ p are the normalized quasi-Fermi levels.

All the parameters in these equations are dimensionless, i.e. normalized, using the normalization parameters defined in Table I. The currents are expressed in terms of quasi-Fermi levels for simplicity, and include both drift and diffusion terms. The net generation term GR(z) includes light-induced carrier generation (photogeneration) and the various recombination phenomena, including nonradiative Shockley-Read-Hall (SRH), radiative and Auger mechanisms.

The electron and hole concentrations are given by

n(z) = n i e (+V (z)+V n (z)-φ n (z)) p(z) = n i e (-V (z)+V p (z)+φ p (z)) (2)
where n i is the intrinsic carrier concentration. V n and V p are the band parameters for heterostructures and nonuniform graded materials (i.e. for homostructures V n = V p = 0). The net generation term GR(z) is expressed as:

Parameter

GR(z) = G(z) -R D (z) -R I (z) -R A (z) G(z) = λ α(λ , z)φ (λ )exp(-α(λ , z)z) dλ R D = β (np -n 2 i ) R I = ∑ t (np -n 2 i ) τ p (n + n i exp(E t -E i )) + τ n (p + n i exp(-E t + E i )) R A = (np -n 2 i ) (C n n +C p p) (3)
where G(z) is the photogeneration rate, R D (z) is the direct (radiative) recombination rate, R I (z) is the SRH recombination rate and R A (z) is the Auger recombination rate. R I (z) account for dopants and traps (where t index stands for trap), each described by an activation energy E t and electron and hole lifetimes τ n and τ p . E i is the intrinsic Fermi level. α(λ ) is the absorption coefficient, varying with the light wavelength λ , and φ the incident light flux. β is the direct recombination coefficient. C n and C p are the Auger coefficients for electrons and holes, respectively.

B. Solving methods and Solis implementation

The drift-diffusion model as defined in Eq. 1 is solved to determine the potential V (z) and the quasi-Fermi levels φ n (z) and φ p (z). The other quantities are then calculated using these fundamental parameters. The Scharfetter-Gummel discretization scheme [START_REF] Scharfetter | [END_REF] is used to ensure the numerical stability needed in this partial differential equation (PDE) system. The discretized PDE system is then solved using two methods implemented in Solis, giving complete flexibility:

• The Gummel iterative decoupled method. In this method, the three equations are solved iteratively until convergence: Starting with initial guess vectors V(z),

φ n (z), and φ p (z), Solis solves the discretized Poisson system, using the Newton-Raphson method and determines the new value of the potential vector V(z), which is then used to solve the electron continuity equation and determine the φ n (z) vector. V(z) and φ n (z) are then used to solve the hole continuity equation to get the φ p (z) vector and the process iterates until convergence. A damping strategy is implemented is Solis to ensure convergence in most cases since this method can converge slowly for problems where the three driftdiffusion equations are highly coupled.

• The Newton method solves the full discretized nonlinear drift-diffusion PDE system simultaneously using the Newton-Raphson method. This method is suitable for highly coupled cases and can converge fast providing that a good starting solution is given. Solis provides a starting point for the solver to speed up the convergence, and can also use the Gummel method to refine the initial guess.

Solis can handle both Dirichlet and Neumann boundary conditions. The device contacts can be nonideal ohmic or rectifying (Schottky). The numerical parameters, such as the starting initial guess, the damping parameter and tolerance, and the boundary conditions, can be set by the user to handle specific structures, even if Solis automatically adapts these parameters for convergence.

As underlined above, Solis has been developed with modularity, versatility, and performance as the main criteria and guidelines. Its general architecture is shown in Fig. 1 and its main components are:

• The simulator driver, soliscomp.exe (or soliscomp under Linux), controlling the simulator engine. The driver and the simulation engine are developed in standard C++ implementing the numerical methods described above and handling the whole simulation process: input file format and device definition, memory management, data input and output and solving procedures. The simulator driver also controls the embedded Lua scripting engine that can be used to implement user-defined physical models and parameters, permitting advanced control of the simulation process. The simulator driver is a command line executable with a device input in a simple and clean text format. It can be easily controlled and automated by any language (and thus the embedded Lua interpreter), giving the user unprecedented flexibility and control over the simulation.

• A graphical device editor, solisdevice.exe (or solisdevice under Linux), implemented in C. This tool provides an easy-to-use graphical frontend to Solis.

• An advanced code editor, solisedit.exe (or solisedit under Linux), implemented in C, to edit the device structure using the straightforward Solis syntax. This editor offers all functionality found in modern editors and can be used as a general code editor. • A data plotter, solisplot.exe (under Windows) or solisplot (under Linux), implemented in C and C++. This tool is used by Solis to plot the simulation results but could also be used as a standalone data plotter.

• An advanced scientific calculator, soliscalc, implemented in C.

The size of the whole Solis distribution, including documentation and examples, is less than 10 MB.

These tools are independent and can be used in a complementary way; For example, solisdevice can be used to perform simulations in a complete graphical environment. To develop a complete simulation framework, with custom physical models and optimization scripts, one can use solisedit to achieve full control over the code. These tools are, by design, compatible; e.g., an input file created with the code editor can be open/modified by the graphical device editor, and vice-versa.

The Solis input format is an easy-to-use plain text format with simple syntax and some useful features such as variable definition and a mathematical parser.

A user manual, describing the underlying physics, the input syntax, the models used, the implementation, and the software tools, is provided with the Solis distribution.

III. AN APPLICATION TO THE STUDY OF CZTS SOLAR CELLS

Next-generation thin-film solar cells face, among other challenges, two critical issues: their overall cost and environmental impact. The overall cost is affected by the lack of abundance of the chemical elements contained in the active layers and the elaboration techniques used to fabricate such solar cells. On the other hand, environmental impact must take into account, for example, the toxicity of the chemical elements used in the elaboration process and the recycling procedure. One of the main compound semiconductors used in the thin-film solar cell technology is copper indium gallium selenide CuIn 1-x Ga x Se 2 (CIGS) with the record efficiency recently reaching 22 % [START_REF] Kamada | New world record Cu(In, Ga)(Se, S) 2 thin film solar cell[END_REF]. While mature, CIGS technology is affected by the use of indium, costly and rare element, that is already widely used in screen manufacturing [START_REF] Woodhouse | Supply-chain dynamics of tellurium, indium and gallium within the context of pv module[END_REF]. Other technologies that are far less mature than CIGS are also affected by their use of indium, e.g., those based on the potentially promising indium gallium nitride (InGaN) alloy [START_REF] Jani | [END_REF]14]. To address this issue, several materials using Earth-abundant and nontoxic elements have been developed. Among these materials, copper zinc tin sulfide Cu 2 ZnSnS 4 (CZTS) alloys (and, to a lesser extent, copper zinc tin selenide Cu 2 ZnSnSe 4 (CZTSe)), are become promising materials for use in thin-film solar cells [START_REF] Jiang | Cu 2 ZnSnS 4 thin film solar cells: present status and future prospects Solar Cells-Research and Application Perspectives[END_REF][START_REF] Wang | [END_REF]. The record photovoltaic efficiency obtained using these new materials, 12.6 % [START_REF] Wang | [END_REF], while below the CIGS efficiency, is higher than that of the well-established amorphous silicon solar cells. CZTS has the potential to reach the CIGS level if some issues can be addressed. Some of these issues are related to phase separation in these complex alloys. The next sections present results for a ZnO/CdS/CZTS solar cell, firstly without phase separation and, secondly, with a phase separation simulated using the capability of Solis to handle arbitrary position-varying physical properties. The basic parameters of CZTS, CdS, and ZnO used in the simulation. E G is the bandgap, χ is the electron affinity, N C and N V are the density of states in the conduction and valence band, respectively, and ε r is the relative permittivity. The direct and Auger recombination parameters are set to β = 10 -12 cm 3 /s and C n = C p = 10 -30 cm 6 /s respectively. The experimental data are taken from [START_REF] Madelung | Semiconductors: data handbook[END_REF][START_REF] Simya | [END_REF]. CZTS absorber, while Fig. 3 plots the band diagram simulated by Solis at thermodynamic equilibrium. Table II presents the basic CZTS, CdS, and ZnO parameters used in the simulations. The CZTS extinction coefficient varies with the the photon energy according to the standard formula in Eq. 4.

E G (eV ) χ(eV ) N C (cm -3 ) N V (cm -3 ) ε r ZnO 3.
k(E) = k o 2E G E E -E G E G 1 2 (4)
where E G is the CZTS bandgap, E the photon energy and k o the extinction coefficient at E = 2 × E G , taken to be equal to 0.2 [17]. The used AM1.5 solar spectrum is the ASTM G173-03 reference spectrum taken from NREL [START_REF]Reference Solar Spectral Irradiance[END_REF].

Figure 4 shows the current-voltage characteristic of the homogeneous CZTS solar cell obtained using Solis and that simulated using the Atlas R tool from Silvaco R . The obtained photovoltaic efficiency of ≈ 19.2 % is close to the highest reported value for a CIGS solar cell [START_REF] Kamada | New world record Cu(In, Ga)(Se, S) 2 thin film solar cell[END_REF] and highlights the potential of this alloy as an alternative to CIGS. Further optimization, taking the doping and thickness values as param- III. The photovoltaic performance obtained using Solis and Atlas R for the single-phase CZTS solar cell illuminated with an integrated AM1.5 power of 0.099271 W/cm 2 . η is the efficiency, J SC the short-circuit current, V OC the open-circuit voltage and FF the fill factor. eters, would give the absolute optimum efficiency using, for example, the method presented in Ref. [START_REF] Saad Hamady | [END_REF]. Another issue with the CZTS solar cell structure is the use of CdS, which contains cadmium. This could be replaced with In 2 S 3 [22] or, more consistently, with ZnS [23], containing Eath-abundant elements.

η (%) J SC (A/cm 2 ) V OC (V) FF (%) Solis

B. The multiple-phase CZTS solar cell

In the complex CZTS quaternary alloy, phase separation is usually observed, with evidence of two phases: ZnS and Cu 2 SnS 3 , in addition to the Cu 2 ZnSnS 4 phase [24]. The presence of ZnS is also evidenced between the CZTS absorber and the bottom molybdenum contact [25]. The ability of a simulator to handle any position-varying semiconductor parameters is key to the study and evaluation of the impact of phase separation on the performance of the solar cell. Using Solis, one can set any material graded profile, using the embedded scripting language, and simulate the phase separation in CZTS. To capture the real material properties precisely, the profile of the position-varying parameters (bandgap, affinity, permittiv- η (%) J SC (A/cm 2 ) V OC (V) FF (%) R S (Ω.cm 2 ) R P (Ω.cm 2 )

12.53 0.0213 0.777 75.00 2.2 139 TABLE IV: The photovoltaic performance obtained by Solis for the multiple phase CZTS solar cell with ζ = 0.16 when illuminated with an integrated AM1.5 power of 0.099271 W/cm 2 . η is the efficiency, J SC is the short-circuit current, V OC is the open-circuit voltage, FF is the fill factor, R S the series resistance, and R P is the shunt resistance.

ity, density of states, etc.) can be continuous and inspired by experience; For instance, an abrupt square profile can be used, and is in fact equivalent to defining a multilayer structure (or superlattice), but this is not well adapted to a material showing phase separation. A continuous profile with no abrupt changes in the physical parameters is more well adapted to the realistic simulation of multiphase alloys. Such a smoothed profile is modeled here using a periodic inverted Gaussian function, as plotted in Fig. 5. The analysis presented here is limited to the two phases usually observed in this material: Cu 2 ZnSnS 4 with a bandgap of ≈ 1.5 eV, and Cu 2 SnS 3 with a bandgap of ≈ 1 eV. In the chosen profile, the ratio between the Gaussian full width at half maximum (FWHM) and the total period represents the fraction between the secondary Cu 2 SnS 3 phase and the main Cu 2 ZnSnS 4 phase. This ratio ζ is equal to zero for a homogeneous CZTS layer, as presented in Sect. III A, and is now increased up to 0.4.

Figure 6 shows the band diagram simulated by Solis at thermodynamic equilibrium, for the multiple phase CZTS absorber with a phase ratio ζ = 0.16.

The photovoltaic performance obtained by Solis for the multiple phase CZTS solar cell with ζ = 0.16 is presented in Table IV. For comparison, the performance for the homogeneous CZTS absorber is shown in Fig. 4. The phase separation dramatically impacts the efficiency of the solar cell, even for a relatively low ζ ratio, and the efficiency ≈ 12 % found here approaches the experimental record [START_REF] Wang | [END_REF]. To illustrate this behavior, Fig. 7 shows the variation of the photovoltaic efficiency with respect to ζ , the fraction between the secondary Cu 2 SnS 3 phase and the main Cu 2 ZnSnS 4 phase. The efficiency decreases rapidly to reach 11 % for a fraction of 0.4. In this complex heterostructure, with continuously varying CZTS absorber parameters, the change in the electrical field profile causes a decrease in the open-circuit voltage and the accompanying impact on the photogenerated carrier collection decreases the short-circuit current. Other models, including e.g. a random distribution and interface related inhomogeneities, could be used to simulate the effect of phase separation. For more complex structures, a more specific and comprehensive approach, in two dimensions (2D) or even three dimensions (3D), should be used to capture the effect of phase separation in the solar cell absorber more precisely.

IV. CONCLUSIONS

A new modular, portable and high-performance 1D semiconductor device simulator is presented. This free simulator, Solis, is developed in standard C++, runs natively on Windows and Linux and is portable to other platforms. It includes a fast scripting engine permitting the development of custom physical models and excitation parameters with a clean and simple language and simulation input. An application to the study of a CZTS heterostructure solar cell is presented, taking into account phase separation in the absorber, modeled using the capability of Solis to handle arbitrary position-varying pa-rameters. The Solis simulator is continuously updated and will include in the coming release a coherent optical propagation model and the possibility to simulate the admittance spectroscopy characteristic, while the transient simulation functionality will be included if it turns out to be important for emerging photovoltaic technologies. Tunneling through the anode Schottky contact, for Schottky solar cells or detectors, is already implemented and will be included in the next release.

= 10 22 m - 3 Space

 3 Debye length, L = ε 0 kT/(q 2 N) Mobility µ 0 = 0.1 m 2 /Vs Recombination β 0 = 10 -20 m 3 /s Continuity factor γ 2 = µ 0 kT/ β 0 qNL 2

FIG. 2 :

 2 FIG.2:The ZnO/CdS/CZTS solar cell structure. The ZnO and CdS layers are n-doped with a donor concentration of 10 18 cm -3 . The CZTS p-doping concentration is equal to 10 16 cm -3 .

A.FIG. 3 :

 3 Figure2shows the simulated structure with the ZnO window, the CdS buffer layer, and the stoichiometric single-phase

FIG. 4 :

 4 FIG.4: The current-voltage characteristic of the single phase CZTS solar cell under the illumination by the AM1.5 spectrum. The voltage is applied to the top contact of the n-p structure. The symbols indicates the characteristic simulated using Atlas R from Silvaco R , while the straight line shows that simulated by Solis. The photovoltaic performance obtained by Solis and Atlas R is presented in TableIII.

FIG. 5 :

 5 FIG. 5: The periodic inverted Gaussian profile used to model the variation of the bandgap with position in the CZTS alloy based on the Cu 2 SnS 3 / Cu 2 ZnSnS 4 phase separation fraction. The bandgap of Cu 2 ZnSnS 4 is ≈ 1.5 eV, while the bandgap of Cu 2 SnS 3 is ≈ 1 eV. The fraction between the secondary Cu 2 SnS 3 phase and the main Cu 2 ZnSnS 4 phase is ζ = 0.16. The same type of function is used for the other parameters, viz. the affinity, permittivity, and density of states.

FIG. 6 :FIG. 7 :

 67 FIG.6:The ZnO/CdS/CZTS band diagram at thermodynamic equilibrium for the multiple-phase CZTS absorber.

TABLE I :

 I Normalization parameters used for the drift-diffusion model.

  The Schematic Solis architecture. The core part of Solis is entirely coded in standard C++ (the Lua engine being coded in standard C) and is easily portable to almost all operating systems, in addition to the natively supported Windows and Linux systems. The Solis code editor, device editor, and data plotter are developed in C and use the IUP GUI toolkit coded in C [9] and the Scintilla component coded in C++ [10].

	SolisgTools
	SolisgCodegEditorg[C]	SolisDevicegEditorg[C]
	solisedit.exeg(Windows)	solisdevice.exeg(Windows)
	soliseditg(Linux)	solisdeviceg(Linux)
	SolisgDriverg[StandardgC++]	SolisgPlotterg[C/C++]
	soliscomp.exeg(Windows)	solisplot.exeg(Windows)
	soliscompg(Linux)	solisplotg(Linux)
	SolisgCore
	Solisg1DgSemiconductorgDevicegSimulatorg[StandardgC++]
	LuagScriptinggEngineg[StandardgC]
	FIG. 1:

TABLE II :

 II

TABLE III :

 III

For example, the commercial reference simulator Atlas R from Silvaco R includes a C interpreter that can be used to extend it and develop custom physical models.

The latest Solis release (extracted total size less than 10 MB) is available to download: http://www.hamady.org/download/solis windows 64bit.zip (for Windows XP/Vista/7/8/10 64 bit) http://www.hamady.org/download/solis linux 64bit.tgz (for Linux (Debian, CentOS, Ubuntu, etc.) 64 bit). The Solis user manual is also available to download here: http://www.hamady.org/download/solis simulator.pdf

CONFLICT OF INTEREST

The author declares no conflicts of interest.


Ricardo José López
email: ricardo.lopez-dawn@lip6.fr

Anastasios Giovanidis
email: anastasios.giovanidis@lip6.fr

Social Influencer Selection by Budgeted Portfolio Optimization

Influencer marketing has become in the recent years a thriving industry that includes more than 1120 agencies worldwide and with a global market value expected to reach 15 billion dollars by 2022. The advertising problem that such agencies face is the following: given a monetary budget find a set of appropriate influencers on a social platform and recruit them to create a number of posts for the promotion of a certain product. The objective of the campaign is to maximize some impact metric, e.g. the number of impressions, the sales, or the audience reach. In this work, we present an original formulation of the budgeted campaign orchestration problem as a convex program, and further derive a near-optimal algorithm to solve it efficiently. The proposed algorithm has low computational complexity and can scale well for problems with large numbers (millions) of social users, encountered in real-world platforms. We apply our algorithm to a Twitter data set and illustrate the optimal campaign performance for various metrics of interest.

I. INTRODUCTION

In the age of Online Social Platforms (OSPs) 1 , audiences trust contents generated by influential users more than advertisement promoted by the platform itself [START_REF] Mackinnon | User Generated Content vs. Advertising: Do Consumers Trust the Word of Others Over Advertisers?[END_REF]. This can be observed in the social sphere, where brands like Puma [2], advertised their #IgniteXT line through posts created by 61 influencers to promote their line among young public. Another well-known example was Spotify with its #thatsongwhen influencer campaign [3], where, the objective was to increase its new subscribers through posts created by influencers in its favour. Other examples are documented and can be found in different industries as Mattel, Dreamworks, Netflix, etc.

At present, there exist more than 1120 influencer marketing focused agencies, the average earned media value per $1 spent has increased to $5.78 [4], and it is estimated that the influencer marketing industry is on track to be worth up to $15 billion dollars by 2022. Due to the growing relevance and magnitude of this market, a general framework is necessary to determine how to select influencers to create posts in favour of some company that can maximize the objective of the advertising campaign subject to a monetary budget constraint.

The great majority of the objectives in an advertising campaign aims to maximize one of the following metrics [4]:

1) Impressions: The total number of times that the content related to the campaign has been displayed in the Newsfeeds of all users on the OSP. 2) Reach: The total number of different users that found a post related to the campaign in their Newsfeeds. Impressions and reach are ways to quantify the spread of a campaign in an OSP. 3) Engagements: These include the total number of likes, comments and re-posts related to the campaign. This metric captures the interactions received in an advertising campaign. 4) Conversion/Sales: Generally, these metrics quantify the ROI (return on investment) which equals the value received from content shared by an advertising campaign.

Influencers can be divided into three categories, neither exclusive nor exhaustive, based on their dissemination capacity:

• Nano-influencers: These possess small, niche, and highly engaged audience. Nano-influencers have the smallest number of followers, the highest engagement per post, biggest ROI, and they are easier to recruit. • Micro-influencers: These have the characteristics of being strongly connected with their audience, they tend to receive a lot of engagements per post and are costaccessible to businesses of all sizes. • Macro-influencers: These share characteristics such as greater reach than micro-influencers, they have a significantly higher cost per post than the micro-influencers, a wide audience and a higher level of professionalism.

Generally the price per post of influencers varies depending on various characteristics like: the type of the social media platform, the number of followers, the average number of engagements per post, the advertised product, etc. Therefore, nowadays we even have companies that are dedicated to the task of how to price the influential users.

Given a monetary budget over a time period where the campaign is deployed, small and medium-sized companies will search for a basket of influencers to maximize their campaign objective (impressions, engagements, reach). Note here that most influencers will not sell all their posting activity for the promotion of a single company/product, so that they can preserve their personal style and offer variety in posting that keeps on feeding their followers' interest.

A. Related Literature

The most relevant literature about our Budgeted Portfolio Optimization Problem in OSPs is related to the social influence maximization problem introduced by Kempe et al. in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. The elements of this problem are:

• A graph of the social network with the users as the vertex set and social ties among the users as the edge set. • A diffusion process describing how content is diffused among social neighbors over discrete steps. In this context the influencer selection problem is stated as follows: for a given size k, choose at most k users of the social network called the seed set, such that the number of users influenced (reached) is maximized when the diffusion process is over [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. Subsequently, user costs and budgetary restrictions have been introduced [START_REF] Lakhotia | Approximation algorithms for coordinating Ad campaigns on social networks[END_REF], [START_REF] Nguyen | On budgeted influence maximization in social networks[END_REF].

These works result in an NP-hard problem with sub-modular structure that can be sub-optimally solved in polynomial time using greedy approximation algorithms. However, this formulation does not model reality because an influencer does not necessarily attribute his whole activity to the advertising campaign, so it is not sufficient to make a binary decision to include an influencer in the seed set or not. Also, the cost is in reality calculated per post or content produced rather than per recruited user. Furthermore, the knowledge of a model for the dissemination of information in the OSPs is generally not available. Finally, information about the post impressions and engagements can be measured and collected, so there are available data sets available that track the campaign results and the detailed mutual influence between social users.

B. Our Contribution

In this work, we introduce a new formulation of the budgeted portfolio optimization problem of OSPs, which aims to find the participation ratio of each user in the campaign acquired by the advertiser that maximizes the campaign objective under budget restrictions. Our formulation takes advantage of the known user activity over a time period, the cost per post of each influencer and the information availability over previously collected data about impressions and user interactions in general. The participation ratio per user is the proportion of user generated posts in favour of the campaign during its realisation. The main differences between our model and Kempe's approach are summarized in the Table I.

To further elaborate on the differences in Table I, in [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] the work concerns the spread of a single post, the knowledge of the diffusion process is necessary and the user selection is binary. On the other hand, in our model the spread of influence is achieved by posting over time, the knowledge of the number of impressions from each source to any other user Newsfeed should be known, and we search for a continuous rate per user.

The formulation of the budgeted portfolio optimization problem of OSPs as well as some further assumptions are provided in Section II. In Section III, we develop two algorithms, one for linear and another for concave objective functions that can solve three particular cases of campaign objective:

Influence Maximization [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF] Our Impressions/Engagements: This case arrives when we consider the advertiser's campaign objective as linear. The optimal solution can be found by a greedy algorithm with computational complexity of order O(max((N -1) log(N -1), D)) where N -1 is the number of users minus the advertiser and D ≤ (N -1) 2 is the total number of pairs of users who create content and appear in other users' Newsfeeds/Walls. Hence the solution scales well with the number of users.

Conversion/Sales: Under the assumption that the purchasing propensity of users (or the ROI) varies depending on their exposure to product related content, we study campaign objectives that are monotone increasing and concave with respect to user impressions i.e. functions that exhibit diminishing returns. To achieve near-optimal solution, we propose an iterative greedy algorithm with complexity O(max((N -1) log(N -1), D)) per iteration. For illustration, we work with the αfairness utility family. A special case is proportional fairness with sum of logarithmic utility functions as objective.

Reach: Another special case of α-fairness is when α tends to infinity, which gives a Max-Min fairness solution. We can maximize the Reach by selecting such specific utility because its solution maximises the number of selected influencers who receive non-zero participation ratio.

In Section IV, the algorithm performance is evaluated on a real data-trace from Twitter and finally, conclusions are drawn in section V. The code is available in [12].

II. THE BUDGETED PORTFOLIO OPTIMIZATION PROBLEM

Let us first describe a generic social network platform, such as Facebook or Twitter. A set of users generate and share some content, denoted as posts, through the platform. Each user has a list of followers and a list of leaders. A user can simultaneously be follower and/or leader of others. As a follower, he (she) is interested in the content posted by his (her) leaders. With each user a Newsfeed is associated, which is a list of received posts.

At each specific point in time, a user sees in his (her) Newsfeed posts originated by other users who may or may not be their direct leaders, the number of these posts seen represents the impressions on him (her) and the impression ratio is the ratio of the impressions originated by some given user over all impressions in a given snapshot. The average ratio over several snapshots is called the average impression ratio in the time window.

We consider a constant number N of active users in a specific time window, forming the set N . Users are labelled by an index n = 1, ..., N . We denote by λ (n) [posts/time window] the rate with which user n generates new posts, and we make the assumption that content posted instantaneously appears on the Newsfeeds of his followers and is further propagated through the social network. For all users n ∈ N we suppose that they preserve their post rate λ (n) constant in the timewindow.

Let us denote by p

(j)
n the average impression ratio of posts that originate from user n in the Newsfeed of user j. This quantity p (j) n is assumed known for the rest of the article and can be measured or estimated in two ways: Empirically, by taking multiple Newsfeed snapshots in the time window and calculating the average of the ratio of impressions between pairs of users over those time points. Alternatively, through Markovian analysis. If we have complete knowledge of the social graph and user posting activity, we can derive p (j) n using the Markovian diffusion model introduced in [START_REF] Giovanidis | Performance analysis of online social platforms[END_REF].

Naturally, our average impression ratios satisfy:

n∈N p (j) n = 1, ∀j ∈ N . (1)
Our model does not require explicit knowledge of the list of followers and leaders of each user, nor a diffusion process as in the approach by Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF]. However, it does require knowledge over the average impression ratio, that contains all this information resulting from diffusion. Furthermore, we are interested in studying the relative impact between pairs of users and not the absolute impact, since the Walls and Newsfeeds can vary in size between users.

Note here that in Instagram and other OSPs, due to the lack of a re-posting option the propagation of information is only given to the immediate followers of a user, thus hindering post-propagation. These networks are simpler to describe; the user sets form a bipartite graph (leaders/followers).

A. The budgeted portfolio optimization problem

In the budgeted portfolio optimization problem an advertiser i ∈ N with a certain monetary budget B [EUR/time window] in his (her) disposal orchestrates an advertising campaign in a unit of time (equal to the time window) by investing on other users to create posts in his (her) favour. The aim is to maximize some impact metric, e.g. the number of impressions, the sales, or the audience reach.

We suppose that for each user n = i there is an associated cost per post c n [EUR/post] so that the user n will be willing to create posts in favor of the advertiser i.

In order to formulate this optimisation problem, we need to quantify the participation of each user n in the campaign of the advertiser i. Hence, we define for each user n = i, the continuous participation ratio a n ∈ [0, 1] in the campaign as the unknown proportion of user n's generated posts acquired by the advertiser i in the unit of time. We fix a i = 1 meaning that the advertiser always posts to promote its own product. Then, a n λ n [posts/time window] represents the number of posts that the user n creates in favor of the advertiser i.

Similarly, we define by p

(j)
n (a n ) the campaign-related impression ratio as the average value of the impression ratio in the Newsfeed of user j originating from user n and related to the campaign of the advertiser i. The campaign-related impression ratio can be similarly estimated and measured as above and satisfies:

p (j) n (a n ) ≤ p (j) n ∀n, j ∈ N . (2)
The empirical probability that an impression reaching user j is related to the campaign is called the potential of user j:

ω (j) (a) = n∈N \{j} p (j) n (a n ) ≤ 1. (3)
In the above a = (a 1 , ..., a N ) T is the participation vector of all the users into the advertising campaigns of user i.

We introduce a utility function U j for each user j that maps the potential of user j, ω (j) , to the campaign objective of the advertiser i. Different expressions for U j model different performance metrics.

The budget invested to user n = i by the advertiser i is

B n (a n ) = c n a n λ (n) [EUR/
U j (ω (j) (a)), s.t. n∈N \{i} c n a n λ (n) ≤ B,
[BPO]

a i = 1, 0 ≤ a n ≤ 1, ∀n ∈ N .

B. Variations and extensions

The above formulation allows us to to introduce further extensions of our model: 1) We can consider that certain users want to sell no more than a certain ratio of their posts a n ≤ r n ≤ 1, ∀n. 2) Another variation is by introducing a set of posting categories to every user ς n and to activate an influenceraudience member pair (n, j), only when the two users share some common interests. In this case the potential of influencer n is expressed as:

ω (j) (a) = n∈N \{j} p (j) n (a n )I ςn∩ςj =∅ ,
with ς n ⊂ {1, ..., Number of categories} the hobbies or interests of user n and similarly for ς j .

C. Assumption on ad propagation and impact metrics

An assumption for the rest of the article is that we consider a linear propagation for the posts related to the campaign and seen on the Newsfeeds, namely:

p (j) n (a n ) = a n p (j) n . (4)
This is reasonable because if the user j is an immediate follower of influencer n, and all posts from the influencer appear on his Newsfeed, then a percentage a n will be related to the campaign. This is actually the case for platforms without sharing, like Instagram, but for other platforms, impressions could arrive through sharing of content from intermediate users. Then, the above linear expression implies that a post from j is shared randomly, independent of its content, which of course is not true. We will use however the linear assumption as a reasonable approximation to the campaign diffusion process for any platform, because we lack of any prior information related to how users might react to the campaign's posts. So, for the rest of the article, the potential of the user j is expressed as:

ω (j) (a) = n∈N \{j} a n p (j)
n .

(

) 5
The utility function U j in [BPO] of the user j, represents from a modeling point of view the following:

• Impressions/Engagements: In this case, the objective function for each user is a linear function. This translates as follows: an increase in the impression potential of a user j results in a proportional increase in their utility. • Conversion/Sales: The α-fairness utility function models diminishing returns over the potential of each user j. As the amount of one participation ratio increases, then after some point the marginal conversion/sales (extra output gained by adding an extra unit) decreases. We will use the logarithmic function in particular to measure Sales. • Reach: We model this case by applying user-specific thresholds j for each user j. If the user j sees more than the threshold j campaign-related impression ratio ω (j) (a), then the user j is consider to be reached by the campaign:

U j (ω (j) (a)) = I ω (j) (a)> j . (6)
Hence, under the assumption of a linear propagation model and activity constraints {r n } n =i we have the formulation of the budgeted portfolio optimization problem in OSPs for various objectives (corresponding to impact metrics):

max {an} n =i j∈N \{i} U j ( n∈N \{j} [a n p (j) n ]), s.t. n∈N \{i} c n a n λ (n) ≤ B, [BPO-G] a i = r i , 0 ≤ a n ≤ r n , ∀n ∈ N .

D. Feasibility set

For increasing utility functions the budget constraint is satisfied with equality at the optimal solution. So, the feasible set S in [BPO-G] is reduced to:

S = {(a n ) n =i ∈ R N -1 : n∈N \{i} c n a n λ (n) = B, ∀n ∈ N \ {i}, 0 ≤ a n ≤ r n }. (7)
Note that the feasible set has dimension N -1, excluding the advertiser who always gets a * i = 1. We denote by E(S) the set of extreme points of S.

In Figure 1, we show one example of a campaign in a network of four users with advertiser user #4 (not included in the figure since always a * #4 = 1) accompanied by a unitary budget B = 1 and three users #1, 2, 3 with unitary activity restrictions a n ∈ [0, 1] and total costs (c 1 λ (1) , c 2 λ (2) , c 3 λ (3) ) = ( 1 2 , 1 2 , 1) respectively. Hence, the set S is the blue plane segmenting the brown cube and the extreme points E(S) are the points M = (0, 0, 1), L = (1, 0, 1 2 ), C = (1, 1, 0), and K = (0, 1, 1 2 ). Observe that these points (allocation vectors) have coordinates with specific structure: for each point, all its coordinates are binary {0, 1} except at most one entry which can be in (0, 1). This observation is a general attribute of E(S) as we prove below.

Proposition 1. (i) Let (a n ) n =i ∈ E(S) be an extreme point of S in [BPO-G],
then it satisfies the next property: there exists at most one j ∈ N \ {i} such that a j ∈ (0, r j ) and ∀l ∈ N \ {i, j}, a l ∈ {0, r l }. Conversely, any point {a n } n =i ∈ S that satisfies this property is an extreme point. (ii) Furthermore, a global maximizer in [BPO-G] can be written as a convex combination of points satisfying this attribute.

Proof. (i) The feasible set S is a convex polytope, defined by the intersection of a hyper-plane (from the budget equality) with an (N -1)-dimensional hyper-cube (from the range of participation ratios). Each extreme point of S, (a n ) n =i ∈ E(S) lies on an edge (or vertex) of the hyper-cube. The points at each edge of the cube have all dimensions either 0 or 1 except one dimension varying in [0, 1]. So the extreme point of S will also share this property. Conversely, consider a point (a n ) n =i ∈ S satisfying this property. Such point cannot be written as a convex combination of two other points s 1 , s 2 ∈ S: to see this θs 1,n + (1 -θ)s 2,n = a n , for n = i, and θ ∈ (0, 1). Then, a n = 1 ⇒ s 1,n = s 2,n = 1 and a n = 0 ⇒ s 1,n = s 2,n = 0, hence all coordinates of points s 1 , s 2 ∈ S are equal to those of (a n ) n =i ∈ S, except in dimension j. This means that s 1 , s 2 , (a n ) lie on the same edge of the hyper-cube, which is impossible by construction.

(ii) A global maximizer of [BPO-G] is necessarily in S. A point in S can be written as a convex combination of the extreme points E(S), because S is a compact convex subset of R N -1 , and therefore S can be expressed as the convex hull of its extreme points [START_REF] Narici | Topological vector spaces[END_REF].

We can explicitly determine the extreme points in the set E(S) of the feasible set S as follows: for every permutation {i n } of the user set, we pick sequentially one user after the other in order and allocate full budget a in = r in to the i nth user based on the permutation order, until the budget B is completely consumed. Hence, only the last allocated user i s can get allocated a ratio a is ∈ (0, 1). All user with indices larger than i s will get 0 ratio.

III. SOLUTION TO THE ADVERTISER'S CAMPAIGN

In this section we present the optimization problem, for linear and concave utility functions and in each case, we present specific algorithms to solve [BPO-G]. The above properties of the feasible set and Proposition 1 will be used here to propose low-complexity fast algorithms for both cases. Notation and parameters are summarized in Table II

TABLE II ELEMENTS OF OUR PROBLEM AND NOTATION

A. Linear utility function

In this case, U j (ω (j) (a)) = ω (j) (a). Therefore, solving this problem is equivalent to maximizing the Impressions/Engagements as campaign objective. By defining φ n = j∈N \{n,i} p (j) n , ∀n ∈ N \ {i}, and φ i = j∈N \{i} p (j) i , we express our objective function as:

j∈N \{i} ( n∈N \{j} [p (j) n a n ]) = n∈N \{i} (a n φ n ) + a i φ i .
The global optimum of the linear optimization problem is an extreme point (a * n ) ∈ E(S) and can be found by a greedy algorithm as follows:

The users {i k } k=1,...,N -1 are indexed by decreasing order by their φ i k per EUR, { φn cnλ (n) } n =i . Hence, the user i 1 generates the largest cumulative impressions per EUR, the user i k generates the k-th maximal number of cumulative impressions per EUR and so on. Define the marginal budget of user i l as B l = B -k<l a i k c i k λ (i k ) , B 1 = B, and let us define ∀l ∈ {1, ..., N -1}:

a * i l = r i l I ci l ri l λ (i l ) ≤B l + B l c i l λ (i l ) I ci l ri l λ (i l ) >B l .
Then, by construction l<N a * i l c i l λ (i l ) ≤ B and {a * n } n =i is an optimal vector for our portfolio optimization problem and an extreme point in E(S).

Note that if ∃n 1 , n 2 = i with

φn 1 cn 1 λ (n 1 ) = φn 2
cn 2 λ (n 2 ) , then our optimum may not be the only optimum, but it is unique modulo permutations of the set with equal elements φn cnλ (n) . Notice that this algorithm has a computational complexity of order O(max((N -1) log(N -1), D)) where D is the number of non-zero average impression ratios between pairs of users (using merge sort to order the set { φn cnλ (n) } n =i ). Therefore, it is a good algorithm to use in large data sets.

B. Concave utility function

In this subsection, we solve the general case [BPO-G]. Before moving on to the general algorithmic solution, we mention that as particular choices of concave utility functions, we could consider the α-fairness family of utility functions [START_REF] Srikant | The Mathematics of Internet Congestion Control[END_REF], [START_REF] Shakkottai | Network optimization and control[END_REF]. This is a general class of utility functions that captures different fairness criteria such as proportional fairness for α → 1 (U j (ω (j) ) = log(ω (j) )) and max-min fairness for α → ∞. It also captures many other fairness criteria that lie between them with a suitable choice of the parameter α ∈ (0, ∞) \ {1}.

U j (ω (j) ) = γ j (1 + ω (j) ) 1-α 1 -α . (8)
Here, γ j ∈ R is a given weight that we will assume unitary in the absence of information. From a modeling perspective, the case α → 1 can maximise Sales, if these are modeled as a logarithmic function of impressions, and the case α → ∞ can maximise Reach, i.e. the users who can receive an impression related to the campaign. Note that U j is strictly increasing in ω (j) (a), then [BPO-G] is equivalent to:

max {an} n =i j∈N \{i} U j (ω (j) ), s.t. 0 ≤ ω (j) ≤ n∈N \{j} [a n p (j) n ], ∀j ∈ N \ {i}, n∈N \{i} (c n a n λ (n) ) -B = 0, a i = r i , 0 ≤ a n ≤ r n , ∀n ∈ N ,
where ω (j) is an auxiliary variable.

It is common in convex optimization problems to use primal-dual approaches, however since we are interested in developing algorithms for real-world platforms with millions of variables (one variable per user) and millions of constraints (one constraint per user), then the number of primal and dual variables will be enormous and the convergence of primaldual algorithms with such sizes is problematic. Hence, we need to appeal to heuristic solutions that take advantage of the structure of the feasibility set and can well approximate the optimum for very large size of N . The main idea of our algorithm is to greedily select per step an extreme point of S, that maximises the improvement in the objective function and average over all previous selected points.

First we write the Lagrangian function only with respect to the auxiliary {ω (j) } j =i and B budget constraints.

L(a, ω; ν, µ) = j∈N \{i} U j (ω (j) ) + ν(B - n∈N \{i} c n a n λ (n) ) + j∈N \{i} µ j ( n∈N \{j} a n p (j) n -ω (j) ),
We can apply the KKT conditions and solve the primal problem. We get for the ω (j) primal variables and any pair of duals (ν, µ):

∂L ∂ω (j) = U j (ω (j) ) -µ j = 0. (9)
So, since U j (ω (j) ) > 0 for all ω (j) , we get at the optimum:

µ * j = U j (ω (j) * ). (10)
On the other hand, for the a n primal variables:

∂L ∂a n = -νc n λ n + j∈N \{i,n} µ j p (j) n . (11)
Observe that since the activity restrictions [0, r n ] are not considered in the Lagrangian, then we cannot set (11) equal to 0. There are three cases for [START_REF] Narici | Topological vector spaces[END_REF] given a dual pair (ν, µ):

(i) ∂L ∂an (ν, µ) > 0, implies that a * n = r n because the maximum is found for the largest value of a n . (ii) ∂L ∂an (ν, µ) < 0, implies that a * n = 0 because the maximum is found for the smallest value of a n . (iii) ∂L ∂an (ν, µ) = 0, implies a * n ∈ (0, r n ). The above holds also for the optimal dual pair. Hence, we see that given the optimal threshold ν * and the optimal prices µ * , we can decide whether some a * j is 0, or r j , or in-between. From the case (iii) and by [START_REF] Shakkottai | Network optimization and control[END_REF], we observe for some k ∈ N \ {i} that ∂L ∂a k (ν * , µ * ) = 0 if and only if:

ν * = 1 c k λ k j∈N \{i,k} U j (ω (j) * )p (j) k := Q * k , (12)
Altogether, the conditions (10) and (11.i-.iii) along with (12) summarize the KKT conditions. Hence, let us proceed to give an iterative greedy heuristic by using the KKT conditions and the fact that the global optimum can be written as a convex combination of the extreme points by Proposition 1. For this purpose, we introduce the vector ∆ (to be explained latter) which is initialised at step t = 0 as ∆(0) = 0 N -1 , and µ(0) = (µ n (0)) n =i , assigning very large values. Large µ j corresponds to a very small ω (j) close to 0 by [START_REF] Shakkottai | Network optimization and control[END_REF] and the property of diminishing returns for the utility function U j . We update at step t + 1 as follows:

-Step A: Update extreme points. With the µ(t) vector, we calculate for all users n ∈ N \ {i}:

Q n (t + 1) = j∈N \{i,n} µ j (t)p (j) n λ n c n (13)
The threshold ν * splits (refer to (11.i,.ii,.iii)) the user set into those users who get zero participation, those who get maximum, and those with Q * n = ν * , from (12). Then we proceed to order the Q's in decreasing order of value and we store the user indices P er(t + 1) = {i 1 , i 2 , ..., i N -1 } given by the order at step t + 1. The users with highest Q(t + 1) will be much higher than ν * (still unknown). So, let us first choose as participation ratio at step t + 1:

a i1 (t + 1) = r i1 , ..., a is (t + 1) = r is , a is+1 (t + 1) = B - s j=1 c ij λ ij r ij , & a is+2 (t + 1) = 0, ...
i.e. we allocate greedily the budget to the users with highest Q, while satisfying the KKT condition (11.i,.ii,.iii). By construction at each step a(t + 1) ∈ E(S) is an extreme point of S, see Proposition 1. Note that a(t + 1) = (a n (t + 1)) n =i , where n are the original indices.

-Step B: Update Averages. We update ∆(t + 1) using the extreme points obtained until step t + 1 as:

∆(t + 1) = t ∆(t) t + 1 + 1 t + 1 a(t) = 1 t + 1
[a(1) + ... + a(t + 1)],

where ∆(t+1) represents the average of the extreme points found throughout the process, and certainly ∆(t + 1) ∈ S because it is a convex combination of the extreme points which are in S. Intuitively, the algorithm successively over t selects an extreme point based on the KKT conditions in (11.i,.ii.iii) and averages it over the previously selected extreme points.

-Step C: Update ω and µ. For each user j ∈ N \ {i} we calculate ω (j) (t + 1) and µ j (t + 1) in function of the average ∆(t + 1) using the definition (3) and the KKT condition [START_REF] Shakkottai | Network optimization and control[END_REF] respectively:

ω (j) (t + 1) = n∈N \{j} ∆ n (t + 1)p (j) n , (14)
µ j (t + 1) = U j (ω (j) (t + 1)). (15)
-Step D: Stopping criterion. We return as output association a * = ∆(t + 1) when ||∆(t + 1) -∆(t)|| < or || j∈N \{i} U j (∆(t+1))-j∈N \{i} U j (∆(t))|| < or when the maximum number of iterations T is attained.

Notice that at the step t + 1, (14) and (15) guarantees us that the condition (9) of the KKT condition is satisfied and the condition [START_REF] Narici | Topological vector spaces[END_REF] is satisfied because the budgets are allocated to the users following a threshold policy, albeit the value of ν * is unknown. Note in turn that we artificially introduce the average of the extreme points because otherwise the selection of extreme points alone would be unstable and oscillate, whereas it would not allow for a selection of any point inside the feasible set S.

Let us note that our algorithm is greedy, in the sense that it successively chooses per step the maximum direction of growth of the Lagrangian by applying (15) and the allocation in Step A, which follows (11.i,.ii,.iii). Namely, we are proposing a greedy gradient method on the set of extreme points. Due to the use of average update of ∆(t+1) in Step B our algorithm will eventually converge. The convergence to the optimum is not garanteed, but numerical evaluations show that our greedy approach that respects the KKT conditions stepwise performs sufficiently well. Each iteration has computational complexity of order O(max((N -1) log(N -1), D)) and the algorithm converges sub-linearly in a finite number of steps.

In the linear utility case, the greedy algorithm reduces to the one proposed in the previous sub-section and runs in a single iteration with the same computational complexity.

IV. NUMERICAL EVALUATIONS

The aim of this section is to evaluate the performance of our algorithms for various campaign objectives using information from a real large Twitter data trace [13]. This database represents the activity of users on Twitter during the 2018 Russian elections. In particular for our purposes, we use a 4uple per post with the following information obtained from this database: [T weetID, T imeStamp, U serID, RetweetID].

The dataset is described as a list of such 4-uples. Each participating user and Tweet have a unique associated UserID and TweetID respectively. RetweetID represents the TweetID which was retweeted (or -1 if it is a self-post) and TimeStamp is the time that the Tweet was (re)-posted. The entire database spans 57 days and involves 181, 621 different U serIDs. Moreover, there is an average of 3.71 posts, an average of 7 re-posts per user and we find 87, 987 users who have re-posted (shared a post) at least once. These users can be potentially reached by any advertising campaign, since they share content.

From the dataset, we derive the empirical post and re-post rate for every user {λ (n) } n∈N and {µ (n) } n∈N respectively. We can further infer a friendship graph using the relationships of retweets (RetweetID), by drawing a directed edge from leader to follower, each time a user retweets something. We call this a "star" graph due to its shape: it contains 181, 621 nodes, 517, 421 edges with a mean degree of 5.70 followers per user. Among the users, 167, 646 users lack of followers and only 13, 975 users have followers. The latter can be potential influencers and we denote their set by L.

We classify the 13, 975 potential influencers into 3 categories: 7, 512 users have 1 -3 followers and are potentially Nano-influencers; 5, 064 have 4 -34 followers and are potentially Micro-influencers; and 1, 399 have more than 34 followers and are potentially Macro-influencers. Having complete knowledge of the social graph and the posting and re-posting rates, the average impression ratios {p (j) n } n,j∈N and the average engagement ratios {q (j) n } n,j∈N can be estimated by the Markovian method introduced in [START_REF] Giovanidis | Performance analysis of online social platforms[END_REF] (see Section II.A). By definition, the engagements are the shared impressions during the 57 days. We introduce a constant δ := n∈L

|L (n) |(λ (n) +µ (n) ) |L|
equal to the average number of impressions in the Newsfeed seen by some user in the network within a unit of time. In this expression |L (n) | is the number of leaders of user n and L is the set of users in N who are leaders of at least one user.

As a next step, we need to determine the cost per post c n charged to the advertiser user i by user n. On Twitter, it is a common market practice to consider the cost per post of user n as 2 #Followersn 1000 [EUR/post]. Since that our database is of the order of 10 5 users and Twitter is of the order of 10 8 , we will assume a normalization constant in the number of followers of 10 3 , so our cost per post of user n to consider is 2 #Followers n [EUR/post].

For the evaluations we will consider no restrictions on user participation ratios (r n = 1, ∀n ∈ N ) in the absence of information. Finally, we select as advertiser the user with UserID = 2513730044, who has 15 #F ollowers. This user is potentially a Micro-influencer, like many stores that provide services in a certain medium-populated area.

We proceed to solve and to find the optimal solutions a * L , a * Log and a * M of [BPO] according to three functions respectively: Linear function by Algorithm 1, Logarithmic function and Max-min function by Algorithm 2. The stopping criterion in Algorithm 2 is when the number of iterations reaches a maximum equal to 30, or when the infinite norm of solutions between iterations is less than 0.1%. Using these solutions a * ∈ {a * L , a * Log , a * M }, we evaluate the metrics: • Total number of Impressions: δ j∈N \{i} ω (j) (a * ). • Total Sales: j∈N \{i} log(δ ω (j) (a * ) + 1).

• Total Reach:

j∈N \{i} I ω (j) (a * )> with a threshold which denotes when a user has been reached by the campaign. We select two values: = 0 for the upper reference curve, and = δ obtained as the average rate of impressions in the Newsfeed.

• Selected number of Nano-, Micro-, and Macro-influencers: The number of users with a * j = 0. Specifically: those up to 3 followers are Nano-(fewer followers than 60% of users in our database), those with 3 -34 followers are Micro-(more followers than 60% of users but fewer than 90% in our database), and those with more than 34 followers are Macro-(more followers than 90% of users in our database) respectively.

The six plots in Fig. 2 illustrates how the above metrics change with increasing monetary budget per day, for each of the three different campaign objectives (Linear, Logarithmic and Max-min). Note here that Algorithm 2 has sub-linear convergence as empirically observed. More precisely, from Linear objective -This campaign gives the most impressions performance because this metric coincides with the objective. It gives very high sales for large budgets (more than 50[EU R/day]), but has the worst reach performance everywhere independent of . Interestingly, it selects the least number of influencers in all categories, for any budget given.

Logarithmic objective -This campaign gives the best sales performance because this metric coincides with the campaign. Also, very high impressions and a moderate reach performance. It selects more influencers than the linear, in all categories.

Max-min objective -This campaign gives the best audience reach for any given budget and chosen, but performs bad in Sales and impressions. In fact, for a budget > 40K[EU R/day] the campaign can reach all possible users for both values.

For all three objectives, the optimal policy selects mostly Nano-and Micro-influencers in low budgets. Macroinfluencers are selected for larger budgets. In fact, the number of Nano-and Micro-influencers selected increases logarithmically with increasing Budget, whereas the number of Macroinfluencers linearly with the Budget.

V. CONCLUSIONS

In this work, we have presented an original formulation of the budgeted campaign orchestration problem to maximize some impact metric. We have derived a convex program and then a near-optimal algorithm to solve it efficiently. This algorithm has low computational complexity and can scale well for problems with large numbers (millions) of social users, encountered in real-world platforms. We have applied our algorithm to a Twitter data set and illustrate the optimal campaign performance for various metrics of interest.

Fig. 1 .

 1 Fig. 1. Example of extreme points for a specific campaign.

Fig. 2 .

 2 Fig. 2. Metrics across different campaign policies and number of selected influencers across different campaign policies.

Figure 2

 2 Figure 2 we observe the following:Linear objective -This campaign gives the most impressions performance because this metric coincides with the objective. It gives very high sales for large budgets (more than 50[EU R/day]), but has the worst reach performance everywhere independent of . Interestingly, it selects the least number of influencers in all categories, for any budget given.Logarithmic objective -This campaign gives the best sales performance because this metric coincides with the campaign. Also, very high impressions and a moderate reach performance. It selects more influencers than the linear, in all categories.Max-min objective -This campaign gives the best audience reach for any given budget and chosen, but performs bad in Sales and impressions. In fact, for a budget > 40K[EU R/day] the campaign can reach all possible users for both values.For all three objectives, the optimal policy selects mostly Nano-and Micro-influencers in low budgets. Macroinfluencers are selected for larger budgets. In fact, the number of Nano-and Micro-influencers selected increases logarithmically with increasing Budget, whereas the number of Macroinfluencers linearly with the Budget.

  time window] and the total budget of the advertiser i is B [EUR/time window]. Therefore the constraints in our budgeted portfolio optimization problem will be naturally a budget restriction n =i B n (a n ) ≤ B and the continuous unknown variables a n ∈ [0, 1]. Alltogether, we can formulate the general budgeted portfolio optimization problem max {an} n =i

	j∈N \{i}

  :

	Budgeted Portfolio Optimization Problem
	User set		N
	Advertiser		i ∈ N
	Average impression ratios	{p	(j) n } n,j∈N
	Cost per post	{cn} n∈N
	Budget over a time period		B
	Activity restriction (optional)	{rn} n∈N
	User activity	{λ (n) } n∈N
		Objective:
	Campaign objective	j∈N \{i} U j ( n∈N \{j} [anp	(j) n ])
		Return:
	Participation ratio per user	{an} n =i

This work is funded by the ANR (French National Agency of Research) by the "FairEngine" project under grant ANR-19-CE25-0011.


John Maxwell Campbell
email: jmaxwellcampbell@gmail.com

WZ proofs of identities from Chu and Kiliç, with applications

Keywords: Mathematics Subject Classification. 11B65, 11Y60 WZ method, WZ pair, hypergeometric series, binomial coefficient, mathematical constant

WZ proofs of identities from Chu and Kiliç, with applications

INTRODUCTION

The determination of closed-form evaluations of infinite series involving inverted binomial coefficients forms an important aspect about the discipline that is referred to as experimental mathematics [1, §1.7]. As in [1, §1.7], we record the classical series evaluation 3n n 2 n as two prominent and well-known instances of binomial sum evaluations, but this is not to mention Apéry's famously making use of the equality

(1.3) ζ(3) = 5 2 ∞ n=1 (-1) n+1 n 3 2n
n in his unmitigatedly renowned proof of the irrationality of the constant ζ(3), i.e., Apéry's constant; we also find it pertinent to make reference to Ramanujan's work on infinite series containing inverted binomial coefficients, as in with the following formula involving the golden ratio φ [3, §11]:

(1.4) π 2 6 -3 ln 2 (φ) = ∞ n=0
(-1) n 2n n (2n + 1) 2 . In this article, we systematically apply the Wilf-Zeilberger (WZ) method to finite sum identities involving Catalan numbers that were quite recently proved by Chu and Kilic Ŗeceived:

in [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] using special cases of classical identities for infinite hypergeometric series, and we make use of the WZ pairs obtained from our alternate proofs so as to formulate creative telescoping proofs for new and elegant infinite summations that involve inverted binomial coefficients and that can only be expressed via current Computer Algebra System (CAS) software as linear combinations of inevaluable p F q -series. Our new series evaluations are very much inspired by the famous results displayed above, as in (1.1), (1.2), (1.3), and (1.4). For example, consider how our formula

(1.5) π 2 4 = ∞ n=1
16 n (n + 1)(3n + 1)

n(2n + 1) 2 2n n 3
that is introduced in this article bears a resemblance to the above displayed equations, and, on the other hand, considerably extends previously known series formulas involving "non-powered" expressions as in 1

( 2n n )
, in contrast to the cubed, inverted binomial coefficients in (1.5), which, informally, make the symbolic computation of the infinite summation in (1.5) virtually impossible with CAS software: Mathematica is only able to express this summation as a linear combination of inevaluable 4 F 3 1 4 -series, and Maple is only able to express (1.5) as an inevaluable 5 F 4 1 4 -series.

1.1. Background and preliminaries. The famous WZ method [START_REF] Petkovšek | [END_REF] has, of course, been applied widely in number theory, combinatorics, special functions theory, and computer science, not to mention the applications pertaining to the WZ method in the study of manifolds and cell complexes, in convex/discrete geometry, in the study of difference and functional equations, and in many other areas. For the time being, we only review basics about the WZ method that are directly needed for this article.

A function A(n, k) in two variables is hypergeometric if both A(n + 1, k)/A(n, k) and A(n, k + 1)/A(n, k) are rational functions, and a WZ pair is a pair (F, G) of functions such that F and G are two-variable hypergeometric functions that are such that (1.6)

F (n + 1, k) -F (n, k) = G(n, k + 1) -G(n, k),
and we also enforce the conditions whereby lim k→∞ G(n, k) = 0 and G(n, 0) = 0 [START_REF] Petkovšek | [END_REF]. Letting F (n, k) be hypergeometric, the WZ method determines a function G(n, k) such that F and G form a WZ pair, i.e., provided that such an expression G exists [START_REF] Petkovšek | [END_REF]. Summing each side of (1.6) with respect to k, we obtain that:

(1.7) k F (n + 1, k) = k F (n, k).
Summing both sides of the equality in (1.6) over n, we find that

(1.8) ∞ n=0 G(n, k) - ∞ n=0 G(n, k + 1) = F (0, k) -lim n→∞ F (n, k),
i.e., if the above limit exists and if the above series are convergent. As stated in [START_REF] Guillera | A new formula for computing the Catalan constant[END_REF], an important property concerning WZ pairs is the identity whereby

(1.9) ∞ n=0 G(n, 0) = ∞ k=0 F (0, k).
Guillera, in [START_REF] Guillera | A new formula for computing the Catalan constant[END_REF], used this identity, as applied to the WZ pair obtained by setting 3 , so as to obtain the following formula for Catalan's constant:

U (n, k) := (-1) k+n 4 n 2k k k+n k 2k+2n k+n 3 and F (n, k) := U (n, k) n + 2k + 1 (2n + 2k + 1)
(1.10) 2G = ∞ n=0 -2 6 n (4n + 3) (2n + 1) 3 2n n 3 .
This may be written as a linear combination of 4 F 3 (-1)-series. In contrast, we employ extensions of the WZ identity in (1.9) to prove the 5 F 4 1 4 -series identity in (1.5) along with the π 2 formula highlighted in (2.14) below, and we improve upon Guillera's G-formula in (1.10) by proving a new formula for G that also involves inverted central binomial coefficients but that may be expressed as a linear combination of 5 F 4 -1 4 -series and thus converges extremely quickly, especially compared to (1.10). Our new series for G is highlighted in (2.15) below, with a similarly fast-convergent series for Apéry's constant provided in later in this article; for the time being, let us illustrate the extent to which our G-series in (2.15) improves upon Guillera's formula shown in (1.10).

Numerically computing the finite sum we find that (1.10) is so slowly convergent that the second digit after the decimal point of Catalan's constant 0.915965... is not even reached by summing the first ten thousand entries in the sequence given by the summand of (1.10). In contrast, computing

(1.11) - 1 2 - 1 16 8 n=1 -2 8 n 40n 2 + 4n -1 n 2 (4n + 1) 2n n 4n 2n 2 = 0.915901...,
we see that it only takes eight terms to reach four decimal places of accuracy past the decimal point, in our approximating G. Replacing the upper limit of (1.11) with 100, we obtain 58 digits of accuracy to the right of the decimal point; in contrast, computing

1 2 20000 n=0 -2 6 n (4n + 3) (2n + 1) 3 2n n 3 = 0.920887...,
we see that we still do not even obtain two decimal places of accuracy at the twenty thousandth partial sum for (1.10). We are to provide "one-line" WZ proofs as in [START_REF] Petkovšek | [END_REF] for Chu and Kilic ¸'s identities [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF], so it is worthwhile to review what we mean by the concept of a WZ proof certificate. Mimicking notation used in [6, §2.3], suppose that we want to prove an identity as in (1.12)

k summand(n, k) = rhs(n, k),
where the above summand is such that: For all n, the above summand vanishes for all k outside of some finite interval. We then set

F (n, k) := summand(n, k) rhs(n, k) ,
so that the WZ method gives us a rational function R(n, k) such that F and

G(n, k) = R(n, k)F (n, k)
form a WZ pair [6, §2.3]. Recalling (1.7), we find that k F (n, k) is constant, since it is independent of n, so we simply need to check that this constant is 1. So, in other words, simply "having" the function R(n, k) satisfying all of the desired properties to form a WZ pair is a proof, in itself: Just by evaluating such a function R(n, k) that satisfies the aforementioned properties, this, in itself, is a proof for (1.12), so that we may simply present the rational function R(n, k) as a "one-line proof" (cf. [START_REF] Wilf | Rational functions certify combinatorial identities[END_REF][START_REF] Ekhad | A short, elementary, and easy, WZ proof of the Askey-Gasper inequality that was used by de Branges in his proof of the Bieberbach conjecture[END_REF][START_REF] Zeilberger | Identities in search of identity[END_REF]). A particularly famous instance of a one-line WZ proof is that for the famous identity whereby the level-n row sum of Pascal's triangle is 2 n [8], as below.

Proof: R(n, k) = -k 2(n-k+1) .
One-line WZ proofs that dramatically simplify proofs for Catalan number identities recently due to Chu and Kilic ¸are given below, in Section 2, and applied using extensions of (1.9) in the manner outlined above. However, before we move onto our main proofs/results, it is necessary to recall two basic properties concerning the famous function

Γ(x) = ∞ 0 u x-1 e -u du
known as the Γ-function. In particular, we are to later make use of the famous reflection formula Γ(x)Γ(1 -x) = π sin(πx) .

along with the the Legendre duplication formula:

Γ k + 1 2 = √ π 1 4 k 2k k Γ(k + 1).

MAIN PROOFS AND RESULTS

Letting C m = 2m m /(m + 1) denote the m th entry in the sequence of Catalan numnbers, part (a) of Theorem 1 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] gives us that the identity whereby

n k=0 2n 2k C k C n-k = C n C n+1 holds for n ∈ N 0 ,
and this is proved in a direct way through an application of Gauss' summation theorem, i.e., by writing C n times

2 F 1 -n, -n -1 2 1
as the finite sum under consideration, and by then writing this 2 F 1 (1)-expression as a quotient of Γ-expressions. We offer, as below, a one-line proof for the convolution-type identity under consideration, and we then apply the WZ pair associated with this summation identity to prove the remarkable 5 F 4 1 4 -series evaluation highlighted as a motivating example in (1.5).

Theorem 2.1. Part (a) of Theorem 1 from [2] holds. Proof. R(n, k) = k(2k-3n-5)(k+1) 2(2n+3)(k-n-2)(k-n-1) .
We proceed to make use of an extension of (1.9), as applied to the WZ pair given by our proof of Theorem 2.1. More explicitly, this WZ pair is such that

F (n, k) := (n + 1)(n + 2) 2k k 2n 2k 2(n-k) n-k (k + 1) 2n n 2n+2 n+1 (-k + n + 1)
, with G(n, k) = R(n, k)F (n, k). This leads us to the below proof.

Theorem 2.2. The closed-form evaluation in (1.5), as reproduced below, must hold:

π 2 4 = ∞ n=0
16 n (n + 1)(3n + 1)

n(2n + 1) 2 2n n 3 .
Proof. Letting (F, G) denote the WZ pair indicated above, it is easily seen that

lim a→∞ F (a, b) = 0
for all b. So, in view of the WZ identity in (1.8), we may easily establish that

-F (0, b) = ∞ n=0 (G(n, b + 1) -G(n, b))
for suitably bounded real b. Setting the variable b to be equal to r, r + 1, r + 2, etc., and then adding the resultant identities, so as to form a telescoping sum of infinite series, we can show that (2.13)

m n=0 -F (0, b + n) = ∞ n=0 (G(n, b + m + 1) -G(n, b))
for nonnegative integers m. Since G(n, 0) = 0, we see that

∞ n=0 G(n, b + m + 1) - m n=0 -F (0, b + n)
vanishes as b → 0. According to the reflection formula for the Γ-function, this gives us that:

∞ n=0 G(n, b + m + 1) approaches 2 b 2 + b + 1 sin 2 (πb) π 2 b 2 (b + 1) 2 (b 2 + b -2) as b → 0. This is easily seen to give us that lim c→∞ ∞ n=0 G(n, c) = -1
for real c. So, this leads us, according to (2.13), to the following, for real b, giving us an extension of (1.9):

∞ n=0 -F (0, b + n) = -1 + ∞ n=0 -G(n, b).
In particular, setting b = 1 2 and applying the reflection formula, this gives us that

∞ n=0 16 cos 2 (πn) π 2 (2n -1)(2n + 1) 2 (2n + 3) equals -1 + ∞ n=0 2 -2n-3 (n + 1)(3n + 4)Γ 2 (n + 1)Γ(n + 3) √ πΓ n + 3 2 Γ 2 n + 5 2 .
Evaluating this second-to-last infinite series as -1 2 only involves basic calculus. Rewriting the summand for this latter series according to the Legendre duplication formula, this gives us that:

π 2 256 = ∞ n=0 2 4n (3n + 4) (n + 1)(n + 2) 2n+2 n+1 2n+4 n+2
2 .

The desired result then easily follows by applying an index shift.

We find that the evaluation in the above theorem is equivalent to the following 5 F 4 1 4series evaluation:

9π 2 64 = 5 F 4 1, 1, 2, 7 3 , 3 4 3 , 3 2 , 5 2 , 5 2 1 4 .
There is not much known about q+1 F q 1 4 -series, especially for higher-order values q, motivating our interest in the above formula.

Part (b) of Theorem 1 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] states that n k=0 (-1) k n+k 2k kC k equals (-1) n , and this is proved using the Gauss summation theorem. Instead of using this classical hypergeometric identity, we present the following one-line WZ proof. Proof. R(n, k) = 2(n+1)(k-1)(k+1) (n-k+1)n(n+2) . The techniques that we had used in our proof of Theorem 2.2 cannot be applied to the WZ pair corresponding to the above theorem, since the limit of F (a, b) as a → ∞ is not, in general, finite. So we move onto part (c) of Theorem 1 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] holds, which states that n k=0 2n n+k n+k 2k C k equals 2n+1 n C n . Again, the Gauss summation identity is used in [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] to establish this result, in contrast to our one-line proof below.

Theorem 2.4. Part (c) of Theorem 1 from [2] holds. Proof. R(n, k) = k(2kn-3n 2 +3k-8n-5)(k+1) 2(k-n-1) 2 (2n+3)(n+1)
.

Letting (F, G) denote the WZ pair associated with our proof of the above theorem, we can, using exactly the same approach as in our proof of Theorem 2.2, show that

∞ n=0 -F (0, r + n) = -1 + ∞ n=0 -G(n,
-3 + k - 2 * n) * (-2 + k -2 * n)ˆ3 * (-1 + k -2 * n)ˆ2 * (2 + 3 * n) * (4 + 3 * n))
By mimicking our proof of Theorem 2.2, as applied to the WZ pair corresponding to the above theorem, we may prove the remarkable result below; for the sake of brevity, we leave this to the reader. Mathematica is only able to evaluate the above series as a linear combination of inevaluable 9 F 8 -1 27 -series, and similarly for Maple. Again, for the sake of brevity, we refer the reader to [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] for the Catalan sum identity referred to below. .

In this case, m n=0 (G(n, r + 1) -G(n, r)) does not converge, so it is unclear as to how to go about mimicking our proof of Theorem 2.2.

A number of the results given within the Theorems from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] are not proved in this article, since the WZ method does not seem to apply in these cases with readily available implementations of the WZ method, e.g., through Maple's SumTools[Hypergeometric] subpackage. We encourage extending our results using these "leftover cases" and extending the results given in this paper using variants/generalizations of our WZ pairs.

Theorem 2 . 3 .

 23 Part (b) of Theorem 1 from [2] holds.

  12 ) n 7168n 5 -1664n 4 -1328n 3 + 212n 2 + 49n -9 n 4 (2n -1)(3n + 1)(4n + 1)

Theorem 2 . 8 .

 28 The first case for part (b) of Theorem 3 from [2] holds.Proof. R(n, k) = k(2k-1)(4k 2 n+8k 2 -24kn 2 -64kn-32k+32n 3 +120n 2 +118n+33) 2(n+2)(2n-3)(2k-4n-3)(2k-4n-1)(k-2n-1)

Again, Mathematica is only able to evaluate the above series as a linear combination of inevaluable 4 F 3 1 4 -series. Maple is only able to evaluate the above series as a 6 F 5 1 4series that contains non-rational parameters.

Part (d) of Theorem 1 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] gives us that

We proceed to offer the following one-line WZ proof of this result.

Letting (F, G) denote the WZ pair corresponding to the above proof, we again have that

for real r. Setting r = 1 2 and applying reindexing, this gives us another proof of (2.14). We move on to Theorem 2 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF], which leads us to a proof for our remarkable Gseries discussed in Section 1.1 . Part (a) of Theorem 2 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] states that k=0

if is even, and that this finite sum vanishes otherwise. This is proved in [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] using the Kummer summation theorem together with limiting properties about the Γ-function. In contrast, setting = 2n, we may obtain a one-line proof for the non-vanishing case for the finite sum identity under consideration.

Theorem 2.6. The first case for part (a) of Theorem 2 from [2] holds.

We let (F, G) denote the WZ pair corresponding to the above proof, giving us that

and, by letting m → ∞, we may apply almost exactly the same approach as in our proof of Theorem 2.2 to prove that:

2 .

We now turn our attention toward Theorem 3 from [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF]. Part (a) of this Theorem states that k=0 (-1)

C C /2 if is even, and that this finite sum vanishes otherwise. This is proved in [START_REF] Chu | Binomial sums involving Catalan numbers[END_REF] by expressing this finite sum as a 3 F 2 -series, and by then applying Dixon's theorem and limiting properties about the Γfunction. In contrast, for the non-vanishing case, we may obtain the one-line proof below. Proof. The proof certificate, in this case, is given by the following verbatim output.