R. Verbrugge Ed. Theoretical Aspects of Rationality and Knowledge 2023 TARK 2023 EPTCS 379 2023 pp. 245259 doi10.4204EPTCS.379.20 Y . Gafni M. Tennenholtz

2025-04-29 0 0 476.68KB 15 页 10玖币

侵权投诉

R. Verbrugge (Ed.): Theoretical Aspects of

Rationality and Knowledge 2023 (TARK 2023)

EPTCS 379, 2023, pp. 245–259, doi:10.4204/EPTCS.379.20

This work is licensed under the

Creative Commons Attribution License.

Optimal Mechanism Design for Agents with DSL Strategies:

The Case of Sybil Attacks in Combinatorial Auctions

Yotam Gafni

Technion

Haifa, Israel

yotam.gafni@campus.technion.ac.il

Moshe Tennenholtz

Technion

Haifa, Israel

moshet@ie.technion.ac.il

In robust decision making under uncertainty, a natural choice is to go with safety (aka security) level

strategies. However, in many important cases, most notably auctions, there is a large multitude of

safety level strategies, thus making the choice unclear. We consider two reﬁned notions:

• a term we call DSL (distinguishable safety level), and is based on the notion of “discrimin”

[7], which uses a pairwise comparison of actions while removing trivial equivalencies. This

captures the fact that when comparing two actions an agent should not care about payoffs in

situations where they lead to identical payoffs.

• The well-known Leximin notion from social choice theory, which we apply for robust decision-

making. In particular, the leximin is always DSL but not vice-versa [7].

We study the relations of these notions to other robust notions, and illustrate the results of their

use in auctions and other settings. Economic design aims to maximize social welfare when facing

self-motivated participants. In online environments, such as the Web, participants’ incentives take

a novel form originating from the lack of clear agent identity—the ability to create Sybil attacks,

i.e., the ability of each participant to act using multiple identities. It is well-known that Sybil attacks

are a major obstacle for welfare-maximization. Our main result proves that when DSL attackers

face uncertainty over the auction’s bids, the celebrated VCG mechanism is welfare-maximizing even

under Sybil attacks. Altogether, our work shows a successful fundamental synergy between robust-

ness under uncertainty, economic design, and agents’ strategic manipulations in online multi-agent

systems.

1 Introduction

Consider an agent who needs to decide on her action in an environment consisting of other agents.

In certain cases there is a uniquely deﬁned optimal action for the agent, but in most cases this “agent

perspective” is an open challenge. Given the above, both AI and economics care about an adequate

modeling of an agent, and its ramiﬁcations in a variety of multi agent contexts, for example, on social

welfare.

We consider a notion for agent modeling we term DSL (Distinguishable Safety-Level). The notion

was previously suggested in the context of constraint-satisfaction problems and fuzzy logic, and was

termed “discrimin” [7]. In game theoretic settings, the notion was previously applied [6] as a solution

concept for bargaining in Boolean games [11]. To the best of our knowledge, it was not previously con-

sidered in the context of auctions, voting, and more generally mechanism design, i.e., when considering

the robustness of economic mechanisms’ performance when facing strategic agents.

There are two ways to think of the DSL solution concept, when applied to agent modeling. One is as

a solution concept adapted to capture the behavioral phenomenon of the loss aversion cognitive bias in

agents, particularly when probabilities over nature states are unknown. The other is as a form of robust

strategy choice under uncertainty, that may be required in volatile and unpredictable environments that

246 DSL Reasoning under Uncertainty

do not admit a stable Bayesian description. We show its usefulness in auctions. In the full version of

this paper, we also study its behavior in other prominent strategic settings, such as voting. In our main

result we consider the celebrated welfare maximizing VCG mechanism in combinatorial auctions setting,

where it is known to fail under false name (aka Sybil) attacks. We show that DSL agents lead to optimal

social welfare.

1.1 Reasoning under Uncertainty

A classic distinction [15] separates reasoning under risk, where the actors are rational and there is a

commonly known distribution about their environment (also known as the stochastic or Bayesian setting),

and reasoning under uncertainty, where the general structure of strategies and outcomes is known, but

there is no probabilistic information about the environment. Moreover, even assumptions regarding

actors’ rationality or behavior characteristics may not be guaranteed . For such cases, a robust or worst-

case approach seems appropriate, and various notions exist to capture it. Ideally, a dominant strategy

solution exists, but this is usually not the case (and indeed it is not the case in all the cases we analyze

in this paper). A minimal robust notion is that of a safety level strategy, which uses a max-min approach

over all possible outcomes given a strategy choice. However, though it yields interesting results in some

cases [2, 20], in many other cases it does not tell us much about what strategy to choose, in particular in

auctions settings, where we derive our most interesting results. As we see, this is because in auctions the

natural safety level is 0 (which happens when the bidder loses the auction), and any strategy that does

not overbid guarantees it. It is thus hard to choose among these strategies without considering a more

reﬁned notion. Existing reﬁned notions are the lexicographic max-min (originally deﬁned in [19]) and

min-max regret [18]. We overview their comparison to the notion of DSL in Section 3 and Appendix A,

respectively.

1.2 VCG, Sybil Attacks, and Welfare

VCG is a well known mechanism which can be applied for combinatorial auctions. VCG has good

qualities such as being dominant strategy incentive compatible and achieving optimal social welfare.

However, under the possibility of false-name attacks [22], it is no longer truthful. Coming up with other

mechanisms does not solve the basic conundrum: In the full information settings, any false-name proof

mechanism performs poorly in terms of welfare [12].

A possible avenue to solving the issue is by limiting the discussed valuation classes. However, an

example in [13] shows that even when all bidders have sub-modular valuations, VCG is no longer dom-

inant strategy incentive-compatible under false-name attacks. Notably though, even with this example,

VCG still arrives at the socially optimal allocation, and in fact as [1] show, this observation is true in

general up to a constant with sub-modular (and near sub-modular) bidders. However, in the full version

of our paper, we show an example where for the XOS valuation class, which extends the sub-modular

class, there is such an attack so that VCG arrives at an arbitrarily sub-optimal allocation. The attack we

describe is enabled by the full information settings. Without full information, the attack is risky for the

attacker, since it could lead to negative utility, as the attacker overbids her true valuation.

A useful approach, that can lead to better welfare guarantees than dominant strategy mechanism

design, is Bayesian mechanism design. Assuming that the bidder distributions are common knowledge,

recent work has shown that selling each item separately leads to good constant approximation welfare

guarantees for XOS [4] and sub-additive [8] valuations. Though the works do not explicitly consider

Y. Gafni & M. Tennenholtz 247

Figure 1: Hierarchy for robust decision under uncertainty

false-name attacks, their constructions use the false-name-proof ﬁrst and second price auctions to auction

items separately, and so their results naturally extend to Bayesian false-name mechanism design.

It is important to note, that many of the above positive results for welfare guarantees under false-name

attack assume some form of risk-aversion; most importantly, that bidders do not overbid, i.e., they choose

only strategies that are individually rational (under any possible nature state). This condition is equivalent

to limiting the strategy space only to safety level strategies (as in this case of combinatorial auctions, the

safety level is 0). In [10] the authors do not make this assumption, but their positive welfare optimality

results are limited as they only consider the homogeneous single-minded case with two items. We thus

believe that it is natural to ask: Under our deﬁnition of DSL, which is a strong risk-aversion notion

(compared, e.g., to the safety level strategy), what welfare guarantees can be obtained? Surprisingly, the

answer is optimal, as we show in our main result in Theorem 4.2.

1.3 Our Results

In Section 2 we formally deﬁne our solution concept, and apply it to the ﬁrst-price and discrete ﬁrst-price

auctions. In Section 3 (with the additional discussion of min-max regret in Appendix A) we describe a

hierarchy of solution concepts and their relations to the solution concept we introduce (DSL), as sum-

marized in Figure 1.

In Section 4, we present our main result. We discuss VCG as a combinatorial auction under false-

name attacks, when bidders may create shill identities to send bids. It is known that VCG is not dominant

strategy truthful in these settings, and previous results were limited in establishing good welfare guaran-

tees for combinatorial auctions generally under false-name attacks. We show that when bidders use DSL

strategies, VCG achieves optimal welfare even under the threat of false-name attacks.

2 DSL: Deﬁnition

When deﬁning DSL strategies, we take the perspective of a single agent ifacing uncertainty. The agent

has a utility function uithat determines her utility given the state of the world, which is comprised of

her own action ai, others’ actions a−i, and agent i’s type θi. Formally, ui(ai,a−i|θi). We denote by Ai

the set of all agent i’s pure actions, and by ∆(Ai)the set of all agent i’s mixed actions. An action ai

may be from either of these action sets depending on the context. For mixed strategies, ui(ai,a−i|θi) =

a∼ai[ui(a,a−i|θi)]. We denote by Θithe set of all agent i’s types.

Deﬁnition 2.1. We say that an action aiof agent i is DSL (given a type θi) if for any other action a′

i, over

the set of outcomes where agent i’s utility differs between the actions, the minimal utility attained using

aiis at least as good as that attained by a′

i. Formally, let

Dθi(ai,a′

i) = {a−is.t. ui(ai,a−i|θi)̸=ui(a′

i,a−i|θi)}.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

R.Verbrugge(Ed.):TheoreticalAspectsofRationalityandKnowledge2023(TARK2023)EPTCS379,2023,pp.245–259,doi:10.4204/EPTCS.379.20©Y.Gafni&M.TennenholtzThisworkislicensedundertheCreativeCommonsAttributionLicense.OptimalMechanismDesignforAgentswithDSLStrategies:TheCaseofSybilAttacksinCombinatorialAuctionsYo...

展开>> 收起<<

R. Verbrugge Ed. Theoretical Aspects of Rationality and Knowledge 2023 TARK 2023 EPTCS 379 2023 pp. 245259 doi10.4204EPTCS.379.20 Y . Gafni M. Tennenholtz.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

R. Verbrugge Ed. Theoretical Aspects of Rationality and Knowledge 2023 TARK 2023 EPTCS 379 2023 pp. 245259 doi10.4204EPTCS.379.20 Y . Gafni M. Tennenholtz

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: