Research (Google Scholar, dblp)

Working papers

U2	Metric Distortion under Group-Fair Objectives with E. Anshelevich, C. Jerrett, A. A. Voudouris [arXiv version]
U1	On the Tractability Landscape of Conditional Minisum Approval Voting Rule with M. Lampis, E. Markakis, and G. Papasotiropoulos

Journal publications

J17	Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria with G. Birmpas, P. Lazos, S. Leonardi, and R. Reiffenhäuser Mathematics of Operations Research, forthcoming [arXiv version] Supersedes the EC 2023 paper below.
J16	Approximately Sampling and Counting Graphs with Near-Regular Degree Intervals with P. Kleer SIAM Journal on Discrete Mathematics, forthcoming [arXiv version] Supersedes the STACS 2023 paper below.
J15	Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness with G. Birmpas, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser Mathematics of Operations Research, forthcoming [arXiv version] Supersedes the WINE 2021 paper below.
J14	Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris SIAM Journal on Discrete Mathematics, Vol. 38(1), 1007–1029, 2024 [arXiv version] Supersedes the NeurIPS 2022 paper below.
J13	Fair Division of Indivisible Goods: Recent Progress and Open Questions with H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu Artificial Intelligence, Vol. 322, 103965, 2023 [arXiv version] Supersedes the IJCAI 2022 survey below.
J12	A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris Journal of Artificial Intelligence Research, Vol. 74, 227–261, 2022 [arXiv version] Supersedes the AAAI 2021 paper below.
J11	Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint with F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser Journal of Artificial Intelligence Research, Vol. 74, 661-690, 2022 [arXiv version] Supersedes the NeurIPS 2020 paper below.
J10	Rapid mixing of the switch Markov chain for 2-class joint degree matrices with P. Kleer SIAM Journal on Discrete Mathematics, Vol. 36(1), 118-146, 2022 [journal version] Partially supersedes the SODA 2019 paper below.
J9	Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online with P. Kleer and G. Schäfer Mathematics of Operations Research, Vol. 47(3), 2286-2309, 2022 [arxiv version] Supersedes the EC 2019 paper below.
J8	Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results with P. Fulla, E. Markakis, and K. Sornat Theoretical Computer Science, Vol. 871, 62-78, 2021 [arXiv version] Supersedes the MFCS 2016 paper below.
J7	Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris Artificial Intelligence, Vol. 296, 103488, 2021 [arxiv version] Supersedes the AAAI 2020 paper below.
J6	Maximum Nash welfare and other stories about EFX with G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris Theoretical Computer Science, Vol. 863, 69-85, 2021 [arXiv version] Supersedes the IJCAI 2020 paper below.
J5	A Simple Deterministic Algorithm for Symmetric Submodular Maximization Subject to a Knapsack Constraint with G. Birmpas and E. Markakis Information Processing Letters, Vol. 163, 106010, 2020 [journal version]
J4	Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination with E. Markakis and A. Ntokos Theoretical Computer Science, Vol. 841, 94-109, 2020 [arXiv version] Supersedes the AAAI 2020 paper below.
J3	Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences with P. Kleer Random Structures & Algorithms, Vol. 57, 637-657, 2020 [journal version] Partially supersedes the SODA 2019 paper below.
J2	Connected Realizations of Joint-Degree Matrices with B. Green and M. Mihail Discrete Applied Mathematics, Vol. 250, 65-74, 2018 [journal version] Partially supersedes the DIMACS Workshop poster below.
J1	Approximation Algorithms for Computing Maximin Share Allocations with E. Markakis, A. Nikzad, and A. Saberi ACM Transactions on Algorithms, Vol. 13(4), 52:1-52:28, 2017 [arXiv version] Supersedes the ICALP 2015 paper below.

Conference publications

C29	Algorithmically Fair Maximization of Multiple Submodular Objectives with G. Birmpas, P. Lazos, S. Leonardi, and R. Reiffenhäuser AAMAS 2025, 24th International Conference on Autonomous Agents and Multi-Agent Systems [arXiv version]
C28	Pandora's Box Problem Over Time with F. Fusco, R. Reiffenhäuser, and A. Tsikiridis WINE 2024, 20th Conference on Web and Internet Economics [arXiv version]
C27	Pushing the Frontier on Approximate EFX Allocations with A. Filos-Ratsikas, and A. Sgouritsa EC 2024, 25th ACM conference on Economics and Computation [arXiv version]
C26	On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes with A. Filos-Ratsikas, P. Lazos, E. Markakis, G. Papasotiropoulos AAMAS 2024, 23rd International Conference on Autonomous Agents and Multi-Agent Systems [arXiv version]
C25	Partial Allocations in Budget-Feasible Mechanism Design: Bridging Multiple Levels of Service and Divisible Agents with S. Klumper, E. Markakis, G. Schäfer, A. Tsikiridis WINE 2023, 19th Conference on Web and Internet Economics [arXiv version]
C24	Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria with G. Birmpas, P. Lazos, S. Leonardi, and R. Reiffenhäuser EC 2023, 24th ACM conference on Economics and Computation [arXiv version] Superseded by the MOR paper above.
C23	Approximately Sampling and Counting Graphs with Near-Regular Degree Intervals with P. Kleer STACS 2023, 40th International Symposium on Theoretical Aspects of Computer Science [arXiv version] Superseded by the SIDMA paper above.
C22	Don't Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris NeurIPS 2022, 36th Conference on Neural Information Processing Systems [arXiv version] Superseded by the SIDMA paper above.
C21	Decentralised Update Selection with Semi-Strategic Experts with G. Birmpas, P. Lazos, F. Marmolejo-Cossío SAGT 2022, 15th International Symposium on Algorithmic Game Theory [arXiv version]
C20	Fair Division of Indivisible Goods: A Survey with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris IJCAI 2022 - Survey Track, 30th International Joint Conference on Artificial Intelligence [arXiv version] Superseded by the ARTINT paper above.
C19	Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness with G. Birmpas, F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser WINE 2021, 17th Conference on Web and Internet Economics Best Paper Award [arXiv version] Superseded by the MOR paper above.
C18	Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity with F. Fusco, P. Lazos, S. Leonardi, A. Marchetti-Spaccamela, and R. Reiffenhäuser ICML 2021, 38th International Conference on Machine Learning [arXiv version]
C17	A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris AAAI 2021, 35th AAAI Conference on Artificial Intelligence [arXiv version] Superseded by the JAIR paper above.
C16	Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint with F. Fusco, P. Lazos, S. Leonardi, and R. Reiffenhäuser NeurIPS 2020, 34th Conference on Neural Information Processing Systems [arXiv version] Appeared as a poster in HALG 2021. Superseded by the JAIR paper above.
C15	Maximum Nash Welfare and Other Stories About EFX with G. Birmpas, A. Filos-Ratsikas, A. Hollender, and A. A. Voudouris IJCAI 2020, 29th International Joint Conference on Artificial Intelligence [arXiv version] Superseded by the TCS paper above.
C14	Peeking Behind the Ordinal Curtain: Improving Distortion via Cardinal Queries with G. Birmpas, A. Filos-Ratsikas, and A. A. Voudouris AAAI 2020, 34th AAAI Conference on Artificial Intelligence [arxiv version] Superseded by the ARTINT paper above.
C13	Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination with E. Markakis and A. Ntokos AAAI 2020, 34th AAAI Conference on Artificial Intelligence [arxiv version] Superseded by the TCS paper above.
C12	Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online with P. Kleer and G. Schäfer EC 2019, 20th ACM conference on Economics and Computation [arxiv version] Superseded by the MOR paper above.
C11	Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices with P. Kleer SODA 2019, 30th Annual ACM-SIAM Symposium on Discrete Algorithms [arxiv version] Superseded by the RSA paper and the SIDMA paper above.
C10	An Improved Envy-Free Cake Cutting Protocol for Four Agents with G. Christodoulou, J. Fearnley, E. Markakis, C.-A. Psomas, and E. Vakaliou SAGT 2018, 11th International Symposium on Algorithmic Game Theory [arXiv version] Appeared as a poster in WINE 2017.
C9	Comparing Approximate Relaxations of Envy-Freeness with G. Birmpas and E. Markakis IJCAI 2018, 27th International Joint Conference on Artificial Intelligence [arXiv version] Also presented at the COMSOC 2018 workshop.
C8	On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives with G. Birmpas and E. Markakis WINE 2017, 13th Conference on Web and Internet Economics [arXiv version]
C7	Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness with G. Birmpas, G. Christodoulou, and E. Markakis EC 2017, 18th ACM conference on Economics and Computation [arXiv version]
C6	Coverage, Matching, and Beyond: New Results on Budgeted Mechanism Design with G. Birmpas and E. Markakis WINE 2016, 12th Conference on Web and Internet Economics [arXiv version]
C5	Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results with E. Markakis and K. Sornat MFCS 2016 , 41st International Symposium on Mathematical Foundations of Computer Science [arXiv version] Also presented at the AGT@IJCAI 2016 workshop. Superseded by the TCS paper above.
C4	On Truthful Mechanisms for Maximin Share Allocations with G. Birmpas and E. Markakis IJCAI 2016, 25th International Joint Conference on Artificial Intelligence [arXiv version] Also presented at the COMSOC 2016 workshop, and appeared as a poster in WINE 2016.
C3	Approximation Algorithms for Computing Maximin Share Allocations with E. Markakis, A. Nikzad, and A. Saberi ICALP 2015 (A) , 42nd International Colloquium on Automata, Languages, and Programming [arXiv version] Also appeared as a poster in WINE 2015. Superseded by the TALG paper above.
C2	Multiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulability with N. Barrot, J. Lang, E. Markakis, and B. Ries AAMAS 2015, 14th International Conference on Autonomous Agents and Multiagent Systems [AAMAS version]
C1	Provably-Secure Schemes for Basic Query Support in Outsourced Databases with A. Boldyreva and A. O'Neill DBSec 2007, 21st IFIP WG11.3 Working Conference on Data and Application Security [DBSec version]

Theses

T2	Algorithmic and Mechanism Design Aspects of Problems with Limited—or no—Payments PhD Thesis, Athens University of Economics and Business, August 2017 Advisor: Asst. Prof. Vangelis Markakis [thesis]
T1	Probabilisticaly Checkable Proofs and Hardness of Approximation (in Greek) Diploma Thesis, National Technical University of Athens, July 2004 Advisor: Prof. Stathis Zachos

Other

O3	Flexible Models for Complex Networks with M. Mihail and S. Young WebSci 2009, 1st Web Science Conference: Society On-Line [WebSci version] Also appeared as a poster at the ARC2 GaTech workshop (October 2008).
O2	Graphic Realizations of Joint-Degree Matrices with B. Green and M. Mihail DIMACS Workshop on New Directions in Algorithms, Combinatorics and Optimization, 2008, Poster [arXiv version] Partially superseded by the DAM paper above.
O1	Side-Channel Attacks with S. Zachos and V. Zikas Workshop on Internet-Education-Science, Pristina, Serbia, 2004