Fairness Driven Slot Allocation Problem in Billboard Advertisement
Dildar Ali, Suman Banerjee, Shweta Jain, Yamuna Prasad · 2025
Read Fairness Driven Slot Allocation Problem in Billboard Advertisement by Dildar Ali, Suman Banerjee, Shweta Jain, Yamuna Prasad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-05851.txt.
Introduction
Dildar Ali, Suman Banerjee, Shweta Jain, and Yamuna Prasad tackle how to share digital billboard time fairly among advertisers, in this 2025 paper. A provider owns many screens, and each advertiser pays for a set number of views of its ads. Earlier work on this sharing problem chased total value and ignored whether the split was just.
The authors adopt a fairness rule that lifts the worst off advertiser as high as possible, so no one is starved while others feast. Their method builds an allocation and comes with a guarantee on how close it gets to the best fair share, plus an analysis of its running time and memory. Tests on real movement and billboard data show balanced splits that still keep advertisers' total value high.
Catalog record
| CREATOR | Dildar Ali, Suman Banerjee, Shweta Jain, Yamuna Prasad |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-05851
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fairness Driven Slot Allocation Problem in Billboard Advertisement Thanks: This work is supported by the Start-Up Research Grant provided by the Indian Institute of Technology Jammu, India (Grant No.: SG100047). Dildar Ali, Suman Banerjee, Shweta Jain, Yamuna Prasad Abstract In billboard advertisement , a number of digital billboards are owned by an influence provider , and several commercial houses (which we call advertisers) approach the influence provider for a specific number of views of their advertisement content on a payment basis. Though the billboard slot allocation problem has been studied in the literature, this problem still needs to be addressed from a fairness point of view. In this paper, we introduce the Fair Billboard Slot Allocation Problem, where the objective is to allocate a given set of billboard slots among a group of advertisers based on their demands fairly and efficiently. As fairness criteria, we consider the maximin fair share , which ensures that each advertiser will receive a subset of slots that maximizes the minimum share for all the advertisers. We have proposed a solution approach that generates an allocation and provides an approximate maximum fair share. The proposed methodology has been analyzed to understand its time and space requirements and a performance guarantee. It has been implemented with real-world trajectory and billboard datasets, and the results have been reported. The results show that the proposed approach leads to a balanced allocation by satisfying the maximin fairness criteria. At the same time, it maximizes the utility of advertisers. 1 Introduction In recent years, Billboard Advertisement has emerged as an effective out-of-home advertisement technique. Many commercial houses have adopted this mode of advertisement due to its guaranteed return on investment. In a billboard advertisement, there is an influence provider who owns a set of digital billboards, and a set of advertisers approaches the influence provider for a specific amount of influence on a payment basis. A few computational problems have been studied in the context of billboard advertisements, and in particular, there are two study directions. The first one concerns giving a billboard database; how can we find a limited number of influential billboard slots? The proposed solution methodologies include a modified greedy approach proposed by Zhang et al. [ 8 ] , a branch and bound approach proposed by Zhang et al. [ 10 ] , a divide and conquer approach proposed by Wang et al. [ 7 ] , Pruned Submodularity Graph-based approach, Spatial Clustering based approach proposed by Ali et al. [ 1 ] The other direction of research aims to minimize the regret while allocating the billboard slots among the multiple advertisers. The proposed solution methodologies for the regret minimization problem include several local search-based techniques proposed by Zhang et al. [ 11 ] , Budget Effective Greedy and Randomized Greedy approaches proposed by Ali et al. [ 3 ] , and many more. Counter Example 1. Consider an influence provider have six billboard slots \mathcal{U}=\{bs_{1},bs_{2},bs_{3},bs_{4},bs_{5},bs_{6}\} and four advertisers \mathcal{A}=\{a_{1},a_{2},a_{3},a_{4}\} as reported in Table 3 and 3 . Now, the advertisers approach the influence provider with their required influence demand and the corresponding budget shown in Table 3 . Next, the influence provider’s goal is to allocate billboard slots to the advertisers and assume it follows the order be (a_{1},a_{2},a_{3},a_{4}) for allocation. Hence, the influence provider will get full payment from the advertiser a_{1} and a_{2} and from the advertiser a_{3} ; a partial payment will be made due to some penalty for not fulfilling required influence demand i,e., \mathcal{I}(\pi_{a_{3}})<\sigma_{a_{3}} . However, in the case of advertiser a_{4} , no billboard slots remain to allocate from the influence provider side and allocation of a_{4} , i.e., \pi_{a_{4}} is empty as shown in Table 3 . \mathcal{BS}_{i} bs_{1} bs_{2} bs_{3} bs_{4} bs_{5} bs_{6} \mathcal{I}(bs_{i}) 2 6 3 7 1 1 Cost $4 $12 $6 $14 $2 $2 Table 1: Billboard Info. Advertiser( \mathcal{A} ) a_{1} a_{2} a_{3} a_{4} Demand( I_{i} ) 5 7 8 3 Budget( L_{i} ) $15 $15 $17 $6 Table 2: Advertiser Info. \mathcal{A} a_{1} a_{2} a_{3} a_{4} \mathcal{BS}_{i} bs_{2} bs_{4} bs_{1},bs_{3},bs_{5},bs_{6} - \mathcal{I}(\mathcal{BS}_{i})-I_{i} 1 0 -1 0 Satisfied Yes Yes No No Table 3: Billboard Slot Allotment. The proposed solution approaches in the existing literature will return an allocation of slots. However, this allocation may not always be practically usable. Consider the example described in Example 1 containing the billboard database, advertiser database, influence demand, and budget of the advertisers. Now, if we apply the Spatial Clustering-based approach proposed by Ali et al. [ 1 ] on this problem instance, the allocation of slots to the advertisers is shown in Table 3 . It can be observed that advertiser a_{3} and a_{4} have not been satisfied. Hence, this allocation may not be considered fair as a_{3} and a_{4} may envy with a_{1} or a_{2} . Given a set of indivisible goods and a set of agents, it remained a central question how we can fairly divide the goods among the agents for decades. A significant amount of research has been done on this problem. However, it is surprising that the existing literature does not address the issue of fairness in the context of billboard slot allocation. To tackle this problem, in this paper, we pose the slot allocation problem as a problem of fair division of indivisible items, which is a very well-studied problem in Fair Division literature. In particular, we make the following contributions in this paper: • We introduce the problem of the Fair Billboard Slot Allocation Problem for which no existing literature exists. • In this problem context, we introduce maximin fairness notions and study its properties in our problem context. • We propose an approximation algorithm that provides a fair solution to the billboard slot allocation problem. • We implement the proposed solution methodologies with real-life datasets, and several experiments have been conducted to show the effectiveness and efficiency of our solutions. The rest of the paper is organized as follows. Section 2 describes required background concepts and defines the problem formally. Section 3 describes the proposed solution approach with illustration and analysis. Section 4 contains the experimental evaluations of the proposed solution approaches. Section 5 concludes this study and gives future research directions. 2 Background and Problem Definition 2.1 Notation and Preliminaries This section introduces the background of the problem and presents its formal definition. Let us assume, there is a set of \ell billboard \mathcal{B}=\{b_{1},b_{2},\ldots,b_{\ell}\} . Each one of them are operating for the time interval [t_{1},t_{2}] , and we assume that T=t_{2}-t_{1} . Consider each billboard is allocated slot-wise for advertising, and each slot has a time duration of \Delta . Assuming that a person u_{i} crosses a billboard, b_{i} at a time t_{i} . Now assume that the advertisement content of an E-Commerce house is displayed on that billboard in the slot [t_{x},t_{y}] , and t_{i}\in[t_{x},t_{y}] . Then u_{i} is likely to be influenced by the advertisement content with a certain probability. The billboard b_{i} will influence the trajectory t_{j} with probability Pr(b_{i},t_{j}) . One of the way to calculate this value as, Pr(b_{i},u_{i})=\frac{Size(b_{i})}{\underset{b_{i}\in\mathcal{B}}{max}\ Size(b_{i})} where Size(b_{i}) is the billboard panel size. We adopt this probability setting [ 8 , 10 , 9 ] in