Degree of Truthfulness
for Risk-Avoiding Agents
Speaker: Eden Hartman (Bar-Ilan University)
Joint With:
Erel Segal-Halevi
(Ariel University)
Biaoshuai Tao
(Shanghai Jiao Tong University)
Social Choice
Q: How to aggregate individual preferences into one collective choice?
Mechanism
A collective choice
Examples: Voting, Fair Division, Matching….
A Truthful Mechanism
Telling the truth is a dominant strategy for all agents
A Truthful Mechanism
Telling the truth is a dominant strategy for all agents
A Truthful Mechanism
Telling the truth is a dominant strategy for all agents
A Truthful Mechanism
Telling the truth is a dominant strategy for all agents
| Joint report 1 | Joint report 2 | Joint report 3 | Joint report 4 | Joint report 5 | Joint report 6 | … |
Tell the Truth | | | | | | | |
Manipulation 1 | | | | | | | |
Manipulation 2 | | | | | | | |
Manipulation 3 | | | | | | | |
Manipulation 4 | | | | | | | |
Always at-least as good
Sometimes strictly better
Truthfulness is the dream
Telling the truth is a dominant strategy for all agents
Truthfulness is the dream
Many impossibility results
Truthfulness is the dream
Many impossibility results
Indivisible Goods Allocations:
[Amanatidis, Birmpas, Christodoulou, and Markakis, 2017]
Cake Cutting:
Voting:
[Gibbard, 1973; Satterthwaite, 1975]
Two-Sided Matching:
Examples:
Truthfulness is the dream
Many impossibility results
Goal: Mechanisms that are close to truthfulness
Goal: Mechanisms that are close to truthfulness
Computational Complexity
Regret-Free Truth-Telling
Incentive Ratio
Probability of Having Profitable Manipulation
Risk-Avoiding Truthfulness
(RAT)
Maximin Strategy-Proofness
Not-Obviously Manipulable
Queries and Bits
And many more…
Computational Complexity
Computational Complexity
Computational Complexity
Getting information
Informational
The amount of information on others
necessary to enable good manipulations
Degree of Truthfulness
The amount of information on others
necessary to enable good manipulations
Degree of Truthfulness
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Truthful
Not Truthful
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Truthful
Not Truthful
n
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Sometimes Profitable, Never Harmful
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Risk-Avoiding Truthfulness (RAT)
For agents who avoid risk from not knowing others’ preferences
[Bu, Song, and Tao, 2023]
Sometimes Profitable, Never Harmful
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Risk-Avoiding Truthfulness (RAT)
For agents who avoid risk from not knowing others’ preferences
[Bu, Song, and Tao, 2023]
Sometimes Profitable, Never Harmful
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Risk-Avoiding Truthfulness (RAT)
For agents who avoid risk from not knowing others’ preferences
[Bu, Song, and Tao, 2023]
Sometimes Profitable, Never Harmful
The number of “known-agents”
necessary to enable good manipulations
Degree of Truthfulness
Sometimes Profitable, Never Harmful
Risk-Avoiding Truthfulness (RAT)
For agents who avoid risk from not knowing others’ preferences
[Bu, Song, and Tao, 2023]
The number of “known-agents”
necessary to enable good manipulations
RAT
Degree
Risk-Avoiding Truthfulness (RAT)
For agents who avoid risk from not knowing others’ preferences
[Bu, Song, and Tao, 2023]
Sometimes Profitable, Never Harmful
The number of “known-agents”
necessary to enable good manipulations
RAT
Degree
Worst case for the mechanism designer
Does there exist a situation
for which this number is sufficient?
The number of “known-agents”
necessary to enable good manipulations
RAT
Degree
Single Good Auctions
Indivisible Goods Allocations
Cake Cutting
Two-Sided Matching
Single-Winner Voting
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
Single Good Auctions
Second Price
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
Single Good Auctions
First Price
Second Price
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
Single Good Auctions
First Price
Second Price
First Price
with Discount
Value = 100
Known-Agents
Bid 105
Discount = 20$
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
Single Good Auctions
First Price
Second Price
First Price
with Discount
Avg. Between
First & Second Prices
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
Single Good Auctions
First Price
Second Price
First Price
with Discount
Avg. Between
First & Second Prices
Value = 100
Known-Agents
Unknown-Agents
n-2
Bid 90?
Bid 95
Max = 80
Truthful
Not Truthful
n
0
1
2
3
n-1
…
n-2
Single Good Auctions
First Price
Second Price
First Price
with Discount
Avg. Between
First & Second Prices
For any weighted average!
Single-Good Auctions
Single-Good Auctions
Combinatorial auctions?
With more than 5 goods, EF1 is incompatible with truthfulness
[Amanatidis, Birmpas, Christodoulou, and Markakis, 2017]
Indivisible Goods Allocations
Degree of max Nash-welfare mechanism?
Non-additive utilities?
Proportionality and EF is incompatible with truthfulness [Tao, 2022]
Cake Cutting
Proportionality and EF is incompatible with truthfulness [Tao, 2022]
Cake Cutting
Even-Paz?
n/2?
Max Nash welfare?
With three or more candidates, the only truthful rules are dictatorships
[Gibbard, 1973; Satterthwaite, 1975]
Single-Winner Voting
Degree of non-positional voting rules?
Degree of multi-winner voting rules?
No stable matching mechanism is truthful for all agents [Roth, 1982]
Two-Sided Matching
No stable matching mechanism is truthful for all agents [Roth, 1982]
Highest degree for stable matching mechanisms?
Two-Sided Matching
Stable matching mechanism with higher degree?
Open Questions
Please contact us for any question and any answer!
eden.r.hartman@gmail.com erelsgl@gmail.com bstao@sjtu.edu.cn
Open Questions
Please contact us for any question and any answer!
eden.r.hartman@gmail.com erelsgl@gmail.com bstao@sjtu.edu.cn
Goal: Mechanisms that are less likely to be manipulated
Computational Complexity
Regret-Free Truth-Telling
Incentive Ratio
Probability of Having Profitable Manipulation
Risk-Avoiding Truthfulness
(RAT)
Maximin Strategy-Proofness
Not-Obviously Manipulable
Queries and Bits
And many more…
The next step after information
Incomparable between different domains
Requires knowledge of the distribution over preference profiles
Only for numerical valuations
Our approach can also be combined with other types of manipulations
Truthful | Truth-telling is a dominant strategy | |
RAT (Risk-Avoiding Truthful) | No strategy dominates truth-telling | |
Relation of the RAT-degree to previous definition: