Stream-based inconsistency measurement

Inconsistency measures have been proposed to assess the severity of inconsistencies in knowledge bases of classical logic in a quantitative way. In general, computing the value of inconsistency is a computationally hard task as it is based on the satisfiability problem which is itself NP-complete. In this work, we address the problem of measuring inconsistency in knowledge bases that are accessed in a stream of propositional formulæ. That is, the formulæ of a knowledge base cannot be accessed directly but only once through processing of the stream. This work is a first step towards practicable inconsistency measurement for applications such as Linked Open Data, where huge amounts of information is distributed across the web and a direct assessment of the quality or inconsistency of this information is infeasible due to its size. Here we discuss the problem of stream-based inconsistency measurement on classical logic, in order to make use of existing measures for classical logic. However, it turns out that inconsistency measures defined on the notion of minimal inconsistent subsets are usually not apt to be used in the streaming scenario. In order to address this issue, we adapt measures defined on paraconsistent logics and also present a novel inconsistency measure based on the notion of a hitting set. We conduct an extensive empirical analysis on the behavior of these different inconsistency measures in the streaming scenario, in terms of runtime, accuracy, and scalability. We conclude that for two of these measures, the stream-based variant of the new inconsistency measure and the stream-based variant of the contension inconsistency measure, large-scale inconsistency measurement in streaming scenarios is feasible.     

Distributed caching over heterogeneous mobile networks

Sharing content over a mobile network through opportunistic contacts has recently received considerable attention. In proposed scenarios, users store content they download in a local cache and share it with other users they meet, e.g., via Bluetooth or WiFi. The storage capacity of mobile devices is typically limited; therefore, identifying which content a user should store in her cache is a fundamental problem in the operation of any such content distribution system. In this work we propose Psephos, a novel mechanism for determining the caching policy of each mobile user. Psephos is fully distributed: users compute their own policies individually, in the absence of a central authority. Moreover, it is designed for a heterogeneous environment, in which demand for content, access to resources, and mobility characteristics may vary across different users. Most importantly, the caching policies computed by our mechanism are optimal: we show that Psephos maximizes the system’s social welfare. To the best of our knowledge, our work is the first to address caching with heterogeneity in a fully distributed manner.     

Assuring consistency in mixed models

Information systems security defines three properties of information: confidentiality, integrity, and availability. These characteristics remain major concerns throughout the commercial and military industry. Ordinary users have taken these features as basis for their businesses. Furthermore, users may find it necessary to combine policies in order to protect their information in a suitable way. However, inconsistencies may arise as a result of implementing multiple secrecy and privacy models; and therefore, render these services unsecure. In this paper, we propose an approach to detect and report inconsistencies when choosing mixed models for integrity and security. It is based on specifying the policies in first order logic and applying formal analysis. We demonstrate the feasibility of our proposition by applying it to the Clark Wilson and role based access control models. We use the Alloy language and analyzer to formalize the mixed model and check for any inconsistencies.     

Model Based Comparison of Discounted Cumulative Gain and Average Precision

In this paper, we propose to explain Discounted Cumulative Gain (DCG) as the expectation of the total utility collected by a user given a generative probabilistic model on how users browse the result page ranking list of a search engine. We contrast this with a generalization of Average Precision, pAP, that has been defined in Dupret and Piwowarski (2010) [13]. In both cases, user decision models coupled with Web search logs allow to estimate some parameters that are usually left to the designer of a metric. In this paper, we compare the user models for DCG and pAP at the interpretation and experimental level.DCG and AP are metrics computed before a ranking function is exposed to users and as such, their role is to predict the function performance. In counterpart to prognostic metric, a diagnostic metric is computed after observing the user interactions with the result list. A commonly used diagnostic metric is the clickthrough rate at position 1, for example. In this work we show that the same user model developed for DCG can be used to derive a diagnostic version of this metric. The same hold for pAP and any metric with a proper user model.We show that not only does this diagnostic view provide new information, it also allows to define a new criterion for assessing a metric. In previous works based on user decision modeling, the performance of different metrics were compared indirectly in terms of the ability of the associated user model to predict future user actions. Here we propose a new and more direct criterion based on the ability of the prognostic version of the metric to predict the diagnostic performance.     

Rough sets theory for multicriteria decision analysis

The original rough set approach proved to be very useful in dealing with inconsistency problems following from information granulation. It operates on a data table composed of a set U of objects (actions) described by a set Q of attributes. Its basic notions are: indiscernibility relation on U, lower and upper approximation of either a subset or a partition of U, dependence and reduction of attributes from Q, and decision rules derived from lower approximations and boundaries of subsets identified with decision classes. The original rough set idea is failing, however, when preference-orders of attribute domains (criteria) are to be taken into account. Precisely, it cannot handle inconsistencies following from violation of the dominance principle. This inconsistency is characteristic for preferential information used in multicriteria decision analysis (MCDA) problems, like sorting, choice or ranking. In order to deal with this kind of inconsistency a number of methodological changes to the original rough sets theory is necessary. The main change is the substitution of the indiscernibility relation by a dominance relation, which permits approximation of ordered sets in multicriteria sorting. To approximate preference relations in multicriteria choice and ranking problems, another change is necessary: substitution of the data table by a pairwise comparison table, where each row corresponds to a pair of objects described by binary relations on particular criteria. In all those MCDA problems, the new rough set approach ends with a set of decision rules playing the role of a comprehensive preference model. It is more general than the classical functional or relational model and it is more understandable for the users because of its natural syntax. In order to workout a recommendation in one of the MCDA problems, we propose exploitation procedures of the set of decision rules. Finally, some other recently obtained results are given: rough approximations by means of similarity relations, rough set handling of missing data, comparison of the rough set model with Sugeno and Choquet integrals, and results on equivalence of a decision rule preference model and a conjoint measurement model which is neither additive nor transitive.     

Centralized and decentralized management of groundwater with multiple users

In this work, we investigate two groundwater inventory management schemes with multiple users in a dynamic game-theoretic structure: (i) under the centralized management scheme, users are allowed to pump water from a common aquifer with the supervision of a social planner, and (ii) under the decentralized management scheme, each user is allowed to pump water from a common aquifer making usage decisions individually in a non-cooperative fashion. This work is motivated by the work of Saak and Peterson [14], which considers a model with two identical users sharing a common aquifer over a two-period planning horizon. In our work, the model and results of Saak and Peterson [14] are generalized in several directions. We first build on and extend their work to the case of n non-identical users distributed over a common aquifer region. Furthermore, we consider two different geometric configurations overlying the aquifer, namely, the strip and the ring configurations. In each configuration, general analytical results of the optimal groundwater usage are obtained and numerical examples are discussed for both centralized and decentralized problems.     

Multiple voting location and single voting location on trees

We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by γ-proportion.     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

Flow-level performance and capacity of wireless networks with user mobility

The performance evaluation of wireless networks is severely complicated by the specific features of radio communication, such as highly variable channel conditions, interference issues, and possible hand-offs among base stations. The latter elements have no natural counterparts in wireline scenarios, and create a need for novel performance models that account for the impact of these characteristics on the service rates of users. Motivated by the above issues, we review several models for characterizing the capacity and evaluating the flow-level performance of wireless networks carrying elastic data transfers. We first examine the flow-level performance and stability of a wide family of so-called α-fair channel-aware scheduling strategies. We establish that these disciplines provide maximum stability, and describe how the special case of the Proportional Fair policy gives rise to a Processor-Sharing model with a state-dependent service rate. Next we turn attention to a network of several base stations with inter-cell interference. We derive both necessary and sufficient stability conditions and construct lower and upper bounds for the flow-level performance measures. Lastly we investigate the impact of user mobility that occurs on a slow timescale and causes possible hand-offs of active sessions. We show that the mobility tends to increase the capacity region, both in the case of globally optimal scheduling and local α-fair scheduling. It is additionally demonstrated that the capacity and user throughput improve with lower values of the fairness index α.     

Resolving sets and integer programs for recommender systems

Recommender systems make use of different sources of information for providing users with recommendations of items. Such systems are often based on either collaborative filtering methods which make automatic predictions about the interests of a user, using preferences of similar users, or content based filtering that matches the user’s personal preferences with item characteristics. We adopt the content-based approach and propose to use the concept of resolving set that allows to determine the preferences of the users with a very limited number of ratings. We also show how to make recommendations when user ratings are imprecise or inconsistent, and we indicate how to take into account situations where users possibly don’t care about the attribute values of some items. All recommendations are obtained in a few seconds by solving integer programs.

     

Anonymous Membership Broadcast Schemes

A membership broadcast scheme is a method by which a dealer broadcasts a secret identity among a set of users, in such a way that only a single user is sure that he is the intended recipient. Anonymous membership broadcast schemes have several applications, such as anonymous delegation, cheating prevention, etc. In a w-anonymous membership broadcast scheme any coalition of at most w users, which does not include the user chosen by the dealer, has no information about the identity of the chosen user. Wang and Pieprzyk proposed a combinatorial approach to 1-anonymous membership broadcast schemes. In particular, they proposed a 1-anonymous membership broadcast scheme offering a logarithmic complexity for both communication and storage. However, their result is non-constructive. In this paper, we consider w-anonymous membership broadcast schemes. First, we propose a formal model to describe such schemes and show lower bounds on the communication and randomness complexities of the schemes. Afterwards, we show that w-anonymous membership broadcast schemes can be constructed starting from (w + 1)-wise independent families of permutations. The communication and storage complexities of our schemes are logarithmic in the number of users.     

The Leibniz catenary and approximation of e — an analysis of his unpublished calculations

Leibniz published his Euclidean construction of a catenary in Acta Eruditorum of June 1691, but he was silent about the methods used to discover it. He explained how he used his differential calculus only in a private letter to Rudolph Christian von Bodenhausen and specified a number that was key to his construction, 2.7182818, with no clue about how he calculated it. Apparently, the calculations were never divulged to anyone but were discovered later among his personal papers. They may be the earliest record of an accurate approximation of the number we label e and a demonstration of its role as the base of the natural logarithm and exponential function.This, at that time, was a remarkably precise estimate for e, accomplished more than 22 years before Roger Cotes published e to 12 significant digits, and some 57 years before Euler's treatment of the logarithm in his Introductio in Analysin Infinitorum. The Leibniz construction reveals a hyperbolic cosine built on an exponential curve based on his estimated value, which implies that he understood the number as the base of his logarithmic curve. The sheets of arithmetic used by Leibniz preserved at the Gottfried Wilhelm Leibniz Bibliothek (GWLB) in Hannover, confirm this.Those sheets show how Leibniz calculated e and applied it to his catenary construction. The data actually yield e to 12 significant figures: 2.71828182845, missed by Leibniz because of a misplaced decimal point. We summarize the construction and examine the worksheets. The unpublished methods seem entirely modern to us and could serve as enrichening examples in modern calculus texts.     

Dynamic power control in a fading downlink channel subject to an energy constraint

A central controller chooses a state-dependent transmission rate for each user in a fading, downlink channel by varying transmission power over time. For each user, the state of the channel evolves over time according to an exogenous continuous-time Markov chain (CTMC), which affects the quality of transmission. The traffic for each user, arriving at the central controller, is modeled as a finite-buffer Markovian queue with adjustable service rates. That is, for each user data packets arrive to the central controller according to a Poisson process and packet size is exponentially distributed; an arriving packet is dropped if the associated buffer is full, which results in degradation of quality of service. The controller forwards (downlink) the arriving packets to the corresponding user according to an optimally chosen transmission rate from a fixed set A _i of available values for each user i, depending on the backlog in the system and the channel state of all users. The objective is to maximize quality of service subject to an upper bound on the long-run average power consumption. We show that the optimal transmission rate for each user is solely a function of his own packet queue length and channel state; the dependence among users is captured through a penalty rate. Further, we explicitly characterize the optimal transmission rate for each user. This project is partially supported by Motorola grant # 0970-350-AF24. The authors thank Phil Fleming,Randy Berry and Achal Bassamboo for helpful comments.     

Generalized Fibonacci broadcasting: An efficient VOD scheme with user bandwidth limit

Broadcasting is attractive in delivering popular videos in video-on-demand service, because the server broadcast bandwidth is independent of the number of users. However, the required server bandwidth does depend on how much bandwidth each user can use, as well as on the user's initial waiting time. This paper addresses the issue of limiting the user bandwidth, and proposes a new broadcasting scheme, named Generalized Fibonacci Broadcasting (GFB). In terms of many performance graphs, we show that, for any given combination of the server bandwidth and user bandwidth, GFB can achieve the least waiting time among all the currently known fixed-delay broadcasting schemes. Furthermore, it is very easy to implement GFB. We also demonstrate that there is a trade-off between the user waiting time and the buffer requirement at the user.     

Linear spaces and transversal designs: k-anonymous combinatorial configurations for anonymous database search notes

Anonymous database search protocols allow users to query a database anonymously. This can be achieved by letting the users form a peer-to-peer community and post queries on behalf of each other. In this article we discuss an application of combinatorial configurations (also known as regular and uniform partial linear spaces) to a protocol for anonymous database search, as defining the key-distribution within the user community that implements the protocol. The degree of anonymity that can be provided by the protocol is determined by properties of the neighborhoods and the closed neighborhoods of the points in the combinatorial configuration that is used. Combinatorial configurations with unique neighborhoods or unique closed neighborhoods are described and we show how to attack the protocol if such configurations are used. We apply k-anonymity arguments and present the combinatorial configurations with k-anonymous neighborhoods and with k-anonymous closed neighborhoods. The transversal designs and the linear spaces are presented as optimal configurations among the configurations with k-anonymous neighborhoods and k-anonymous closed neighborhoods, respectively.     

Imperfect recall and time inconsistencies: an experimental test of the absentminded driver “paradox”

Absentmindedness is a special case of imperfect recall, in which a single history includes more than one decision node in an information set. Put differently, players, after making a decision, sometimes face it again without recalling having ‘been there before’. Piccione and Rubinstein (Game Econ Behav 20(1):3–24, 1997b) have argued that absentmindedness may lead to time inconsistencies. Specifically, in certain cases, a player’s optimal strategy as calculated when called to choose an action (the action stage) deviates from the optimal strategy as calculated in a preceding planning stage, although preferences remain constant and no new information is revealed between the two stages. An alternative approach assumes that the player maximizes expected payoff in the action stage while considering his actions at other decision nodes to be immutable. With this approach, no time inconsistencies arise. The present paper explores this issue from a behavioral point of view. We elicit participants’ strategies in an experimental game of absentmindedness, separately for a planning stage and an action stage. We find systematic and robust time inconsistencies under four variations of the experiment and using ten different parameterizations of the game. We conclude that real decisions under absentmindedness without commitment are susceptible to time inconsistencies.     

Central versus local multiple stage inventory planning: An analysis of solutions

Supply chain management refers to the integration of all activities associated with moving goods from raw material stages through to end users. Yet this system-wide vision of inventory planning often requires the coordination of several commercially independent entities, such as suppliers, manufacturers and distributors. This study explores the issue of friction between replenishment policies, defined as the disparity between centrally and locally planned solutions to 98,820 deterministic, multiple stage inventory planning problems modeling systems of varying levels of complexity. Friction is found to be strongly related to certain cost factors, suggesting that certain supply chains could be more vulnerable to tension and inefficiencies when replenishment policies are derived without cooperation between commercially independent yet logistically interdependent stages. These results can also be applied to identify relationships between the findings of otherwise seemingly disparate previous studies of coordination schemes for supply chain partners.     

An incentive charging scheme for video-on-demand

Video-on-demand (VOD) systems can provide either an individual service or batch service. For individual service, a user can receive video immediately after making a request and he/she can perform interactive operations (such as pause, jump, fast forward and rewind), and the system uses one video stream to serve one user. For batch service, a user has to wait after making a request and cannot perform interactive operations, but the system can use one video stream to serve a batch of users. Therefore, individual service has a better quality while batch service requires less resources to serve each user. In this paper, we consider a VOD system providing both services and propose an incentive charging scheme to optimize the coexistence of both services. This scheme imposes a lower service charge on batch service in order to attract users to choose this service. Consequently, the service provider can get more revenue by serving more concurrent users via batch service and users can choose their preferred services. We analyze the incentive charging scheme and maximize the mean revenue subject to a given availability specification. The numerical results show that the incentive charging scheme is particularly effective in peak hours when the demand for the VOD service is large.     

Likelihood estimation of consumer preferences in choice-based conjoint analysis

In marketing research the measurement of individual preferences and assessment of utility functions have long traditions. Conjoint analysis, and particularly choice-based conjoint analysis (CBC), is frequently employed for such measurement. The world today appears increasingly customer or user oriented wherefore research intensity in conjoint analysis is rapidly increasing in various fields, OR/MS being no exception. Although several optimization based approaches have been suggested since the introduction of the Hierarchical Bayes (HB) method for estimating CBC utility functions, recent comparisons indicate that challenging HB is hard. Based on likelihood maximization we propose a method called LM and compare its performance with HB using twelve field data sets. Performance comparisons are based on holdout validation, i.e. predictive performance. Average performance of LM indicates an improvement over HB and the difference is statistically significant. We also use simulation based data sets to compare the performance for parameter recovery. In terms of both predictive performance and RMSE a smaller number of questions in CBC appears to favor LM over HB.