More Like this

1. Fairness and Incentive Compatibility via Percentage Fees

   https://doi.org/10.1145/3580507  

   Dobzinski, Shahar; Oren, Sigal; Vondrak, Jan (July 2023, ACM)

   Leyton-Brown, Kevin; Samuelson, Larry; Hartline, Jason D (Ed.)

   We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentivecompatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a widely used charging method (e.g., royalties, a lawyer that charges some percentage of possible future compensation), we suggest charging the players some percentage of their value of the outcome. We call this model the percentage fee model. We show that there is a mechanism that maximizes exactly the Nash Social Welfare in every setting with non-negative valuations. Moreover, we prove an analog of Roberts theorem that essentially says that if the valuations are non-negative, then the only implementable social choice functions are those that maximize weighted variants of the Nash Social Welfare. We develop polynomial time incentive compatible approximation algorithms for the Nash Social Welfare with subadditive valuations and prove some hardness results. 

   more » « less
2. Fairness and Incentive Compatibility via Percentage Fees

   Dobzinski, Shahar; Oren, Sigal; Vondrak, Jan (July 2023, ACM)

   We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentive-compatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a widely used charging method (e.g., royalties, a lawyer that charges some percentage of possible future compensation), we suggest charging the players some percentage of their value of the outcome. We call this model the percentage fee model. We show that there is a mechanism that maximizes exactly the Nash Social Welfare in every setting with non-negative valuations. Moreover, we prove an analog of Roberts theorem that essentially says that if the valuations are non-negative, then the only implementable social choice functions are those that maximize weighted variants of the Nash Social Welfare. We develop polynomial time incentive compatible approximation algorithms for the Nash Social Welfare with subadditive valuations and prove some hardness results. 

   more » « less
3. Learning Revenue-Maximizing Auctions With Differentiable Matching

   Curry, Michael J.; Lyi, Uro; Goldstein, Tom; Dickerson, John P. (January 2022, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics)

   We propose a new architecture to approximately learn incentive compatible, revenue-maximizing auctions from sampled valuations. Our architecture uses the Sinkhorn algorithm to perform a differentiable bipartite matching which allows the network to learn strategyproof revenue-maximizing mechanisms in settings not learnable by the previous RegretNet architecture. In particular, our architecture is able to learn mechanisms in settings without free disposal where each bidder must be allocated exactly some number of items. In experiments, we show our approach successfully recovers multiple known optimal mechanisms and high-revenue, low-regret mechanisms in larger settings where the optimal mechanism is unknown. 

   more » « less
4. Why Do Heterosporous Plants Have So Few Chromosomes?

   https://doi.org/10.3389/fpls.2022.807302  

   Kinosian, Sylvia P.; Rowe, Carol A.; Wolf, Paul G. (February 2022, Frontiers in Plant Science)

   The mechanisms controlling chromosome number, size, and shape, and the relationship of these traits to genome size, remain some of the least understood aspects of genome evolution. Across vascular plants, there is a striking disparity in chromosome number between homosporous and heterosporous lineages. Homosporous plants (comprising most ferns and some lycophytes) have high chromosome numbers compared to heterosporous lineages (some ferns and lycophytes and all seed plants). Many studies have investigated why homosporous plants have so many chromosomes. However, homospory is the ancestral condition from which heterospory has been derived several times. Following this phylogenetic perspective, a more appropriate question to ask is why heterosporous plants have so few chromosomes. Here, we review life history differences between heterosporous and homosporous plants, previous work on chromosome number and genome size in each lineage, known mechanisms of genome downsizing and chromosomal rearrangements, and conclude with future prospects for comparative research. 

   more » « less
5. Information Elicitation from Rowdy Crowds

   https://doi.org/10.1145/3442381.3449840  

   Schoenebeck, Grant; Yu, Fang-Yi; Zhang, Yichi (April 2021, Proceedings of the Web Conference (WWW '21))

   We initiate the study of information elicitation mechanisms for a crowd containing both self-interested agents, who respond to incentives, and adversarial agents, who may collude to disrupt the system. Our mechanisms work in the peer prediction setting where ground truth need not be accessible to the mechanism or even exist. We provide a meta-mechanism that reduces the design of peer prediction mechanisms to a related robust learning problem. The resulting mechanisms are ϵ-informed truthful, which means truth-telling is the highest paid ϵ-Bayesian Nash equilibrium (up to ϵ-error) and pays strictly more than uninformative equilibria. The value of ϵ depends on the properties of robust learning algorithm, and typically limits to 0 as the number of tasks and agents increase. We show how to use our meta-mechanism to design mechanisms with provable guarantees in two important crowdsourcing settings even when some agents are self-interested and others are adversarial. 

   more » « less