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]
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]
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Y. Zick, E. Markakis, E. Elkind.
Stability via Convexity and LP Duality in
OCF games. AAAI, 2012.
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.
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.
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.
K. R. Apt, E. Markakis.
Diffusion in Social Networks with Competing
Products.
Symposium on Algorithmic Game Theory (SAGT), pp. 212-223, 2011.
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.
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.
I. Caragiannis, D. Kalaitzis, E. Markakis.
Approximation Algorithms and Mechanism Design for Minimax
Approval Voting
. AAAI, 2010.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
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".
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.
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.
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.
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
.
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.
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.
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.