In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any algorithm to a dominant-strategy ascending mechanism . This technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. In particular, for “single-value CAs”, where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. Our second result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). The mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless P=NP). This mechanism is an algorithmic implementation in undominated strategies , a notion that we define and justify, and is of independent interest.

This paper presents a truthful sponsored search auction based on an incentive-compatible multi-armed bandit mechanism. The mechanism described combines several desirable traits. The mechanism gives advertisers the incentive to report their true bid, learns the click-through rate for advertisements, allows for slots with different quality, and loses the minimum welfare during the sampling process.

When designing a mechanism there are several desirable properties tomaintain such as incentive compatibility (IC), individual rationality (IR), and budget balance (BB). It is well known [15] that it is impossible for a mechanism to maximize social welfare whilst also being IR, IC, and BB. There have been several attempts to circumvent [15] by trading welfare for BB, e.g.,in domains such as double-sided auctions [13], distributed markets [3] and supply chain problems [2, 4].

We have implemented a firewall application on a Network Interface Card (NIC). We have tested the CPU utilization and the bandwidth in a variety of scenarios. The benefits of offloading code are most pronounced when rejecting packets. Our results suggest significant benefits of offloading applications and in particular firewall logic to a NIC. I. INTRODUCTION There are many communication applications that act on every incoming packet. Offloading such applications to the network interface card (NIC) has many potential advantages. Utilizing the onboard computational power of the NIC can reduce the demands put on the CPU. If the NIC can process incoming information it can avoid costly interrupts to the CPU. In addition, the NIC can serve as a gatekeeper thus avoiding potential threats to the CPU. Furthermore, applications on a NIC can be built such that they are system and OS indepen- dent. An application of particular promise for offloading is a firewall application. Since a firewall is an application that filters packets by a user defined security policy, earlier filtering (especially discarding packets) has a potential for significant improvements in performance. A firewall application on a NIC also has the additional advantage that it is harder for an adversary to modify than a software application running at the host. We have designed and implemented a firewall application which we call SCIRON (Secure-Communication IntegRated Over NIC) on a NIC. The system consists of three elements: The firewall logic, a management console and a policy builder. This paper presents SCIRON, and shows that offloading full applications has significant advantages and market potential more so than TCP offload engines (9) (TOEs) or protocol specific offloaded extensions.

In this paper, we use random-selection protocols in the full-information model to solve classical problems in distributed computing. Our main results are the following: An O(log n)-round randomized Byzantine agreement (BA) protocol in a synchronous full-information network tolerating t0). As such, our protocol is asymptotically optimal in terms of fault-tolerance. An O(1)-round randomized BA protocol in a synchronous full-information network tolerating t = O(n/((log n)1.58)) faulty players. A compiler that converts any randomized protocol Piindesigned to tolerate t fail-stop faults, where the source of randomness of Piinis an SV-source, into a protocol Pioutthat tolerates min(t, n/3) Byzantine faults. If the round-complexity of Piinis r, that of Pioutis O(r log* n). Central to our results is the development of a new tool, "audited protocols". Informally "auditing" is a transformation that converts any protocol that assumes built-in broadcast channels into one that achieves a slightly weaker guarantee, without assuming broadcast channels. We regard this as a tool of independent interest, which could potentially find applications in the design of simple and modular randomized distributed algorithms

Mobile devices are generally used in public, where the user is surrounded by others not involved in the interaction. Audible notification cues are often a cause of unnecessary disruption and distraction both for co-located people and even for the user to whom they are directed. We present a wearable peripheral display embedded in eyeglasses that delivers subtle, discreet and unobtrusive cues. The display is personal and intimate; it delivers visual cues in the wearers' periphery without disrupting their immediate environment. A user study conducted to validate the design reveals that the display is effective and subtle in notifying users. Experimental results show, with significance, that the cues can be designed to meet specific levels of visibility and disruption for the wearer, so that some cues are less noticeable when the user is not under high workload, which is highly desirable in many practical circumstances. Hence, peripheral notification displays can provide an effective solution for designing socially acceptable notification displays, unobtrusive to the user and the immediate environment.

We present a randomized Byzantine Agreement (BA) protocol with an expected running time of O(log n) rounds, in a synchronous full-information network of n players. For any constant ε > 0, the constructed protocol tolerates t non-adaptive Byzantine faults, as long as n ≥ (4 + ε)t. In the full-information model, no restrictions are placed on the computational power of the faulty players or the information available to them. In particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.This constitutes significant progress over the best known randomized BA protocol in the same setting which has a round-complexity of Θ(t/log n) rounds [9], and answers an open problem posed by Chor and Dwork [10].

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm which constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to every other process. If message size is $\Theta(n^\epsilon)$ for some $\epsilon>0$, then the number of communication rounds is $O(\log{1\over\epsilon})$.

We consider the problem of a spatially distributed market with strategic agents. In this problem a single good is traded in a set of independent markets, where shipment between markets is possible but incurs a cost. The problem has previously been studied in the non-strategic case, inwhich it can be analyzed and solved as a min-cost-flow problem. We considerthe case where buyers and sellers are strategic. Our first result gives adouble characterization of the VCG prices, first as distances in acertain residue graph and second as the minimal (for buyers) and maximal (forsellers) equilibrium prices. This provides a computationally efficient, individually rational and incentive compatible welfare maximizing mechanism. This mechanism is, necessarily, not budget balanced and we provide alsoa budget-balanced mechanism (which is also computationally efficient,incentive compatible, and individually rational) that achieves highwelfare. Some of our results extend to the cases where buyers andsellers have arbitrary convex demand and supply functions and to the case where transportation is controlled by strategic agents as well.

We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a distributed algorithm that constructs a minimum-weight spanning tree in O(log log n) communication rounds, where in each round any process can send a message to each other process. This result is the first to break the ω(log n) parallel time complexity barrier with small message sizes.