28 citations · 46 across the 20 of their papers we have counts for
25 papers · 1 filter
Universally truthful mechanisms for scheduling
Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias +2
We consider universally truthful randomized mechanisms for the problem of scheduling jobs on unrelated machines. We prove a lower bound on the expected approximation ratio…
Mechanism design augmented with output advice
George Christodoulou, Alkmini Sgouritsa, Ioannis Vlachos
Our work revisits the design of mechanisms via the learning-augmented framework. In this model, the algorithm is enhanced with imperfect (machine-learned) information concerning th…
A proof of the Nisan-Ronen conjecture
George Christodoulou, Elias Koutsoupias, Annamaria Kovacs
Noam Nisan and Amir Ronen conjectured that the best approximation ratio of deterministic truthful mechanisms for makespan-minimization for unrelated machines is . This work…
Truthful Aggregation of Budget Proposals with Proportionality Guarantees
Ioannis Caragiannis, George Christodoulou, Nicos Protopapas
We study a participatory budgeting problem, where a set of strategic agents wish to split a divisible budget among different projects, by aggregating their proposals on a single di…
Truthful allocation in graphs and hypergraphs
George Christodoulou, Elias Koutsoupias, Annamaria Kovacs
We study truthful mechanisms for allocation problems in graphs, both for the minimization (i.e., scheduling) and maximization (i.e., auctions) setting. The minimization problem is…
Impartial selection with prior information
Ioannis Caragiannis, George Christodoulou, Nicos Protopapas
We study the problem of {\em impartial selection}, a topic that lies at the intersection of computational social choice and mechanism design. The goal is to select the most popular…
On the Nisan-Ronen conjecture
George Christodoulou, Elias Koutsoupias, Annamaria Kovacs
The Nisan-Ronen conjecture states that no truthful mechanism for makespan-minimization when allocating tasks to unrelated machines can have approximation ratio less than $n…
Resource-Aware Protocols for Network Cost-Sharing Games
George Christodoulou, Vasilis Gkatzelis, Mohamad Latifian +1
We study the extent to which decentralized cost-sharing protocols can achieve good price of anarchy (PoA) bounds in network cost-sharing games with agents. We focus on the mode…
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games
George Christodoulou, Martin Gairing, Yiannis Giannakopoulos +2
We study the existence of approximate pure Nash equilibria (-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree . Previously it was kno…
Impartial Selection with Additive Approximation Guarantees
Ioannis Caragiannis, George Christodoulou, Nicos Protopapas
Impartial selection has recently received much attention within the multi-agent systems community. The task is, given a directed graph representing nominations to the members of a…
On the Nisan-Ronen conjecture for submodular valuations
George Christodoulou, Elias Koutsoupias, Annamaria Kovacs
We consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling unrelated machines: the single exception is that the valuation of just o…
Strategic Contention Resolution in Multiple Channels
George Christodoulou, Themistoklis Melissourgos, Paul G. Spirakis
We consider the problem of resolving contention in communication networks with selfish users. In a \textit{contention game} each of identical players has a single inform…
An Improved Envy-Free Cake Cutting Protocol for Four Agents
Georgios Amanatidis, George Christodoulou, John Fearnley +3
We consider the classic cake-cutting problem of producing envy-free allocations, restricted to the case of four agents. The problem asks for a partition of the cake to four agents,…
The Price of Stability of Weighted Congestion Games
George Christodoulou, Martin Gairing, Yiannis Giannakopoulos +1
We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer we constru…
A 3-player protocol preventing persistence in strategic contention with limited feedback
George Christodoulou, Martin Gairing, Sotiris Nikoletseas +2
In this paper, we study contention resolution protocols from a game-theoretic perspective. In a recent work, we considered acknowledgment-based protocols, where a user gets feedbac…
Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness
Georgios Amanatidis, Georgios Birmpas, George Christodoulou +1
We study the mechanism design problem of allocating a set of indivisible items without monetary transfers. Despite the vast literature on this very standard model, it still remains…
Strategic Contention Resolution with Limited Feedback
George Christodoulou, Martin Gairing, Sotiris Nikoletseas +2
In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on \emph{acknowledgment-based} protocols, where a user gets feedback from the ch…
On the Efficiency of All-Pay Mechanisms
George Christodoulou, Alkmini Sgouritsa, Bo Tang
We study the inefficiency of mixed equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auc…
On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
George Christodoulou, Alkmini Sgouritsa, Bo Tang
We study the efficiency of the proportional allocation mechanism, that is widely used to allocate divisible resources. Each agent submits a bid for each divisible resource and rece…
Designing Networks with Good Equilibria under Uncertainty
George Christodoulou, Alkmini Sgouritsa
We consider the problem of designing network cost-sharing protocols with good equilibria under uncertainty. The underlying game is a multicast game in a rooted undirected graph wit…
Social Welfare in One-Sided Matching Mechanisms
George Christodoulou, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen +3
We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both or…
Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions
George Christodoulou, Annamária Kovács, Alkmini Sgouritsa +1
We study the Price of Anarchy of simultaneous first-price auctions for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian Price of An…
A deterministic truthful PTAS for scheduling related machines
George Christodoulou, Annamaria Kovacs
Scheduling on related machines () is one of the most important problems in the field of Algorithmic Mechanism Design. Each machine is controlled by a selfish agent and…
A characterization of 2-player mechanisms for scheduling
George Christodoulou, Elias Koutsoupias, Angelina Vidali
We study the mechanism design problem of scheduling unrelated machines and we completely characterize the decisive truthful mechanisms for two players when the domain contains both…