Efficient Money Burning in General Domains

We study mechanism design where the objective is to maximize the residual surplus, i.e., the total value of the outcome minus the payments charged to the agents, by truthful mechanisms. The motivation comes from applications where the payments charged are not in the form of actual monetary transfers, but take the form of wasted resources. We consider a general mechanism design setting with m discrete outcomes and n multidimensional agents. We present two randomized truthful mechanisms that extract an O(logm) fraction of the maximum social surplus as residual surplus. The first mechanism achieves an O(logm)-approximation to the social surplus, which is improved to an O(1)-approximation by the second mechanism. An interesting feature of the second mechanism is that it optimizes over an appropriately restricted space of probability distributions, thus achieving an efficient tradeoff between social surplus and the total amount of payments charged to the agents.     

The power of verification for one-parameter agents

We initiate the study of mechanisms with verification for one-parameter agents. We give an algorithmic characterization of such mechanisms and show that they are provably better than mechanisms without verification, i.e., those previously considered in the literature. These results are obtained for a number of optimization problems motivated by the Internet and recently studied in the algorithmic mechanism design literature. The characterization can be regarded as an alternative approach to existing techniques to design truthful mechanisms. The construction of such mechanisms reduces to the construction of an algorithm satisfying certain “monotonicity” conditions which, for the case of verification, are much less stringent. In other words, verification makes the construction easier and the algorithm more efficient (both computationally and in terms of approximability).     

Average-case analysis of VCG with approximate resource allocation algorithms

The Vickrey-Clarke-Groves (VCG) mechanism offers a general technique for resource allocation with payments, ensuring allocative efficiency while eliciting truthful information about preferences. However, VCG relies on exact computation of an optimal allocation of resources, a problem which is often computationally intractable, and VCG that uses an approximate allocation algorithm no longer guarantees truthful revelation of preferences. We present a series of results for computing or approximating an upper bound on agent incentives to misreport their preferences. Our first key result is an incentive bound that uses information about average (not worst-case) performance of an algorithm, which we illustrate using combinatorial auction data. Our second result offers a simple sampling technique for amplifying the difficulty of computing a utility-improving lie. An important consequence of our analysis is an argument that using state-of-the-art algorithms for solving combinatorial allocation problems essentially eliminates agent incentives to lie.     

Scheduling Without Payments

We consider mechanisms without payments for the problem of scheduling unrelated machines. Specifically, we consider truthful in expectation randomized mechanisms under the assumption that a machine (player) is bound by its reports: when a machine lies and reports value $\tilde{t}_{ij}$ for a task instead of the actual one t _ij , it will execute for time $\tilde{t}_{ij}$ if it gets the task (unless the declared value $\tilde{t}_{ij}$ is less than the actual value t _ij , in which case, it will execute for time t _ij ). Our main technical result is an optimal mechanism for one task and n players which has approximation ratio (n+1)/2. We also provide a matching lower bound, showing that no other truthful mechanism can achieve a better approximation ratio. This immediately gives an approximation ratio of (n+1)/2 and n(n+1)/2 for social cost and makespan minimization, respectively, for any number of tasks. We also study the price of anarchy of natural algorithms.     

Reducing mechanism design to algorithm design via machine learning

We use techniques from sample-complexity in machine learning to reduce problems of incentive-compatible mechanism design to standard algorithmic questions, for a broad class of revenue-maximizing pricing problems. Our reductions imply that for these problems, given an optimal (or β-approximation) algorithm for an algorithmic pricing problem, we can convert it into a (1+?)-approximation (or β(1+?)-approximation) for the incentive-compatible mechanism design problem, so long as the number of bidders is sufficiently large as a function of an appropriate measure of complexity of the class of allowable pricings. We apply these results to the problem of auctioning a digital good, to the attribute auction problem which includes a wide variety of discriminatory pricing problems, and to the problem of item-pricing in unlimited-supply combinatorial auctions. From a machine learning perspective, these settings present several challenges: in particular, the “loss function” is discontinuous, is asymmetric, and has a large range. We address these issues in part by introducing a new form of covering-number bound that is especially well-suited to these problems and may be of independent interest.     

A Lower Bound of 1+φ for Truthful Scheduling Mechanisms

We study the mechanism design version of the unrelated machines scheduling problem, which is at the core of Algorithmic Game Theory and was first proposed and studied in a seminal paper of Nisan and Ronen. We give an improved lower bound of 1+φ≈2.618 on the approximation ratio of deterministic truthful mechanisms for the makespan. The proof is based on a recursive preprocessing argument which yields a strictly increasing series of new lower bounds for each fixed number of machines n≥4.     

Window-games between TCP flows

We consider network congestion problems between TCP flows and define a new game, the Window-game, which models the problems of network congestion caused by the competing flows. Analytical and experimental results show the relevance of the Window-game to real TCP congestion games and provide interesting insight into the respective Nash equilibria. Furthermore, we propose a new algorithmic queue mechanism, called Prince, which at congestion makes a scapegoat of the most greedy flow. We provide evidence which shows that Prince achieves efficient Nash equilibria while requiring only limited computational resources.     

Conceptual Combination with PUNC

Noun–noun compounds play a key role in the growth of language. In this article we present a system for producing and understanding noun–noun compounds (PUNC). PUNC is based on the Constraint theory of conceptual combination and the C ³ model. The new model incorporates the primary constraints of the Constraint theory in an integrated fashion, creating a cognitively plausible mechanism of interpreting noun–noun phrases. It also tries to overcome algorithmic limitations of the C ³ model in being more efficient in its computational complexity, and deal with a wider span of empirical phenomena, such as dimensions of word familiarity. We detail the model, including knowledge representation and interpretation production mechanisms. We show that by integrating the constraints of the Constraint theory of conceptual combination and prioritizing the knowledge available within a concept's representation, PUNC can not only generate interpretations that reflect those produced by people, but also mirror the differences in processing times for understanding familiar, similar and novel word combinations.     

Exact and approximate rhythm matching algorithms

An interesting problem in music information retrieval is to classify songs according to rhythms. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S?=?2Q. Christodoulakis et?al. presented an efficient algorithm that can be used to classify musical sequences according to rhythms. In this article, the above algorithm is implemented, along with a naive brute force algorithm to solve the same problem. The theoretical time complexity bounds are analyzed with the actual running times achieved by the experiments, and the results of the two algorithms are compared. Furthermore, new efficient algorithms are presented that take temporal errors into account. This, the approximate pattern matching version, could not be handled by the algorithms previously presented. The running times of two algorithmic variants are analyzed and compared and examples of their implementation are shown.     

A comparison of two chromosome representation schemes used in solving a family-based scheduling problem

Meta-heuristic algorithms have been widely used in solving scheduling problems; previous studies focused on enhancing existing algorithmic mechanisms. This study advocates a new perspective—developing new chromosome (solution) representation schemes may improve the performance of existing meta-heuristic algorithms. In the context of a scheduling problem, known as permutation manufacturing-cell flow shop (PMFS), we compare the effectiveness of two chromosome representation schemes (S_old and S_new) while they are embedded in a meta-heuristic algorithm to solve the PMFS scheduling problem. Two existing meta-heuristic algorithms, genetic algorithm (GA) and ant colony optimization (ACO), are tested. Denote a tested meta-heuristic algorithm by X_Y, where X represents an algorithmic mechanism and Y represents a chromosome representation. Experiment results indicate that GA_ S_new outperforms GA_S_old, and ACO_S_new also outperforms ACO_S_old. These findings reveal the importance of developing new chromosome representations in the application of meta-heuristic algorithms.     

Evaluation and comparison of two efficient probabilistic primality testing algorithms

We analyse two recent probabilistic primality testing algorithms; the first one is derived from Miller [6] in a formulation given by Rabin [7], and the second one is from Solovay and Strassen [9]. Both decide whether or not an odd number n is prime in time O(m, lognM(n)) with an error probability less than α^m, for some $\text{0≤a<}\text{1}\text{2}$. Our comparison shows that the first algorithm is always more efficient than the second, both in probabilistic and algorithmic terms.     

Nonlinear mappings in problem solving and their PSO-based development

The study is devoted to a concept and algorithmic realization of nonlinear mappings aimed at increasing the effectiveness of the problem solving method. Given the original input space X and a certain problem solving method M, designed is a nonlinear mapping ? so that the method operating in the transformed space M(?(X)) becomes more efficient. The nonlinear mappings realize a transformation of X through contractions and expansions of selected regions of the original space. In particular, we show how a piecewise linear mapping is optimized by using particle swarm optimization (PSO) and a suitable fitness function quantifying the objective of the problem. Several families of problems are investigated and illustrated through illustrative experimental results.     

Truthful Approximation Mechanisms for Scheduling Selfish Related Machines

We consider the problem of scheduling jobs on related machines owned by selfish agents. We provide a 5-approximation deterministic truthful mechanism, the first deterministic truthful result for the problem. Previously, Archer and Tardos showed a 2-approximation randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). In case the number of machines is constant, we provide a deterministic Fully Polynomial-Time Approximation Scheme (FPTAS) and a suitable payment scheme that yields a truthful mechanism for the problem. This result, which is based on converting FPTAS to monotone FPTAS, improves a previous result of Auletta et al., who showed a (4 + ε)-approximation truthful mechanism.     

A Lower Bound for Scheduling Mechanisms

We study the mechanism design problem of scheduling tasks on n unrelated machines in which the machines are the players of the mechanism. The problem was proposed and studied in the seminal paper of Nisan and Ronen on algorithmic mechanism design, where it was shown that the approximation ratio of mechanisms is between 2 and n. We improve the lower bound to \(1+\sqrt{2}\) for 3 or more machines.     

The Nørsett time integration methodology for finite element transient analysis

This paper presents a set of methods for time integration of problems arising from finite element semidiscretizations. The purpose is to obtain computationally efficient methods which possess higher-order accuracy and controllable dissipation in the spurious high modes. The methods are developed and analysed by a general collocation methodology which leads to the class of Nørsett approximants. An algorithmic parameter is used to achieve an effective control over numerical dissipation. Moreover, a simple and efficient implementation scheme is presented. At each time step, algorithms based on p-order collocation polynomials require the solution of p sets of linear algebraic equations with the same coefficient matrix. In this way, a single factorization is needed and no transformations are required to recover the approximate solution at the end or within the time interval. To demonstrate the performance of the proposed algorithms, a wide experimental evaluation is carried out on typical test problems in finite element transient analysis.     

无线Ad Hoc 网络最大生命周期路由算法的诚实机制

将已有的生命周期路由算法分成两类:普通Max-Min(GMM)算法和条件Max-Min(CMM)算法,然后为这两类算法分别提出它们的诚实机制.通过给予中继节点适当的报酬,这些诚实机制可以确保已有的算法在面对自私节点的时候也可以实现它们的设计目标.说明生命周期路由算法的本质可以使这种报酬率相对较低且比较稳定,实验结果也进一步证明了这一点.     

MRO-MPI: MapReduce overlapping using MPI and an optimized data exchange policy

MapReduce is a programming model proposed to simplify large-scale data processing. In contrast, the message passing interface (MPI) standard is extensively used for algorithmic parallelization, as it accommodates an efficient communication infrastructure. In the original implementation of MapReduce, the reduce function can only start processing following termination of the map function. If the map function is slow for any reason, this will affect the whole running time. In this paper, we propose MapReduce overlapping using MPI, which is an adapted structure of the MapReduce programming model for fast intensive data processing. Our implementation is based on running the map and the reduce functions concurrently in parallel by exchanging partial intermediate data between them in a pipeline fashion using MPI. At the same time, we maintain the usability and the simplicity of MapReduce. Experimental results based on three different applications (WordCount, Distributed Inverted Indexing and Distributed Approximate Similarity Search) show a good speedup compared to the earlier versions of MapReduce such as Hadoop and the available MPI-MapReduce implementations.