ﻻ يوجد ملخص باللغة العربية
On-line firms deploy suites of software platforms, where each platform is designed to interact with users during a certain activity, such as browsing, chatting, socializing, emailing, driving, etc. The economic and incentive structure of this exchange, as well as its algorithmic nature, have not been explored to our knowledge. We model this interaction as a Stackelberg game between a Designer and one or more Agents. We model an Agent as a Markov chain whose states are activities; we assume that the Agents utility is a linear function of the steady-state distribution of this chain. The Designer may design a platform for each of these activities/states; if a platform is adopted by the Agent, the transition probabilities of the Markov chain are affected, and so is the objective of the Agent. The Designers utility is a linear function of the steady state probabilities of the accessible states minus the development cost of the platforms. The underlying optimization problem of the Agent -- how to choose the states for which to adopt the platform -- is an MDP. If this MDP has a simple yet plausible structure (the transition probabilities from one state to another only depend on the target state and the recurrent probability of the current state) the Agents problem can be solved by a greedy algorithm. The Designers optimization problem (designing a custom suite for the Agent so as to optimize, through the Agents optimum reaction, the Designers revenue), is NP-hard to approximate within any finite ratio; however, the special case, while still NP-hard, has an FPTAS. These results generalize from a single Agent to a distribution of Agents with finite support, as well as to the setting where the Designer must find the best response to the existing strategies of other Designers. We discuss other implications of our results and directions of future research.
We describe a structured system for distributed mechanism design. It consists of a sequence of layers. The lower layers deal with the operations relevant for distributed computing only, while the upper layers are concerned only with communication amo
The Possible-Winner problem asks, given an election where the voters preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of Possi
We provide a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with mu
In this paper, we study a problem of truthful mechanism design for a strategic variant of the generalized assignment problem (GAP) in a both payment-free and prior-free environment. In GAP, a set of items has to be optimally assigned to a set of bins
In a stable matching setting, we consider a query model that allows for an interactive learning algorithm to make precisely one type of query: proposing a matching, the response to which is either that the proposed matching is stable, or a blocking p