research-article

Free access

When Online Dating Meets Nash Social Welfare: Achieving Efficiency and Fairness

Authors:

Wei XuAuthors Info & Claims

WWW '18: Proceedings of the 2018 World Wide Web Conference

Pages 429 - 438

https://doi.org/10.1145/3178876.3186109

Published: 23 April 2018 Publication History

All formats PDF

Abstract

Mobile dating applications such as Coffee Meets Bagel, Tantan, and Tinder, have become significant for young adults to meet new friends and discover romantic relationships. From a system designer's perspective, in order to achieve better user experience in these applications, we should take both the efficiency and fairness of a dating market into consideration, so as to increase the overall satisfaction for all users. Towards this goal, we investigate the nature of diminishing marginal returns for online dating markets (i.e., captured by the submodularity), and trade-off between the efficiency and fairness of the market with Nash social welfare. We further design effective online algorithms to the apps. We verify our models and algorithms through sound theoretical analysis and empirical studies by using real data and show that our algorithms can significantly improve the ecosystems of the online dating applications.

References

[1]

Coffee Meets Bagel. https://coffeemeetsbagel.com/.

[2]

TanTan. https://tantanapp.com/en/.

[3]

Tinder. https://www.gotinder.com/.

[4]

15% of American Adults Have Used Online Dating Sites or Mobile Dating Apps. Retrived from http://www.pewinternet.org/2016/02/11/15-percent-of-american- adults-have-used-online-dating-sites-or-mobile-dating-apps/, 2016.

[5]

Marie Claire. Tinder: The Online Dating App Everyone's Talking About. Retrived from http://www.marieclaire.co.uk/life/sex-and-relationships/tinder-the- online-dating-app-that-everyone-s-talking-about-112522, 2017.

[6]

Cosmo's Dating App School. Cosmopolitan, 2017.

[7]

Tantan, China's top dating app, raises $70M for monetization push and overseas expansion. Retrived from https://techcrunch.com/2017/06/21/chinas-tantan-raises- 70-million/, 2017.

[8]

Maria Zhang. Retrived from http://tech.gotinder.com/building-tinder/. In Tinder Tech Blog: Building Tinder, 2016.

[9]

Günter J. Hitsch, Ali Hortaçsu, and Dan Ariely. What makes you click? mate preferences in online dating. Quantitative marketing and Economics, 2010.

[10]

Medium. Retrived from https://medium.com/@worstonlinedater/tinder- experiments-ii-guys-unless-you-are-really-hot-you-are-probably-better-off-not-wasting-your-2ddf370a6e9a. In Tinder Experiments II: Guys, unless you are really hot you are probably better off not wasting your time on Tinder -- a quantitative socio-economic study, 2015.

[11]

Jessica Strubel and Trent A Petrie. Love me tinder: Body image and psychosocial functioning among men and women. Body Image, 2017.

[12]

Gareth Tyson, Vasile C. Perta, Hamed Haddadi, and Michael C. Seto. A first look at user activity on tinder. In Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2016.

Digital Library

[13]

S. R. Sumter, L. Vandenbosch, and L. Ligtenberg. Love me Tinder: Untangling emerging adults motivations for using the dating application Tinder. Telematics and Informatics, 2017.

Digital Library

[14]

Christopher J. Carpenter and Bree McEwan. The players of micro-dating: Individ- ual and gender differences in goal orientations toward micro-dating apps. First Monday, 2016.

[15]

J. Ward. What are you doing on Tinder? impression management on a matchmaking mobile app. Information, Communication & Society, 2016.

[16]

Gábor Orosz, István Tóth-Király, Beáta Bőthe, and Dóra Melher. Too many swipes for today: The development of the problematic tinder use scale. Journal of Behavioral Addictions, 2016.

[17]

Camille Cobb and Tadayoshi Kohno. How Public Is My Private Life? Privacy in Online Dating. In Proceedings of the 26th International Conference on World Wide Web (WWW), 2017.

Digital Library

[18]

Olga Abramova, Annika Baumann, and Hanna Krasnova. Gender differences in online dating: What do we know so far?. In Hawaii International Conference on System Sciences (HICSS), 2016.

Digital Library

[19]

Jennie Zhang and Taha Yasseri. What happens after you both swipe right: A statistical description of mobile dating communications. arXiv preprint arXiv:1607.03320, 2016.

[20]

Günter J. Hitsch, Ali Hortaçsu, and Dan Ariely. Matching and Sorting in Online Dating. The American Economic Review, 2010.

[21]

Jean-Charles Rochet and Jean Tirole. Two-Sided Markets: An Overview. mimeo: MIT, 2004.

[22]

M. Keith Chen. Dynamic Pricing in a Labor Market: Surge Pricing and Flexible Work on the Uber Platform. In Proceedings of the ACM Conference on Economics and Computation, 2016.

Digital Library

[23]

Zhixuan Fang, Longbo Huang, and Adam Wierman. Prices and Subsidies in the Sharing Economy. In Proceedings of the 26th International Conference on World Wide Web (WWW), 2017.

Digital Library

[24]

Yongzheng Jia, Wei Xu, and Xue Liu. An Optimization Framework For On- line Ride-sharing Markets. In IEEE International Conference on Distributed Computing Systems (ICDCS), 2017.

[25]

Google Adwords. https://adwords.google.com.

[26]

Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 2013.

Digital Library

[27]

Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S. Mirrokni, and Cliff Stein. Online Stochastic Packing Applied to Display Ad Allocation. In European Symposium on Algorithms (ESA), 2010.

Digital Library

[28]

Subhash Khot, Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Inap- proximability results for combinatorial auctions with submodular utility functions. In Proceedings of the international conference on Internet and Network Economics (WINE), 2005.

Digital Library

[29]

Vahab Mirrokni, Michael Schapira, and Jan Vondrak. Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In Proceedings of the conference on Electronic commerce (EC), 2008.

Digital Library

[30]

Jan Vondrak. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the annual ACM symposium on Theory of computing (STOC), 2008.

Digital Library

[31]

Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In Proceedings of the IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2012.

Digital Library

[32]

Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. In Proceedings of the ACM conference on Electronic Commerce (EC), 2001.

Digital Library

[33]

Michael Kapralov, Ian Post, and Jan Vondrák. Online submodular welfare maxi- mization: Greedy is optimal. In Proceedings of the annual ACM-SIAM symposium on discrete algorithm (SODA), 2013.

Digital Library

[34]

Nitish Korula, Vahab Mirrokni, and Morteza. Online submodular welfare maxi- mization: Greedy beats 1/2 in random order. In Proceedings of the annual ACM symposium on Theory of computing (STOC), 2015.

Digital Library

[35]

John Nash. The Bargaining Problem. Econometrica 18, 2, 1950.

[36]

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. In Proceedings of the ACM Conference on Economics and Computation (EC), 2016.

Digital Library

[37]

Euiwoong Lee. APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items. Information Processing Letters 122, 17--20, 2017.

[38]

Simina Branzei, Vasilis Gkatzelis, and Ruta Mehta. Nash social welfare approxi- mation for strategic agents. In Proceedings of the ACM Conference on Economics and Computation (EC), 2017.

Digital Library

[39]

Richard Cole and Vasilis Gkatzelis. Approximating the nash social welfare with indivisible items. In Proceedings of the annual ACM symposium on Theory of computing, 2015.

Digital Library

[40]

Jugal Garg, Martin Hoefer, and Kurt Mehlhorn. Approximating the nash social welfare with budget-additive valuations. In Arxiv: 1707.04428v1, 2017.

[41]

Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Arxiv: 1707.04731, 2017.

[42]

Sara Ramezani and Ulle Endriss. Nash Social Welfare in Multiagent Resource Allocation. Lecture Notes in Business Information Processing, 2010.

[43]

Hervé Moulin. Fair Division and Collective Welfare. Public Choice, 2004.

[44]

Edmund Eisenberg and David Gale. Consensus of Subjective Probabilities: The Pari-Mutuel Method. The Annals of Mathematical Statistics 30, 1, 1959.

[45]

Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), 2010.

Digital Library

[46]

Vinod Thomas, Yan Wang, and Xibo Fan. Measuring education inequality : Gini coefficients of education. Policy Research Working Papers, 2001.

Cited By

Do VUsunier NAmigo ECastells PGonzalo JCarterette BCulpepper JKazai G(2022)Optimizing Generalized Gini Indices for Fairness in RankingsProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3477495.3532035(737-747)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3477495.3532035
Pidoux JKuntz PGatica-Perez D(2021)Declarative Variables in Online DatingProceedings of the ACM on Human-Computer Interaction10.1145/34491745:CSCW1(1-32)Online publication date: 22-Apr-2021
https://dl.acm.org/doi/10.1145/3449174
Peng AGu F(2020)Interface culture and gendered privacy risks in the context of Chinese locative social media useSocial Identities10.1080/13504630.2020.1814725(1-16)Online publication date: 3-Sep-2020
https://doi.org/10.1080/13504630.2020.1814725

Index Terms

When Online Dating Meets Nash Social Welfare: Achieving Efficiency and Fairness
1. Applied computing
  1. Law, social and behavioral sciences
2. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms

Recommendations

Nash Social Welfare Approximation for Strategic Agents
EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation

The fair division of resources among strategic agents is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist mechanisms that can implement fair outcomes, ...
Online Nash Welfare Maximization Without Predictions
Web and Internet Economics
Abstract
The maximization of Nash welfare, which equals the geometric mean of agents’ utilities, is widely studied because it balances efficiency and fairness in resource allocation problems. Banerjee, Gkatzelis, Gorokh, and Jin (2022) recently introduced ...
Approximating the nash social welfare with budget-additive valuations
SODA '18: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms

We present the first constant-factor approximation algorithm for maximizing the Nash social welfare when allocating indivisible items to agents with budget-additive valuation functions. Budget-additive valuations represent an important class of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

WWW '18: Proceedings of the 2018 World Wide Web Conference

April 2018

2000 pages

ISBN:9781450356398

General Chairs:
Pierre-Antoine Champin
Universitè Claude Bernard Lyon 1, France
,
Fabien Gandon
Inria, Université Côte d'Azur, CNRS, I3S, France
,
Lionel Médini
Université Claude Bernard Lyon 1, France
,
Program Chairs:
Mounia Lalmas
Spotify, UK
,
Panagiotis G. Ipeirotis
New York University, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IW3C2: International World Wide Web Conference Committee

In-Cooperation

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

International World Wide Web Conferences Steering Committee

Republic and Canton of Geneva, Switzerland

Publication History

Published: 23 April 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Tsinghua Initiative Research Program Grant

Conference

WWW '18

Sponsor:

IW3C2

WWW '18: The Web Conference 2018

April 23 - 27, 2018

Lyon, France

Acceptance Rates

WWW '18 Paper Acceptance Rate 170 of 1,155 submissions, 15%;

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
1,416
Total Downloads

Downloads (Last 12 months)295
Downloads (Last 6 weeks)40

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Do VUsunier NAmigo ECastells PGonzalo JCarterette BCulpepper JKazai G(2022)Optimizing Generalized Gini Indices for Fairness in RankingsProceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3477495.3532035(737-747)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3477495.3532035
Pidoux JKuntz PGatica-Perez D(2021)Declarative Variables in Online DatingProceedings of the ACM on Human-Computer Interaction10.1145/34491745:CSCW1(1-32)Online publication date: 22-Apr-2021
https://dl.acm.org/doi/10.1145/3449174
Peng AGu F(2020)Interface culture and gendered privacy risks in the context of Chinese locative social media useSocial Identities10.1080/13504630.2020.1814725(1-16)Online publication date: 3-Sep-2020
https://doi.org/10.1080/13504630.2020.1814725

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents