More Web Proxy on the site http://driver.im/

research-article

Proportionally fair online allocation of public goods with predictions

AUTHORs:

Siddhartha Banerjee,

Vasilis Gkatzelis,

Safwan Hossain,

Nisarg ShahAuthors Info & Claims

IJCAI '23: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

Article No.: 3, Pages 20 - 28

https://doi.org/10.24963/ijcai.2023/3

Published: 19 August 2023 Publication History

Abstract

We design online algorithms for the fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent's total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N,L)·T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.

References

[1]

Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. Advances in Neural Information Processing Systems, 34, 2021.

[2]

Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference on Machine Learning, pages 345- 355. PMLR, 2020.

[3]

Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33:7933-7944, 2020.

[4]

Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Learning-augmented dynamic power management with multiple states via new ski rental bounds. Advances in Neural Information Processing Systems, 34, 2021.

[5]

Yossi Azar, Niv Buchbinder, and Kamal Jain. How to allocate goods in an online market? Algorithmica, 74(2):589-601, 2016.

Digital Library

[6]

Haris Aziz and Nisarg Shah. Participatory budgeting: Models and approaches. In Pathways Between Social Science and Computational Social Science, pages 215-236. Springer, 2021.

[7]

Haris Aziz, Anna Bogomolnaia, and Hervé Moulin. Fair mixing: the case of dichotomous preferences. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 753-781, 2019.

Digital Library

[8]

Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094, 2020.

[9]

Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022. SIAM, 2022.

[10]

Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. Proportionally fair online allocation of public goods with predictions (full version). arXiv preprint arXiv:2209.15305, 2022.

[11]

Siddharth Barman, Arindam Khan, and Arnab Maiti. Universal and tight online algorithms for generalized-mean welfare. In The Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI. AAAI Press, 2022.

[12]

Gerdus Benade, Aleksandr M. Kazachkov, Ariel D. Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. InÉva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 593-610. ACM, 2018.

Digital Library

[13]

Anna Bogomolnaia, Hervé Moulin, and Richard Stong. Collective choice under dichotomous preferences. Journal of Economic Theory, 122(2):165-184, 2005.

[14]

Anna Bogomolnaia, Hervé Moulin, and Fedor Sandomirskiy. A simple online fair division problem. CoRR, abs/1903.10361, 2019.

[15]

Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005.

Digital Library

[16]

Florian Brandl, Felix Brandt, Dominik Peters, and Christian Stricker. Distribution rules under dichotomous preferences: Two out of three ain't bad. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 158-179, 2021.

Digital Library

[17]

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors. Fair Allocation, page 259-260. Cambridge University Press, 2016.

[18]

Niv Buchbinder and Joseph Naor. The design of competitive online algorithms via a primal-dual approach. Now Publishers Inc, 2009.

Digital Library

[19]

Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In Constantinos Daskalakis, Moshe Babaioff, and Hervé Moulin, editors, Proceedings of the 2017 ACM Conference on Economics and Computation, EC '17, Cambridge, MA, USA, June 26-30, 2017, pages 629-646. ACM, 2017.

Digital Library

[20]

Nikhil R Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 137-144, 2012.

Digital Library

[21]

Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances in Neural Information Processing Systems, 34, 2021.

[22]

Virginie Do, Matthieu Hervouin, Jérôme Lang, and Piotr Skowron. Online approval committee elections. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 251- 257, 2022.

[23]

Conal Duddy. Fair sharing under dichotomous preferences. Mathematical Social Sciences, 73:1-5, 2015.

[24]

Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 409-429, 2021.

Digital Library

[25]

Soroush Ebadian, Rupert Freeman, and Nisarg Shah. Efficient resource allocation with secretive agents. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), 2022.

[26]

Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized distortion and proportional fairness in voting. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022.

Digital Library

[27]

Brandon Fain, Ashish Goel, and Kamesh Munagala. The core of the participatory budgeting problem. In International Conference on Web and Internet Economics, pages 384-399. Springer, 2016.

Digital Library

[28]

Brandon Fain, Kamesh Munagala, and Nisarg Shah. Fair allocation of indivisible public goods. In Éva Tardos, Edith Elkind, and Rakesh Vohra, editors, Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 575-592. ACM, 2018.

Digital Library

[29]

Duncan K Foley. Lindahl's solution and the core of an economy with public goods. Econometrica: Journal of the Econometric Society, pages 66-72, 1970.

[30]

Rupert Freeman, Seyed Majid Zahedi, and Vincent Conitzer. Fair and efficient social choice in dynamic settings. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 4580-4587. ijcai.org, 2017.

[31]

Eric J. Friedman, Vasilis Gkatzelis, Christos-Alexandros Psomas, and Scott Shenker. Fair and efficient memory sharing: Confronting free riders. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 1965-1972. AAAI Press, 2019.

Digital Library

[32]

Jugal Garg, Pooja Kulkarni, and Aniket Murhekar. On fair and efficient allocations of indivisible public goods. In Proceedings of the 41st conference on Foundations of Software Technology and Theoretical Computer Science, number 22, pages 1-19, 2021.

[33]

Vasilis Gkatzelis, Alexandros Psomas, and Xizhi Tan. Fair and efficient online allocations with normalized valuations. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI. AAAI Press, 2021.

[34]

Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.

[35]

Frank P Kelly, Aman K Maulloo, and David Kim Hong Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research society, 49(3):237-252, 1998.

[36]

Mayuresh Kunjir, Brandon Fain, Kamesh Munagala, and Shivnath Babu. ROBUS: fair cache allocation for data-parallel workloads. In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017, pages 219-234. ACM, 2017.

Digital Library

[37]

Martin Lackner. Perpetual voting: Fairness in long-term decision making. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2103-2110, 2020.

[38]

Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.

[39]

Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3296-3305. PMLR, 2018.

[40]

Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms, page 646-662. Cambridge University Press, 2021.

[41]

Kamesh Munagala, Yiheng Shen, Kangning Wang, and Zhiyi Wang. Approximate core for committee selection via multilinear extension and market clearing. CoRR, abs/2110.12499, 2021.

[42]

John Nash. The bargaining problem. Econometrica, 18(2):155-162, April 1950.

[43]

Joel Oren and Brendan Lucier. Online (budgeted) social choice. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.

[44]

Dominik Peters, Grzegorz Pierczynski, and Piotr Skowron. Proportional participatory budgeting with cardinal utilities. CoRR, abs/2008.13276, 2020.

[45]

Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.

[46]

Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1834-1845. SIAM, 2020.

[47]

Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. Advances in Neural Information Processing Systems, 33:8150-8160, 2020.

[48]

David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. In Péter Biró, Jason Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, pages 911-912. ACM, 2020.

Digital Library

Cited By

Cohen SAgmon NDastani MSichman JAlechina NDignum V(2024)Near-Optimal Online Resource Allocation in the Random-Order ModelProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663113(2219-2221)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663113
Shah NElkind E(2023)Pushing the limits of fairness in algorithmic decision-makingProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/806(7051-7056)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/806
Zhang SHe X(2023)DProvDB: Differentially Private Query Processing with Multi-Analyst ProvenanceProceedings of the ACM on Management of Data10.1145/36267611:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626761

Index Terms

Proportionally fair online allocation of public goods with predictions
1. Theory of computation
  1. Design and analysis of algorithms
    1. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory

Index terms have been assigned to the content through auto-classification.

Recommendations

Proportionally fair distributed resource allocation in multiband wireless systems

A challenging problem in multiband multicell self-organized wireless systems, such as femtocells/picocells in cellular networks, multichannel Wi-Fi networks, and more recent wireless networks over TV white spaces, is of distributed resource allocation. ...
Online Unit Profit Knapsack with Predictions
Abstract
A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio ... $\frac{}{\overset{}{}}$ $\overset{}{}$ $\frac{}{}$ $\frac{}{}$ $\frac{}{}$ $\frac{}{}$ $\frac{}{}$
Proportional fair throughput allocation in multirate IEEE 802.11e wireless LANs

Under heterogeneous radio conditions, Wireless LAN stations may use different modulation schemes, leading to a heterogeneity of bit rates. In such a situation, 802.11 DCF allocates the same throughput to all stations independently of their transmitting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IJCAI '23: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

August 2023

7242 pages

ISBN:978-1-956792-03-4

Editor:
Edith Elkind

Copyright © 2023 International Joint Conferences on Artificial Intelligence.

Sponsors

International Joint Conferences on Artifical Intelligence (IJCAI)

Publisher

Unknown publishers

Publication History

Published: 19 August 2023

Qualifiers

Research-article
Research
Refereed limited

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cohen SAgmon NDastani MSichman JAlechina NDignum V(2024)Near-Optimal Online Resource Allocation in the Random-Order ModelProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663113(2219-2221)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663113
Shah NElkind E(2023)Pushing the limits of fairness in algorithmic decision-makingProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/806(7051-7056)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/806
Zhang SHe X(2023)DProvDB: Differentially Private Query Processing with Multi-Analyst ProvenanceProceedings of the ACM on Management of Data10.1145/36267611:4(1-27)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1145/3626761

View Options

View options

Media

Figures

Other

Tables

View Table of Contents