Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNon-zero-sum Stackelberg Budget Allocation Game for Computational Advertising
73
0
0.0
(
0
)
Added by
Hanna Sumita
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Computational advertising has been studied to design efficient marketing strategies that maximize the number of acquired customers. In an increased competitive market, however, a market leader (a leader) requires the acquisition of new customers as well as the retention of her loyal customers because there often exists a competitor (a follower) who tries to attract customers away from the market leader. In this paper, we formalize a new model called the Stackelberg budget allocation game with a bipartite influence model by extending a budget allocation problem over a bipartite graph to a Stackelberg game. To find a strong Stackelberg equilibrium, a standard solution concept of the Stackelberg game, we propose two algorithms: an approximation algorithm with provable guarantees and an efficient heuristic algorithm. In addition, for a special case where customers are disjoint, we propose an exact algorithm based on linear programming. Our experiments using real-world datasets demonstrate that our algorithms outperform a baseline algorithm even when the follower is a powerful competitor.
rate research
Read More
Vehicular ad-hoc networks (VANETs) have recently attracted a lot of attention due to their immense potentials and applications. Wide range of coverage and accessibility to end users make VANETs a good target for commercial companies. In this paper, we consider a scenario in which advertising companies aim to disseminate their advertisements in different areas of a city by utilizing VANETs infrastructure. These companies compete for renting the VANETs infrastructure to spread their advertisements. We partition the city map into different blocks, and consider a manager for all the blocks who is in charge of splitting the time between interested advertising companies. Each advertising company (AdC) is charged proportional to the allocated time. In order to find the best time splitting between AdCs, we propose a Stackelberg game scheme in which the block manager assigns the companies to the blocks and imposes the renting prices to different companies in order to maximize its own profit. Based on this, AdCs request the amount of time they desire to rent the infrastructure in order to maximize their utilities. To obtain the Stackelberg equilibrium of the game, a mixed integer nonlinear optimization problem is solved using the proposed optimal and sub-optimal algorithms. The simulation results demonstrate that the sub-optimal algorithm approaches the optimal one in performance with lower complexity.
We study the problem of an online advertising system that wants to optimally spend an advertisers given budget for a campaign across multiple platforms, without knowing the value for showing an ad to the users on those platforms. We model this challenging practical application as a Stochastic Bandits with Knapsacks problem over $T$ rounds of bidding with the set of arms given by the set of distinct bidding $m$-tuples, where $m$ is the number of platforms. We modify the algorithm proposed in Badanidiyuru emph{et al.,} to extend it to the case of multiple platforms to obtain an algorithm for both the discrete and continuous bid-spaces. Namely, for discrete bid spaces we give an algorithm with regret $Oleft(OPT sqrt {frac{mn}{B} }+ sqrt{mn OPT}right)$, where $OPT$ is the performance of the optimal algorithm that knows the distributions. For continuous bid spaces the regret of our algorithm is $tilde{O}left(m^{1/3} cdot minleft{ B^{2/3}, (m T)^{2/3} right} right)$. When restricted to this special-case, this bound improves over Sankararaman and Slivkins in the regime $OPT ll T$, as is the case in the particular application at hand. Second, we show an $ Omegaleft (sqrt {m OPT} right)$ lower bound for the discrete case and an $Omegaleft( m^{1/3} B^{2/3}right)$ lower bound for the continuous setting, almost matching the upper bounds. Finally, we use a real-world data set from a large internet online advertising company with multiple ad platforms and show that our algorithms outperform common benchmarks and satisfy the required properties warranted in the real-world application.
Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) can yield unacceptably low revenue. We therefore study core selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder optimal core point with almost linear number of calls to the welfare maximization oracle. Our algorithm is faster than previously-proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time sensitive practical use cases such as realtime auctions for online advertising and can yield more revenue. We justify this claim experimentally using the Microsoft Bing Ad Auction data, through which we show our core pricing algorithm generates almost 26% more revenue than VCG on average, about 9% more revenue than other core pricing rules known in the literature, and almost matches the revenue of the standard Generalized Second Price (GSP) auction.
Machine learning processes, e.g. learning in games, can be viewed as non-linear dynamical systems. In general, such systems exhibit a wide spectrum of behaviors, ranging from stability/recurrence to the undesirable phenomena of chaos (or butterfly effect). Chaos captures sensitivity of round-off errors and can severely affect predictability and reproducibility of ML systems, but AI/ML communitys understanding of it remains rudimentary. It has a lot out there that await exploration. Recently, Cheung and Piliouras employed volume-expansion argument to show that Lyapunov chaos occurs in the cumulative payoff space, when some popular learning algorithms, including Multiplicative Weights Update (MWU), Follow-the-Regularized-Leader (FTRL) and Optimistic MWU (OMWU), are used in several subspaces of games, e.g. zero-sum, coordination or graphical constant-sum games. It is natural to ask: can these results generalize to much broader families of games? We take on a game decomposition approach and answer the question affirmatively. Among other results, we propose a notion of matrix domination and design a linear program, and use them to characterize bimatrix games where MWU is Lyapunov chaotic almost everywhere. Such family of games has positive Lebesgue measure in the bimatrix game space, indicating that chaos is a substantial issue of learning in games. For multi-player games, we present a local equivalence of volume change between general games and graphical games, which is used to perform volume and chaos analyses of MWU and OMWU in potential games.
Fog computing is a promising architecture to provide economic and low latency data services for future Internet of things (IoT)-based network systems. It relies on a set of low-power fog nodes that are close to the end users to offload the services originally targeting at cloud data centers. In this paper, we consider a specific fog computing network consisting of a set of data service operators (DSOs) each of which controls a set of fog nodes to provide the required data service to a set of data service subscribers (DSSs). How to allocate the limited computing resources of fog nodes (FNs) to all the DSSs to achieve an optimal and stable performance is an important problem. In this paper, we propose a joint optimization framework for all FNs, DSOs and DSSs to achieve the optimal resource allocation schemes in a distributed fashion. In the framework, we first formulate a Stackelberg game to analyze the pricing problem for the DSOs as well as the resource allocation problem for the DSSs. Under the scenarios that the DSOs can know the expected amount of resource purchased by the DSSs, a many-to-many matching game is applied to investigate the pairing problem between DSOs and FNs. Finally, within the same DSO, we apply another layer of many-to-many matching between each of the paired FNs and serving DSSs to solve the FN-DSS pairing problem. Simulation results show that our proposed framework can significantly improve the performance of the IoT-based network systems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
