Simple Science

La science de pointe expliquée simplement

# Informatique# Informatique et théorie des jeux# Apprentissage automatique

Maximiser les revenus dans les enchères publicitaires conjointes

Une étude sur les enchères publicitaires collaboratives pour les commerçants et les marques.

― 9 min lire


Optimisation conjointeOptimisation conjointedes revenus publicitairescollaboratives.dans les enchères publicitairesStratégies pour maximiser les profits
Table des matières

Dans le monde du shopping en ligne d'aujourd'hui, vendre des publicités, c'est un peu comme vendre des articles dans un magasin. Cet article examine comment on peut vendre un seul article, comme un espace publicitaire, à deux acheteurs qui ne peuvent pas être empêchés de voir l'annonce, comme un commerçant et une marque.

Cette situation arrive quand le commerçant et la marque veulent enchérir ensemble lors d'une enchère pour obtenir plus de visibilité pour un produit, les deux partis profitant de l'annonce affichée. Le défi est de récolter les enchères des deux, puis de décider comment répartir l'espace pub et combien chacun doit payer. Ce système crée une situation complexe avec plein de règles pour que tout reste équitable, surtout en ce qui concerne la division des paiements.

On se concentre sur la création d'un mécanisme qui encourage l'honnêteté dans les enchères tout en maximisant les revenus, en se basant sur des méthodes utilisées dans le monde de l'apprentissage en ligne. Les défis sont importants. D'abord, il y a plein de façons de structurer ces mécanismes. Ensuite, le lien entre les mécanismes et leurs revenus n'est pas évident, ce qui rend les méthodes traditionnelles peu efficaces.

Dans une situation où la valeur de l'annonce est imprévisible, on cherche à concevoir une méthode d'apprentissage qui garantit un certain niveau de regret, c'est-à-dire la différence entre les revenus qu'on a générés et ce qu'un mécanisme optimal aurait pu rapporter. Notre méthode s'appuie sur une stratégie qui s'ajuste en fonction de l'espace des mécanismes observés, car une approche fixe ne permet pas d'atteindre nos objectifs de revenus.

Quand on regarde des scénarios avec des valeurs décidées à l'avance, on se rend compte qu'aucune méthode d'apprentissage ne peut faire mieux que la moitié de ce qu'un bon mécanisme structuré aurait gagné après coup. On plonge ensuite dans un cadre "d'adversaire lisse", où les valeurs viennent de distributions qui varient mais de manière fluide. Ici, on peut développer une méthode d'apprentissage qui minimise le regret et fonctionne efficacement.

Imagine un site de vente en ligne comme Amazon ou Alibaba. Ces sites ne vendent pas seulement des produits directement, mais permettent aussi à d'autres de faire de la pub. Les annonces profitent souvent à la fois à une marque, comme Nike, et à un commerçant, comme Footlocker, qui bossent ensemble. Le programme "Collaborative Ads" de Facebook en est un exemple où les marques et les commerçants unissent leurs forces pour acheter des annonces.

On s'intéresse particulièrement aux cas où deux parties enchérissent ensemble pour un espace publicitaire. Notre mécanisme vise à maximiser les revenus tout en récoltant les enchères et en décidant de l'allocation de l'annonce. Quand le mécanisme fonctionne bien, il détermine combien chaque partie doit payer et garantit que les deux sont contents du résultat. On appelle ce défi le problème des annonces conjointes.

Quand on conçoit ce genre de mécanismes, on fait face à plusieurs complexités. Si on ne met pas le système en place correctement, le commerçant ou la marque pourrait ne pas enchérir honnêtement, ce qui pourrait mener à des résultats indésirables. Donc, le mécanisme doit être conçu pour décourager tout comportement malhonnête et s'assurer que les deux acheteurs révèlent leurs vraies évaluations.

Bien qu'on sache gérer les acheteurs uniques dans ces situations, on a besoin d'une approche plus axée sur les données quand on s'occupe de plusieurs acheteurs. Du coup, on considère le problème des annonces conjointes répétées, où notre mécanisme interagit avec une nouvelle paire d'agents à chaque étape, chacun ayant sa propre volonté de payer.

À chaque étape, notre mécanisme propose un système qui encourage les enchères honnêtes et calcule les revenus basés sur les paiements faits par les deux agents. L'objectif est d'atteindre le revenu maximum possible tout en mesurant à quel point on est éloigné du standard du meilleur mécanisme fixe.

On évalue trois façons différentes dont les agents peuvent déterminer leurs valeurs : le modèle adversarial, où les valeurs sont attribuées de manière imprévisible ; le modèle stochastique, où les valeurs proviennent d'une distribution fixe mais inconnue ; et le modèle lisse, où les valeurs proviennent de distributions variables mais dans des limites prévisibles.

Dans le modèle stochastique, on développe une méthode d'apprentissage qui atteint une borne de regret, ce qui signifie que même si on n'atteint pas toujours le revenu optimal, on peut garantir qu'il est assez proche sous certaines conditions. En revanche, dans le cadre adversarial, on découvre qu'aucune méthode ne peut constamment atteindre plus de la moitié des revenus du meilleur mécanisme fixe.

Dans le scénario d'adversaires lisses, on conçoit une méthode d'apprentissage qui fournit une bonne borne de regret, s'appuyant sur une façon compacte de gérer de nombreux experts dans notre cadre. On démontre également qu'aucune méthode ne peut faire mieux qu'un certain niveau de regret dans les Modèles Stochastiques et lisses, ce qui réduit les attentes pour ces problèmes.

La discussion ci-dessus tourne autour de la compréhension de la mécanique des espaces de vente en ligne, en particulier comment les annonces peuvent être efficacement commercialisées lorsque deux acheteurs collaborent. Un aspect crucial est que les annonces peuvent simultanément bénéficier à différentes parties et créer une dynamique intéressante en termes d'enchères et de paiements.

Par exemple, quand une marque et un commerçant veulent acheter ensemble de l'espace publicitaire, ils coordonnent leurs enchères dans un environnement d'enchères, créant le besoin d'un mécanisme d'allocation efficace. Notre proposition aborde ce problème complexe d'allocation des enchères.

Le défi réside dans plusieurs contraintes d'incitation qui apparaissent. Sans structurer l'enchère correctement, une partie pourrait essayer de baisser son enchère au détriment de l'autre, créant un déséquilibre. Donc, un mécanisme efficace doit stratégiquement empêcher les deux parties de sous-enchérir, en s'assurant qu'elles rapportent leurs évaluations réelles sans craindre d'être prises au piège.

Bien que la tâche ponctuelle de vendre un seul bien non excluable soit bien documentée, elle repose souvent sur une connaissance préalable des valeurs des agents. Une solution plus efficace serait une approche axée sur les données qui évolue avec le temps, s'adaptant aux enchères reçues.

On cherche à créer un mécanisme Compatible avec les incitations, maximisant les revenus d'un point de vue d'apprentissage. Formulons cela par le biais d'interactions répétées avec des paires d'agents qui arrivent à chaque étape, révélant leurs évaluations pour l'espace publicitaire. Le mécanisme utilise une combinaison de stratégies dominantes pour encourager l'honnêteté et des enchères rationnelles de la part des deux parties.

Notre objectif à chaque étape est de maximiser le revenu global tout en mesurant le regret, qui indique combien de revenus on perd par rapport au meilleur mécanisme fixe. On explore trois modèles d'évaluation distincts : le modèle adversarial, où les valeurs sont prédéterminées ; le modèle stochastique, où les valeurs ont une distribution inconnue ; et le modèle lisse, où les valeurs suivent un patron non stationnaire.

Le scénario adversarial est le plus difficile puisque les valeurs peuvent être arbitraires. Dans ce cas, on trouve que les mécanismes d'apprentissage ne peuvent pas atteindre un regret sous-linéaire par rapport au meilleur mécanisme fixe, rendant la tâche beaucoup plus difficile.

Quant aux adversaires lisses, on conçoit un algorithme d'apprentissage qui atteint une efficacité significative. La complexité de ce modèle nous permet de créer une méthode qui minimise le regret tout en s'adaptant à la nature changeante des valeurs des agents.

On introduit également le concept de mécanismes orthogonaux et souligne leur importance en termes de maximisation des revenus. Ces mécanismes reposent sur des régions d'allocation qui peuvent être représentées par des chemins spécifiques dans un graphe, fournissant une structure claire pour la prise de décision.

En résumé, on progresse dans la compréhension du problème des annonces conjointes en se concentrant sur la minimisation du regret à travers des algorithmes d'apprentissage efficaces. Cette approche fournit des aperçus sur comment deux parties peuvent collaborer efficacement dans des environnements d'enchères pour sécuriser un espace publicitaire sans sacrifier les revenus.

Globalement, cette recherche éclaire les complexités de la publicité conjointe et les implications pratiques de ces découvertes pour le commerce en ligne. En adaptant les cadres d'apprentissage et les mécanismes, on ouvre de nouvelles voies pour améliorer les modèles de revenus dans les environnements de publicité collaborative, garantissant que les commerçants et les marques peuvent bénéficier de leurs efforts conjoints.

Continuer à améliorer ces méthodes nécessitera encore d'explorer de nouveaux modèles, en s'assurant qu'ils restent adaptables et efficaces face à la nature toujours changeante de la publicité en ligne. Nos découvertes jettent les bases pour de futures recherches sur des approches plus sophistiquées qui pourraient encore améliorer la génération de revenus dans des contextes collaboratifs, menant finalement à de meilleurs résultats pour toutes les parties impliquées.

Source originale

Titre: Selling Joint Ads: A Regret Minimization Perspective

Résumé: Motivated by online retail, we consider the problem of selling one item (e.g., an ad slot) to two non-excludable buyers (say, a merchant and a brand). This problem captures, for example, situations where a merchant and a brand cooperatively bid in an auction to advertise a product, and both benefit from the ad being shown. A mechanism collects bids from the two and decides whether to allocate and which payments the two parties should make. This gives rise to intricate incentive compatibility constraints, e.g., on how to split payments between the two parties. We approach the problem of finding a revenue-maximizing incentive-compatible mechanism from an online learning perspective; this poses significant technical challenges. First, the action space (the class of all possible mechanisms) is huge; second, the function that maps mechanisms to revenue is highly irregular, ruling out standard discretization-based approaches. In the stochastic setting, we design an efficient learning algorithm achieving a regret bound of $O(T^{3/4})$. Our approach is based on an adaptive discretization scheme of the space of mechanisms, as any non-adaptive discretization fails to achieve sublinear regret. In the adversarial setting, we exploit the non-Lipschitzness of the problem to prove a strong negative result, namely that no learning algorithm can achieve more than half of the revenue of the best fixed mechanism in hindsight. We then consider the $\sigma$-smooth adversary; we construct an efficient learning algorithm that achieves a regret bound of $O(T^{2/3})$ and builds on a succinct encoding of exponentially many experts. Finally, we prove that no learning algorithm can achieve less than $\Omega(\sqrt T)$ regret in both the stochastic and the smooth setting, thus narrowing the range where the minimax regret rates for these two problems lie.

Auteurs: Gagan Aggarwal, Ashwinkumar Badanidiyuru, Paul Dütting, Federico Fusco

Dernière mise à jour: Sep 12, 2024

Langue: English

Source URL: https://arxiv.org/abs/2409.07819

Source PDF: https://arxiv.org/pdf/2409.07819

Licence: https://creativecommons.org/licenses/by/4.0/

Changements: Ce résumé a été créé avec l'aide de l'IA et peut contenir des inexactitudes. Pour obtenir des informations précises, veuillez vous référer aux documents sources originaux dont les liens figurent ici.

Merci à arxiv pour l'utilisation de son interopérabilité en libre accès.

Plus d'auteurs

Articles similaires