Research (Google Scholar, dblp)



Working papers


U2 Metric Distortion under Group-Fair Objectives
with E. Anshelevich, C. Jerrett, A. A. Voudouris
[arXiv version]
U1 Algorithmically Fair Maximization of Multiple Submodular Objectives
with G. Birmpas, P. Lazos, S. Leonardi, and R. Reiffenhäuser
[arXiv version]

Journal publications


 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, forthcoming
[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


C27 Pushing the Frontier on Approximate EFX Allocations
with A. Filos-Ratsikas, and A. Sgouritsa
EC 2024, 25th ACM conference on Economics and Computation
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]
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]
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