## Abstract

We study the bilateral trade problem where a seller owns a single indivisible item, and a potential buyer seeks to purchase it. Previous mechanisms for this problem only considered the case where the values of the buyer and the seller are drawn from independent distributions. In contrast, this paper studies bilateral trade mechanisms when the values are drawn from a joint distribution. We prove that the buyer-offering mechanism guarantees an approximation ratio of e/e-1 ≈ 1.582 to the social welfare even if the values are drawn from a joint distribution. The buyer-offering mechanism is Bayesian incentive compatible, but the seller has a dominant strategy. We prove the buyer-offering mechanism is optimal in the sense that no Bayesian mechanism where one of the players has a dominant strategy can obtain an approximation ratio better than e/e-1. We also show that no mechanism in which both sides have a dominant strategy can provide any constant approximation to the social welfare when the values are drawn from a joint distribution. Finally, we prove some impossibility results on the power of general Bayesian incentive compatible mechanisms. In particular, we show that no deterministic Bayesian incentive-compatible mechanism can provide an approximation ratio better than 1+ln2/2≈ 1.346.

Original language | English |
---|---|

Title of host publication | STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing |

Editors | Bojan Mohar, Igor Shinkar, Ryan O�Donnell |

Pages | 237-246 |

Number of pages | 10 |

ISBN (Electronic) | 9798400703836 |

DOIs | |

Publication status | Published - 10 Jun 2024 |

Event | 56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada Duration: 24 Jun 2024 → 28 Jun 2024 |

### Publication series

Series | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|

### Conference

Conference | 56th Annual ACM Symposium on Theory of Computing, STOC 2024 |
---|---|

Country/Territory | Canada |

City | Vancouver |

Period | 24/6/24 → 28/6/24 |

### Bibliographical note

Work supported by ISF grant 2185/19 and BSF-NSF grant (BSF number: 2021655, NSFnumber: 2127781).

Publisher Copyright:

© 2024 Owner/Author.

## All Science Journal Classification (ASJC) codes

- Software