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

​

​

EconCS Seminar, Hebrew University, July 2024

​

Yotam Gafni

Weizmann Institute

Moshe Tennenholtz

Ron Lavi

Based on my PhD work with my advisors:

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, even if all bidders are single-minded and we are not limited computationally [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]

​

​

A Model of Weighted Voting Games (WVGs)

Sybil Attacks in Weighted Voting Games

Past Results for This Model and Related Work

​

• Square root seat assignment [Penrose ‘46]
• “Double” square root (choosing the threshold) [Slomczynski and Zyczkowski ‘06, ‘07]
• “Quota games” [Zick, Skopalik, and Elkind ‘11, Oren, Filmus, Zick, and Bachrach ’14, …]
• “P-power”: The ability to extract rent or bribes, as measured by a power index [Felsenthal & Machover ’05, Young ‘78]

​

​

​

• First work to study Sybil attacks in WVGs: [Aziz, Bachrach, Elkind & Paterson ‘11]
• Upper and lower bounds for a single agent to split her vote into two parts (Shapley-Shubik and Banzhaf)
• NP-hard to determine the gain from splitting the vote into two equal parts (both indices, reduction from partition)
• PP-complete [Faliszewski & Hemaspaandra ‘09, Rey & Rothe ‘14]

​

Our Goal

Spoiler: We can guarantee something, for some indices…

As a numerical example:

• If the small players sum up to 70% of total votes, under Shapley-Shubik they are guaranteed 40% of the power even with arbitrary Sybil attacks.
• If the small players sum up to 90% of total votes, under Shapley-Shubik they are guaranteed 80% of the power even with arbitrary Sybil attacks.
• If the small players sum up to 30% of total votes, under Shapley-Shubik, …

​

It will be more convenient to talk about Big players bounds

So, Recap:

This Goes Back At Least to the 18th Century…

“The number of delegates ought not to be in exact proportion to the number of inhabitants, because the influence and power of those states whose delegates are numerous, will be greater [even relative to their proportion] when compared to the influence and power of the other states...”

​

(Luther Martin, The Anti-Federalist Papers)

Let’s see some examples

Power and proportion may not coincide II…

Time for Proofs!

Shapley-Shubik – It’s just induction

Some useful definitions and arithmetics…

Some justified simplifying assumptions…

Now we just do the induction over T

What’s Wrong with Banzhaf?

What’s Wrong with Banzhaf?

Deegan-Packel – Separate to Two Regimes

The example is the same as for Shapley

In the high-threshold regime, in any coalition the big players can not be ‘too many’ of this coalition.

​

In the low-threshold regime, there must be at least twice as many pure small player coalitions than ones that contain big players, because we are on the ‘lower side’ of the binomial (and big players push us even lower).

What’s next?

For the math folks in the crowd…

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

…

​