ACAC '14

x Temporal graphs and temporal networks
Paul Spirakis, University of Liverpool & CTI

Joint work with O. Michail, I. Chatzigiannakis and G. Mertzios, results appeared in ICALP 2013 and results that will appear in MFCS 2014.

We discuss here the notion of temporal graphs. These are abstract models of networks that change with time. Here, edges have labels (positive integers indicating discrete times of availability). A basic notion is that of a journey (that is a path in which subsequent edges appear with increasing labels). We examine foremost journeys, Menger's theorem, design issues of temporal nets and also some questions on traversals and the Temporal Travelling salesman Problem.

x Implementing the L∞ segment Voronoi diagram in CGAL and an application in VLSI pattern analysis
Panagiotis Cheilaris, Università della Svizzera italiana

Joint work with Sandeep Kumar Dey, Maria Gabrani, Evanthia Papadopoulou

We present a CGAL (Computational Geometry Algorithm Library) implementation of the line segment Voronoi diagram under the L∞ metric, building on top of the existing line segment Voronoi diagram under the Euclidean (L2) metric in CGAL. CGAL is an open- source collection of geometric algorithms implemented in C++, used in both academia and industry. We also discuss an application of the L∞ segment Voronoi diagram in the area of VLSI pattern analysis. In particular, we identify potentially critical locations in VLSI design patterns, where a pattern (when printed) may differ substantially from the original intended VLSI design.

x Nearly optimal algorithm for complex root refinement
Elias Tsigaridas, Inria Paris-Rocquencourt

Joint work with Victor Y. Pan (CUNY, USA)

What is the bit complexity for approximating up to L bits the complex root of a univariate polynomial with integer coefficients? We present an optimal, up to poly-logarithmic factors, algorithm for this problem.

x Polyhedral Omega: A linear Diophantine system solver
Zafeirakis Zafeirakopoulos, RISC-Linz

Joint work with Felix Breuer

Polyhedral Omega is a new algorithm for solving linear Diophantine systems (LDS), i.e., for computing a multivariate rational function representation of the set of all non-negative integer solutions to a system of linear equations and inequalities. Polyhedral Omega combines methods from partition analysis with methods from polyhedral geometry. In particular, we combine MacMahon's iterative approach based on the Omega operator and explicit formulas for its evaluation with geometric tools such as Brion decompositions and Barvinok's short rational function representations. In this way, we connect two recent branches of research that have so far remained separate, unified by the concept of symbolic cones which we introduce. The resulting LDS solver Polyhedral Omega is significantly faster than previous solvers based on partition analysis and it is competitive with state-of-the-art LDS solvers based on geometric methods. Most importantly, this synthesis of ideas makes Polyhedral Omega by far the simplest algorithm for solving linear Diophantine systems available to date.

x On the Efficiency of Simple Allocation Mechanisms for Divisible Goods
Alkmini Sgouritsa, University of Liverpool

We study the Price of Anarchy (PoA) of simple mechanisms where divisible goods are to be allocated among selfish individuals. In such mechanisms, each bidder submits a single bid for each divisible good to represent her preference and the mechanism determines the fractional allocation and payments for bidders based on their bids. We are interested in simultaneous (i.e. running in parallel) allocation mechanisms when the valuations of the bidders are subadditive and we mainly focus on the well-known proportional-share allocation mechanism.

x Duality and Optimality of Auctions for Uniform Distributions
Yiannis Giannakopoulos, University of Oxford

We derive exact optimal solutions for the problem of optimizing revenue in single-bidder multi-item auctions for uniform i.i.d. valuations. We give optimal auctions of up to 6 items; previous results were only known for up to three items. To do so, we develop a general duality framework for the general problem of maximizing revenue in many-bidders multi-item additive Bayesian auctions with continuous probability valuation distributions. The framework extends linear programming duality and complementarity to constraints with partial derivatives. The dual system reveals the geometric nature of the problem and highlights its connection with the theory of bipartite graph matchings. The duality framework is used not only for proving optimality, but perhaps more importantly, for deriving the optimal auction; as a result, the optimal auction is defined by natural geometric constraints.

x The Performance of Deferred-Acceptance Auctions
Vasilis Gkatzelis, Stanford University

Joint work with Paul Duetting and Tim Roughgarden

Deferred-acceptance auctions are auctions for binary single-parameter mechanism design problems whose allocation rule can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal [2014] recently introduced these auctions and proved that they satisfy a remarkable list of incentive guarantees: in addition to being dominant-strategy incentive-compatible, they are weakly group-strategyproof, can be implemented by ascending-clock auctions, and admit outcome-equivalent full-information pay-as-bid versions. Neither forward greedy mechanisms nor the VCG mechanism generally possess any of these additional incentive properties. The goal of this paper is to initiate the study of deferred-acceptance auctions from an approximation standpoint. We study these auctions through the lens of two canonical welfare-maximization problems, in knapsack auctions and in combinatorial auctions with single-minded bidders.

x Welfare guarantees for proportional allocations
Alexandros Voudouris, University of Patras

According to the proportional allocation mechanism, users compete for a divisible resource by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to her bid and collects an amount equal to her bid as payment. Since users act as utility-maximizers, this naturally defines a proportional allocation game. Recently, Syrgkanis and Tardos (STOC 2013) quantified the inefficiency of equilibria in this game with respect to the social welfare and presented a lower bound of $26.8\%$ on the price of anarchy over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In this paper, we improve this bound to $50\%$ over both equilibrium concepts. Our analysis is simpler and it cannot be improved by arguments that do not take the equilibrium structure into account. We also extend it to settings with budget constraints where we show the first constant bound (between $36\%$ and $50\%$) on the price of anarchy of the corresponding game with respect to an effective welfare benchmark that takes budgets into account.

x A characterization result for strongly monotone scheduling mechanisms
Angelina Vidali, Duke University, Durham, North Carolina, USA

Joint work with Annamária Kovács, Goethe University, Frankfurt/M, Germany

Our work is a step towards the important problem of globaly characterizing truthful mechanisms with multi-parameter, additive player-valuations like unrelated scheduling or additive combinatorial auctions. Very few mechanisms are known for these multi-parameter nondownward closed settings and the question is: Can we prove that no other mechanisms exist? We characterize decisive, strongly monotone mechanisms for two tasks or items as either task independent mechanisms or ’player-grouping minimizers’, a new monotone generalization of affine minimizers. We present a general lemma implying the local linearity of payment functions in ’most’ cases.

x Influence Maximization in Switching-Selection Threshold Models
Thodoris Lykouris, Cornell University

Joint work with Dimitris Fotakis, Evangelos Markakis, Svetlana Obraztsova

We study influence maximization problems over social networks, in the presence of competition. Our focus is on diffusion processes within the family of threshold models. Motivated by the general lack of positive results establishing monotonicity and submodularity of the influence function for threshold models, we introduce a general class of switching-selection threshold models where the switching and selection functions may also depend on the node activation history. This extension allows us to establish monotonicity and submodularity when (i) the switching function is linear and depends on the influence by all active neigh- bors, and (ii) the selection function is linear and depends on the influence by the nodes activated only in the last step. This implies a (1 − 1/e − ε)-approximation for the influence maximization problem in the competitive setting. On the nega- tive side, we present a collection of counterexamples establishing that the restric- tions above are essentially necessary. Moreover, we show that switching-selection threshold games with properties (i) and (ii) are valid utility games, and thus their Price of Anarchy is at most 2.

x Congestion Games with Risk-Averse Players
Thanasis Lianeas, National Technical University of Athens

Congestion games ignore the stochastic nature of resource delays and the risk-averse attitude of the players to uncertainty. In the first part of the talk, we introduce two variants of atomic congestion games, one with stochastic players, where each player assigns load to her strategy independently with a given probability, and another with stochastic edges, where the latency functions are random. In both variants, the players are risk-averse, and their individual cost is a player-specific quantile of their delay distribution. We investigate the existence of equilibria and potential functions and the Price of Anarchy. In the second part of the talk, we investigate how and to which extent one can exploit risk-aversion and modify the perceived latencies of the players so that the Price of Anarchy wrt the total latency of the players is improved. The starting point is to introduce some small (and carefully selected) random perturbations to the edge latencies so that the expected latency does not change, but the perceived cost of the players increases, due to risk-aversion.

x Mechanism Design with Verification
Manolis Zambetakis, National Technical University of Athens

We investigate the reasons that make symmetric partial verification essentially useless in virtually all domains. Departing from previous work, we consider any possible (finite or infinite) domain and general symmetric verification. We identify a natural property, namely that the correspondence graph of a symmetric verification M is strongly connected by finite paths along which the preferences are consistent with the preferences at the endpoints, and prove that this property is sufficient for the equivalence of truthfulness and M-truthfulness. In fact, defining appropriate versions of this property, we obtain this result for deterministic and randomized mechanisms with and without money. Moreover,we show that a slightly relaxed version of this property is also necessary for the equivalence of truthfulness and M-truthfulness. Our conditions provide a generic and convenient way of checking whether truthful implementation can take advantage of any symmetric verification scheme in any domain. Since the simplest case of symmetric verification is local verification, our results imply, as a special case, the equivalence of local truthfulness and global truthfulness in the setting without money. To complete the picture, we consider asymmetric verification, and prove that a social choice function is M-truthfully implementable by some asymmetric verification M if and only if f does not admit a cycle of profitable deviations.

x Sparsification and subexponential approximation
Vangelis Paschos, University Paris-Dauphine

Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this talk, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems as dominating set, feedback vertex set, min set cover.

x Item Bidding from Combinatorial Public Projects
Orestis Telelis, Athens University of Economics and Business

This is a joint work, with Vangelis Markakis.

We analyze equilibria of mechanisms for the Combinatorial Public Project Problem (CPPP). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of truthful approximation mechanisms. We study two non-truthful mechanisms that are, however, practically relevant to multi-agent environments, by virtue of their simplicity. Both mechanisms employ an item bidding interface, wherein every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are chosen and agents are charged according to VCG-based payment rules. For expressive classes of the agents’ valuation functions, we establish existence of socially optimal pure Nash and strong equilibria, that are resilient to coordinated deviations of subsets of agents. Subsequently, we derive worst-case bounds on the approximation of the optimum social welfare achieved in equilibrium.

x Nash equilibria in bimatrix 5x4 games
Raimundas Vidunas, University of Athens

We establish the maximal number of Nash equilibria in bimatrix 5x4 games.

x Reliable Broadcast with Respect to Topology Knowledge
Giorgos Panagiotakos, National Technical University of Athens

We study the Reliable Broadcast problem in incomplete networks against a Byzantine adversary. We examine the problem under the locally bounded adversary model of Koo (2004) and the general adversary model of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. We refine the local pair-cut technique of Pelc and Peleg (2005) in order to obtain impossibility results for every level of topology knowledge and any type of corruption distribution. On the positive side we devise protocols that match the obtained bounds and thus, exactly characterize the classes of graphs in which Reliable Broadcast is possible. Among others, we show that Koo's Certified Propagation Algorithm (CPA) is unique against locally bounded adversaries in ad hoc networks, that is, it can tolerate as many local corruptions as any other non-faulty algorithm; this settles an open question posed by Pelc and Peleg. We also provide an adaptation of CPA against general adversaries and show its uniqueness in this case too. To the best of our knowledge this is the first optimal algorithm for Reliable Broadcast in generic topology ad hoc networks against general adversaries.

x Game Semantics for Logic Programming
Chrysida Galanaki, University of Athens

Joint work with C. Nomikos, P. Rondogiannis, and W. W. Wadge

We present infinite games of perfect information that capture the semantics of logic programs with negation and other non-monotonic operators. We consider the following cases: (i) Normal logic programs, that have a finite number of rules and negation-as-failure, (ii) Infinite logic programs, that have an infinite number of rules, and (iii) Intensional logic programs, that have non-monotonic intensional operators.

x Multiprocessor Speed Scaling with Precedence Constraints
Dimitris Letsios, Technical University of Munich

We consider the problem of scheduling a set of jobs, under precedence constraints, on a set of speed scalable parallel processors. The goal is to minimize the makespan of the schedule, i.e. the time at which the last job finishes its execution, without violating a given energy budget. This situation finds applications in computer devices whose life-time depends on a limited battery efficiency. In order to handle the energy consumption we use the energy model introduced in [Yao et al., FOCS’95], which captures the intuitive idea that the higher is the processor’s speed the higher is the energy consumption. We propose a (2-1/m)-approximation algorithm improving the best known poly-log(m)-approximation algorithm for the problem [Pruhs et al., TOCS 2008], where m is the number of the processors. We also extend the simple idea used for the above problem, in order to propose a generalized framework that finds applications to other scheduling problems in the speed scaling setting.

x Reductions from Mechanism to Algorithm Design
Costantinos Daskalakis, MIT

Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient reductions from mechanism design (i.e. optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.

x Exclusive Graph Searching in Various Graph Classes
Euripides Markou, University of Thessaly

Joint work with Nicolas Nisse and Stephane Perennes

In Graph Searching, a team of searchers tries to capture an invisible fugitive who is moving arbitrary fast in a graph. Many variants of this problem have been studied with respect to the constraints that the searchers' strategy must satisfy. We study here the Exclusive Graph Searching problem in which two searchers can not occupy simultaneously a node. We will discuss the complexity of finding the minimum number of searchers capable of solving the problem in various classes of graphs. We show that the problem is NP-hard in planar graphs with maximum degree $3$. We will also present a graph family in which the problem of finding a monotone strategy of a minimum number of searchers remains NP-hard and some other graph families in which the problem can be solved in polynomial time.