Publications

Sort by: Date | Author | Title

Caragiannis, I., Micha, E. & Shah, N. (2022). A Little Charity Guarantees Fair Connected Graph Partitioning. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Vol. 11, pp. 4908-4916). AAAI Press. Proceedings of the AAAI Conference on Artificial Intelligence Vol. 36 No. 5 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). Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS Vol. 1

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 13112 LNCS 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), [1]. https://doi.org/10.1007/s10458-021-09530-w

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. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS https://doi.org/10.1109/FOCS52979.2021.00085

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

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

Limaye, N., Srinivasan, S. & Tavenas, S. (2022). On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In S. Lovett (Ed.), 37th Computational Complexity Conference, CCC 2022 [32] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 234 https://doi.org/10.4230/LIPIcs.CCC.2022.32

Curticapean, R., Limaye, N. & Srinivasan, S. (2022). On the VNP-Hardness of Some Monomial Symmetric Polynomials. In A. Dawar & V. Guruswami (Eds.), 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022 [16] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 250 https://doi.org/10.4230/LIPIcs.FSTTCS.2022.16

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 13112 LNCS https://doi.org/10.1007/978-3-030-94676-0_8

Tavenas, S., Limaye, N. & Srinivasan, S. (2022). Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. In S. Leonardi & A. Gupta (Eds.), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 416-425). Association for Computing Machinery. Proceedings of the Annual ACM Symposium on Theory of Computing https://doi.org/10.1145/3519935.3520044

Limaye, N., Srinivasan, S. & Tavenas, S. (2022). Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. In Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021 (pp. 804-814). IEEE Computer Society. https://doi.org/10.1109/FOCS52979.2021.00083

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

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

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

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

Bhandari, S., Harsha, P., Saptharishi, R. & Srinivasan, S. (2022). Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. In S. Lovett (Ed.), 37th Computational Complexity Conference, CCC 2022 [31] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 234 https://doi.org/10.4230/LIPIcs.CCC.2022.31

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 Athens, Greece, September 12–15, 2021 Proceedings (pp. 259-271). Springer. Lecture Notes in Computer Science Vol. 12867 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, Sochi, Russia, June 28–July 2, 2021, Proceedings (pp. 1-17). Springer. Lecture Notes in Computer Science Vol. 12730 https://doi.org/10.1007/978-3-030-79416-31

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. EC 2021 - Proceedings of the 22nd ACM Conference on Economics and Computation https://doi.org/10.1145/3465456.3467648

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

Srinivasan, S. & Venkitesh, S. (2021). On the probabilistic degree of an n-variate boolean function. In M. Wootters & L. Sanita (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021 [42] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 207 https://doi.org/10.4230/LIPIcs-APPROX/RANDOM.2021.42

Caragiannis, I., Filos-Ratsikas, A., Kanellopoulos, P. & Vaish, R. (2021). Stable Fractional Matchings. Artificial Intelligence, 295, [103416]. https://doi.org/10.1016/j.artint.2020.103416

Batziou, E., Hansen, K. A. & Høgh, K. (2021). Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In N. Bansal, E. Merelli & J. Worrell (Eds.), 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (Vol. 198, pp. 24:1-24:20). Schloss Dagstuhl--Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Vol. 198 https://doi.org/10.4230/LIPIcs.ICALP.2021.24

Caragiannis, I. & Voudouris, A. (2021). The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users. Mathematics of Operations Research, 46(2), 503-523. https://doi.org/10.1287/moor.2020.1070

Babai, L., Hansen, K. A., Podolskii, V. V. & Sun, X. (2021). Weights of exact threshold functions. Izvestiya: Mathematics, 85(6), 1039-1059. https://doi.org/10.1070/IM9113

Hansen, K. A. & Sølvsten, S. C. (2020). ∃R-completeness of stationary nash equilibria in perfect information stochastic games. In J. Esparza & D. Král (Eds.), 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020 (pp. 45:1-45:15). Schloss Dagstuhl--Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Vol. 170 https://doi.org/10.4230/LIPIcs.MFCS.2020.45

Hansen, K. A. & Raskin, M. (2019). A Stay-in-a-Set Game without a Stationary Equilibrium. In J. Leroux & J-F. Raskin (Eds.), Proceedings Tenth International Symposium on Games, Automata, Logics, and Formal Verification (pp. 83-90). Electronic Proceedings in Theoretical Computer Science. https://doi.org/10.4204/EPTCS.305.6

Berthelsen, M. L. T. & Hansen, K. A. (2019). On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria. In D. Fotakis & E. Markakis (Eds.), Algorithmic Game Theory - 12th International Symposium, SAGT 2019, Proceedings (pp. 153-167). Springer VS. Lecture Notes in Computer Science Vol. 11801 https://doi.org/10.1007/978-3-030-30473-7_11

Branzei, S., Orlandi, C. & Yang, G. (2019). Sharing Information with Competitors. In D. Fotakis & E. Markakis (Eds.), Algorithmic Game Theory: SAGT 2019 (pp. 34-48). Springer. Lecture Notes in Computer Science Vol. 11801 https://doi.org/10.1007/978-3-030-30473-7

Hansen, K. A. (2019). The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. Theory of Computing Systems, 63(7), 1554-1571. https://doi.org/10.1007/s00224-018-9887-9

Dan, C., Hansen, K. A., Jiang, H., Wang, L. & Zhou, Y. (2018). Low rank approximation of binary matrices: Column subset selection and generalizations. In I. Potapov, J. Worrell & P. Spirakis (Eds.), 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018 (Vol. 117, pp. 41:1-41:16). [41] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics No. 117 https://doi.org/10.4230/LIPIcs.MFCS.2018.41

Bosanský, B., Brânzei, S., Hansen, K. A., Lund, T. B. & Miltersen, P. B. (2017). Computation of Stackelberg Equilibria of Finite Sequential Games. A C M Transactions on Economics and Computation, 5(4), 23:1-23:24. [23]. https://doi.org/10.1145/3133242

Chatterjee, K., Hansen, K. A. & Ibsen-Jensen, R. (2017). Strategy Complexity of Concurrent Safety Games. In K. G. Larsen, H. L. Bodlaender & J-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) (Vol. 83, pp. 55:1-55:13). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH. Leibniz International Proceedings in Informatics No. 83 https://doi.org/10.4230/LIPIcs.MFCS.2017.55

Hansen, K. A. (2017). The Real Computational Complexity of Minmax Value and Equilibrium Refinements in Multi-player Games. In V. Bilò & M. Flammini (Eds.), Algorithmic Game Theory - 10th International Symposium, SAGT 2017, Proceedings: 10th International Symposium, SAGT 2017 (pp. 119-130). Springer VS. Lecture Notes in Computer Science Vol. 10504 https://doi.org/10.1007/978-3-319-66700-3_10

Brânzei, S., Filos-Ratsikas, A., Miltersen, P. B. & Zeng, Y. (2017). Walrasian pricing in multi-unit auctions. In K. G. Larsen, H. L. Bodlaender & J-F. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017 (Vol. 83, pp. 80:1-80:14). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics No. 83 https://doi.org/10.4230/LIPIcs.MFCS.2017.80

Hansen, K. A., Ibsen-Jensen, R. & Koucký, M. (2016). The big match in small space. In M. Gairing & R. Savani (Eds.), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings (Vol. 9928, pp. 64-76). Springer VS. Lecture Notes in Computer Science Vol. 9928 https://doi.org/10.1007/978-3-662-53354-3_6

Caragiannis, I., Filos-Ratsikas, A., Frederiksen, S. K. S., Hansen, K. A. & Tan, Z. (2016). Truthful facility assignment with resource augmentation: An exact analysis of serial dictatorship. In Web and Internet Economics - 12th International Conference, WINE 2016, Proceedings (Vol. 10123, pp. 236-250). Springer VS. Lecture Notes in Computer Science Vol. 10123 https://doi.org/10.1007/978-3-662-54110-4_17

Branzei, S. & Miltersen, P. B. (2015). A Dictatorship Theorem for Cake Cutting. In Q. Yang & M. Wooldridge (Eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015) (pp. 481-488). AAAI Press. http://ijcai.org/papers15/Papers/IJCAI15-074.pdf

Branzei, S. (2015). A note on envy-free cake cutting with polynomial valuations. Information Processing Letters, 115(2), 93-95. https://doi.org/10.1016/j.ipl.2014.07.005

Branzei, S., Hosseini, H. & Miltersen, P. B. (2015). Characterization and Computation of Equilibria for Indivisible Goods. In Algorithmic Game Theory: 8th International Symposium, SAGT 2015, Saarbrücken, Germany, September 28–30, 2015, Proceedings (pp. 244-255). Springer VS. Lecture Notes in Computer Science Vol. 9347 https://doi.org/10.1007/978-3-662-48433-3_19

Bosansky, B., Branzei, S., Hansen, K. A., Miltersen, P. B. & Sørensen , T. B. (2015). Computation of Stackelberg Equilibria of Finite Sequential Games. In E. Markakis & G. Schäfer (Eds.), Web and Internet Economics: 11th International Conference, WINE 2015, Amsterdam, The Netherlands, December 9-12, 2015, Proceedings (Vol. 9470, pp. 201-215). Springer VS. Lecture Notes in Computer Science http://arxiv.org/abs/1507.07677

Branzei, S. (2015). Computational Fair Division. Department of Computer Science, Aarhus University.

Hansen, K. A. & Podolskii, V. V. (2015). Polynomial threshold functions and Boolean threshold circuits. Information and Computation, 240, 56-73. https://doi.org/10.1016/j.ic.2014.09.008

Displaying results 1 to 50 out of 221

Sort by: Date | Author | Title

Revised 09.03.2023