Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Mohar, Bojan ; Shinkar, Igor ; O'Donnell, Ryan (Ed.)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 buyeroffering 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 buyeroffering mechanism is Bayesian incentive compatible, but the seller has a dominant strategy. We prove the buyeroffering 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 incentivecompatible mechanism can provide an approximation ratio better than 1+ln2/2ā 1.346.more » « lessFree, publiclyaccessible full text available June 11, 2025

Mohar, Bojan ; Shinkar, Igor ; O'Donnell, Ryan (Ed.)We present a constantfactor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configurationtype LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constantfactor approximation for submodular valuations with value queries can also be derived from our framework.more » « lessFree, publiclyaccessible full text available June 11, 2025

Mohar, Bojan ; Shinkar, Igor ; O'Donnell, Ryan (Ed.)We present a constantfactor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines that (1) solve a congurationtype LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constantfactor approximation for submodular valuations with value queries can also be derived from our framework.more » « lessFree, publiclyaccessible full text available June 10, 2025