tinsir888
commented
2 months ago Presentation Sketch of This Paper:
Strategic Setting
The Fair allocation algorithm can be seen as MECHANISM.
- It receive the inputs (bids) of players, and output the allocation results.
Agents are strategic players:
- Each player has incentive to misreport her value for the goods in order to get better bundle with higher valuations.
- The payoff of each player is the true valuation she holds for her allocated bundle.
Questions we ask
- Does there always exist Pure Nash Equilibrium (abbr. PNE)?
- Does the output of mechanism with PNE input comply with fairness notion?
Main Results
The paper explore 2 methods: Round-Robin and Cut-and-Choose. Both of them have PNE.
The 3 main results:
- Round-Robin (abbr. RR): For $n$ strategic agents, $m$ goods, if RR receives the PNE input, output allocation is EF1 w.r.t. all players' true valuation. (hard☠️)
- Cut-and-Choose: For $2$ strategic agents, $m$ goods, if it receives the PNE input, output allocation is EFX + MMS w.r.t. true valuation. (easy😄)
- For any mechanism has EFX-Equilibrium, the output is EFX + (better than 2/3)-MMS allocation w.r.t. true valuation. (hard☠️)
RR
Let agent $1$ be the first to choose the item in each round.
Lemma 1: if all the agents are truth-telling, agent $1$ is EF-satisfied. (trivial😄)
- Because in each round, agent $1$ always choose her favorite one among the remaining goods.
RR is a non-truthful mechanism.
Theorem 3: For $2$ agents, every PNE input, the output of RR is EF1.
- Proof by contradiction and equilvalence between PROP and EF for $n=2$. (easy😄)
Theorem 4: For $\ge3$ agents, every PNE input, the output of RR is EF1. (VERY HARD☠️)
- Proof by theorem 5.
Theorem 5: If $\mathbf b1$ is Best Response (BR) to $\mathbf b{-1}$, agent $1$ is EF-satisfied with $A_1$.
- Result of $RR(\mathbf b1,\mathbf b{-1})$ is EF-satisfied to agent $1$ w.r.t. $\mathbf b_1$.
- By lemma 2, result of $RR(\mathbf b1,\mathbf b{-1})$ also produce $A_1$.
- By 2. and 3. of lemma 2, agent $1$ is EF-satisfied w.r.t. $v_1$.
Lemma 2 (VERY HARD☠️): If BR $\mathbf b_1$ induces strict preference and $RR(\mathbf b1,\mathbf b{-1})$ produces $A_1$, there exist $v_1^*$ s.t.
- $\mathbf b_1=v_1^$
- $v_1^*(A_1)=v_1(A_1)$
- $v_1^*(g)=v_1(g)\forall g\not\in A_1$
- $RR(\mathbf b1*,\mathbf b{-1})$ also produces $A_1$.
Cut-and-Choose
It's also a non-truthful mechanism.
Algorithm Detail
- Sort the goods in decreasing order according to agent $1$'s bids.
- Agent $1$ allocates each good to bundle with currently lower bundle.
- Agent $2$ choose one of the bundle according to her bids.
Lemma 4: Agent $1$ can manimuplate partition whatever she wants. (easy😄)
Thus by strategic bidding, agent $1$ can force $\min(v_1(A_1),v_1(A_2))\ge\mu_1$. (MMS-satisfied to agent $1$)
Theorem 6: For $2$ agents and PNE inputs, Cut-and-Choose derivates MMS + EFX.
- For agent $1$, she can be MMS-satisfied by manipulating her bids.
- For agent $2$, she choose the better between the two, trivially $v_2(A_2)\ge v_2(M)/2$, which is also MMS-satisfied.
EFX Nash Equilibria
Consider all mechanisms that have PNE for every instance, and these equilibria always lead to EFX allocations.
For general EFX allocation, its 2/3-MMS (2/3 is tight bound). In this part, this paper proves that with PNE input, these mechanisms produce EFX + (better than 2/3)MMS.
https://tinsir888.github.io/posts/fd26edcc.html
Objective: Investigate strategic aspects of fair division, considering Pure Nash equilibria and fairness. Activities: Review the paper Allocating Indi