We revisit a classic coordination problem from the perspective of mechanism design: how can we coordinate a social welfare maximizing flow in a network congestion game with selfish players? The classical approach, whi...
详细信息
ISBN:
(纸本)9781450334105
We revisit a classic coordination problem from the perspective of mechanism design: how can we coordinate a social welfare maximizing flow in a network congestion game with selfish players? The classical approach, which computes tolls as a function of known demands, fails when the demands are unknown to the mechanism designer, and naively eliciting them does not necessarily yield a truthful mechanism. Instead, we introduce a weak mediator that can provide suggested routes to players and set tolls as a function of reported demands. However, players can choose to ignore or misreport their type to this mediator. Using techniques from differential privacy, we show how to design a weak mediator such that it is an asymptotic ex-post Nash equilibrium for all players to truthfully report their types to the mediator and faithfully follow its suggestion, and that when they do, they end up playing a nearly optimal flow. Notably, our solution works in settings of incomplete information even in the absence of a prior distribution on player types. Along the way, we develop new techniques for privately solving convex programs which may be of independent interest.
A multiprogrammed (or partitionable) parallel computer system can be partitioned into subsystems which are allocated to independent jobs. The performance of such a parallel processing system is determined by the syste...
详细信息
A multiprogrammed (or partitionable) parallel computer system can be partitioned into subsystems which are allocated to independent jobs. The performance of such a parallel processing system is determined by the system partitioning strategy and the job scheduling policy adopted. In this paper, we consider the impact of a job scheduling algorithm on the system performance, mainly the average job response time. A refined First-Come-First-Serve (FCFS) queueing discipline called FCFS/SJE is studied, which, when there are not enough processors available for large jobs in the front of a waiting queue, schedules small jobs behind these large jobs earlier. We develop a multi-server queueing system for modelling multiprogrammed parallel processing systems. A system is specified by the number of processors and jobs are characterized by a probability distribution of the number of processors requested, a Poisson arrival process, and an exponential distribution of execution time. Our analysis as well as simulation indicate that FCFS/SJE results in a noticeable improvement on system performance compared with FCFS.
In the (classical) SECRETARY PROBLEM, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a uniformly random order, and one has to decide on the spot, whether to hire a candi...
详细信息
ISBN:
(纸本)9781510836358
In the (classical) SECRETARY PROBLEM, one has to hire the best among n candidates. The candidates are interviewed, one at a time, at a uniformly random order, and one has to decide on the spot, whether to hire a candidate or continue interviewing. It is well known that the best candidate can be hired with a probability of 1/e (Dynkin, 1963). Recent works extend this problem to settings in which multiple candidates can be hired, subject to some constraint. Here, one wishes to hire a set of candidates maximizing a given objective set function. Almost all extensions considered in the literature assume the objective set function is either linear or submodular. Unfortunately, real world functions might not have either of these properties. Consider, for example, a scenario where one hires researchers for a project. Indeed, it can be that some researchers can substitute others for that matter. However, it can also be that some combinations of researchers result in synergy (see, e.g., Woolley et al., science 2010, for a study on collective intelligence). The first phenomenon can be modeled by a submoudlar set function, while the latter cannot. In this work, we study the secretary problem with an arbitrary non-negative monotone valuation function, subject to a general matroid constraint. One can prove that, generally, only very poor results can be obtained for this class of objective functions. We tackle this hardness by combining the following: (1) Parametrizing our algorithms by the supermodular degree of the objective function (defined by Feige and Izsak, ITCS 2013), which, roughly speaking, measures the distance of a function from being submodular. (2) Suggesting an (arguably) natural model that permits approximation guarantees that are polynomial in the supermodular degree (as opposed to the standard model which allows only exponential guarantees). Our algorithms learn the input by running a non-trivial estimation algorithm on a portion of it whose size depends on the s
The uniform persistence is proved for a non-autonomous competitive and prey-predator model with ratio-dependent functional response and stage-structure. By constructing a Liapunov functional, we establish the conditio...
详细信息
The uniform persistence is proved for a non-autonomous competitive and prey-predator model with ratio-dependent functional response and stage-structure. By constructing a Liapunov functional, we establish the conditions of existence and uniqueness for the positive periodic solution, which is globally asymptotically stable. We get a unique almost periodic solution for an almost periodic system as well under corresponding conditions .by means of the Razumikhin function method.
We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improv...
详细信息
A Query by Humming system allows the user to find a song by humming part of the tune. No musical training is needed. Previous query by humming systems have not provided satisfactory results for various reasons. Some s...
ISBN:
(纸本)9781581136340
A Query by Humming system allows the user to find a song by humming part of the tune. No musical training is needed. Previous query by humming systems have not provided satisfactory results for various reasons. Some systems have low retrieval precision because they rely on melodic contour information from the hum tune, which in turn relies on the error-prone note segmentation process. Some systems yield better precision when matching the melody directly from audio, but they are slow because of their extensive use of Dynamic Time Warping (DTW). Our approach improves both the retrieval precision and speed compared to previous approaches. We treat music as a time series and exploit and improve well-developed techniques from time series databases to index the music for fast similarity queries. We improve on existing DTW indexes technique by introducing the concept of envelope transforms, which gives a general guideline for extending existing dimensionality reduction methods to DTW indexes. The net result is high scalability. We confirm our claims through extensive experiments.
TCP performance degrades significantly in mobile ad hoc networks because most of packet losses occur as a result of route failures. Prior work proposed to provide link failure feedback to TCP so that TCP can avoid res...
详细信息
ISBN:
(纸本)9781581138689
TCP performance degrades significantly in mobile ad hoc networks because most of packet losses occur as a result of route failures. Prior work proposed to provide link failure feedback to TCP so that TCP can avoid responding to route failures as if congestion had occurred. However, after a link failure is detected, several packets will be dropped from the network interface queue;TCP will time out because of these losses. It will also time out for ACK losses caused by route failures. In this paper, we propose to make routing protocols aware of lost data packets and ACKs and help reduce TCP timeouts for mobility-induced losses. Toward this end, we present two mechanisms: early packet loss notification (EPLN) and best-effort ACK delivery (BEAD). EPLN seeks to notify TCP senders about lost data packets. For lost ACKs, BEAD attempts to retransmit ACKs at either intermediate nodes or TCP receivers. Both mechanisms extensively use cached routes, without initiating route discoveries at any intermediate node. We evaluate TCP-ELFN enhanced with the two mechanisms using two caching strategies for DSR, path caches and a distributed cache update algorithm proposed in our prior work. We show that TCP-ELFN with EPLN and BEAD significantly outperforms TCP-ELFN under both caching strategies. We conclude that cross-layer information awareness is key to making TCP efficient in the presence of mobility.
A parallel computation model that takes advantage of a networking infrastructure that enables server-free resource sharing based on the Jini approach is described. The network is a connected network of nodes that dire...
详细信息
ISBN:
(纸本)1581134282
A parallel computation model that takes advantage of a networking infrastructure that enables server-free resource sharing based on the Jini approach is described. The network is a connected network of nodes that directly know their neighborhood but can access the entire network. The constructed network infrastructure of handheld machines tolerates the dynamic nature of a mobile ad hoc network and provides the foundation for applications to take advantage of this type of computing network.
We study a partial-information online-learning problem where actions are restricted to noisy comparisons between pairs of strategies (also known as bandits). In contrast to conventional approaches that require the abs...
We study a partial-information online-learning problem where actions are restricted to noisy comparisons between pairs of strategies (also known as bandits). In contrast to conventional approaches that require the absolute reward of the chosen strategy to be quantifiable and observable, our setting assumes only that (noisy) binary feedback about the relative reward of two chosen strategies is available. This type of relative feedback is particularly appropriate in applications where absolute rewards have no natural scale or are difficult to measure (e.g., user-perceived quality of a set of retrieval results, taste of food, product attractiveness), but where pairwise comparisons are easy to make. We propose a novel regret formulation in this setting, as well as present an algorithm that achieves (almost) information-theoretically optimal regret bounds (up to a constant factor).
暂无评论