False-name Attacks � in Auctions

Yotam Gafni, 12/22

​

For Moshe Tennenholtz Mechanism Design for Data Science Class

Reminder: VCG for combinatorial auctions

Reminder: VCG for combinatorial auctions (Cont.)

• VCG is ^truthful in dominant strategies and ^{welfare-maximizing}
• Example: Two items and two bidders

– v1({b}) = v1({a}) = 0, v1({a,b}) = 15

– v2({b}) = 10, v2({a}) = 10, v2({a,b}) = 10

15

10

10

Is VCG really truthful?

• What if we allow bidder 2 to assume a false identity (Bidder 3)?
• Same preferences: Two items and two bidders

– v1({b}) = v1({a}) = 0, v1({a,b}) = 15

– v2({b}) = 10, v2({a}) = 10, v2({a,b}) = 10

• Bidder 2 has utility 0 bidding truthfully. Can he do better with a false-name attack?

Is VCG really truthful? (Cont.)

• Can agent 2 do better with a false-name attack? Bid:

– b2({b}) = 0, b2({a}) = b2({a,b}) = 15

– b3({a}) = 0, b2({b}) = b2({a,b}) = 15

– VCG allocates 𝒂_𝟏 = {}, 𝒂_𝟐 = 𝒂 , 𝒂_𝟑 = {𝒃} and agents 2 and 3 pay nothing

15

15

15

This is a problem…

• Truthfulness is not a dominant strategy
• It is not even a Nash Equilibrium
• It’s not clear that there is even any Nash Equilibrium unless # of false identities and valuations are restricted (Remember that NE is guaranteed for ^compact type spaces)

First attempt: Detect attacks

[Matsuo, Ito, Day & Shintani 2006]

First attempt: Detect attacks (Cont.)

In the example we saw before:

• The attack doesn’t work anymore
• If the two single agents are honest, it has half the social welfare as VCG

15

15

15

First attempt: Detect attacks (Cont.)

But… Will this always stop False-name attacks?

• 3 items, 2 bidders
• Agent 1 values entire bundle as 15
• Agent 2 values entire bundle as 20

First attempt: Detect attacks (Cont.)

Will this always stop False-name attacks?

• 3 items, 2 bidders
• Agent 1 values entire bundle as 15
• Agent 2 values entire bundle as 20

15

20

20

20

First attempt: Detect attacks (Cont.)

What’s mis-detection worst-case efficiency?

15

10

10

Second attempt: ’Set’ mechanism

[Iwasaki, Conitzer, Omori, Sakurai, Todo, Guo & Yokoo 2010]

• For each bidder, consider the bundle it offers the most for
• The bidder with the best max bundle gets it, and pays the price of the 2^nd max bundle
• False-name-proof (why?)
• Efficiency can be as bad as O(1/m)
• Bidder 0 values the entire bundle as c
• All other m bidders value some unique good as c − ϵ
• Set allocates entire bundle to agent 0 with efficiency c
• Best possible efficiency is m(c − ϵ)

A General Impossibility Result

​

• Negative results on efficiency:
• There is no false-name-proof and ^{Pareto-efficient} mechanism
• Pareto efficiency is natural because of the property of `Mutually beneficial exchanges’
• For any false-name-proof mechanism, the worst-case efficiency is at most O(1/m)

Limited valuation classes - Submodular

Red

Blue

Green

Budget: 6

Budget: ∞

Budget: ∞

A

B

C

3

5

3

1

2

2

5

Green gets {a,c} and pays 3

Limited valuation classes – Submodular cont.

• Counter-example (Lehmann Lehmann and Nisan 2006]:

​

​

5

Red

Blue

Green1

Budget: 6

Budget: ∞

Budget: ∞

A

B

C

3

5

3

1

2

2

Green2

Budget: ∞

Green gets {a,c} and pays 2

• If the valuations satisfy a more involved sub-modular condition, [Yokoo 2003]’s results hold.
• Approximately submodular valuations give better efficiency guarantees [Alkalay-Houlihan & Vetta 2014]

​

​

Limited valuation classes – Submodular cont. II

​

• [Christodoulou, Kovacs & Schapira 2016] For XOS valuations, selling each item in a 2^nd price auction with no over-bidding has a pure Nash equilibrium that guarantees at least half of the optimal welfare.
• Moreover, every such Nash equilibrium guarantees at least half of the optimal welfare.

​

​

​

(Taken from Michal Feldman’s slides)

Single-minded bidders

Single-minded bidders

Blue

Green

A

B

18

19

Single-minded bidders

Blue2

Blue1

Green

A

B

8

10

19

Is uncertainty the answer?

• What we showed is that with false-name attacks, VCG is no longer DSIC
• I.e., False-name attacks’ success depends on other bidders’ valuations
• If other bidders are drawn from a distribution, truthfulness could still be a BNE for VCG
• In our paper we show this holds for many settings [Gafni, Lavi & Tennenholtz 2020]

​

​

Which is it? The left or the right?

15

15

15

15

15

15

15

Is uncertainty the answer? II

Big open question:

• Take our running example. It belongs to a valuation class called single-minded bidders
• This valuation class does not belong in the XOS valuation hierarchy we saw before
• With identical goods, it maps to this general question: Groups come to a movie with some amount of tickets and valuation-per-ticket in mind.
• Can we find a mechanism, that has a truthful BNE, and guarantees O(1) efficiency there?

​

​

​