Publications

Sort by: Date | Author | Title

Caragiannis, I., Gravin, N. & Jiang, Z. (2025). On the Satisfiability of Random 3-SAT Formulas with k-Wise Independent Clauses. In A. Benoit, H. Kaplan, S. Wild, S. Wild & G. Herman (Eds.), 33rd Annual European Symposium on Algorithms, ESA 2025 Article 103 Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ESA.2025.103

Jiang, Z. (2025). Randomness in Structures and Computation. [PhD thesis, Aarhus University].

Caragiannis, I., Mehlhorn, K. & Rathi, N. (2025). Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity. Proceedings of the AAAI Conference on Artificial Intelligence, 39(13), 13675-13682. https://doi.org/10.1609/aaai.v39i13.33494

Caragiannis, I., Micha, E. & Peters, J. (2024). Can a Few Decide for Many? The Metric Distortion of Sortition. In R. Salakhutdinov, Z. Kolter & K. Heller (Eds.), Proceedings of the 41st International Conference on Machine Learning (ICML) (Vol. 235, pp. 5660-5679). Article 220 JMLR.org.

Caragiannis, I. & Homrighausen, S. (2024). Estimating the Expected Social Welfare and Cost of Random Serial Dictatorship. In G. Schäfer & C. Ventre (Eds.), Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings (pp. 184–201). Springer. https://doi.org/10.1007/978-3-031-71033-9_11

Burkhardt, J., Caragiannis, I., Fehrs, K., Russo, M., Schwiegelshohn, C. & Shyam, S. (2024). Low-Distortion Clustering with Ordinal and Limited Cardinal Information. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9), 9555-9563. https://doi.org/10.1609/aaai.v38i9.28811

Caragiannis, I., Hansen, K. A. & Rathi, N. (2024). On the Complexity of Pareto-Optimal and Envy-Free Lotteries. In AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (pp. 244-252). Association for Computing Machinery. https://dl.acm.org/doi/10.5555/3

Caragiannis, I. & Rathi, N. (2024). Optimizing Over Serial Dictatorships. Theory of Computing Systems, 68(5), 1180-1206. https://doi.org/10.1007/s00224-024-10196-6

Filos-Ratsikas, A., Hansen, K. A., Høgh, K. & Hollender, A. (2024). PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization. In B. Mohar, I. Shinkar & R. O'Donnell (Eds.), STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing (pp. 1204-1215). Association for Computing Machinery. https://doi.org/10.1145/3618260.3649645

Caragiannis, I. & Kalantzis, G. (2024). Randomized learning-augmented auctions with revenue guarantees. In K. Larson (Ed.), Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI) (pp. 2687-2694). International Joint Conferences on Artificial Intelligence.

Caragiannis, I. & Narang, S. (2024). Repeatedly matching items to agents fairly and efficiently. Theoretical Computer Science, 981, Article 114246. https://doi.org/10.1016/j.tcs.2023.114246

Caragiannis, I., Christodoulou, G. & Protopapas, N. (2024). Truthful aggregation of budget proposals with proportionality guarantees. Artificial Intelligence, 335, Article 104178. https://doi.org/10.1016/j.artint.2024.104178

Caragiannis, I., Filos-Ratsikas, A., Frederiksen, S. K. S., Hansen, K. A. & Tan, Z. (2024). Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship. Mathematical Programming, 203(1-2), 901-930. https://doi.org/10.1007/S10107-022-01902-8

Caragiannis, I., Filos-Ratsikas, A., Nath, S. & Voudouris, A. (2024). Truthful ownership transfer with expert advice. Mathematical Programming, 203(1-2), 871-900. https://doi.org/10.1007/s10107-022-01834-3

Bilò, V., Hansen, K. A. & Mavronicolas, M. (2023). Computational Complexity of Decision Problems About Nash Equilibria in Win-Lose Multi-player Games. In A. Deligkas & A. Filos-Ratsikas (Eds.), Algorithmic Game Theory: SAGT 2023 (pp. 40-57). Springer. https://doi.org/10.1007/978-3-031-43254-5_3

Caragiannis, I. & Jiang, Z. (2023). Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming. In B. Saha & R. A. Servedio (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 710-722). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585236

Barman, S., Khan, A., Shyam, S. & Sreenivas, K. V. N. (2023). Guaranteeing Envy-Freeness under Generalized Assignment Constraints. EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation, 242-269. https://doi.org/10.1145/3580507.3597698

Caragiannis, I., Christodoulou, G. & Protopapas, N. (2023). Impartial Selection with Prior Information. In Y. Ding, J. Tang, J. Sequeda, L. Aroyo, C. Castillo & G.-J. Houben (Eds.), WWW '23: Proceedings of the ACM Web Conference 2023 (pp. 3614-3624). Association for Computing Machinery. https://doi.org/10.1145/3543507.3583553

Caragiannis, I., Garg, J., Rathi, N., Sharma, E. & Varricchio, G. (2023). New Fairness Concepts for Allocating Indivisible Items. In E. Elkind (Ed.), IJCAI '23: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 2554-2562). Article 284 Association for Computing Machinery.

Caragiannis, I. & Rathi, N. (2023). Optimizing over Serial Dictatorships. In A. Deligkas & A. Filos-Ratsikas (Eds.), Algorithmic Game Theory: 16th International Symposium, SAGT 2023, Egham, UK, September 4–7, 2023, Proceedings (pp. 329-346). Springer. https://doi.org/10.1007/978-3-031-43254-5_19

Caragiannis, I. & Schwartzbach, N. I. (2023). Outsourcing Adjudication to Strategic Jurors. In E. Elkind (Ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 2546-2553). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2023/283

Airiau, S., Aziz, H., Caragiannis, I., Kruger, J., Lang, J. & Peters, D. (2023). Portioning using ordinal preferences: Fairness and efficiency. Artificial Intelligence, 314, Article 103809. https://doi.org/10.1016/j.artint.2022.103809

Caragiannis, I. & Narang, S. (2023). Repeatedly Matching Items to Agents Fairly and Efficiently. In A. Deligkas & A. Filos-Ratsikas (Eds.), Algorithmic Game Theory: 16th International Symposium, SAGT 2023, Egham, UK, September 4–7, 2023, Proceedings (pp. 347-364). Springer. https://doi.org/10.1007/978-3-031-43254-5_20

Caragiannis, I. & Narang, S. (2023). Repeatedly Matching Items to Agents Fairly and Efficiently. In AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (pp. 2670-2672). Association for Computing Machinery.

Bouras, C., Caragiannis, I., Gkamas, A., Protopapas, N., Sardelis, T. & Sgarbas, K. (2023). State of the Art Analysis of Resource Allocation Techniques in 5G MIMO Networks. In 37th International Conference on Information Networking, ICOIN 2023 (pp. 632-637). IEEE. https://doi.org/10.1109/ICOIN56518.2023.10049018

Hansen, K. A., Ibsen-Jensen, R. & Neyman, A. (2023). The Big Match with a Clock and a Bit of Memory. Mathematics of Operations Research, 48(1), 419-432. https://doi.org/10.1287/moor.2022.1267

Brânzei, S., Filos-Ratsikas, A., Miltersen, P. B. & Zeng, Y. (2023). Walrasian pricing in multi-unit auctions. Artificial Intelligence, 322, Article 103961. https://doi.org/10.1016/j.artint.2023.103961

Caragiannis, I., Micha, E. & Shah, N. (2022). A Little Charity Guarantees Fair Connected Graph Partitioning. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4908-4916. https://doi.org/10.1609/aaai.v36i5.20420

Bilo, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C. & Zwicker, W. (2022). Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131, 197-221. https://doi.org/10.1016/j.geb.2021.11.006

Caragiannis, I., Gkatzelis, V., Psomas, A. & Schoepflin, D. (2022). Beyond Cake Cutting: Allocating Homogeneous Divisible Goods. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022) (pp. 208-216). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Caragiannis, I., Kanellopoulos, P. & Voudouris, A. A. (2022). Bounding the Inefficiency of Compromise in Opinion Formation. Algorithmica, 84(1), 234-271. https://doi.org/10.1007/s00453-021-00892-x

Caragiannis, I. & Ioannidis, S. D. (2022). Computing Envy-Freeable Allocations with Limited Subsidies. In M. Feldman, H. Fu & I. Talgam-Cohen (Eds.), Web and Internet Economics : 17th International Conference, WINE 2022 (pp. 522-539). Springer. https://doi.org/10.1007/978-3-030-94676-0_29

Caragiannis, I., Kaklamanis, C., Karanikolas, N. & Krimpas, G. (2022). Evaluating approval-based multiwinner voting in terms of robustness to noise. Autonomous Agents and Multi-Agent Systems, 36(1), Article 1. https://doi.org/10.1007/s10458-021-09530-w

Aziz, H., Caragiannis, I., Igarashi, A. & Walsh, T. (2022). Fair allocation of indivisible goods and chores. Autonomous Agents and Multi-Agent Systems, 36(1), Article 3. https://doi.org/10.1007/s10458-021-09532-8

Barman, S., Khan, A., Shyam, S. & Sreenivas, K. V. N. (2022). Finding Fair Allocations under Budget Constraints. arxiv.org. https://doi.org/10.48550/arXiv.2208.08168

Filos-Ratsikas, A., Hansen, K. A., Hogh, K. & Hollender, A. (2022). FIXP-membership via Convex Optimization: Games, Cakes, and Markets. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (pp. 827-838). IEEE. https://doi.org/10.1109/FOCS52979.2021.00085

Caragiannis, I., Christodoulou, G. & Protopapas, N. (2022). Impartial Selection with Additive Approximation Guarantees. Theory of Computing Systems, 66(3), 721-742. https://doi.org/10.1007/s00224-022-10081-0

Berthelsen, M. L. T. & Hansen, K. A. (2022). On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. Theory of Computing Systems, 66(3), 519-545. https://doi.org/10.1007/s00224-022-10080-1

Caragiannis, I., Gravin, N., Lu, P. & Wang, Z. (2022). Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching. In M. Feldman, H. Fu & I. Talgam-Cohen (Eds.), Web and Internet Economics : 17th International Conference, WINE 2021 (pp. 131-148). Springer. https://doi.org/10.1007/978-3-030-94676-0_8

Caragiannis, I. & Fehrs, K. (2022). The Complexity of Learning Approval-Based Multiwinner Voting Rules. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4925-4932. https://doi.org/10.1609/aaai.v36i5.20422

Caragiannis, I., Shah, N. & Voudouris, A. A. (2022). The metric distortion of multiwinner voting. Artificial Intelligence, 313, Article 103802. https://doi.org/10.1016/j.artint.2022.103802

Caragiannis, I., Shah, N. & Voudouris, A. A. (2022). The Metric Distortion of Multiwinner Voting. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4900-4907. https://doi.org/10.1609/aaai.v36i5.20419

Caragiannis, I., Christodoulou, G. & Protopapas, N. (2022). Truthful Aggregation of Budget Proposals with Proportionality Guarantees. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4917-4924. https://doi.org/10.1609/aaai.v36i5.20421

Hansen, K. A., Liu, T. X. & Malekian, A. (Eds.) (2022). Web and Internet Economics: 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings. Springer. Lecture Notes in Computer Science Vol. 13778 https://doi.org/10.1007/978-3-031-22832-2

Hansen, K. A., Ibsen-Jensen, R. & Neyman, A. (2021). Absorbing games with a clock and two bits of memory. Games and Economic Behavior, 128, 213-230. https://doi.org/10.1016/j.geb.2021.04.008

Caragiannis, I. & Hansen, K. A. (Eds.) (2021). Algorithmic Game Theory: 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, Proceedings. Springer. Lecture Notes in Computer Science https://doi.org/10.1007/978-3-030-85947-3

Hansen, K. A. & Lund, T. B. (2021). Computational Complexity of Computing a Quasi-Proper Equilibrium. In E. Bampis & A. Pagourtzis (Eds.), Fundamentals of Computation Theory - 23rd International Symposium, FCT 2021, Proceedings: 23rd International Symposium, FCT 2021 Athens, Greece, September 12–15, 2021 Proceedings (pp. 259-271). Springer. https://doi.org/10.1007/978-3-030-86593-1_18

Blanc, M. & Hansen, K. A. (2021). Computational Complexity of Multi-player Evolutionarily Stable Strategies. In R. Santhanam & D. Musatov (Eds.), Computer Science – Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Proceedings: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings (pp. 1-17). Springer. https://doi.org/10.1007/978-3-030-79416-31

Caragiannis, I. & Fanelli, A. (2021). On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Journal of Computer and System Sciences, 117, 40-48. https://doi.org/10.1016/j.jcss.2020.10.007

Caragiannis, I., Kanellopoulos, P. & Kyropoulou, M. (2021). On Interim Envy-Free Allocation Lotteries. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC 2021) (pp. 264-284). Association for Computing Machinery. https://doi.org/10.1145/3465456.3467648

Displaying results 1 to 50 out of 219

Sort by: Date | Author | Title

Revised 01.09.2025