2025-11-22T09:19:16.214677

Approximately Bisubmodular Regret Minimization in Billboard and Social Media Advertising

Ali, Benerjee, Prasad
In a typical \emph{billboard advertisement} technique, a number of digital billboards are owned by an \emph{influence provider}, and several commercial houses approach the influence provider for a specific number of views of their advertisement content on a payment basis. If the influence provider provides the demanded or more influence, then he will receive the full payment else a partial payment. In the context of an influence provider, if he provides more or less than the advertisers demanded influence, it is a loss for him. This is formalized as 'Regret', and naturally, in the context of the influence provider, the goal will be to allocate the billboard slots among the advertisers such that the total regret is minimized. In this paper, we study this problem as a discrete optimization problem and propose two solution approaches. The first one selects the billboard slots from the available ones in an incremental greedy manner, and we call this method the Budget Effective Greedy approach. In the second one, we introduce randomness in the first one, where we do it for a sample of slots instead of calculating the marginal gains of all the billboard slots. We analyze both algorithms to understand their time and space complexity. We implement them with real-life datasets and conduct a number of experiments. We observe that the randomized budget effective greedy approach takes reasonable computational time while minimizing the regret.
academic

تقليل الندم التقريبي ثنائي الوحدة في إعلانات اللوحات الإعلانية ووسائل التواصل الاجتماعي

المعلومات الأساسية

  • معرّف الورقة: 2510.09084
  • العنوان: تقليل الندم التقريبي ثنائي الوحدة في إعلانات اللوحات الإعلانية ووسائل التواصل الاجتماعي
  • المؤلفون: ديلدار علي، سومان بانرجي، يامونا براساد (معهد الهند للتكنولوجيا جامو)
  • التصنيف: cs.GT (نظرية الألعاب)، cs.DB (قواعد البيانات)، cs.DS (هياكل البيانات والخوارزميات)
  • تاريخ النشر: أكتوبر 2025 (نسخة arXiv المسبقة)
  • رابط الورقة: https://arxiv.org/abs/2510.09084

الملخص

تبحث هذه الورقة عن مشكلة تقليل الندم في بيئة إعلانية متعددة الأنماط، حيث يحتاج مزودو التأثير إلى تخصيص فترات اللوحات الإعلانية وعقد البذور في وسائل التواصل الاجتماعي في نفس الوقت لعدة معلنين. يقترح المؤلفون نموذج تأثير تفاعلي جديد لالتقاط التأثيرات الفردية والمركبة لوسيطي الإعلان المختلفين، ويصممان حلين: طريقة التدرج المسقط (PGM) والبحث المحلي ثنائي الوحدة التقريبي (ABLS). تُظهر التجارب أن الطرق المقترحة تقلل بفعالية إجمالي الندم في إعدادات الطلب المختلفة.

الخلفية البحثية والدافع

تعريف المشكلة

  1. المشكلة الأساسية: كيف يمكن لمزودي التأثير تخصيص الموارد بشكل مشترك بين إعلانات اللوحات الإعلانية ووسائل التواصل الاجتماعي لتقليل إجمالي الندم
  2. السيناريوهات العملية: تقدم الشركات التجارية مقترحات يومية لمزودي التأثير تتضمن متطلبات التأثير، تغطي الأنماط عبر الإنترنت وغير المتصلة بالإنترنت، مع الدفع الشرطي بناءً على تحقيق المتطلبات

أهمية البحث

  • تنفق الشركات التجارية عادة 7-10% من إيراداتها السنوية على الإعلانات
  • يركز البحث الحالي في الغالب على منظور المعلنين، مع افتقار إلى التحسين المشترك من منظور مزودي التأثير
  • تتجاهل الطرق التقليدية التأثيرات التفاعلية بين اللوحات الإعلانية ووسائل التواصل الاجتماعي

قيود الطرق الموجودة

  • تتعامل الأدبيات الموجودة مع نماذج الندم للوحات الإعلانية ووسائل التواصل الاجتماعي بشكل منفصل
  • تفتقر إلى إطار عمل موحد يأخذ في الاعتبار التأثيرات التفاعلية بين نمطي الإعلان
  • نماذج الندم الموجودة ليست رتيبة وليست فرعية، مما يؤدي إلى عدم إمكانية تحقيق ضمانات الأداء

المساهمات الأساسية

  1. النمذجة المشتركة الأولى: تقديم مشكلة تقليل الندم التي تأخذ في الاعتبار في نفس الوقت إعلانات اللوحات الإعلانية والشبكات الاجتماعية
  2. التحليل النظري: إثبات أن المشكلة صعبة NP وغير قابلة للتقريب ضمن أي عامل ثابت
  3. تصميم الخوارزمية: اقتراح حلين: طريقة التدرج المسقط (PGM) والبحث المحلي ثنائي الوحدة التقريبي (ABLS)
  4. نموذج التأثير التفاعلي: نمذجة رياضية للتأثيرات التفاعلية بين اللوحات الإعلانية ووسائل التواصل الاجتماعي
  5. التحقق التجريبي: التحقق من فعالية الطرق على مجموعات البيانات الحقيقية

شرح الطريقة

تعريف المهمة

المدخلات:

  • مجموعة فترات اللوحات الإعلانية BS = {bs₁, bs₂, ..., bsₘ}
  • مجموعة عقد البذور في الشبكة الاجتماعية P = {p₁, p₂, ..., pᵣ}
  • مجموعة المعلنين A = {a₁, a₂, ..., aₙ}، حيث يمتلك كل معلن متطلب تأثير σᵢ وميزانية Kᵢ

المخرجات:

  • خطة التخصيص L = {(S₁,P₁), (S₂,P₂), ..., (Sₙ,Pₙ)} التي تقلل إجمالي الندم

القيود:

  • قيد الحصرية: لا يمكن أن تتداخل تخصيصات المعلنين المختلفين
  • قيد الميزانية: لا يمكن أن تتجاوز تكاليف التخصيص ميزانية المعلن

النموذج الأساسي

1. نموذج التأثير

Φ(S,P) = I(S) + IG(P) + Ψ(S,P)

حيث:

  • I(S): التأثير من مجموعة فترات اللوحات الإعلانية S
  • IG(P): التأثير من مجموعة عقد البذور P
  • Ψ(S,P): التأثير التفاعلي

2. نموذج التأثير التفاعلي

Ψ(S,P) = ρ · Σᵤ∈U (1 - ∏ᵦ∈S(1 - Pr(u,b))) · Σᵥ∈P Pr'(u,v)

حيث ρ ∈ 0,1 يتحكم في قوة التفاعل

3. نموذج الندم

R(Naᵢ) = Kaᵢ · (1 - γ · min(Φ(Saᵢ,Paᵢ),σaᵢ)/σaᵢ) + δ · log(1 + |Saᵢ| + |Paᵢ|)

تصميم الخوارزمية

1. طريقة التدرج المسقط (PGM)

  • طريقة التحسين المستمر بناءً على امتداد Lovász
  • استخدام متجهات كسرية لتمثيل الاختيار الناعم للفترات والبذور
  • التحديث التكراري من خلال خطوات الانحدار الفرعي والإسقاط
  • التعقيد الزمني: O(T·m³·n·r·t + Tm²·n·r²·t + m⁴·n·r·t + m³·n·r²·t + m²·n·r³·t)

2. البحث المحلي ثنائي الوحدة التقريبي (ABLS)

  • طريقة البحث المحلي الجشعة
  • ترتيب المعلنين بترتيب تنازلي حسب نسبة الطلب إلى الميزانية
  • اختيار العناصر التي تحقق أقصى تقليل في الندم لكل وحدة تأثير
  • التعقيد الزمني: O(m·r²·t + m²·r·t)

نقاط الابتكار التقنية

  1. الخاصية ثنائية الوحدة التقريبية ε: توسيع الدوال ثنائية الوحدة التقليدية، مما يسمح بانحراف محدود
  2. إطار العمل الموحد: أول نمذجة موحدة لإعلانات اللوحات الإعلانية ووسائل التواصل الاجتماعي
  3. تحديد التأثيرات التفاعلية: توفير طريقة حسابية رياضية للتأثيرات التفاعلية
  4. الضمانات النظرية: توفير حدود الأداء للدوال ثنائية الوحدة التقريبية

إعداد التجارب

مجموعات البيانات

  1. بيانات المسار: بيانات تسجيل الدخول من Foursquare (2012.4-2014.1)
    • 124,539 تسجيل دخول، 51,318 مستخدم فريد
    • تغطي المدن الرئيسية في الولايات المتحدة
  2. بيانات الشبكة الاجتماعية: لقطة شبكة اجتماعية للمستخدمين
    • الشبكة القديمة: 95,994 علاقة صداقة
    • الشبكة الجديدة: 129,864 علاقة صداقة
  3. بيانات اللوحات الإعلانية: مجموعة بيانات LAMAR
    • نيويورك: 716 لوحة إعلانية، 1,031,040 فترة زمنية
    • لوس أنجلوس: 1,483 لوحة إعلانية، 2,135,520 فترة زمنية

مؤشرات التقييم

  • إجمالي الندم: مجموع ندم جميع المعلنين
  • عدد المعلنين المرضيين: عدد المعلنين الذين تم تلبية احتياجاتهم
  • وقت الحساب: وقت تشغيل الخوارزمية

طرق المقارنة

  • التخصيص العشوائي (RA): اختيار عشوائي لفترات اللوحات الإعلانية وعقد البذور
  • تخصيص أفضل k: اختيار أكثر k فترات لوحات إعلانية وعقد بذور تأثيراً

المعاملات الرئيسية

المعاملالمعنىنطاق القيم
αنسبة الطلب إلى العرض40%-120%
λمتوسط نسبة الطلب الفردي1%-20%
γنسبة عقوبة عدم الرضا0-1
δنسبة عقوبة العدد0-1
εمعامل تسامح الندم0-0.1
ρمعامل التفاعل0-1

نتائج التجارب

النتائج الرئيسية

1. الأداء في سيناريوهات الطلب المختلفة

الحالة 1 (α منخفض، λ منخفض): α ≤ 80%, λ ≤ 2%

  • يتفوق PGM و ABLS بشكل كبير على طرق الأساس
  • عدد أكبر من المعلنين المرضيين
  • تقليل الندم بنسبة 30-40%

الحالة 2 (α منخفض، λ مرتفع): α ≤ 80%, λ ≥ 5%

  • عندما تكون المتطلبات الفردية عالية، ينخفض الإفراط في العرض
  • تحافظ الطرق المقترحة على أفضليتها
  • تقليل الندم بنسبة 25-35%

الحالة 3 (α مرتفع، λ منخفض): α ≥ 100%, λ ≤ 2%

  • نقص العرض يؤدي إلى زيادة الندم الإجمالي
  • يظل PGM و ABLS متفوقين على الأساس
  • تقليل الندم بنسبة 15-25%

الحالة 4 (α مرتفع، λ مرتفع): α ≥ 100%, λ ≥ 5%

  • تواجه جميع الطرق ندماً أعلى
  • المعلنون القلائل ذوو الطلب العالي أقل فائدة من العديد من المعلنين ذوي الطلب المنخفض

2. تحليل الكفاءة الحسابية

  • يتمتع ABLS بوقت حساب أقصر في معظم الحالات
  • يزداد الحمل الحسابي لـ PGM بشكل كبير عندما يزداد عدد المعلنين
  • يزداد وقت الحساب لجميع الطرق مع زيادة نسبة الطلب إلى العرض α

3. تحليل حساسية المعاملات

  • زيادة ε: يقل وقت التشغيل لكن يزداد الندم
  • زيادة δ: تعاقب التخصيصات الكبيرة، مما يؤدي إلى حلول مضغوطة لكن أقل فعالية
  • زيادة γ: التركيز على تحقيق المتطلبات، مع مقابلة استخدام موارد أعلى بندم أقل
  • زيادة ρ: تزداد قوة التفاعل بين فترات اللوحات الإعلانية وعقد البذور

تجارب الاستبعاد

  1. تأثير التأثيرات التفاعلية:
    • ينخفض إجمالي الندم من 341.37 إلى 295.14 عند النظر في التأثيرات التفاعلية
    • يثبت أهمية نمذجة التأثيرات التفاعلية
  2. تأثير إعدادات الاحتمالية:
    • يُظهر إعداد الاحتمالية ثلاثي القيم (trivalency) أفضل أداء
    • يحاكي بشكل أفضل التباين في التأثير بين الأفراد في الواقع

اختبار القابلية للتوسع

  • السيناريو واسع النطاق: λ = 1%, |A| = 100
  • السيناريو الصغير النطاق: λ = 20%, |A| = 5
  • يتفوق PGM و ABLS على طرق الأساس في كلا السيناريوهين

الأعمال ذات الصلة

أبحاث تعظيم التأثير

  • تعظيم التأثير في إعلانات اللوحات الإعلانية 6, 33, 36
  • تعظيم التأثير في إعلانات الشبكات الاجتماعية 17, 19, 24
  • مشاكل الاختيار المشترك للعلامات والفترات الزمنية 7

أبحاث تقليل الندم

  • تقليل الندم في الشبكات الاجتماعية 13, 30
  • تقليل الندم في إعلانات اللوحات الإعلانية 37
  • تقليل الندم تحت قيود التأثير الإقليمي 2, 4

مساهمة هذه الورقة

هذه الورقة هي الأولى التي تدرس تقليل الندم مع الأخذ في الاعتبار في نفس الوقت إعلانات اللوحات الإعلانية والشبكات الاجتماعية، مما يملأ فجوة في هذا المجال.

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. تعقيد المشكلة: إثبات أن مشكلة تقليل الندم في الإعلانات متعددة الأنماط صعبة NP وغير قابلة للتقريب
  2. فعالية الخوارزمية: يمكن لـ PGM و ABLS تقليل الندم بفعالية في إعدادات مختلفة
  3. أهمية التأثيرات التفاعلية: يؤدي النظر في التأثيرات التفاعلية بين اللوحات الإعلانية ووسائل التواصل الاجتماعي إلى تحسين كبير في النتائج
  4. التوجيهات العملية: المعلنون المتعددون ذوو الطلب المنخفض أكثر فائدة من المعلنين القلائل ذوي الطلب العالي

القيود

  1. التعقيد الحسابي: يتمتع PGM بحمل حسابي أعلى في السيناريوهات واسعة النطاق
  2. حساسية المعاملات: تتطلب معاملات متعددة ضبطاً دقيقاً
  3. تبسيط نموذج التفاعل: قد لا يتمكن نموذج التأثير التفاعلي من التقاط التعقيد الكامل للواقع
  4. الإعداد الثابت: لا يأخذ في الاعتبار سيناريوهات وصول المعلنين الديناميكي

الاتجاهات المستقبلية

  1. الخوارزميات عبر الإنترنت: تطوير خوارزميات عبر الإنترنت للتعامل مع وصول المعلنين الديناميكي
  2. التحسين المتوازي: تصميم إطار عمل تحسين متوازي وموزع لتحسين القابلية للتوسع
  3. نماذج تفاعل أكثر تعقيداً: استكشاف طرق نمذجة التأثيرات التفاعلية الأكثر دقة
  4. مجالات تطبيق أخرى: توسيع الإطار إلى مجالات أخرى مثل تخصيص موارد الحوسبة السحابية

التقييم المتعمق

المميزات

  1. جدة المشكلة: أول دراسة لتقليل الندم المشترك في الإعلانات متعددة الأنماط، ذات أهمية عملية كبيرة
  2. الصرامة النظرية: توفير تحليل نظري شامل، بما في ذلك إثبات التعقيد وضمانات التقريب
  3. ابتكار الطريقة:
    • تقديم مفهوم الخاصية ثنائية الوحدة التقريبية ε
    • تصميم نموذج رياضي للتأثيرات التفاعلية
    • تطوير خوارزميتين متكاملتين
  4. كفاية التجارب:
    • استخدام مجموعات بيانات حقيقية واسعة النطاق
    • النظر في إعدادات وسيناريوهات معاملات متعددة
    • توفير تجارب استبعاد وتحليل حساسية مفصلة

أوجه القصور

  1. قيود نموذج التفاعل: قد تكون افتراضات التركيب الخطي للتأثيرات التفاعلية مبسطة جداً
  2. الكفاءة الحسابية: التعقيد الزمني العالي لـ PGM قد يشكل تحدياً في التطبيقات العملية
  3. الاعتماد على المعاملات: أداء الخوارزمية حساسة لمعاملات متعددة، مما يتطلب ضبطاً دقيقاً عند النشر
  4. قيود التقييم: نقص المقارنة مع طرق أساسية أكثر تقدماً

التأثير

  1. المساهمة الأكاديمية:
    • فتح اتجاه بحثي جديد في تحسين الإعلانات متعددة الأنماط
    • توسيع نظرية التحسين الفرعي إلى الدوال ثنائية الوحدة التقريبية
    • توفير أساس نظري لمشاكل التحسين ذات الصلة
  2. القيمة العملية:
    • قابلة للتطبيق المباشر على صناعة الإعلانات الرقمية
    • يمكن توسيع الإطار إلى مشاكل تخصيص الموارد الأخرى
    • توفير أداة دعم القرار لمزودي التأثير
  3. قابلية إعادة الإنتاج: توفير وصف خوارزمي مفصل وإعداد تجريبي يسهل إعادة الإنتاج

السيناريوهات القابلة للتطبيق

  1. منصات الإعلانات الرقمية: مناسبة للمنصات التي تحتاج إلى إدارة موارد إعلانية عبر الإنترنت وغير المتصلة بالإنترنت في نفس الوقت
  2. أنظمة تخصيص الموارد: يمكن توسيعها إلى مشاكل تخصيص الموارد في الحوسبة السحابية واللوجستيات وغيرها
  3. التسويق بالتأثير: مناسبة للتحسين المشترك لتسويق وسائل التواصل الاجتماعي والإعلانات التقليدية

المراجع

تستشهد الورقة بـ 37 مرجعاً ذا صلة، تغطي مجالات بحثية متعددة مثل تعظيم التأثير والتحسين الفرعي وتخصيص الإعلانات، مما يوفر أساساً نظرياً قوياً لهذا البحث.

التقييم الشامل: هذه ورقة بحثية عالية الجودة حققت توازناً جيداً بين الابتكار النظري والتطبيق العملي. على الرغم من وجود بعض القيود، فإن اتجاهها البحثي الرائد وتصميم طريقتها الصارم يمنحها قيمة أكاديمية وعملية مهمة.