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

​

​

P.h.D Thesis Committee, Technion, September 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 in the 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 recall 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

…

​

Collaborative ML: A Growing Interest…

Building shared models – a simple use case

• Two real estate marketplaces want to predict house prices
• Users randomly go to each, so the joint data should better predict
• They want to run linear regression of the price vs. square ft
• They want to keep updating the model as more data is added

Great… Where is the problem?

• There are works that study strategic data sharing:
• Disincentives to effort exertion in collecting data [Blum et. al 21’]
• Privacy concerns [Dwork et. al 06’, …]
• Mutually beneficial information design in competitive markets [Gradwohl & Tennenholtz 21’,22’]
• Partitioning into coalitions of shared model building [Donahue & Kleinberg 21’]

Other works study how competition changes the nature of individual learning (without sharing):

• Designing models to take over a submarket [Ben-Porat and Tennenholtz 19’]
• Trading off bias and variance when learning under competition [Feng et. al 22’]

​

We talk about a different security risk we call exclusivity attacks

• Exclusivity attack – by sending distorted data, a firm can learn the best model fit, but also mislead the other firm. (Though top priority is to learn the best model)
• This is an understudied attack [Shoham & Tennenholtz 2005] [Kantarcioglu and Jiang 2013]

One-shot vs long-term

• Data collaboration is usually a long-term project with ongoing updates
• + Risk: An attacker has the option to submit multiple updates and learn more
• Simple example: [Kantarcioglu and Jiang 2013] show that average can not be learnt in one-shot. But with two samples, it can be.
• Sybil attacks make blocking this hard
• + Benefit: An attacker must consider future consequences of data corruption

​

Main Question:

• Given a communication protocol and learning algorithm,

where all agents report truthfully and accept the model estimation

can an attacker deviate successfully with an exclusivity attack?

​

Main Results Preview:

• Continuous Protocol:

​

​

​

​

• Periodic Protocol: d-LR, k-Center are not vulnerable.

​

​

A successful attack with one-shot data sharing

• Max
• Agent 1 has the number 10.
• Agent 2 has the number 20.
• If they share truthfully, they both know the max is 20.
• If agent 1 sends 25 instead…
• Agent 2 now thinks the true max is 25
• Can agent 1 know the true max for sure?

A failed attack with one-shot data sharing

Formal model – Continuous Protocol

Running Example – Continuous Protocol

Revisiting max in the continuous protocol.

Here 90 < y < x.

Agent 1 is strategic. Agent 2 is truthful.

Observed history, Strategy and Vulnerability

Observed history, Strategy and Vulnerability (Cont.)

​

​

​

​

• We consider deviations from truthfulness, i.e., all other agents act truthfully.

​

Linear regression

Challenge Intuition:

How to ‘reverse’ effects of fake points submitted?

A sneak attack

• What if the line of the last output and the new update (by itself) are the same?

Triangulation attacks

High level construction of triangulation for LR

Example of a triangulation attack (1-LR)

Under truth

Under triangulation

Example of a triangulation attack (2-LR)

The periodic communication model

In periodic model, LR is not vulnerable

��Take away messages:�����

• The choice of protocol matters for security against exclusivity attacks, and this might require sacrifice of high availability
• The # Sybils an attacker controls matters for the security of the system, and we derive exact bounds
• Implications for federated learning (obscuring learning parameters)

Bounds on Power Indices in Weighted Voting Games

“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...”

​

(The Anti-Federalist Papers)

A model of weighted voting games…

Power and proportion may not coincide…

Power and proportion may not coincide II…

Power and proportion may not coincide III…

Summary of the bounds we prove

We believe (and this is supported by experiments) that the Shapley-Shubik upper bound of 2 holds not only against proportion, but any type of false-name split.

The implication would be that splitting is not too bad for the big players (as a whole).