Vangelis Markakis

Associate Professor, Department of Informatics, Athens University of Economics and Business (AUEB)


Note: The list below contains only certain selected publications. For a complete list of my papers, please see my DBLP and Google scholar accounts:

Conference Publications (with refereed proceedings)

For the conference papers below, an extended version with all missing material is provided, whenever there is one available for distribution. If there is even a follow-up journal publication, a link to this is also provided (journal versions can also be found directly under the section on journal publications below).
  1. G. Amanatidis, E. Markakis, A. Ntokos. Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 1790-1797, 2020.
    Our main result is an algorithm that computes a 0.618-approximation to EFX (the best known so far). At the same time, the algorithm achieves a better than 1/2-approximation for GMMS and satisfies further fairness properties.
    [conference version | journal version]
  2. G. Amanatidis, E. Markakis, A. Nikzad, A. Saberi. Approximation Algorithms for Computing Maximin Share Allocations. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), 2015.
    Our main result is a 2/3-approximation algorithm for computing a maximin-share (MMS) allocation, a fairness notion introduced by Budish in 2011. We also provide improved approximations for some special cases.
    [conference version | full version]
  3. G. Amanatidis, N. Barrot, J. Lang, E. Markakis, B. Ries. Multiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulability. Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS 2015), pp. 715-723, 2015.
  4. S. Obraztsova, E. Markakis, M. Polukarov, Z. Rabinovich, N. R. Jennings. On the Convergence of Iterative Voting: How Restrictive should Restricted Dynamics be? Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), 2015.
  5. Z. Rabinovich, S. Obraztsova, O. Lev, E. Markakis, J. Rosenschein. Analysis of Equilibria in Iterative Voting Schemes. Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), 2015.
  6. D. Fotakis, T. Lykouris, E. Markakis, S. Obraztsova. $ Influence Maximization in Switching-Selection Threshold Models. Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT 2014). pp. 122-133, 2014.
  7. E. Markakis, O. Telelis. Item Bidding for Combinatorial Public Projects. Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014), pp. 749-755, 2014.
  8. J. Diaz, I. Giotis, L. Kirousis, E. Markakis, M. Serna. On the Stability of Generalized Second Price Auctions with Budgets. Proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN 2014), pp. 695-706, 2014.
  9. S. Obraztsova, E. Markakis, D. Thompson. Plurality Voting with Truth-biased Agents. Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT 2013), pp. 26-37, 2013.
    An equilibrium analysis of the standard Plurality voting rule, under the model that voters prefer to be honest when they are not pivotal, i.e., when they cannot affect the outcome, given the other players' choices. This leads to a refinement of the set of equilibria, eliminating certain undesirable equilibria that are present in the more classic game-theoretic models of voting.
  10. B. de Keijzer, E. Markakis, G. Schaefer, O. Telelis. On the Inefficiency of Standard Multi-unit Auctions. In Proceedings of the 21st European Symposium on Algorithms (ESA 2013), pp. 385-396, 2013.
    An analysis of the Price of Anarchy for certain auction formats that are used in practice for selling multiple units of a single item. These include the uniform price auction, the discriminatory auction and their uniform bidding counterparts. The good news is that all these auction formats have very low Price of Anarchy (a small constant in all cases), hence at equilibrium we still have a very good approximation to the optimal social welfare. Our full version with all missing proofs is available at arxiv here.
  11. V. Tzoumas, C. Amanatidis, E. Markakis. A Game-theoretic Analysis of a Competitive Diffusion Process over Social Networks. Workshop on Internet and Network Economics (WINE 2012), pp. 1-14, 2012.
    A game-theoretic approach for the diffusion of information in social networks is presented. We consider a non-cooperative game among firms that promote their product in a network by choosing appropriate seeds. We focus on various questions regarding pure Nash equilibria of these games.
    See our full version for all missing proofs and for some more results on these questions.
  12. E. Markakis, O. Telelis. Uniform Price Auctions: Equilibria and Efficiency. In Proceedings of the 5th Symposium on Algorithmic Game Theory (SAGT 2012), pp. 227-238, 2012.
  13. Y. Zick, E. Markakis, E. Elkind. Stability via Convexity and LP Duality in OCF games. AAAI, 2012.
  14. E. Bampis, D. Letsios, G. Lucarelli, E. Markakis, I. Milis. On Multiprocessor Temperature-Aware Scheduling Problems. International Conference on Algorithmic Aspects of Information and Management (AAIM), pp. 149-160, 2012.
    A paper on certain scheduling problems under temperature constraints.
  15. G. Chalkiadakis, E. Markakis, N. R. Jennings. Coalitional Stability in Structured Environments. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2012.
    This work deals with cooperative games where not all coalitions are feasible due to connectivity constraints. In particular, there exists an underlying graph and a coalition can form only if it forms a connected subset of the graph. We look at computational problems related to the core, such as computing the core, or checking membership in the core. Both algorithmic and hardness results are obtained.
  16. E. Markakis, C.A. Psomas. On Worst-Case Allocations in the Presence of Indivisible Goods. Workshop on Internet and Network Economics (WINE), pp. 278-289, 2011.
  17. K. R. Apt, E. Markakis. Diffusion in Social Networks with Competing Products. Symposium on Algorithmic Game Theory (SAGT), pp. 212-223, 2011.
  18. N. Immorlica, E. Markakis, G. Piliouras. Coalition Formation and Price of Anarchy in Cournot Oligopolies. Workshop on Internet and Network Economics (WINE), pp. 270-281, 2010.
  19. E. Markakis, O. Telelis. Discrete Strategies in Keyword Auctions and Their Inefficiency for Locally Aware Bidders . Workshop on Internet and Network Economics (WINE), pp. 523-530, 2010.
  20. I. Caragiannis, D. Kalaitzis, E. Markakis. Approximation Algorithms and Mechanism Design for Minimax Approval Voting . AAAI, 2010.
  21. K. Apt, E. Markakis. Sequential Bidding in the Bailey-Cavallo Mechanism. Workshop on Internet and Network Economics (WINE), pp. 483-490, 2009.
    The version I have here is a more extended one with the proofs that are missing from the WINE proceedings and with some more results. An initial version of this work also appeared as "Optimal Strategies in Sequential Bidding" in International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (short paper), 2009.
  22. R. Gomes, N. Immorlica, E. Markakis. Externalities in Keyword Auctions: an empirical and theoretical assessment. Workshop on Internet and Network Economics (WINE), pp. 172-183, 2009.
  23. Y. Bachrach, E. Markakis, A. Procaccia, J. Rosenschein, A. Saberi. Approximating Power Indices. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 943-950, 2008. See the journals section for an extended version which also contains some computer simulations.
  24. S. Koenig, X. Zheng, C. A. Tovey, R. B. Borie, P. Kilby, E. Markakis, P. Keskinocak. Agent Coordination with Regret Clearing. AAAI, pp. 101-107, 2008.
  25. K. Apt, V. Conitzer, M. Guo, E. Markakis. Welfare Undominated Groves Mechanisms . Workshop on Internet and Network Economics (WINE), pp. 426-437, 2008.
    The version I have here is a more extended one, containing all missing proofs from the conference version.
  26. G. Chalkiadakis, E. Elkind, E. Markakis, N. Jennings. Overlapping Coalition Formation. Workshop on Internet and Network Economics (WINE), pp. 307-321, 2008.
    We propose a model of cooperative games where the formation of overlapping coalitions is allowed. Within this framework we define and study various notions of stability, extending the notion of the core for usual cooperative games into this setting. Our journal version (JAIR) gives a better exposition of the 3 notions of the core that we study and it also contains some computational results.
  27. H. Bosse, J. Byrka, E. Markakis. New Algorithms for Approximate Nash Equilibria. Workshop on Internet and Network Economics (WINE), pp. 17-29, 2007.
    This is our 0.3639 approximation algorithm for computing additive epsilon-Nash equilibria. Our journal version (Theoretical Computer Science) also contains some extensions to games with more than 2 players. In particular, we can have a 0.602-approximation for 3-player games and a 0.715-approximation for 4-player games.
  28. H. Hatami, A. Magen, E. Markakis. Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of Negative Type metrics. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pp. 164-179, 2007.
    We consider various SDP relaxations for the Vertex Cover problem, such as adding the triangle inequalities and the pentagonal inequalities. See our journal version (SIAM Journal on Discrete Mathematics) for a more complete exposition and all missing proofs from the conference version.
  29. G. Chalkiadakis, E. Markakis, C. Boutilier. Coalition Formation under Uncertainty: Bargaining Equilibria and the Bayesian Core Stability Concept. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2007.
    Some notions of Bayesian core are introduced and their properties are studied especially with respect to linking them with noncooperative solution concepts. A journal version is currently under preparation.
  30. R. LeGrand, E. Markakis, A. Mehta. Some Results on Approximating the Minimax Solution in Approval Voting. International Conference on Autonomous Agents and Multiagent Systems (AAMAS), (short paper), pp. 198-200, 2007.
    We look at the problem of minimizing the maximum Hamming distance to the voters in the context of approval voting. We also consider the question of designing truthful mechanisms (without money) that achieve constant approximations to the minimax solution. The version I have here is a more detailed one than the actual 3-page conference version. See above our AAAI '10 paper for improved results on these questions.
  31. S. Koenig, C. Tovey, M. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, A. Meyerson, S. Jain. The Power of Sequential Single-Item Auctions for Agent Coordination. AAAI, pp. 1625-1629, 2006.
    This is our AAAI nectar paper, based on our Robotics '05 paper. It is of a more expository and less technical flavor than the Robotics paper (as nectar papers typically are).
  32. S. Khot, R. J. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions. Workshop on Internet and Network Economics (WINE), pp. 92-101, 2005.
    We show that under submodular valuations, no algorithm can have a better than (1-1/e)-approximation for maximizing the social welfare. Journal version invited for submission to Algorithmica.
  33. M. Lagoudakis, E. Markakis, D. Kempe, P. Keskinocak, A. Kleywegt, S. Koenig, C. Tovey, A. Meyerson, S. Jain. Auction-based Multi-robot Routing. Robotics:Science and Systems, pp. 343-350, 2005.
    We study certain robot routing problems where a set of robots need to visit a set of targets. We consider various objectives such as the total, the maximum and the average distance and we provide approximation algorithms. A more expository and less technical version appeared as a nectar paper in AAAI 2006 as "The Power of Sequential Single-Item Auctions for Agent Coordination".
  34. M. Kolountzakis, E. Markakis, A. Mehta. Learning Symmetric k-juntas in time n^{o(k)}. Proceedings of "Interface between Harmonic Analysis and Number Theory", CIRM, Marseilles, 2005.
    This is an improvement over our CCC '05 paper, showing that there always exists a non-zero Fourier coefficient of order at most o(k) for symmetric boolean functions of k variables. This implies a subexponential algorithm for the problem of learning k-juntas in the PAC-learning model. Our journal version (Combinatorica) is a merge of this paper and our CCC '05 paper.
  35. R. J. Lipton, E. Markakis, A. Mehta, N. Vishnoi. On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. IEEE Conference on Computational Complexity (CCC), pp. 112-119, 2005.
    The main result is that every symmetric boolean function of k variables (apart from constant and parity functions) has a non-zero Fourier coefficient of "small" order (well, no more than about 0.1k). See the paper above or the journals section for more details and improvements.
  36. R. J. Lipton, E. Markakis, E. Mossel, A. Saberi. On Approximately Fair Allocations of Indivisible Goods. ACM Conference on Electronic Commerce (EC), pp. 125-131, 2004.
    We address some algorithmic questions regarding the computation of approximately envy-free allocations when we have only indivisible goods. The extended version contains some more results regarding the continuous case as well, in particular, that we can have epsilon-envy-freeness with O(n/epsilon) cuts.
  37. R. J. Lipton, E. Markakis. Nash Equilibria via Polynomial Equations. Latin American Symposium on Theoretical Informatics (LATIN), pp. 413-422, 2004.
    Some more observations regarding Nash equilibria, when seen as solutions to systems of polynomial equations .
  38. E. Markakis, A. Saberi. On the Core of the Multicommodity Flow Game. ACM Conference on Electronic Commerce (EC), pp. 93-97, 2003.
    Recipient of the best student paper award. We show that the core of such games is non-empty using LP-based techniques in the TU case and Scarf's Lemma in the NTU case. Journal version invited in special issue of Decision Support Systems.
  39. R. J. Lipton, E. Markakis, A. Mehta. Playing Large Games using Simple Strategies. ACM Conference on Electronic Commerce (EC), pp. 36-41, 2003.
    Our n^{logn/epsilon^2} algorithm for finding epsilon-Nash equilibria. It is still an open problem to determine if a PTAS exists for this problem.
  40. M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. A Greedy Facility Location Algorithm Analyzed using Dual Fitting. Proceedings of 5th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROX-RANDOM), pp. 127--137, 2001.
    A 1.86-approximation algorithm for the facility location problem. The journal version (Journal of the ACM) combines this paper and the follow up STOC paper by K. Jain, M. Mahdian and A. Saberi.
Bak to the top

Journal Publications

  1. K. R. Apt, E. Markakis. Social Networks with Competing Products, Fundamenta Informaticae, forthcoming, 2013.
  2. E. Bampis, D. Letsios, G. Lucarelli, E. Markakis, I. Milis. On Multiprocessor Temperature-Aware Scheduling Problems, Journal of Scheduling, 16(5), pp. 529-538, 2013.
  3. M. Guo, E. Markakis, K. R. Apt, V. Conitzer. Undominated Groves Mechanisms. Journal of Artificial Intelligence Research (JAIR), 46, pp. 129-163, 2013.
  4. G. Chalkiadakis, E. Elkind, E. Markakis, M. Polukarov, N. R. Jennings. Cooperative Games with Overlapping Coalitions. Journal of Artificial Intelligence Research (JAIR), 39, pp. 179-216, 2010.
    This is the journal version of our WINE '08 paper. It contains quite a few results that did not appear in the conference version, among others, three definitions of variants of the core and comparisons between them (each is capturing a different aspect regarding allowable deviations), and computational results on threshold task games.
  5. H. Bosse, J. Byrka, E. Markakis. New Algorithms for Approximate Nash Equilibria. In Theoretical Computer Science, 411(1), pp. 164-173, 2010.
    This is the journal version of our WINE '07 paper. This version contains one extra observation from the conference version, namely that from an alpha-approximation for k-player games, one can obtain a 1/(2-alpha)-approximation for (k+1)-player games. Hence, by using the currently best result for 2-player games, we can have a 0.602-approximation for 3-player games, a 0.715-approximation for 4-player games and so on. This was also independently discovered in the SAGT '08 paper of S. Hemon, M. de Rougemont, M. Santha.
  6. Y. Bachrach, E. Markakis. A. D. Procaccia, E. Resnick, J. S. Rosenschein and A. Saberi. Approximating Power Indices: Theoretical and Empirical Analysis. In Journal of Autonomous Agents and Multiagent Systems, 20(2), pp. 105-122, 2010.
  7. M. Kolountzakis, R. Lipton, E. Markakis, A. Mehta, N. Vishnoi. On the Fourier Spectrum of Symmetric Boolean Functions. In Combinatorica, 29(3) pp. 363-387, 2009.
    This is a merge of 2 papers, the CCC '05 paper and the one from the CIRM '05 conference.
  8. H. Hatami, A. Magen, E. Markakis. Integrality gaps of semidefinite programs for Vertex Cover and relations to $ell_1$ embeddability of Negative Type metrics. In SIAM Journal on Discrete Mathematics, 23(1), pp. 178-194, 2008.
    The journal version of our APPROX '07 paper.
  9. S. Khot, R. J. Lipton, E. Markakis, A. Mehta. Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions, Algorithmica, 52(1), pp. 3--18, 2008.
    This is the journal version of our WINE '05 paper.
  10. E. Markakis, A. Saberi. On the Core of the Multicommodity Flow Game. Decision Support Systems, 39(1), pp. 3-10, 2005.
    The journal version of our EC '03 paper.
  11. K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. V. Vazirani. Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP. Journal of the ACM, 50 (6), pp. 795--824, November 2003.
    This is a merge of our APPROX '01 paper with the follow up STOC '02 paper by K. Jain, M. Mahdian and A. Saberi.
Bak to the top

Book Chapters - Surveys

  1. P. Maille, E. Markakis, M. Naldi, G. D. Stamoulis, B. Tuffin. Sponsored Search Auctions: An Overview of Research with Emphasis on Game Theoretic Aspects. Electronic Commerce Research (ECR), pp. 265-300, 2012.
    A survey paper we wrote on sponsored search auctions.
  2. E. Elkind, E. Markakis. Game-theoretic Foundations of Multiagent Systems. Chapter 17 in the book "Multiagent Systems", edited by Gerhard Weiss, MIT Press, 2012.
Bak to the top

Theses

  1. E. Markakis. Computational Aspects of Game Theory and Microeconomics. PhD thesis, Georgia Institute of Technology, 2005.
  2. E. Markakis. Logics of Knowledge and Belief - Belief Revision. Bachelor's thesis, National Technical University of Athens, 2000.
Bak to the top

Other Unpublished Manuscripts

  1. R. Lipton, E. Markakis, A. van den Essen. Some Remarks on the Jacobian Conjecture and Connections with Hilbert's Irreducibility Theorem.
  2. R. Lipton, E. Markakis, A. Mehta. On Stability Properties of Economic Solution Concepts.

Bak to the top