1,720,985 research outputs found
Bounded incentives in manipulating the Probabilistic Serial rule
No full textThe Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not incentive-compatible, thereby these desirable properties only hold for the agents' declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is 3/2. That is, no agent can misreport its preferences such that its utility becomes more than 1.5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents' reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agent's utility gain on average by experiments. The experiments show that an agent' incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible
On the design of truthful mechanisms for the capacitated facility location problem with two and more facilities
Full text linkIn this paper, we explore the Mechanism Design aspects of the m-Capacitated Facility Location Problem (m-CFLP) on a line, focusing on two frameworks. In the first framework, the number of facilities is arbitrary, all facilities share the same capacity, and the number of agents matches the total capacity of the facilities. In the second framework, we need to locate two facilities, each with a capacity equal to at least half the number of agents. For both frameworks, we propose truthful mechanisms with bounded approximation ratios in terms of Social Cost (SC) and Maximum Cost (MC). When m>2, our results stand in contrast to the impossibility results known for the classical m-Facility Location Problem, where capacity constraints are absent. Moreover, all the proposed mechanisms are optimal with respect to MC and either optimal or near-optimal with respect to the SC among anonymous mechanisms. We then establish lower bounds on the approximation ratios that any truthful and deterministic mechanism achieves with respect to SC and MC for both frameworks. Lastly, we run several numerical experiments to empirically evaluate the performances of our mechanisms with respect to the SC or the MC. Our empirical analysis shows that our proposed mechanisms outperform all previously proposed mechanisms applicable in this setting
On the Distortion of Multi-winner Election Using Single-Candidate Ballots
No full textpaper, we study the distortion bounds for voting mechanisms in multi-winner elections in general metric spaces. Our study pertains to the case in which each voter only reports her favorite candidate amongst m possible choices. Given that candidates’ locations are undisclosed to the mechanism, the mechanism has to form a w-winner committee based solely on the number of votes received by candidates. We establish distortion bounds for both truthful and non-truthful mechanisms. Our research highlights the significance of the σ parameter, which represents the ratio between maximum and minimum distances among all candidate pairs. We show that the distortion is linear in σ. First, we demonstrate that all mechanisms possess a distortion greater than 1+w-1w+1(σ-1). To give an upper bound, we study the Single Non-Transferable Vote (SNTV) mechanism, whose distortion is at most 1+2σ. Second, we retrieve the upper bounds for strategyproof mechanisms. In particular, we infer an upper bound by examining the Random Sequential Dictator mechanism that achieves a distortion less than 1+4σ when w=2
Optimal pricing policy design for selling cost-reducing innovation in Cournot games
Full text linkIn a marketplace where a number of firms produce and sell a homogeneous product, an innovator develops cost-cutting manufacturing technology and decides to sell it to various firms in the form of a license for profit. Given the innovator's license pricing policy, each firm independently decides whether to purchase the innovation license and how many products to produce. To put it simply, the firms are then in a Cournot market in which the product price is a decreasing function of the total amount of the product on the market. Both the innovator and the firms are acting out of self-interest and look to maximize their utilities. We consider the problem of designing optimal pricing policies for the innovator. A pricing policy could be in the form of a one-off upfront fee, a per-unit royalty fee, or a hybrid of both. Building upon the results of Segal [1], we first show that in a properly designed pricing policy, it is a strictly dominant strategy for the firms to accept the pricing policy, and that this constitutes the unique Nash equilibrium of the game. For the hybrid-fee policy, we devise an algorithm that computes the optimal price in time O(n
3), where n is the number of firms. For the royalty-fee policy, we show that the problem is captured by convex quadratic programming and can be solved in time O(n
6L
2), where L is the number of input bits. For the upfront-fee policy, we show the optimal policy problem is NP-complete and we devise an FPTAS algorithm. Moreover, we compare the revenue achievable through the above three pricing policies when all firms are identical.
</p
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
