Collective schedules: axioms and algorithms. (English) Zbl 1519.91106
Kanellopoulos, Panagiotis (ed.) et al., Algorithmic game theory. 15th international symposium, SAGT 2022, Colchester, UK, September 12–15, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13584, 454-471 (2022).
Summary: The collective schedules problem consists in computing a schedule of tasks shared between individuals. Tasks may have different duration, and individuals have preferences over the order of the shared tasks. This problem has numerous applications since tasks may model public infrastructure projects, events taking place in a shared room, or work done by co-workers. Our aim is, given the preferred schedules of individuals (voters), to return a consensus schedule. We propose an axiomatic study of the collective schedule problem, by using classic axioms in computational social choice and new axioms that take into account the duration of the tasks. We show that some axioms are incompatible, and we study the axioms fulfilled by three rules: one which has been studied in the seminal paper on collective schedules [F. Pascual et al., “Collective schedules: scheduling meets computational social choice”, in: Proceedings of the 17th international conference on autonomous agents and multiagent systems, AAMAS 2018. New York, NY: Association for Computing Machinery (ACM). 667–675 (2018; doi:10.5555/3237383.3237482)], one which generalizes the Kemeny rule, and one which generalizes Spearman’s footrule. From an algorithmic point of view, we show that these rules solve NP-hard problems, but that it is possible to solve optimally these problems for small but realistic size instances, and we give an efficient heuristic for large instances. We conclude this paper with experiments.
For the entire collection see [Zbl 1515.91014].
For the entire collection see [Zbl 1515.91014].
MSC:
| 91B14 | Social choice |
| 90B35 | Deterministic scheduling theory in operations research |
| 91A68 | Algorithmic game theory and complexity |
References:
| [1] | Agnetis, A.; Billaut, JC; Gawiejnowicz, S.; Pacciarelli, D.; Soukhal, A., Multiagent Scheduling. Models and Algorithms (2014), Heidelberg: Springer, Heidelberg · Zbl 1286.90002 · doi:10.1007/978-3-642-41880-8 |
| [2] | Asudeh, A., Jagadish, H.V., Stoyanovich, J., Das, G.: Designing fair ranking schemes. In: Proceedings of the 2019 International Conference on Management of Data, SIGMOD 2019, pp. 1259-1276. Association for Computing Machinery (2019). doi:10.1145/3299869.3300079 |
| [3] | Aziz, H.; Shah, N.; Rudas, T.; Péli, G., Participatory budgeting: models and approaches, Pathways Between Social Science and Computational Social Science, 215-236 (2021), Cham: Springer, Cham · doi:10.1007/978-3-030-54936-7_10 |
| [4] | Bartholdi, J.; Tovey, CA; Trick, MA, Voting schemes for which it can be difficult to tell who won the election, Soc. Choice Welf., 6, 2, 157-165 (1989) · Zbl 0672.90004 · doi:10.1007/BF00303169 |
| [5] | Biega, A.J., Gummadi, K.P., Weikum, G.: Equity of attention: amortizing individual fairness in rankings. In: The 41st International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2018, pp. 405-414. Association for Computing Machinery (2018). doi:10.1145/3209978.3210063 |
| [6] | Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; Procaccia, AD, Handbook of Computational Social Choice (2016), Cambridge: Cambridge University Press, Cambridge · Zbl 1436.91001 · doi:10.1017/CBO9781107446984 |
| [7] | Brucker, P., Scheduling Algorithms (2010), Heidelberg: Springer, Heidelberg · Zbl 1060.90034 |
| [8] | Celis, L.E., Straszak, D., Vishnoi, N.K.: Ranking with fairness constraints. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming, ICALP. LIPIcs, vol. 107, pp. 28:1-28:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018). doi:10.4230/LIPIcs.ICALP.2018.28 · Zbl 1499.68399 |
| [9] | Condorcet, M.-J.-N.C.M.: Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (1785) |
| [10] | Conitzer, V., Davenport, A., Kalagnanam, J.: Improved bounds for computing Kemeny rankings. In: AAAI, vol. 6, pp. 620-626 (2006) |
| [11] | Diaconis, P., Graham, R.: Spearman’s footrule as a measure of disarray. Stanford University, Department of Statistics (1976) · Zbl 0375.62045 |
| [12] | Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods for the web. In: Shen, V.Y., Saito, N., Lyu, M.R., Zurko, M.E. (eds.) Proceedings of the Tenth International World Wide Web Conference, WWW, pp. 613-622. ACM (2001). doi:10.1145/371920.372165 |
| [13] | Geyik, S.C., Ambler, S., Kenthapadi, K.: Fairness-aware ranking in search and recommendation systems with application to linkedin talent search. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019, pp. 2221-2231. Association for Computing Machinery (2019). doi:10.1145/3292500.3330691 |
| [14] | Kemeny, JG, Mathematics without numbers, Daedalus, 88, 4, 577-591 (1959) |
| [15] | Luce, R.D.: Individual Choice Behavior: A Theoretical Analysis. Courier Corporation (2012) · Zbl 0093.31708 |
| [16] | Narasimhan, H., Cotter, A., Gupta, M., Wang, S.L.: Pairwise fairness for ranking and regression. In: 33rd AAAI Conference on Artificial Intelligence (2020) |
| [17] | Pascual, F., Rzadca, K., Skowron, P.: Collective schedules: scheduling meets computational social choice. In: Seventeenth International Conference on Autonomous Agents and Multiagent Systems, July 2018. https://hal.archives-ouvertes.fr/hal-01744728 |
| [18] | Plackett, R.L.: The analysis of permutations. J. Roy. Stat. Soc. Ser. C (Appl. Stat.) 24(2), 193-202 (1975). doi:10.2307/2346567. https://www.jstor.org/stable/2346567 |
| [19] | Saule, E., Trystram, D.: Multi-users scheduling in parallel systems. In: 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS, pp. 1-9. IEEE (2009). doi:10.1109/IPDPS.2009.5161037 · Zbl 1214.68104 |
| [20] | Singh, A., Joachims, T.: Fairness of exposure in rankings. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2018, pp. 2219-2228. Association for Computing Machinery (2018). doi:10.1145/3219819.3220088 |
| [21] | Skowron, P., Lackner, M., Brill, M., Peters, D., Elkind, E.: Proportional rankings. In: Sierra, C. (ed.) Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI, pp. 409-415. ijcai.org (2017). doi:10.24963/ijcai.2017/58 |
| [22] | Talmon, N., Faliszewski, P.: A framework for approval-based budgeting methods. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2181-2188 (2019) |
| [23] | Wan, L.; Yuan, J., Single-machine scheduling to minimize the total earliness and tardiness is strongly NP-hard, Oper. Res. Lett., 41, 4, 363-365 (2013) · Zbl 1286.90068 · doi:10.1016/j.orl.2013.04.007 |
| [24] | Young, HP; Levenglick, A., A consistent extension of Condorcet’s election principle, SIAM J. Appl. Math., 35, 2, 285-300 (1978) · Zbl 0385.90010 · doi:10.1137/0135023 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
