False-name Attacks under Uncertainty�In Combinatorial Auctions, Voting Games, and Collaborative ML

​

​

P.h.D Thesis Seminar, Technion, June 2023

​

Yotam Gafni

Technion, Israel

Moshe Tennenholtz

Ron Lavi

Advised by:

What are False-name Attacks?

Too ominous to deal with?

Many negative results in different settings:

• No combinatorial auction is Sybil-proof and Pareto-efficient [Yokoo, Saburai & Matsubara 2004]
• A Sybil-proof combinatorial auction with m items is O(1/m) efficient [Iwasaki et. al 2010]
• A Sybil-proof mechanism for Multi-level marketing has o(1) revenue [Emek et. al 2011]
• Exponentially bad efficiency in resource-sharing games [Mazorra & Della Penna 2023]
• In false-name proof voting with m alternatives, even if all voters vote for alternative a, it can win w.p. O(1/m) [Conitzer 2008]

​

​

Approaches to Mitigation in Combinatorial Auctions

• Limited valuation classes
• With Submodular valuations++ a Sybil-proof mechanism exists (=VCG) [Nisan & Ronen 2006]
• Approximately submodular valuations give approximate efficiency guarantees in VCG [Alkalay-Houlihan & Vetta 2014]
• [Christodoulou, Kovacs & Schapira 2016] For XOS valuations, every pure Nash equilibrium when selling each item in a 2^nd price auction with no over-bidding guarantees at least half of the optimal welfare, and such equilibrium exists.

​

​

​

​

​

​

(Taken from Michal Feldman’s slides)

A New Approach: Uncertainty

• All the negative results we saw were under full information settings.
• What happens if the agents face uncertainty?
• We see an example where an attack only succeeds based on the circumstances.
• But to understand the example, we first need to dive into combinatorial auctions.

Reminder: VCG & Combinatorial Auctions

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

​

– VCG allocates 𝒂_𝟏 = {a,b}, 𝒂_𝟐 ={} and agent 1 (the couple) pays 10.

​

15

10

10

A False-name Attack for the Example

• Can agent 2 do better with a false-name attack? Bid:
• – b2({b}) = 0, b2({a}) = b2({a,b}) = 15
• – b3({a}) = 0, b3({b}) = b3({a,b}) = 15
• – VCG allocates 𝒂_𝟏 = {}, 𝒂_𝟐 ={𝒂} , 𝒂_𝟑 = {𝒃} and agents 2 and 3 pay nothing

15

15

15

Is uncertainty the answer to the example?

• What we showed is that with false-name attacks, VCG is no longer DSIC
• But, false-name attacks’ success depends on other bidders’ valuations
• What if the attacker is uncertain about the other bidders?

​

​

Left-hand, the attacker’s utility is -20. Right-hand, the attacker’s utility is 10

15

15

15

15

15

15

15

This Calls for a Bayesian Analysis… [Gafni, Lavi & Tennenholtz 2020]

Results…

What If There is No Bayesian Prior? [Gafni & Tennenholtz 2023]

Let’s apply ’Safety Level’ to the First-price Auction.

The worst-case performance of any under-bid (including exact-bid) is 0, when it does not win the item.

The worst-case performance of overbidding is negative, when it wins the item and pays more than its value.

A Refined Safety Notion

- How does it apply to the first-price auction?

​

Discrete First-price Auction with DSL

Discrete First-price Auction with DSL

Ok… and how about VCG under Sybil Attacks?

Exact-bidding Strategies can come in many forms

10

10

30

30

10

10

10

10

20

10

6

20

10

4

An Attacker Can Benefit From an Exact-Bidding Attack

10

10

15

15

10

10

5

5

20

5

5

Conclusion

• We saw two models of VCG under uncertainty
• If the attacker knows a distribution over the agents’ types, in many cases truthfulness is a BNE.
• If the attacker doesn’t know a distribution, it is prudent to follow a DSL strategy.
• But then, given DSL attackers, we are still guaranteed optimal welfare!

​

​

​

​

Future Work?

Bids:

3 rooms, 5000$ total

8 rooms, 10000$ total

1 room, 2000$ total

…

​

Future Work cont.

• Can we design an auction for the general single-minded case that is BNE Sybil-proof with O(1) welfare?

​

• With exact-bidding strategies, VCG can have arbitrarily low revenue for the seller.
• Is there an auction so that DSL Sybil attackers guarantee O(1) revenue?
• Is there a computationally efficient auction with good welfare guarantees under DSL?
• Our argument both for the first-price auction and for VCG under Sybil uses discretization of the bid space.

Is it possible to design a polynomially-bound discretization that guarantees O(1) welfare with DSL?

​

​

​

​

​