اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLearning Whats going on: reconstructing preferences and priorities from opaque transactions
44
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider a setting where $n$ buyers, with combinatorial preferences over $m$ items, and a seller, running a priority-based allocation mechanism, repeatedly interact. Our goal, from observing limited information about the results of these interactions, is to reconstruct both the preferences of the buyers and the mechanism of the seller. More specifically, we consider an online setting where at each stage, a subset of the buyers arrive and are allocated items, according to some unknown priority that the seller has among the buyers. Our learning algorithm observes only which buyers arrive and the allocation produced (or some function of the allocation, such as just which buyers received positive utility and which did not), and its goal is to predict the outcome for future subsets of buyers. For this task, the learning algorithm needs to reconstruct both the priority among the buyers and the preferences of each buyer. We derive mistake bound algorithms for additive, unit-demand and single minded buyers. We also consider the case where buyers utilities for a fixed bundle can change between stages due to different (observed) prices. Our algorithms are efficient both in computation time and in the maximum number of mistakes (both polynomial in the number of buyers and items).
قيم البحث
اقرأ أيضاً
We motivate and propose a new model for non-cooperative Markov game which considers the interactions of risk-aware players. This model characterizes the time-consistent dynamic risk from both stochastic state transitions (inherent to the game) and ra
ndomized mixed strategies (due to all other players). An appropriate risk-aware equilibrium concept is proposed and the existence of such equilibria is demonstrated in stationary strategies by an application of Kakutanis fixed point theorem. We further propose a simulation-based Q-learning type algorithm for risk-aware equilibrium computation. This algorithm works with a special form of minimax risk measures which can naturally be written as saddle-point stochastic optimization problems, and covers many widely investigated risk measures. Finally, the almost sure convergence of this simulation-based algorithm to an equilibrium is demonstrated under some mild conditions. Our numerical experiments on a two player queuing game validate the properties of our model and algorithm, and demonstrate their worth and applicability in real life competitive decision-making.
The design of optimal auctions is a problem of interest in economics, game theory and computer science. Despite decades of effort, strategyproof, revenue-maximizing auction designs are still not known outside of restricted settings. However, recent m
ethods using deep learning have shown some success in approximating optimal auctions, recovering several known solutions and outperforming strong baselines when optimal auctions are not known. In addition to maximizing revenue, auction mechanisms may also seek to encourage socially desirable constraints such as allocation fairness or diversity. However, these philosophical notions neither have standardization nor do they have widely accepted formal definitions. In this paper, we propose PreferenceNet, an extension of existing neural-network-based auction mechanisms to encode constraints using (potentially human-provided) exemplars of desirable allocations. In addition, we introduce a new metric to evaluate an auction allocations adherence to such socially desirable constraints and demonstrate that our proposed method is competitive with current state-of-the-art neural-network based auction designs. We validate our approach through human subject research and show that we are able to effectively capture real human preferences. Our code is available at https://github.com/neeharperi/PreferenceNet
A preference profile is single-peaked on a tree if the candidate set can be equipped with a tree structure so that the preferences of each voter are decreasing from their top candidate along all paths in the tree. This notion was introduced by Demang
e (1982), and subsequently Trick (1989) described an efficient algorithm for deciding if a given profile is single-peaked on a tree. We study the complexity of multiwinner elections under several variants of the Chamberlin-Courant rule for preferences single-peaked on trees. We show that the egalitarian version of this problem admits a polynomial-time algorithm. For the utilitarian version, we prove that winner determination remains NP-hard, even for the Borda scoring function; however, a winning committee can be found in polynomial time if either the number of leaves or the number of internal vertices of the underlying tree is bounded by a constant. To benefit from these positive results, we need a procedure that can determine whether a given profile is single-peaked on a tree that has additional desirable properties (such as, e.g., a small number of leaves). To address this challenge, we develop a structural approach that enables us to compactly represent all trees with respect to which a given profile is single-peaked. We show how to use this representation to efficiently find the best tree for a given profile for use with our winner determination algorithms: Given a profile, we can efficiently find a tree with the minimum number of leaves, or a tree with the minimum number of internal vertices among trees on which the profile is single-peaked. We also consider several other optimization criteria for trees: for some we obtain polynomial-time algorithms, while for others we show NP-hardness results.
We study the three-dimensional stable matching problem with cyclic preferences. This model involves three types of agents, with an equal number of agents of each type. The types form a cyclic order such that each agent has a complete preference list
over the agents of the next type. We consider the open problem of the existence of three-dimensional matchings in which no triple of agents prefer each other to their partners. Such matchings are said to be weakly stable. We show that contrary to published conjectures, weakly stable three-dimensional matchings need not exist. Furthermore, we show that it is NP-complete to determine whether a weakly stable three-dimensional matchings exists. We achieve this by reducing from the variant of the problem where preference lists are allowed to be incomplete. Our results can be generalized to the $k$-dimensional stable matching problem with cyclic preferences for $k geq 3$.
We consider the problem of committee selection from a fixed set of candidates where each candidate has multiple quantifiable attributes. To select the best possible committee, instead of voting for a candidate, a voter is allowed to approve the prefe
rred attributes of a given candidate. Though attribute based preference is addressed in several contexts, committee selection problem with attribute approval of voters has not been attempted earlier. A committee formed on attribute preferences is more likely to be a better representative of the qualities desired by the voters and is less likely to be susceptible to collusion or manipulation. In this work, we provide a formal study of the different aspects of this problem and define properties of weak unanimity, strong unanimity, simple justified representations and compound justified representation, that are required to be satisfied by the selected committee. We show that none of the existing vote/approval aggregation rules satisfy these new properties for attribute aggregation. We describe a greedy approach for attribute aggregation that satisfies the first three properties, but not the fourth, i.e., compound justified representation, which we prove to be NP-complete. Furthermore, we prove that finding a committee with justified representation and the highest approval voting score is NP-complete.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
