Algorithmic Bayesian persuasion
with combinatorial actions

Kaito Fujii (National Institute of Informatics)(joint work with Shinsaku Sakaue (UTokyo))
AAAI 2022

Bayesian persuasion

2/ 23

A game-theoretic model of strategic information revelation
for how to lead an agent to a preferred action
Bayesian persuasion [Kamenica–Gentzkow’11]

SenderQQ

1

Send a signal

3

The action aﬀects
the sender’s utility

2

ReceiverDecidean action

How to compute an optimal signaling strategy?

Applications of Bayesian persuasion(1) AdsAdsCompany(2) Election

Proﬁt

Buy the productor not
Customer

SpeechVote or not

Candidate

Elected or not

Citizen

3/ 23

Example of Bayesian persuasion [Kamenica–Gentzkow’11]
QQ
0

4/ 23

What is an optimal signaling strategy for the company?
The state isrevealed
1Good with prob. 13

ProductBad with prob. 23

Recommend the product or not

Company
Want to sell products
as many as possible

3

Obtain a proﬁt2

Decide whether

Customer
Want to buy
good products

to buy or not
Follow therecommendation
if at least half ofproducts are good

Example of Bayesian persuasion [Kamenica–Gentzkow’11]
OptimalOptimal

5/ 23

Recommend all good products and half of bad products
Customer buys 23 of all products

ProductProb. 13

GoodProb. 23

Bad

1
31
3
1
3

Company

Customer

Recommend

Buy

Not recommend

Not buyExample of Bayesian persuasion [Kamenica–Gentzkow’11]

Good

Badwith prob. 1

with prob. 1

Good with prob. 13
Bad with prob. 32

6/ 23

Example of Bayesian persuasion [Kamenica–Gentzkow’11]
Receiver’s utility ofReceiver’s utility ofbuying

not buying

Goodwith prob. 1

BadBuyNot buyGood with prob. 13
Bad with prob. 32with prob. 1

6/ 23

Notation for Bayesian persuasion
0The state θ isrevealed
1SenderMaximize sθ (a)7/ 23

The state of nature θ ∈ Θ isNatutegenerated from prior μ ∈ ∆Θ

Recommend a ∼ φθ ∈ ∆A
3Obtain sθ (a)2ReceiverMaximize rθ (a)signaling scheme (φθ )θ∈Θ is declared in advance

Decide a ∈ A

if Eθ∼ξa [rθ (a)]≥ Eθ∼ξa [rθ (a′ )]for any a′ ∈ A(commitment assumption)

Linear programming formulation [Kamenica–Gentzkow’11]

8/ 23

Computation of an optimal strategy can be formulated as LPmaximize(φθ )θ∈ΘX Xμ(θ)φθ (a)sθ (a)θ∈Θ a∈A= Eθ∼μ,a∼φθ [sθ (a)]subject toX

Sender’s expected utility

μ(θ)φθ (a) rθ (a) − rθ (a′ ) ≥ 0 (a, a′ ∈ A)θ∈Θ⇔ Eθ∼ξa [rθ (a)] ≥ Eθ∼ξa [rθ (a′ )] persuasiveness constraints
φ θ ∈ ∆A(θ ∈ Θ)

Bayesian persuasion with combinatorial actions 9/ 23(1) Buy multiple products
Ads

Proﬁt

CompanyCustomer

Buy k products

CarChoose a path from s to t

(2) Choose a path

Recommend a pathNavigation
systemSolve congestion

Bayesian persuasion with combinatorial actions 10/ 23
Receiver’s action is a combination of elements in a ﬁnite set Ei.e., A = I, where I ⊆ 2E is a set family

Buy k products

E is the set of products
I = {S ⊆ E | |S| ≤ k}uniform matroid constraints

Choose a path from s to t

E is the set of edges
I = {S ⊆ E | s–t path}
path constraints

Notation for BP with combinatorial actions

11/ 23

Consider a recommendation of combinatorial action S ∈ I ⊆ 2E0The state θ isrevealed
1SenderMaximize sθ (S)The state of nature θ ∈ Θ isNatutegenerated from prior μ ∈ ∆ΘRecommend S ∼ φθ ∈ ∆I
3Obtain sθ (S∗ )2ReceiverMaximize rθ (S)

Decide S ∈ Iif Eθ∼ξS [rθ (S)]≥ Eθ∼ξS [rθ (S′ )]for any S′ ∈ ILP formulation of BP with combinatorial actions 12/ 23
LP with exponentially many variables and constraints
maximize(φθ )θ∈Θ

subject toXXμ(θ)φθ (S)sθ (S) Sender’s expected utilityθ∈Θ S∈IX

μ(θ)φθ (S) rθ (S) − rθ (S′ ) ≥ 0 (S, S′ ∈ I)

persuasiveness constraintsθ∈Θφ θ ∈ ∆IQQ(θ ∈ Θ)

Is it possible to solve this LP in time polynomial in |E|?

Summary of our contributions

13/ 23QQ

Is it possible to eﬃciently compute an optimal signaling strategy

QQ

for Bayesian persuasion with combinatorial actions?

Our
Our resultsresults
1NP-hardness of constant-factor approximations

2

Poly-time algorithms when the number of states is a constant3

Poly-time algorithms for CCE-persuasivenessResult (1): NP-hardness

14/ 23

Constant-factor approximation is NP-hard for simple constraints
Theorem

For any α ∈ (0, 1], it is NP-hard to compute an α-approximate signaling
scheme for Bayesian persuasion with any of
uniform matroid constraints

partition matroid constraints
graphic matroids constraints
path constraints

if the utility functions are linear, i.e., sθ (S) =Pi∈S sθ ({i}) and rθ (S) =Pi∈S rθ ({i})

Result (1): NP-hardness

15/ 23

Partition matroids

Reduction from public Bayesian persuasion with no externalities[Dughmi–Xu’17]

Uniform matroids, Graphic matroids, Paths

Reduction from LINEQ-MA(1 − ζ, δ) [Guruswami–Raghavendra’09]
Given a linear system Ax = c, the promise problem of distinguishing– there exists x ∈ {0, 1}n that satisﬁes at least a 1 − ζ fraction of the equations– every x ∈ Qn satisﬁes less than a δ fraction of the equations

based on the reduction for OptSignal [Castiglioni–Celli–Marchesi–Gatti’20]

Result (2): When |Θ| is a constant16/ 23

We need to consider combinations that can be a best responseP′θ∈Θ μ(θ)φθ (S) (rθ (S) − rθ (S )) ≥ 0⇔ S ∈ argmax
S∈IX
θ∈Θ

(S, S′ ∈ I)
persuasiveness constraints

μ(θ)φθ (S)rθ (S) for each S ∈ I

S is a best response for posterior ξS (θ) ∝ μ(θ)φθ (S)Observation

In the LP formulation,
instead of I, it is suﬃcient to consider¨«XI ∗ = S ∈ I ∃ξ ∈ ∆Θ : S ∈ argmax
ξ(θ)rθ (S)S∈Iθ∈Θ

Result (2): When |Θ| is a constant
Assume rθ (·) is linear, i.e., rθ (S) =P

Uniform matroids{ , }17/ 23

{ , }
{ , }
{ , }

i∈S rθ ({i}) and sθ (·) is given by a value oracle

For each posterior ξ ∈ ∆Θ ,selecting top-k elements is best↓

k-level faces enumeration [Mulmuley’91]

θ1Lemma∆Θ

θ2studied in computational geometry

Under a certain degeneracy assumption, |I ∗ | = O(|E||Θ|−1 )Result (2): When |Θ| is a constant18/ 23General matroids
For each posterior ξ ∈ ∆Θ ,θ3Erθ ({1}) < Erθ ({3})

Erθ ({1}) > Erθ ({3}){1, 2}
is bestθ1Erθ ({2}) > Erθ ({3})

LemmaErθ ({1}) < Erθ ({2}){2, 3}
is bestErθ ({1}) > Erθ ({2}){1, 3}
is bestθ2Erθ ({2}) < Erθ ({3})

the ranking of Erθ ({·}) determines thebest response↓

cell enumeration in an arrangement ofhyperplanes [Edelsbrunner’87]

Under a certain degeneracy assumption, |I ∗ | = O(|E|2(|Θ|−1) )Result (2): When |Θ| is a constant19/ 23

Partition matroids

It is suﬃcient to consider the ranking in each partition|I ∗ | = O(|E|2(|Θ|−1) / P(|Θ|−1) ), where P is the number of partitionsGraphic matroids

The enumeration is reduced to the parametric spanning tree problem|I ∗ | = O(|E||V |1/ 3 ) when |Θ| = 2, where V is the set of vertices [Dey’98]

Paths

Even if |Θ| = 2, there exists an instance such that |I ∗ | = |E|Ω(log |E|)

[Carstensen’83]

Result (3): CCE-persuasiveness20/ 23In the CCE-persuasiveness setting, the receiver selects either of:following the signal the expected utility isXXμ(θ)φθ (S)rθ (S)θ∈Θ S∈I

not receiving the signal the expected utility is maxS∈Imaximize
subject toXXμ(θ)rθ (S)θ∈Θμ(θ)φθ (S)sθ (S)θ∈Θ S∈IXXXμ(θ)φθ (S)rθ (S) ≥ maxS∈Iθ∈Θ S∈Iφ θ ∈ ∆I(θ ∈ Θ)Xθ∈Θμ(θ)rθ (S)CCE-persuasiveness constraints

Result (3): CCE-persuasiveness
Theorem (informal)

21/ 23

If we have an oracle that, for any y ≥ 0 and θ ∈ Θ, returns S ∈ I s.t.
sθ (S) + y · rθ (S) ≥ max α · sθ (S′ ) + y · rθ (S′ ),S′ ∈I

then we can compute an (α − ε)-approximation for any ε ∈ (0, α)
Proof
ProofConsider a separation oracle for the dual LPApplications
Applicationssθ , rθ : linear, I: matroid, α = 1sθ : monotone submodular, rθ : linear, I: matroid, α = 1 − 1/ e

Summary of our contributions

22/ 23Q
Q

Is it possible to eﬃciently compute an optimal signaling strategy

QQ

for Bayesian persuasion with combinatorial actions?

Our
Our results
results
1

NP-hardness of constant-factor approximations

2

Poly-time algorithms when the number of states is a constant3

Poly-time algorithms for CCE-persuasivenessReference

23/ 23Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti: Online BayesianPersuasion. In NeurIPS 2020.

P. J. Carstensen: Complexity of some parametric integer and network programming
problems. Mathematical Programming 26(1): 64–75 (1983).

T. K. Dey: Improved bounds for planar k-sets and related problems. Discrete & Computational
Geometry 19(3): 373–382 (1998).
Shaddin Dughmi and Haifeng Xu: Algorithmic persuasion with no externalities. In EC 2017.
H. Edelsbrunner: Algorithms in Combinatorial Geometry (1987).

Emir Kamenica and Matthew Gentzkow: Bayesian persuasion. American Economic Review
101(6): 2590–2615 (2011).

Ketan Mulmuley: On levels in arrangements and Voronoi diagrams. Discrete & Computational
Geometry 6(3): 307–338 (1991).

Venkatesan Guruswami and Prasad Raghavendra: Hardness of Learning Halfspaces withNoise. SIAM Journal on Computing 39(2): 742–765 (2009).
Illustrations: "Twemoji" by Twitter, Inc and other contributors is licensed under CC BY 4.0