330 research outputs found
Limited Verification of Identities to Induce False-Name-Proofness
No full textIn open, anonymous environments such as the
Internet, mechanism design is complicated by
the fact that a single agent can participate in
the mechanism under multiple identifiers. One
way to address this is to design false-name-proof
mechanisms, which choose the outcome in such
a way that agents have no incentive to use more
than one identifier. Unfortunately, there are inherent
limitations on what can be achieved with
false-name-proof mechanisms, and at least in
some cases, these limitations are crippling. An
alternative approach is to verify the identities of
all agents. This imposes significant overhead and
removes any benefits from anonymity.
In this paper, we propose a middle ground. Based
on the reported preferences, we check, for various
subsets of the reports, whether the reports in
the subset were all submitted by different agents.
If they were not, then we discard some of them.
We characterize when such a limited verification
protocol induces false-name-proofness for a
mechanism, that is, when the combination of the
mechanism and the verification protocol gives
the agents no incentive to use multiple identi-
fiers. This characterization leads to various optimization
problems for minimizing verification
effort. We study how to solve these problems.
Throughout, we use combinatorial auctions (using
the Clarke mechanism) and majority voting
as examples
Anonymity-Proof Voting Rules
No full textA (randomized, anonymous) voting rule maps any multiset of total orders of
(aka. votes over) a fixed set of alternatives to a probability distribution over these alternatives. A voting rule f is neutral if it treats all alternatives symmetrically. It satisfies participation if no voter ever benefits from not casting her vote. It is falsename-proof if no voter ever benefits from casting additional (potentially different)
votes. It is anonymity-proof if it satisfies participation and it is false-name-proof. We
show that the class of anonymity-proof neutral voting rules consists exactly of the
rules of the following form. With some probability kf in [0, 1], the rule chooses an
alternative at random. With probability 1-kf , the rule first draws a pair of alternatives
at random. If every vote prefers the same alternative between the two (and there
is at least one vote), then the rule chooses that alternative. Otherwise, the rule flips a
fair coin to decide between the two alternatives
Editor's puzzle
No full text
Solutions should be sent to the editor at [email protected] with subject header
SIGecom Exchanges Puzzle
. The author(s) of the most elegant solution (as judged by the editor) will be allowed to publish his or her or their proof in the next issue of the Exchanges (ties broken towards earlier submissions). To make the solution accessible to a wide audience, try to minimize technical jargon in the proof. Until the winner is chosen, the editor will not give any feedback on submitted solutions and ignore any requests for hints,
etc
.
</jats:p
Essays on Privacy, Information, and Anonymous Transactions
No full textThis dissertation uses game theoretic models to examine the effects of agent anonymity on markets for goods and for information. In open, anonymous settings, such as the Internet, anonymity is relatively easy to obtain --- oftentimes another email address is sufficient. By becoming anonymous, agents can participate in various mechanisms (such as elections, opinion polls, auctions, etc.) multiple times. The first chapter (joint work with Vincent Conitzer) studies elections that disincentivize voters from voting multiple times. A voting rule is false-name-proof if no agent ever benefits from casting additional votes. In elections with two alternatives, it is shown that there is a unique false-name-proof voting rule that is most responsive to votes. The probability that this rule selects the majority winner converges to 1 as the population grows large. Methods to design analogous rules for elections with 3 or more alternatives are proposed. The second chapter (also joint work with Vincent Conitzer) extends the analysis in the first chapter to broader mechanism design settings, where the goal is to disincentivize agents from participating multiple times. The cost model from the first chapter is generalized and revelation principles are proven. The third chapter studies a setting where firms are able to recognize their previous customers, and may use information about consumers' purchase histories to price discriminate (which may incentivize consumers to be anonymous). The formal model considers a monopolist and a continuum of heterogeneous consumers, where consumers are able to maintain their anonymity at some cost. It is shown that when consumers can costlessly maintain their anonymity, they all individually choose to do so, which paradoxically results in the highest profit for the monopolist. Increasing the cost of anonymity can benefit consumers, but only up to a point; at that point, the effect is reversed. Some of the results are extended to a setting with two competing firms selling differentiated products. Finally, the cost of maintaining anonymity is endogenized by considering a third party that can make consumers anonymous for a fee of its choosing. It is shown that this third party would prefer to be paid by the firm for allowing consumers to costlessly maintain their anonymity.</p
Editor's puzzle
No full text
Solutions should be sent to the editor at [email protected] with subject header
SIGecom Exchanges Puzzle
. The author(s) of the most elegant solution (as judged by the editor) will be allowed to publish his or her or their proof in the next issue of the Exchanges (ties broken towards earlier submissions). To make the solution accessible to a wide audience, try to minimize technical jargon in the proof. The editor will not give any feedback on submitted solutions and ignore any requests for hints,
etc
.
</jats:p
Computational Aspects of Mechanism Design
No full textions (Conitzer, Derryberry, & Sandholm 2004). It also introduces an expressive bidding protocol for matching donations to charities (Conitzer & Sandholm 2004e), as well as an expressive bidding protocol for general settings in which agents' actions impose externalities on the other agents (that is, affect the other agents' utilities). Mechanism design with strategic agents While having a good outcome optimization algorithm is necessary for preference aggregation to be successful, it is not sufficient. The reason is that generally, the agents' preferences are not known beforehand and will have to be elicited Copyright c # 2005, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. from them. Unfortunately, agents will misreport their preferences if it is in their interest to do so. This may lead to the outcome optimization algorithm choosing an outcome that is good under the reported preferences, but bad under the agents' true preferences. The solut
Budget-Balanced and Nearly Efficient Randomized Mechanisms: Public Goods and Beyond
No full textMany scenarios where participants hold private information require payments to encourage truthful revelation. Some of these scenarios have no natural residual claimant who would absorb the budget surplus or cover the deficit. Faltings proposed the idea of excluding one agent uniformly at random and making him the residual claimant. Based on this idea, we propose two classes of public good mechanisms and derive optimal ones within each class: Faltings' mechanism is optimal in one of the classes. We then move on to general mechanism design settings, where we prove guarantees on the social welfare achieved by Faltings' mechanism. Finally, we analyze a modification of the mechanism where budget balance is achieved without designating any agent as the residual claimant
Minimum search to establish worst-case guarantees in coalition structure generation
No full textCoalition formation is a fundamental research topic in multi-agent systems. In this context, while it is desirable to generate a coalition structure that maximizes the sum of the values of the coalitions, the space of possible solutions is often too large to allow exhaustive search. Thus, a fundamental open question in this area is the following: Can we search through only a subset of coalition structures, and be guaranteed to find a solution that is within a desirable bound (beta) from optimum? If so, what is the minimum such subset? To date, the above question has only been partially answered by Sandholm et al. in their seminal work on anytime coalition structure generation [Sandholm et al., 1999]. More specifically, they identified minimum subsets to be searched for two particular bounds: β = n and β = [n/2]. Nevertheless, the question remained open for other values of β. In this paper, we provide the complete answer to this question
Prediction mechanisms that do not incentivize undesirable actions
No full textA potential downside of prediction markets is that they may incentivize agents to take undesirable actions in the real world. For example, a prediction market for whether a terrorist attack will happen may incentivize terrorism, and an in-house prediction market for whether a product will be successfully released may incentivize sabotage. In this paper, we study principal-aligned prediction mechanisms–mechanisms that do not incentivize undesirable actions. We characterize all principal-aligned proper scoring rules, and we show an “overpayment” result, which roughly states that with n agents, any prediction mechanism that is principal-aligned will, in the worst case, require the principal to pay Θ(n) times as much as a mechanism that is not. We extend our model to allow uncertainties about the principal’s utility and restrictions on agents’ actions, showing a richer characterization and a similar “overpayment” result.Peng Shi, Vincent Conitzer, Mingyu Gu
Disarmament Games With Resource
No full textA paper by Deng and Conitzer in AAAI'17 introduces disarmament games, in which players alternatingly commit not to play certain pure strategies. However, in practice, disarmament usually does not consist in removing a strategy, but rather in removing a resource (and doing so rules out all the strategies in which that resource is used simultaneously). In this paper, we introduce a model of disarmament games in which resources, rather than strategies, are removed. We prove NP-completeness of several formulations of the problem of achieving desirable outcomes via disarmament. We then study the case where resources can be fractionally removed, and prove a result analogous to the folk theorem that all desirable outcomes can be achieved. We show that we can approximately achieve any desirable outcome in a polynomial number of rounds, though determining whether a given outcome can be obtained in a given number of rounds remains NP-complete
- …
